用于编码单词列表的压缩算法

Question

我正在寻找对算法和/或数据结构的具体建议或参考，用于将单词列表编码为有效的拼写检查字典。该方案的目标将导致原始单词列表到编码形式的压缩率非常高。我对编码字典的唯一输出要求是，可以以相对有效的方式根据原始单词列表测试任何建议的目标单词是否存在。例如，应用程序可能想要根据 100,000 个单词的字典检查 10,000 个单词。这是 不是 要求编码字典形式能够[轻松]转换回原始单词列表形式 - 二进制是/否结果是针对结果字典测试的每个单词所需的全部。

我假设为了提高压缩率，编码方案将利用给定语言中的已知结构，例如单数和复数形式、所有格形式、缩写等。我主要对英语单词的编码特别感兴趣，但要明确的是，该方案必须能够对任何和所有 ASCII 文本“单词”进行编码。

我想到的特定应用程序可以假设是针对嵌入式设备的，其中非易失性存储空间非常宝贵，并且字典将是可随机访问的只读存储区域。

编辑: ：总结一下词典的要求：

• 零误报
• 零漏报
• 非常高的压缩比
• 无需减压

Answer 1

参见麦克罗伊 “拼写列表的开发” 在 他的酒吧页面. 。关于小型计算机上的拼写检查的经典旧论文，其约束令人惊讶地很好地映射到您列出的约束。词缀剥离和两种不同压缩方式的详细分析：布隆过滤器和相关方案霍夫曼编码稀疏位集；我可能会选择布隆过滤器，而不是他选择的方法，这种方法以显着的速度成本压缩了更多的 kB。（编程珍珠 有一个关于本文的简短章节。）

另请参阅全文搜索系统中用于存储词典的方法，例如 信息检索简介. 。与上述方法不同，该方法没有误报。

Answer 2

布隆过滤器（http://en.wikipedia.org/wiki/Bloom_filter 和 http://www.coolsnap.net/kevin/?p=13）是一些拼写检查器中用于非常紧凑地存储字典单词的数据结构。然而，存在误报的风险。

Answer 3

我建议使用填充后缀树。词表压缩良好，查找时间短。

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

Answer 4

总结：

• 零误报
• 零漏报
• 高压缩比
• 不需要逆（即无需解压缩）

我本来打算建议布隆过滤器，但它们的误报率非零。

相反，Programming Pearls 讨论了一组类似的要求（/usr/share/dict/words 41K）。

这采用了茎收缩的方法：例如：发送的是根，因此可以添加前后修复：

• 展示
• 代表
• 表示
• 失实陈述

Answer 5

通过将单词存储为 7 位格式的连续后缀，您可以获得 30% 以上的压缩率。我不确定这叫什么，但它可以非常有效地转换为树结构。

前任。：a+n+d+s|an+d+y|和+es+roid

是 26 个字符，相比之下：

一个广告和任何安第斯山脉

即 33。

考虑到存储为 7 位内容时的 12.5% 压缩率，总共压缩率约为 31%。当然，压缩率取决于单词列表的大小和内容。

将其转换为 26 根树结构可能会导致查找速度比与平面文件进行明文子字符串比较更快。

想一想，如果您只使用 26 个字符加上两个分隔符，那么您可以用 5 位完成所有操作，这本身就是 37.5% 的压缩，使上面的示例达到超过 50% 的压缩率。

Answer 6

我认为你最好的选择是 压缩后缀树 / 压缩后缀数组. 。您可以在上述链接中找到丰富的信息。这是一个正在进行的研究领域，确实非常有趣。

Answer 7

我不是这方面的专家，但不是 前缀树 几乎是这个问题的标准解决方案？它只存储一次单词的公共前缀。

Answer 8

对于纯压缩， 最大压缩 网站提供了 4 MB 英语单词列表的一些结果，最好的程序将其压缩到大约 400 KB。用于文本/单词压缩的其他一些压缩资源是 哈特奖页面 和 大文本压缩基准.

Answer 9

高德纳提到 “帕特里夏·特里” 在 计算机编程艺术卷。3. 。我从未将它用于任何实际工作，但也许这会有所帮助。

编辑：你的内存限制是什么？如果可用的 RAM 多于 ROM，也许在 ROM 中进行数据压缩（需要解压到 RAM 中）是正确的方法。我想，如果您有中等但不是大量的 RAM，从技术上讲，您还可以将部分数据结构作为压缩 blob 存储在内存中，并使用最近最少使用的缓存来保留其中的几个，然后动态解压缩适当的数据。当 blob 不在缓存中时。