压缩类似但不是相同字符串的最佳方法是什么？

Question

说，我有许多字符串，它们非常相似但没有绝对相同。 它们可以或多或少地不同，但肉眼可以看到相似性。

所有长度相等，每个长度为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 ......”。 想象一下现在是一万个孩子的孩子们在这种语言的帮助下绘制了一些非常特定的形象：就像他们国家的旗帜一样。我们将获得10k的字符串，这些字符串都不同，同时都相同。

我们的任务是压缩尽可能好的串的字符串。

我的怀疑是，有一种方法可以利用这种相似性和常见长度的字符串，而霍夫曼尤。明确使用它。

Answer 1

你能告诉我们这些数据是什么？也许像DNA序列？像

agctgtgcgagagagagcggtggg ...

ggctgtgcgagcgagagcggtggg ...

cgctgtgagagngagagcggtggg ...

ngctgtgcgagagagagcggtggg ...

ggctgtgcgagtgagagcggtggg ...

... ... ...

？ 也许或不。无论如何，这是两个级别或两种方式来思考：

1. 霍夫曼编码：ref。Wikipedia由自己

2. Strongology：REF。 http://books.google.com.hk/books/about/jewels_of_stringology.html?id=9ndohjxtiyyc

   我认为解决问题很容易，但难以选择最好的方式。您可以通过使用 http://en.wikipedia.org/wiki/data_compression更多的工具。

Answer 2

由于您的固定宽度为256字节，因此它的功率为2，我会尝试挖掘机轮车变换或具有该尺寸的移动到前算法，或者也许是该大小的双倍。然后你可以尝试霍夫曼代码。也许你可以在256个字节上尝试一个hilbert曲线，然后是bwt和mt？

Answer 3

“字符串的总数小于2 ^ 16。”这是一个小，有界的数字，这使得您的工作非常容易：为什么您不保留先前看到的所有字符串的查找表（哈希表）。然后，您可以将256个字节的每行转换为两个字节索引到此查找表中。

然后有一系列16位整数。这些整数将包含像“笔下载完成后的模式，下一个命令开始绘制”。如果数据包含这样的模式，则ppm是您的选择。7-ZIP具有高质量的PPM-实现。您可以使用GUI或CMD线选择它。