0

次のような数メガバイトのデータがあります。

11  2  1
 4  3  1
11  2  1
 4  3  1
11  2  1
 4  3  1
18  3  2

「前のn行がm回繰り返された」という行を追加して圧縮したいと思います。アルゴリズムは、可能な限り長い m*n が見つかるまで行を読み取り、出力を遅らせる必要がありますが、n<=10 と想定できます。これを行う最良の方法は何ですか？

1..10 前の行の 10 個の配列を繰り返しカウンターで保持し、新しい行が入ってくると配列の内容を回転させ、新しく読み取った行がどの配列の最も古いエントリとも一致しなかったときに上記のメッセージを出力することを考えていました、および配列の少なくとも 1 つが繰り返しで埋められています。

4

3 に答える 3

1

zip アルゴリズムは、データを読み取り可能に保つことができます。繰り返し要素の辞書を作成するだけです (例えば、 lempel - zivを見てください)。あなたが説明したアルゴリズムには問題があると思います。2 番目の行は最初の行とは異なりますが、それらを 1 つのグループとして扱うことになっていることをどのようにして知ることができますか? いつグループを制限して、新しいグループを開始しますか?
どうやってそれを言うことができますか

11 2 1
4 3 1

本当に同じグループ？

可能性のあるすべてのサブセットとその出現回数を含む辞書を使用して、lempel ziv が解決できると思います。辞書には、次のようなサブセットがあります

11 2 1
4 3 1
11 2 1

ただし、繰り返し行がペアまたはトリプレットになることが何らかの形でわかっている場合は、チェックされたサブセットをアルゴリズムで制限し、辞書内のサブセットを予想される長さに保つことができます。
このようにして、最終的に辞書は次のようになります。

key          : count
11 2 1       : 3
4  3 1       : 3
11 2 1, 4 3 1: 3
18 3 2       : 1

もちろん、さらに微調整が必​​要ですが、このアルゴリズムが一般的な方向性であるべきだと思います

于 2012-06-12T07:11:43.960 に答える
1

「前の n 行を m 回コピー」は、「j 行から k 行をコピー」の限定バージョンです。最初のものは、k = n * m および j = n の 2 番目のものです。より一般的な k,j バージョンは LZ77 です。（ただし、通常は行ではなくバイトです。）

LZ77 アルゴリズムは、これに非常に適しています。gzip、zlib などで使用されるハッシュ テーブル アプローチは、高速でコーディングが簡単です。最初に、価値があると考える k の最小値 (mink) を定義し、マッチを探すのにどれだけさかのぼるかを定義します。つまり、j の最大値 (maxj) です。次に、検索する maxj 行のスライディング ウィンドウを作成します。

行が入るたびに、最後のミンク行のみに依存するハッシュを更新します。ハッシュ テーブルでそのハッシュに一致する最後の行を探し、一致しなくなるまでその行をスライディング ウィンドウの内容と直接比較します。次に、結果の長さがミンク以上の場合、長さと距離 (k と j) で構成される一致があります。

次の行を処理するまで一致の発行を遅らせる遅延一致を使用します。これにより、一致が長くなる可能性があります。

于 2012-06-12T16:06:52.043 に答える
0

ファイルを長い文字列と考える場合、問題は最も長く繰り返される部分文字列を見つけることにあると思います

于 2012-06-12T08:18:39.303 に答える