data-structures - 压缩相似但不相同的字符串列表的最佳方法是什么？

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....”。

现在想象一下，一万个 child 被告知要借助这种语言绘制一些非常具体的图像:就像他们国家的国旗一样。我们将同时获得 10K 个不同且相似的字符串。

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

我的怀疑是有一种方法可以利用字符串的这种相似性和共同长度，而 Huffman 例如不会明确使用它。

Answer 1

你能告诉我们数据是什么吗？也许像 DNA 序列？喜欢

AGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGCGAGAGCGGTGGG...

CGCTGTGAGAGNGAGAGCGGTGGG...

NGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGTGAGAGCGGTGGG...

... ...

?
也许与否。无论如何，这里有两个层次或两种思考方式:

霍夫曼编码:引用。自己翻维基百科

弦学:引用。 http://books.google.com.hk/books/about/Jewels_of_stringology.html?id=9NdohJXtIyYC

我认为解决您的问题很容易，但很难选择最佳方式。您可以使用 http://en.wikipedia.org/wiki/Data_compression 设计几种方法进行比较。以及更多工具。