algorithm - 文本打包算法

Question

我敢打赌以前有人解决过这个问题，但我的搜索一无所获。

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

示例:娃娃屋

这些可以简单地作为 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

Answer 1

这是最短超字符串问题:找到包含一组给定字符串作为子字符串的最短字符串。根据this IEEE paper (不幸的是，您可能无法访问)，解决这个问题的方法正是 NP-complete。但是，可以使用启发式解决方案。

作为第一步，您应该找到属于其他字符串子字符串的所有字符串并删除它们(当然您仍然需要以某种方式记录它们相对于包含字符串的位置)。使用 generalised suffix tree 可以有效地找到这些完整包含的字符串.

然后，通过反复合并重叠最长的两个字符串，可以保证生成的解的长度不小于最小可能长度的 4 倍。正如 Zifre 在 Konrad Rudolph's answer 上的评论所建议的那样，应该可以通过使用两个基数树快速找到重叠大小。 .或者，您也许能够以某种方式使用广义后缀树。

很抱歉，我无法为您找到合适的链接——似乎没有维基百科页面，也没有任何关于此特定问题的公开信息。简要提到here , 尽管没有提供建议的解决方案。