代码之家 › 专栏 › 技术社区 › Tall Jeff

词表编码的压缩算法

dictionary data-structures algorithm

Tall Jeff · 技术社区 · 17 年前

我正在寻找对算法和/或数据结构的具体建议或参考,以便将单词列表编码为拼写检查词典。该方案的目标将导致原始单词列表到编码形式的压缩比非常高。我对编码词典的唯一输出要求是,任何提出的目标单词都可以以相对有效的方式与原始单词列表进行测试。例如,应用程序可能希望对照100000个单词的词典检查10000个单词。它是不对编码词典形式的要求是能够[容易地]转换回原始单词列表形式——对于每个根据最终词典测试的单词,只需要一个二进制的是/否结果。

我假设为了提高压缩比,编码方案将利用给定语言中的已知结构,如单数和复数形式、所有格形式、缩写等。我特别感兴趣的是主要对英语单词进行编码,但要清楚的是,该方案必须能够对任何和所有ASCII文本“单词”进行编码。

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

编辑 :总结一下词典的要求:

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

9 回复 | 直到 17 年前

Darius Bacon 17 年前

见麦克罗伊 "Development of a Spelling List" 在 his pubs page 关于小型计算机拼写检查的经典老论文,其中的约束与你列出的约束出奇地吻合。详细分析了词缀剥离和两种不同的压缩方法:布隆滤波器和相关方案霍夫曼编码稀疏比特集;我可能更喜欢Bloom过滤器,而不是他选择的方法,这种方法以巨大的速度代价挤出了更多的kB。 ( 编程珠玑 关于这篇论文有一个简短的章节。)

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

ahy1 17 年前

布隆过滤器( http://en.wikipedia.org/wiki/Bloom_filter 和 http://www.coolsnap.net/kevin/?p=13 )是一种数据结构,用于在某些拼写检查器中以非常紧凑的方式存储词典单词。然而,存在误报的风险。

patros patros 17 年前

我建议使用带衬垫的后缀树。单词表压缩良好,查找时间极佳。

http://en.wikipedia.org/wiki/Suffix_tree

jamesh 17 年前

综上所述:

零误报
零假阴性
高压缩比
不需要反向(即不需要解压缩)

我本来打算建议使用布隆过滤器,但这些过滤器有非零的误报。

相反,Programming Pearls谈到了一组类似的要求( /usr/share/dict/words 41K)。

这采取了茎收缩的方法: 例如:send是root,因此可以添加预修复和后修复:

目前
代表
代表
虚假陈述

Max 17 年前

将单词存储为7位格式的连续后缀,可以获得30%以上的压缩比。我不知道这叫什么,但它可以很有效地转化为树结构。

前任。: a+n+d+s|an+d+y|和+es+roid

是26个字符,相比之下:

一一广告像和任何安第斯山脉安卓

这是33。

考虑到以7位内容存储时12.5%的压缩比,压缩总量约为31%。当然,压缩比取决于单词列表的大小和内容。

将其转换为26根树结构可能会导致查找速度比将明文子字符串与平面文件进行比较更快。

仔细想想,如果你只使用26个字符加上两个分隔符,你可以用5位完成所有事情,这本身就是37.5%的压缩,使上述示例的压缩率超过50%。

martinus 17 年前

我认为你最好的选择是 Compressed Suffix Tree / Compressed Suffix Array 。您可以在上面的链接中找到丰富的信息。这是一个正在进行的研究领域,确实非常有趣。

mattiast 17 年前

我不是这方面的专家,但不是 prefix tree 这几乎是标准的解决方案?它只存储一次单词的常见前缀。

schnaader 17 年前

对于纯压缩 Maximum Compression 该网站提供了一些4MB英语单词表的结果,最好的程序将其压缩到400KB左右。用于文本/单词压缩的其他一些压缩资源是 Hutter Prize page 以及 Large Text Compression Benchmark .

Jason S 17 年前

高德纳提到 "Patricia trie" 在……里面 The Art of Computer Programming vol. 3 我从未在任何实际工作中使用过它,但也许这会有所帮助。

编辑:你的RAM限制是什么?如果你有比ROM更多的RAM,也许ROM中的数据压缩(需要解压缩到RAM中)是正确的选择。我想,如果你有一个中等但不是大量的RAM,从技术上讲,你也可以将数据结构的一部分作为压缩的blob存储在内存中,并使用最近最少使用的缓存来保存其中的几个blob,然后在不在缓存中时动态解压缩相应的blob。