最适合拼写检查器、词典和同义词表的算法和数据结构

看见 this 对于一个21行的Python2.5拼写校正器和一点背景。

http://en.wikipedia.org/wiki/Directed_acyclic_word_graph . 让事情复杂化的是,我最喜欢的关于结构的论文,Ciura和Deorowicz的《如何压缩词典》称它们为“最小ADFA”。谷歌搜索一下,你会发现很多与之竞争的算法来构建这些野兽。祝你好运

Bloom filter .

我会用 std::map (呼叫 Dictionary 在.Net framework中)集合中,将单词作为键,将自定义对象(包含有关单词的所有信息+定义)作为值。

对于叙词表来说,最好的结构是一棵树,其中每个节点都是一个部分,每个分支都以一个对象结束,该对象包含有关必须显示的内容的所有信息。

拼写校正器有点棘手,因为必须将fals输入映射到某种正确的输入。您可以将此链接作为起点: http://en.wikipedia.org/wiki/Spell_checker . 最后,你会找到关于不同算法的论文链接。根据维基百科的文章,本文描述了最成功的算法: Andrew Golding and Dan Roth's "Winnow-based spelling correction algorithm"

在这三种情况下,您都可以从单词集构建一个BK树。BK树允许您查找输入单词在给定编辑距离内的所有单词。见m y blog post 在BK树上查看它们如何工作的解释。

字典和拼写检查器或多或少是相同的——字典只需要提供单词的定义。对于同义词库,单词被聚集到“synset”(同义词集)中,所有元素都插入到BK树中。当某人在语法集中查找一个单词时,您会将所有其他单词显示为备选词。一个单词可以出现在多个语法集中,因此您需要确保BK树节点可以处理给定键的多个值。