car*_*rol 8 c++ algorithm spell-checking levenshtein-distance
我正在使用C++编写一个拼写检查程序,并且我已经陷入了实现中的某个步骤.
假设我们有一个包含正确拼写单词的文本文件和一个我们想要检查拼写错误的输入字符串.如果该字符串是拼写错误的单词,我可以通过检查文本文件中的所有单词并选择与其不同的单词和最少的字母来轻松找到其正确的表单.对于那种类型的输入,我实现了一个函数来计算2个字符串之间的Levenshtein编辑距离.到现在为止还挺好.
现在,困难的部分:如果输入的字符串是拼写错误的单词的组合怎么办？例如,"iloevcokies".考虑到"i","love"和"cookies"是可以在文本文件中找到的单词,我如何使用已经实现的Levenshtein函数来确定文件中哪些单词适合进行校正？另外,我如何在正确的位置插入空格？
欢迎任何想法:)
短语的拼写纠正可以通过几种方式完成.一种方法需要具有单词bi-gram和tri-gram的索引.这些当然可能是巨大的.另一种选择是尝试插入空格的单词的排列,然后对结果短语中的每个单词进行查找.看看Google 的Peter Norvig对拼写检查程序的简单实现.无论哪种方式,考虑使用n-gram索引以获得更好的性能,C++中提供的库可供参考.
谷歌和其他搜索引擎能够对短语进行拼写纠正,因为它们有大量的查询索引和相关的结果集,这使得他们可以计算出统计上的好猜测.总的来说,拼写校正问题可能会变得非常复杂,如上下文敏感校正和语音校正等方法.鉴于使用可能的子项的排列可能变得昂贵,您可以使用某些类型的启发式方法,但这可能会超出范围.
您还可以考虑使用和现有的拼写库,例如aspell.