我正在寻找对算法和/或数据结构的具体建议或参考，以将单词列表编码成有效的拼写检查字典。该方案的目标将导致原始单词列表到编码形式的非常高的压缩比。我对编码字典的唯一输出要求是，可以以相对有效的方式针对原始单词列表测试任何建议的目标单词是否存在。例如，应用程序可能希望对照 100,000 个单词的字典检查 10,000 个单词。它不是编码字典形式能够[轻松]转换回原始单词列表形式的要求 - 二进制是/否结果是针对结果字典测试的每个单词所需要的全部。
我假设编码方案，以提高压缩率，将利用给定语言中的已知结构，例如单数和复数形式、所有格形式、缩写等。我对主要编码英语单词特别感兴趣，但要清楚，该方案必须能够编码任何和所有 ASCII 文本“单词”。
我想到的特定应用程序可以假设用于嵌入式设备，其中非易失性存储空间非常宝贵，而字典将是一个随机访问的只读内存区域。
编辑：总结字典的要求：
请参阅 McIlroy在他的 pubs 页面上的“拼写列表的开发”。关于小型计算机上的拼写检查的经典旧论文，这些约束与您列出的约束非常吻合。词缀剥离和两种不同压缩方法的详细分析：布隆过滤器和相关方案 Huffman-coding a sparse bitset；我可能会优先使用 Bloom 过滤器，而不是他选择的方法，这种方法以显着的速度成本挤出更多 kB。（Programming Pearls有一个关于这篇论文的简短章节。）
另请参阅用于在全文搜索系统中存储词典的方法，例如Introduction to Information Retrieval。与上述方法不同，这没有误报。
布隆过滤器（http://en.wikipedia.org/wiki/Bloom_filter和http://www.coolsnap.net/kevin/?p=13）是一种数据结构，用于以非常紧凑的形式存储字典中的单词一些拼写检查器。但是，存在误报的风险。
我建议使用填充后缀树。对单词表的良好压缩，以及出色的查找时间。
总结一下：
我打算建议 Bloom 过滤器，但这些过滤器的误报率非零。
相反，Programming Pearls 谈到了一组类似的要求（/usr/share/dict/words在 41K 中）。
这采用了词干收缩的方法：例如：sent 是根，因此可以添加前置和后置修复：
将单词存储为 7 位格式的连续后缀可以获得 30% 以上的压缩率。我不确定这叫什么，但它可以非常有效地转换为树结构。
例如：a+n+d+s|an+d+y|and+es+roid
是 26 个字符，相比之下：
一个广告和任何安第斯山脉的安卓
这是33。
考虑到存储为 7 位内容的 12.5% 压缩率，总压缩率约为 31%。当然，压缩比取决于单词列表的大小和内容。
将其转换为 26 根树结构可能会导致查找比纯文本子字符串与平面文件的比较更快。
想一想，如果您只使用 26 个字符加上两个作为分隔符，您可以在 5 位中完成所有操作，这本身就是 37.5% 的压缩率，使上述示例的压缩率超过 50%。
我认为您最好的选择是Compressed Suffix Tree / Compressed Suffix Array。您可以在上述链接中找到大量信息。这是一个正在进行的研究领域，确实非常有趣。
我不是这方面的专家，但是前缀树不是对此的标准解决方案吗？它只存储单词的公共前缀一次。
对于纯压缩，Maximum Compression网站提供了一些 4 MB 英文单词列表的结果，最好的程序将其压缩到 400 KB 左右。用于文本/单词压缩的其他一些压缩资源是Hutter Prize 页面和大文本压缩基准。
Knuth在The Art of Computer Programming vol.中提到了“Patricia trie” 。3 . 我从未将它用于任何实际工作，但也许这会有所帮助。
编辑：你的 RAM 限制是什么？如果您的 RAM 比可用的 ROM 多得多，那么 ROM 中的数据压缩（需要解压缩到 RAM）可能是正确的方法。我想如果您有中等但不是大量的 RAM，从技术上讲，您还可以将数据结构的一部分作为压缩 blob 存储在内存中，并使用最近最少使用的缓存来保留其中的几个，然后动态解压缩适当的blob 不在缓存中时。