2 つの大きなテキスト ファイル (正確には csv) があります。1 つのファイルの行が 1 つの順序であり、もう 1 つのファイルの行が異なる順序であることを除いて、両方の内容はまったく同じです。
これらの 2 つのファイルを (プログラムで DotNetZip を使用して) 圧縮すると、ファイルの 1 つが常にかなり大きいことに気付きます。
私の質問は次のとおりです。
テキスト ファイル内のデータの順序は圧縮にどのように影響し、最適な圧縮率を保証するためにどのような手段を講じることができますか? -同様の行をグループ化すると（少なくとも私が使用しているZIPファイルの場合）、圧縮に役立つと思いますが、さまざまな圧縮アルゴリズムの内部構造に精通していないため、簡単な説明をいただければ幸いですこの教科では。
データの順序に関係なく最高の平均圧縮を達成するという意味で、この種のシナリオをより適切に処理するアルゴリズムはどれですか?
「どのように」はすでに答えられています。あなたの「どの」質問に答えるには：
マッチングのウィンドウが大きいほど、アルゴリズムは注文に対して敏感ではなくなります。ただし、すべての圧縮アルゴリズムはある程度敏感です。
gzip には 32K ウィンドウ、bzip2 には 900K ウィンドウ、xz には 8MB ウィンドウがあります。xz は最大 64MB のウィンドウに移動できます。したがって、xz は順序に対する感度が最も低くなります。より離れた場所にある一致ほど、コーディングに必要なビット数が増えるため、ウィンドウ サイズに関係なく、たとえば並べ替えられたレコードを使用すると、常により適切な圧縮が得られます。短いウィンドウは、遠くの一致を単純に排除します。
ある意味では、それはファイルのエントロピーの尺度であり、それがどれだけ圧縮されるかを定義します。ですから、はい、順序は間違いなく重要です。abcdefgh...zabcd...z簡単な例として、何度も繰り返される値で満たされたファイルを考えてみましょう。非常に順序付けられているため、ほとんどのアルゴリズムで非常によく圧縮されます。ただし、順序を完全にランダム化すると (ただし、各文字の数は同じままにする)、まったく同じデータになります (ただし、「意味」は異なります)。順序が異なる同じデータであり、同様に圧縮されません。
実際、気になったのでやってみました。100,000 文字のa-z繰り返しで配列を埋め、それをファイルに書き込み、その配列を「ランダムに」シャッフルして、もう一度書き込みました。最初のファイルは 394 バイトまで圧縮されました (元のサイズの 1% 未満)。2 番目のファイルは 63,582 バイトに圧縮されました (元のサイズの 63% 以上)。
一般的な圧縮アルゴリズムは次のように機能します。データのチャンクを見てください。最近見た他のチャンクと同じである場合は、現在のチャンクを文字通り出力せず、代わりにその前のチャンクへの参照を出力します。
類似のチャンクが互いに接近している場合、それは確かに役立ちます。アルゴリズムは、圧縮速度を合理的に保つために、限られた量のルックバックデータのみを保持します。したがって、データのチャンクが他のチャンクと同一であっても、その古いチャンクが古すぎる場合は、すでにフラッシュされている可能性があります。
確かにそうです。入力パターンが固定されている場合、各位置の文字を予測する確率は 100% です。2 つの当事者がデータ ストリームについてこれを知っている場合 (つまり、基本的には固定パターンを知っているということになります)、通信する必要は事実上何もありません: 完全な圧縮が可能です (無制限のストリームではなく、有限長の文字列を通信するには、 d はまだ長さをエンコードする必要がありますが、それは要点の横にあります)。相手がパターンを知らない場合は、エンコードするだけで済みます。有限量のデータで無制限のストリームをエンコードできるため、完全な圧縮が可能です。
反対に、完全にランダムなデータがある場合 (つまり、ストリームは何でもよく、次の文字は常に有効な文字である可能性があります)、圧縮は不可能です。相手が正しいストリームを再構築できるようにするには、ストリームを完全にそのまま送信する必要があります。
有限文字列は少しトリッキーです。有限の文字列には必然的に各文字の固定数のインスタンスが含まれるため、最初のトークンの読み取りを開始すると確率が変化する必要があります。ある種の順序を任意の有限文字列に読み取ることができます。
これがあなたの質問に答えているかどうかはわかりませんが、もう少し理論的に対処しています。