indexing - ソートされた整数を圧縮する

Question

バイナリ ファイルに継続的に格納された、順序付けられた 32 ビット整数のセットだけであるインデックスを構築しています。問題は、このファイルがかなり大きくなることです。いくつかの圧縮スキームを追加することを考えていましたが、それは私の専門外です。この場合、どの圧縮アルゴリズムが最適でしょうか? また、このインデックスは make の検索に使用されるため、解凍は高速である必要があります。

Answer 1

あなたが発見したように、N 32 ビット整数のソートされたシーケンスには 32*N ビットのデータがありません。これは驚くべきことではありません。重複がないと仮定すると、ソートされたシーケンスごとに N! 同じ整数を含むソートされていないシーケンス。

では、ソートされたシーケンスで限られた情報をどのように活用しますか? 多くの圧縮アルゴリズムは、共通の入力値に短いビット文字列を使用することに基づいて圧縮します (Huffman はこのトリックのみを使用します)。いくつかの投稿者は、数値間の差を計算し、それらの差を圧縮することを既に提案しています。彼らはそれが一連​​の小さな数であり、その多くが同一であると想定しています。その場合、差分シーケンスはほとんどのアルゴリズムで適切に圧縮されます。

ただし、フィボナッチ数列を取ります。それは間違いなくソートされた整数です。F(n) と F(n+1) の差は F(n-1) です。したがって、差分のシーケンスを圧縮することは、シーケンス自体を圧縮することと同じです。まったく役に立ちません。

したがって、本当に必要なのは、入力データの統計モデルです。シーケンス N[0]...N[x] が与えられた場合、N[x+1] の確率分布は何ですか? シーケンスがソートされているため、P(N[x+1] < N[x]) = 0 であることがわかっています。P(N[x+1] - N[x] = d) が小さな正の d に対して非常に高く、x から独立していると仮定しているため、提示された微分/ハフマンベースのソリューションはうまくいきます。小さな違い。別のモデルを与えることができれば、それを最適化できます。

Answer 2

高速なランダム アクセス ルックアップが必要な場合は、差分のハフマン エンコーディング (Niyaz の提案による) は話の半分にすぎません。n 番目の番号を簡単に抽出できるように、何らかのページング/インデックス スキームも必要になるでしょう。

これを行わない場合、n 番目の数値を抽出することは O(n) 操作になります。ファイルの半分を読み取って Huffman デコードしてから、目的の数値を見つける必要があるからです。ページ オフセットを格納するオーバーヘッドと検索速度のバランスを取るために、ページ サイズを慎重に選択する必要があります。

Answer 3

MSalters の回答は興味深いものですが、適切に分析しないと気を散らす可能性があります。32 ビットに収まるフィボナッチ数は 47 しかありません。

しかし、一連の増分を分析して圧縮すべきパターンを見つけることで、問題を適切に解決する方法を的確に把握しています。

重要なこと: a) 繰り返し値はありますか? もしそうなら、どのくらいの頻度ですか？(重要な場合は、圧縮の一部にします。そうでない場合は、例外にします。) b) 準ランダムに見えますか? 適切な平均増分が見つかる可能性が高いため、これも有効です。