0

假设我有以下字符串：

ABCADCADCADABC

我想通过查找重复的子字符串来压缩它。什么是提供最佳压缩的算法？

在上面的例子中它应该返回

AB*1 CAD*3 ABC*1

为了比较，贪心算法可能会返回

ABC*1 ADC*2 AD*1 ABC*1
4

4 回答 4

3

Depending on whether you prefer fast and simple or high compression ratio you could take a look into the Lempel-Ziv-Welch (LZW) or Lempel-Ziv-Markov chain (LZMA) algorithms. They both keep dictionaries of recurring strings.

于 2012-04-19T02:12:25.450 回答
3

这听起来像是后缀数组/树的工作！

http://en.wikipedia.org/wiki/Suffix_array

您可以使用在字符串上构建的后缀数组来找出重复的模式。例如，我们可以在您的示例上构建一个后缀数组，如下所示（我总是在每个字母之后使用 $，您可以对其进行排序，以便 $ 在每个字母之前......无论哪种方式都可以）：

ABCADCADCADABC$
美元
ADABC$
ADCADABC$
ADCADCADABC$
BCADCADCADABC$
元
加元ABC$
CADCADABC$
CADCADCADABC$
加元
DABC$
DCADABC$
DCADCADABC$
$

由此，我们可以更容易地看出字符串中的常见模式。使用此后缀数组表示中的信息，我们可以看到 CAD 在局部区域中重复了 3 次，我们可能会将其用作我们的压缩选择。ADC 和 DCA 等没有那么吸引人，因为它们压缩的字符串较少。

http://en.wikipedia.org/wiki/Suffix_tree

后缀树是执行相同任务的更有效方法。一旦你了解了如何使用后缀数组来做某事，那么进入后缀树就不会太远了。事实上，这用于流行的压缩算法，包括 LZW 1和 BWT (Bzip) 2。

于 2012-04-19T07:05:31.087 回答
2

它可能实际上并不相关，但是对于您提出的特定问题，有一个动态编程解决方案。如果您已经计算了从第一个字符开始压缩长度为 1、2、3...n-1 的字符串的最佳方法，那么您可以计算从第一个字符开始压缩长度为 n 的字符串的最佳方法：查看每个可能性 k 的最后 k 个字符，并查看它们是否形成简单字符串的倍数。如果是这样，计算压缩前 nk 个字符然后使用字符串的倍数表示最后 k 个字符的成本。

因此，在您的示例中，您最后会注意到 ABC 是其自身的倍数，并且如果您将其表示为 ABC*1，您可以使用您已经为 AB CAD*3 的前 11 个字符计算出的答案来生成AB*1 加元*3 ABC*1

于 2012-04-19T03:57:37.943 回答
1

更好的是：

ABCAD(6,3)(3,11)

其中 (n,d) 是匹配的长度和距离。所以 (6,3) 从三个字节开始复制六个字节。虽然这听起来有点奇怪，但当它输入三个字节时，它需要的下三个字节已经被复制了。所以CADCAD附加。ABC附加的 (3,11) 原因。

这称为 LZ77 压缩。它是 zip、gzip 和 zlib 使用 deflate 压缩数据格式实现的。该格式不仅引用了以前的字符串匹配，而且还对文字（例如ABCAD）以及长度和距离使用了霍夫曼压缩。

于 2012-04-19T02:45:11.540 回答