自动纠正算法

Question

我想在C++中实现以下内容:

1)检查字典中是否存在给定的单词.字典文件是一个巨大的文件; 考虑100MB或3-4百万字.

2)建议对错误的单词进行更正.

3)自动完成功能.

我的方法

1)我打算建一棵树,所以搜索效率很高.

2)我没有得到如何实现自动校正功能.

3)我可以使用树实现自动完成功能

实现上述所有功能的最佳数据结构和算法是什么？

Answer 1

您可以通过查看给定子树中的所有字符串来完成自动完成。一些帮助您选择的分数可能会有所帮助。这就像如果你有“te”，你就沿着特里树中的那条路径走，然后遍历那里的整个子树以获得所有可能的结局。

为了进行更正，您需要在树上实现类似http://en.wikipedia.org/wiki/Levenshtein_distance的内容。您可以利用这样一个事实：如果您处理了 trie 中的给定路径，则可以将结果重复用于以路径末尾为根的子树中的所有字符串。