我正在寻找对算法和/或数据结构的特定建议或参考，以将单词列表编码为有效地将成为拼写检查字典的单词。该方案的目的将导致原始单词列表到编码形式的非常高的压缩率。我对编码字典的唯一输出要求是，可以以相对有效的方式针对原始单词列表测试任何建议的目标单词是否存在。例如，应用程序可能要对照100,000个单词的词典检查10,000个单词。这是 不 编码字典形式必须能够[轻松]转换回原始单词列表形式的要求-对结果字典进行测试的每个单词都需要二进制“是/否”结果。
我假设编码方案为提高压缩率，将利用给定语言中的已知结构，例如单数和复数形式，所有格形式，收缩等。我对主要编码英语单词特别感兴趣，但要清楚，该方案必须能够编码任何和所有ASCII文本“单词”。
我可以想到的特定应用程序是用于非易失性存储空间非常宝贵的嵌入式设备，而字典将是一个可随机访问的只读存储区。
编辑 ：总结字典的要求：
参见McIlroy 在其酒吧页面上的“拼写列表的开发”。关于在小型计算机上进行拼写检查的经典旧论文，该约束出人意料地很好地映射到了您列出的内容。详细分析词缀剥离和两种不同的压缩方法：布隆过滤器和相关方案霍夫曼编码稀疏位集；我可能会优先使用Bloom过滤器，而不是他选择的方法，后者会以明显的速度消耗更多的kB。（ Programming Pearls 在本文中有一小章。） __
另请参阅用于在全文搜索系统中存储词典的方法，例如Information Retrieval简介。与上述方法不同，这没有误报。
