文本打包算法

Question

我打赌有人已经解决了这个问题，但是我的搜索没有结果。

我想将单词列表打包到缓冲区中，并跟踪每个单词的起始位置和长度。关键是，我想通过消除冗余来有效地压缩缓冲区。

例如：doll dollhouse house 这些可以简单地打包到缓冲区中，如dollhouse，记住doll是从位置0开始的四个字母，dollhouse是从0开始的九个字母，house是从3开始的五个字母。

到目前为止，我想到的方法是：

1.按长度从长到短排序：（dollhouse，house，doll） 2.扫描缓冲区以查看该字符串是否已存在作为子字符串，如果是，请记录位置。 3.如果不存在，请将其添加到缓冲区的末尾。

由于长单词通常包含较短的单词，因此这种方法效果很好，但应该可以做得更好。例如，如果我扩展单词列表以包括ragdoll，则我的算法会得出dollhouseragdoll，这比ragdollhouse不够高效。

这是一个预处理步骤，速度不是非常重要。O(n^2)是可以接受的。另一方面，我的实际列表有成千上万个单词，所以O(n!)可能行不通。

顺便提一下，这种存储方案用于TrueType字体的“名称”表中的数据，参见http://www.microsoft.com/typography/otspec/name.htm。

- Adrian McCarthy

---

你不能只是使用gzip之类的东西吗？ - Zifre

你所描述的是所有压缩算法所做的事情，只不过你增加了将明文单词作为被压缩元素的限制，而不是位。 - Richard Nichols

这与压缩算法不完全相同，因为每个单词都必须保持其“词性”。就像我在另一个评论中所说的那样，您不能将“执法官”和“女人”组合在一起，但在压缩中，将“男人”压缩在一起是可以的，因为您不需要维护一个一致的缓冲区。 - Dan Lew

@Draemon：压缩和打包的区别在于压缩数据需要解压缩，而打包则不需要解压缩，只需要一个索引。 - Adrian McCarthy

@Adrian：这是一个错误的区分。是的，你可以通过访问索引来原地解压缩索引打包数据，我同意这种方案特别适合这种用途，但它仍然是压缩；需要一个处理步骤来访问原始数据。其他压缩也可以在原地完成。 - Draemon

Answer 1

这是“最短超级字符串问题”：找到包含一组给定字符串作为子串的最短字符串。根据 这篇IEEE论文（您可能无法访问），精确解决此问题是 NP完全的。但是，可以使用启发式解决方案。

作为第一步，您应该找到所有是其他字符串的子串的字符串并删除它们（当然，您仍然需要以某种方式记录它们相对于包含字符串的位置）。这些完全包含的字符串可以使用广义后缀树有效地找到。

然后，通过反复合并具有最长重叠的两个字符串，您保证会产生一个长度不劣于最小可能长度4倍的解决方案。可以使用Zifre在Konrad Rudolph's answer上建议的两个基数树快速找到重叠大小。或者，您可能可以以某种方式使用广义后缀树。

很抱歉我找不到适当的链接给你--似乎没有维基百科页面，也没有任何公开可见的信息关于这个特定的问题。虽然这里简要提到了它，但没有提供建议的解决方案。

- j_random_hacker

---

谢谢！给问题命名总是一个很好的开始。我想找到一个完美的解决方案可能有些困难，但是一个好的解决方案就已经让人感到满意了。 - Adrian McCarthy

Answer 2

我认为你可以使用基数树。由于指向叶子和父节点的指针，它会占用一些内存，但很容易匹配字符串（O(k)（其中k是最长字符串大小））。

- Qubeuc

---

我认为这仅适用于以常见子字符串开头的字符串。 以常见子字符串结尾的字符串将不被识别。 如果我错了，请纠正我。 - Zifre

如果字符串以相同的子字符串结尾，根据这个描述它们也不会被匹配。这样做会导致单独的字符串变得混乱。 - Dan Lew

具体来说，如果你有“女人”和“执法官”，即使你想合并它们，也不能这样做。唯一的组合方式（据我理解）是一个单词的后缀与另一个单词的前缀匹配。 - Dan Lew

Answer 3

我的第一个想法是：使用数据结构来确定字符串的公共前缀和后缀。然后，在考虑这些前缀和后缀的情况下对单词进行排序。这将导致您所需的ragdollhouse。

- Konrad Rudolph

---

你所建议的听起来可以用双基数树（一个正向，一个反向）实现。这在大多数情况下都能工作，但如果字符串在中间有共同部分，但边缘没有，则无法实现。 - Zifre

例如，它无法识别“consuming”和“sum”。 - Zifre

Answer 4

看起来类似于背包问题，这是NP完全问题，因此没有“确定性”算法。

- friol

---

你能否向我们解释一下与背包问题的联系？ - akappa

背包问题（将一些物品最优地装入袋子中）对我来说看起来很相似。实际上（请参见j_random_hacker的答案），这是一个NP完全问题，就像背包问题一样。 - friol

是的，但我仍然看不出那个问题与KP的相似之处。 3-SAT是NPC问题，但我不能确定它是否类似于那个“字符串打包”问题。 - akappa

“Bag”是长度最短的字符串（即“最优装载”）。将货物装入袋子类似于调整“主”字符串中的子字符串：在两种情况下，您都有约束条件（子字符串约束或总重量限制）。 - friol

在我看来，子字符串约束使问题的性质截然不同，但没关系 ;) - akappa

Answer 5

我在大学时做过一个实验，任务是实现一个简单的压缩程序。

我们所做的是将这些技术顺序应用于文本：

• BWT（Burrows-Wheeler变换）：帮助重新排列字母成为相同字母的序列（提示*有数学替代方法来获取字母而不是实际进行旋转）
• MTF（移动到前面的变换）：将字母序列重写为动态列表的索引序列。
• Huffman编码：一种熵编码形式，构建一个可变长度的代码表，其中频繁出现的符号被赋予较短的代码，不经常出现的符号被赋予较长的代码

在这里，我找到了作业页面。

要恢复原始文本，您需要进行以下三个步骤：(1) 哈夫曼解码， (2) 逆MTF，然后(3) 逆BWT。关于此过程有很多优秀的网络资源。

- Cᴏʀʏ

---

有趣，但与手头的问题基本无关。此外，在进行MTF之前通常要先进行一步运行长度编码。 :) - Nick Johnson

Answer 6

完善步骤3。

• 检查当前列表中是否有任何单词以当前单词的后缀开头。（您可能希望将后缀保持较长的长度 - 例如大于1）。
• 如果是，则将不同的前缀添加为现有单词的前缀，并适当调整所有现有引用（慢！）
• 如果没有，则按照当前步骤3将单词添加到列表末尾。

这将使“ragdollhouse”成为您示例中存储的数据。 不清楚它是否总是能够最优地工作（例如，如果您的单词列表中还有“barbiedoll”和“dollar”）。

- Jonathan Leffler

Answer 7

不清楚你想做什么。

你想要一个数据结构，可以在存储字符串时以节省内存的方式进行，并且能够在合理的时间内进行搜索等操作吗？

还是你只是想要一个压缩的单词数组？

对于第一种情况，你可以选择使用 Patricia Trie 或 String B-Tree。

对于第二种情况，你可以采用一些索引压缩技术，例如：

如果你有这样的东西：

aaa 
aaab
aasd
abaco
abad

你可以这样进行压缩：

0aaa
3b
2sd
1baco
2ad

该数字是前一个字符串与当前字符串的最长公共前缀的长度。 您可以调整该方案，例如在只有K个单词后计划重新开始公共前缀以进行快速重构。

- akappa

---

请注意，使用最后一个模式，您应该比您建议的打包方式压缩更多。当然，您不能只有一个指向单词的指针，而是一个元组（指向具有0前缀的第一个单词的指针，偏移量）。 - akappa

我不是在寻找压缩方法。我需要快速随机访问每个单词的完整文本，因此我不想即时解压缩。打包可以减少内存占用并提高引用的局部性。 - Adrian McCarthy

你确定这会提高局部性吗？局部性很大程度上取决于你请求单词的顺序，而不仅仅是内存占用（当然，除了边缘情况）。 而且你真的确定它可以大幅度地改善内存占用吗？在我看来，如果你有一组特定的字符串，这种优化可能是一件好事，但对于自然语言单词等实际上是无用的。 - akappa

Answer 8

我不想再重复造轮子了。已经有大量的人力投入到压缩算法中，为什么不使用其中一个已经可用的呢？

以下是一些不错的选择：

• gzip 用于快速压缩/解压速度
• bzip2 用于稍微更好的压缩但解压速度慢得多
• LZMA 用于非常高的压缩比和快速解压缩（比bzip2快但比gzip慢）
• lzop 用于非常快速的压缩/解压缩

如果您使用Java，则gzip已经集成。

- martinus

---

我不是追求打包，也不是压缩。在运行时，我希望每个单词的完整文本都可以轻松访问。尽管可以不进行任何打包操作来实现这一点，但我认识到打包可以显著减少占用空间并改善引用位置的局部性。 - Adrian McCarthy

你的打包和解包与其他压缩和解压算法有何不同？ - martinus

使用压缩技术，您需要进行解压缩。而使用我所描述的打包技术，则无需进行拆包操作。我直接拥有原始文本的完整内容。 - Adrian McCarthy