algorithm - 编码单词列表的压缩算法

Question

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

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

我想到的特定应用程序是用于嵌入式设备的，其中非 volatile 存储空间非常宝贵，字典将是一个可随机访问的只读内存区域。

编辑:总结字典的要求:

• 零误报
• 零漏报
• 非常高的压缩率
• 无需解压

Answer 1

参见麦克罗伊的 "Development of a Spelling List"在his pubs page .关于在小型计算机上进行拼写检查的经典旧论文，其约束映射到您列出的约束出奇地好。词缀剥离和两种不同压缩方法的详分割析:Bloom 过滤器和相关方案 Huffman-coding a sparse bitset；我可能会优先使用布隆过滤器而不是他选择的方法，后者以显着的速度成本挤出更多 kB。 (Programming Pearls 有一章是关于这篇论文的。)

另请参阅用于在全文搜索系统中存储词典的方法，例如Introduction to Information Retrieval .与上述方法不同，这没有误报。