在拼写检查器中使用Levenshtein距离

Question

我正在研究C++中的拼写检查器，并且我被困在实现中的某个步骤中。

比方说，我们有一个拼写正确的单词和输入的字符串的文本文件，我们想检查拼写错误。如果该字符串是一个拼写错误的单词，我可以通过检查文本文件中的所有单词并选择与最少字母不同的单词来轻松找到它的正确格式。对于这种类型的输入，我已经实现了一个函数来计算2个字符串之间的Levenshtein编辑距离。到现在为止还挺好。

现在，困难的部分：如果输入的字符串是拼写错误的单词的组合？例如，“iloevcokies”。考虑到“我”，“爱”和“饼干”是可以在文本文件中找到的单词，我如何使用已实现的Levenshtein函数来确定文件中的哪些单词适合于更正？另外，如何将空白插入正确的位置？

欢迎任何想法:)

Answer 1

短语的拼写更正可以通过几种方法完成。一种方法需要具有单词二元组和三元组的索引。这当然可能是巨大的。另一种选择是尝试使用插入空格的单词排列，然后对结果短语中的每个单词进行查找。看一下谷歌的Peter Norvig的拼写检查器的简单实现。无论哪种方式，考虑使用n-gram索引以获得更好的性能，C++中有可用的库供参考。

谷歌和其他搜索引擎能够对词组进行拼写校正，因为它们有很大的查询索引和相关的结果集，这使得他们可以计算出一个统计上很好的猜测。总的来说，拼写纠正问题可能会随着上下文敏感纠正和语音纠正等方法变得非常复杂。鉴于使用可能的子项的排列可能会变得昂贵，您可以使用某些类型的启发式，但这可能会很快超出范围。

您也可以考虑使用和现有的拼写库，如aspell。

Answer 2

一个想法的起点：“iloevcokies”的L距离的顶级命中之一应该是“饼干”。如果你可以改变你的L距离函数来跟踪和返回一个最小索引和最大索引（即，这个匹配最好从字符5开始并到字符10），那么你可以删除那个子串并重新检查L距离d为之前的字符串，之后，再串连那些建议....

只是一个想法，好运气....

Answer 3

我会假设你有一个现有的指数，上你运行你的levenshtein距离（例如，Trie，但任何排序的索引通常工作得很好）。

您可以考虑将白色空格添加为常规编辑操作，只是存在一个转折点：您需要（随后）返回索引的下一个词的根目录。

这样你就可以得到相同的索引，几乎相同的路径，大约相同的遍历，它甚至不会影响你的运行时间。