9

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

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

示例：娃娃屋

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

到目前为止，我想出的是：

  1. 将单词从最长到最短排序：（娃娃屋、房子、娃娃）
  2. 扫描缓冲区以查看字符串是否已作为子字符串存在，如果存在，请记下位置。
  3. 如果它尚不存在，请将其添加到缓冲区的末尾。

由于长词通常包含较短的词，因此效果很好，但应该可以做得更好。例如，如果我扩展单词列表以包含 ragdoll，那么我的算法会dollhouseragdoll比ragdollhouse.

这是一个预处理步骤，所以我并不十分担心速度。O(n^2) 很好。另一方面，我的实际列表有数万个单词，所以 O(n!) 可能是不可能的。

作为旁注，此存储方案用于 TrueType 字体的“名称”表中的数据，参见。http://www.microsoft.com/typography/otspec/name.htm

4

8 回答 8

15

这是最短超字符串问题：找到包含一组给定字符串作为子字符串的最短字符串。根据这篇 IEEE 论文（不幸的是，您可能无法访问），完全解决这个问题是NP-complete。然而，启发式解决方案是可用的。

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

然后，通过重复合并具有最长重叠的两个字符串，可以保证产生一个长度不小于最小可能长度的 4 倍的解。正如 Zifre 对Konrad Rudolph 的回答所建议的那样，使用两棵基数树应该可以快速找到重叠大小。或者，您也许能够以某种方式使用广义后缀树。

很抱歉，我无法为您找到一个像样的链接——似乎没有维基百科页面，或者关于这个特定问题的任何可公开访问的信息。此处简要提及，但未提供建议的解决方案。

于 2009-05-10T14:54:06.247 回答
1

细化步骤 3。

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

这将为您提供“ragdollhouse”作为示例中的存储数据。目前尚不清楚它是否总是能以最佳方式工作（例如，如果您在单词列表中还有 'barbiedoll' 和 'dollar'）。

于 2009-05-10T15:45:40.137 回答
1

我认为您可以使用Radix Tree。由于指向叶子和父节点的指针，它会花费一些内存，但很容易匹配字符串（O（k）（其中 k 是最长的字符串大小）。

于 2009-05-10T13:28:00.677 回答
1

我的第一个想法是：使用数据结构来确定字符串的常见前缀和后缀。然后根据这些前缀和后缀对单词进行排序。这将导致您想要的ragdollhouse.

于 2009-05-10T13:31:58.513 回答
1

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

于 2009-05-10T13:48:07.660 回答
1

我在大学里做过一个实验室，我们的任务是实施一个简单的压缩程序。

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

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

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

要取回原始文本，您执行 (1) Huffman 解码，(2) 逆 MTF，然后 (3) 逆 BWT。Interwebs 上有很多关于这一切的好资源。

于 2009-05-10T14:05:11.647 回答
0

我不会再重新发明这个轮子了。压缩算法已经投入了大量的人力，为什么不采用一种已经可用的算法呢？

这里有几个不错的选择：

  • gzip用于快速压缩/解压缩速度
  • bzip2压缩有点苦，但解压速度要慢得多
  • LZMA用于非常高的压缩比和快速解压缩（比 bzip2 快但比 gzip 慢）
  • lzop用于非常快速的压缩/解压缩

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

于 2009-05-10T15:10:25.720 回答
0

目前还不清楚你想做什么。

您是否想要一种数据结构，可以让您以有记忆力的方式存储字符串，同时让搜索等操作在合理的时间内成为可能？

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

在第一种情况下，您可以选择 patricia trie 或 String B-Tree。

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

如果你有类似的东西：

aaa 
aaab
aasd
abaco
abad

你可以这样压缩：

0aaa
3b
2sd
1baco
2ad

该数字是前面字符串的最大公共前缀的长度。例如，您可以调整该架构。计划在 K 个单词之后“重新启动”公共前缀，以便快速重建

于 2009-05-10T15:23:01.483 回答