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

Question

我正在寻找特定的建议或对算法和/或数据结构的引用,以便将单词列表编码成有效地变成拼写检查字典的单词.该方案的目标将导致原始单词列表与编码形式的非常高的压缩比.我对编码字典的唯一输出要求是,可以以相对有效的方式针对原始单词列表测试任何提出的目标字的存在性.例如,应用程序可能希望针对100,000字词的字典检查10,000个单词.事实并非如此 要求编码的字典表单能够[轻松]转换回原始单词列表形式 - 二进制是/否结果是针对结果字典测试的每个单词所需的全部内容.

我假设编码方案,以提高压缩比,将利用给定语言中的已知结构,如单数和复数形式,所有格形式,收缩等.我特别感兴趣主要编码英语单词,但要明确,该方案必须能够编码任何和所有ASCII文本"单词".

我想到的特定应用程序可以假设是非易失性存储空间非常宝贵的嵌入式设备,而字典则是随机可访问的只读存储区.

编辑:总结字典的要求:

• 零误报
• 零假阴性
• 非常高的压缩比
• 无需减压

Answer 1

在他的酒吧页面上看到麦克罗伊的"拼写清单的发展".关于小型机上拼写检查的经典旧纸,它限制了你列出的那些令人惊讶的地图.详细分析词缀剥离和两种不同的压缩方法:布隆过滤器和相关方案霍夫曼编码稀疏位集; 我选择Bloom过滤器可能优先于他选择的方法,这会以极高的成本速度挤出更多的GPU.(编程Pearls在本文中有一个简短的章节.)

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

Answer 2

Bloom Filter(http://en.wikipedia.org/wiki/Bloom_filter和http://www.coolsnap.net/kevin/?p=13)是一种数据结构,用于以非常紧凑的方式存储字典单词一些拼写检查.但是,存在误报的风险.