同一の文字列のリストを圧縮するための最良の方法は何ですか？

Question

言うと、私は非常に似ているが絶対的に同一の弦の数を持っています。

それらは多かれ少なかれ異なることがありますが、類似性が肉眼で見ることができます。

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

そのような場合の最良の圧縮方法は何でしょうか？

更新（データ形式）：

私はデータを共有することはできませんが、私はそれを現実の近くに説明することができます：

移動と描画のためのいくつかの装置のコマンドのシーケンスである表記（Logo言語）を想像してみてください。 のようなもの：

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

.

など。

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

文字列全体を説明します。 "U12C6P1L74D74R74U74P0 ...."。

この言語の助けを借りていくつかの非常に特定の画像を描画するように言われた1万人の子供たちのクラス：彼らの国の旗のように。私たちはすべて違う文字列を同時に似ています。

私たちの仕事は、できるだけ弦の全体束を圧縮します。

私の疑いは、この類似性と共通の長さを悪用する方法がありますが、Huffmanなどです。明示的に使用しないでください。

Answer 1

データは何ですか？おそらくDNA配列のようなものですか？のように

AGCTGTGCGAGAGAGGGGTGGG ...

ggctgtgcgagcgagcggtggg ...

CGCTGTGAGAGAGAGAGGGGTGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGD

NGCTGTGCGAGAGAGAGCGGTGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG

ggctgtgcgagtgagagcggtggg ...

... ...

？ たぶんそうかどうか。とにかくここには考える2つのレベルか2つの方法があります：

1. ハフマンコーディング：ref。自分でウィキペディア

2. sprislogy：ref。 http://books.google.com.hk/books/avout./jewels_of_stringology.html?id=9ndohjxtiyyc

   あなたの問題を解決するのは簡単だと思いますが、最善の方法を選択するのは難しいです。 http://en.wikipedia.org/wiki/data_compression / wiki/data_compression/a/a>そしてより多くのツール。

Answer 2

あなたは256バイトの修正幅を持ち、それは2の力であるため、そのサイズのサイズの大きさや2倍の間に穴があるか、または多数の移動を試してみましょう。それからあなたはハフマンコードを試すことができます。たぶんあなたは256バイトでヒルベルトの曲線を試すことができ、次にBWTとMFTを試すことができますか？

Answer 3

「文字列の総数は2 ^ 16未満です。」これは小さく、有名な数です。これはあなたの仕事を非常に簡単にします：以前に見たすべての文字列のルックアップテーブル（ハッシュテーブル）を保持しないでください。その後、256バイトのすべての行をこのルックアップテーブルに2バイトのインデックスに変換できます。

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