4

说，我有许多非常相似但不完全相同的字符串。

它们可能或多或少不同，但肉眼可以看出相似之处。

所有长度都是相等的，每个都是 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....”。

现在想象一下，一万名儿童被告知在这种语言的帮助下画出一些非常具体的图像：比如他们国家的国旗。我们将同时获得 10K 个不同且相似的字符串。

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

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

4

3 回答 3

1

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

AGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGCGAGAGCGGTGGG...

CGCTGTGAGAGNGAGAGCGGTGGG...

NGCTGTGCGAGAGAGAGCGGTGGG...

GGCTGTGCGAGTGAGAGCGGTGGG...

……

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

  1. 霍夫曼编码：参考。自己的维基百科

  2. 弦学：参考。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 的幂，因此我会尝试使用 burrow-wheeler 变换或具有该大小或可能是该大小的两倍的移动到前面的算法。然后你可以试试哈夫曼代码。也许您可以尝试 256 字节的希尔伯特曲线，然后尝试 bwt 和 mft？

于 2012-03-11T11:02:15.613 回答
0

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

然后你有一个 16 位整数序列。这些整数将包含诸如“笔落下后，有 90% 的机会下一个命令开始绘制”之类的模式。如果数据包含这样的模式，那么 PPM 是您的选择。7-zip 具有高质量的 PPM 实现。您可以使用 GUI 或 cmd-line 选择它。

于 2012-03-14T10:49:41.057 回答