我正在寻找关于将单词列表编码为拼写检查字典的算法和/或数据结构的具体建议或参考。该方案的目标是将原始单词列表大幅度压缩成编码形式。我仅需要对编码字典的一个输出要求,即可以以相对高效的方式针对原始单词列表测试任何提议的目标单词是否存在。例如,应用程序可能想要检查10,000个单词是否存在于100,000个单词的字典中。不要求将编码后的字典形式能够被轻松转换回原始单词列表形式 - 对于每个针对生成的字典测试的单词,只需二进制的是/否结果即可。
我假设编码方案将利用给定语言中已知的结构(如单数和复数形式、所有格形式、缩略形式等)来提高压缩比。我特别感兴趣的是主要编码英文单词,但需要明确的是,该方案必须能够对任何ASCII文本“单词”进行编码。
我所考虑的特定应用程序是嵌入式设备,其中非易失性存储空间很有限,字典将是一个可随机访问的只读内存区域。
编辑:总结字典的要求:
- 零误报 - 零漏报 - 非常高的压缩比 - 不需要解压缩
我假设编码方案将利用给定语言中已知的结构(如单数和复数形式、所有格形式、缩略形式等)来提高压缩比。我特别感兴趣的是主要编码英文单词,但需要明确的是,该方案必须能够对任何ASCII文本“单词”进行编码。
我所考虑的特定应用程序是嵌入式设备,其中非易失性存储空间很有限,字典将是一个可随机访问的只读内存区域。
编辑:总结字典的要求:
- 零误报 - 零漏报 - 非常高的压缩比 - 不需要解压缩