logo标签列表

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

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

请查看麦克罗伊在他的出版物页面上的拼写列表开发。这是一篇关于小型计算机拼写检查的经典老论文，其中的限制映射得非常好，与您列出的限制相似。对词缀剥离和两种不同压缩方法进行了详细分析：Bloom过滤器和相关方案Huffman编码稀疏比特集合；我可能会选择Bloom过滤器而不是他选择的方法，因为后者在速度方面的成本很高，只能节省几个kB的空间。（编程珠玑有一章简要介绍了这篇论文。）

另请参阅全文搜索系统中存储词汇表的方法，例如信息检索导论。与上述方法不同，它没有误报。

特别感谢McIlroy的参考，这是一个非常好的起点。 - Tall Jeff
5
4
2
总结一下：
  • 零误判
  • 零漏报
  • 高压缩比
  • 不需要反向操作（即无需解压缩）

我原本想建议使用布隆过滤器，但这些有非零误判。

相反，《编程珠玑》谈到了类似的要求（/usr/share/dict/words 有41K）。

采用了词干的缩略形式：

  • present
  • represent
  • representation
  • misrepresentation
词缀剥离会引入假阳性。但我没有看到这里有“零假阳性”的要求——拼写检查本质上是不精确的。 - Darius Bacon
拼写检查，如其定义所示，是完全精确的。但这个定义并没有涵盖上下文。 - Sparr
这是不精确的，因为人类语言是开放式的。Jeff可能确实有字典查找的精确问题，而不是拼写检查的不精确问题（从他的问题陈述中我不确定）——但如果是拼写检查，那就只是一个关于错误数量和类型的问题。 - Darius Bacon
2
将单词作为连续后缀以7位格式存储，可使压缩率达到30%以上。不确定这叫什么，但它可以相当有效地转化为树形结构。
例如： a+n+d+s|an+d+y|and+es+roid
长度为26个字符，而以下单词列表长度为33： a an ad as and any andes android
考虑到将其存储为7位内容的12.5%压缩率，总压缩率约为31%。当然，压缩比取决于单词列表的大小和内容。
将此转换为26个根节点的树形结构可能会导致查找速度比对平面文件进行明文子字符串比较更快。
想想看，如果您只使用26个字符加上两个分隔符，您可以在5位中完成所有操作，这本身就是37.5%的压缩率，将上面的示例提高到超过50%的压缩率。
你甚至可以使用特殊字符来选择下一个后缀：a+n!+d+s|d!+y|es+roid - 使其达到21个字符。或者你总是先写下一个后缀（19个字符）。然后，你可以使用换行符来添加全新的后缀。 - schnaader
2
我认为你最好的选择是使用压缩后缀树/压缩后缀数组。你可以在上述链接中找到大量信息。这是一个持续的研究领域，非常有趣。
1

我对此并不是专家，但前缀树不是这个问题的标准解决方案吗？它只存储单词的公共前缀一次。

1
0

Knuth在《计算机程序设计艺术第3卷》中提到了"Patricia trie"。我从未将其用于任何实际工作，但也许它会有所帮助。

编辑：你的RAM限制是什么？如果你有比ROM更多的RAM可用，也许ROM中的数据压缩（需要解压缩到RAM中）是正确的方法。我想，如果你有适量但不是很大的RAM，技术上你也可以将数据结构的部分存储为内存中的压缩块，并使用最近最少使用的缓存来保留其中的几个，然后在缓存中没有时动态解压缩相应的块。

我的假设是，与编码字典大小相比，RAM 是有限的，要求将块解压缩到 RAM 中进行测试可能在计算上不可行。虽然携带基于 RAM 的状态是可行的，但单词查找需要在原地进行且只读。谢谢。 - Tall Jeff
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接