4

たとえば、非常に似ているが完全に同一ではない多くの文字列があるとします。

それらは多かれ少なかれ異なる場合がありますが、類似性は肉眼で確認できます。

長さはすべて等しく、それぞれが 256 バイトです。文字列の総数が 2^16 未満です。

このような場合の最適な圧縮方法は何でしょうか?

更新 (データ形式):

データを共有することはできませんが、現実に非常に近いことを説明できます。

平面上を移動して描画するためのデバイスの一連のコマンドである (ロゴ言語のような) 表記法を想像してみてください。そのような：

U12 - move up 12 steps
D64 - move down 64 steps
C78 - change drawing color to 78
P1  - pen down (start drawing)

等々。

この言語の語彙全体は、英語のアルファベットのサイズを超えません。

次に、文字列は全体像を表します: "U12C6P1L74D74R74U74P0...."。

今、この言語の助けを借りて非常に具体的なイメージを描くように言われた1万人の子供たちのクラスを想像してみてください:彼らの国の旗のように. すべてが異なっていて、すべてが同じである 10K の文字列を同時に取得します。

私たちの仕事は、一連の文字列全体を可能な限り圧縮することです。

ここで私の疑念は、文字列のこの類似性と共通の長さを利用する方法があるということですが、Huffman はそれを明示的に使用することはありません。

4

3 に答える 3

1

データを教えてください。たぶんDNA配列のように？好き

AGCTGTGCGAGAGAGAGCGGTGGG..。

GGCTGTGCGAGCGAGAGCGGTGGG..。

CGCTGTGAGAGNGAGAGCGGTGGG..。

NGCTGTGCGAGAGAGAGCGGTGGG..。

GGCTGTGCGAGTGAGAGCGGTGGG..。

.....。

？多分かどうか。とにかくここに2つのレベルまたは2つの考え方があります：

  1. ハフマン符号化：ref。自分でウィキペディア

  2. ストリングロジー：ref。http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9NdohJXtIyYC

問題を解決するのは簡単ですが、最善の方法を選択するのは難しいと思います。http://en.wikipedia.org/wiki/Data_compressionやその他のツールを使用して、比較するいくつかの方法を設計できます。

于 2012-03-11T09:49:30.700 に答える
0

256 バイトの固定幅があり、2 の累乗なので、そのサイズまたはそのサイズの 2 倍のバローウィーラー変換または前面への移動アルゴリズムを試してみます。次に、ハフマン コードを試すことができます。たぶん、256 バイトでヒルベルト曲線を試してから、bwt と mft を試すことができますか?

于 2012-03-11T11:02:15.613 に答える
0

「文字列の総数が 2^16 未満です。」これは小さい境界付きの数値なので、作業が非常に簡単になります。以前に見たすべての文字列のルックアップ テーブル (ハッシュ テーブル) を保持しないのはなぜですか。次に、256 バイトのすべての行を、このルックアップ テーブルの 2 バイト インデックスに変換できます。

その後、16 ビット整数のシーケンスが得られます。これらの整数には、「ペンが下がった後、次のコマンドが描画を開始する可能性が 90% ある」などのパターンが含まれます。データにこのようなパターンが含まれている場合は、PPM を選択します。7-zip には、高品質の PPM 実装があります。GUI またはコマンドラインを使用して選択できます。

于 2012-03-14T10:49:41.057 に答える