在拼写检查器中使用Levenshtein距离
我正在开发C++中的拼写检查器，并且在实现过程中遇到了某个特定的步骤。
假设我们有一个文本文件，其中包含拼写正确的单词和输入的字符串，我们希望检查拼写错误。如果该字符串是一个拼写错误的单词，我可以通过检查文本文件中的所有单词并选择与其不同且字母最少的单词来轻松找到其正确形式。对于这种类型的输入，我实现了一个函数来计算两个字符串之间的Levenshtein编辑距离。到目前一切尚好。
现在，困难的部分是:如果输入的字符串是拼写错误的单词的组合怎么办？例如，"iloevcokies“。另外，如何在正确的位置插入空格？
欢迎任何想法:)
回答 3
Stack Overflow用户
发布于 2011-03-23 06:52:38
短语的拼写更正可以通过几种方式来完成。一种方法需要具有单词二元组和三元组的索引。当然，这些可能是巨大的。另一种选择是尝试对插入空格的单词进行排列，然后在结果短语中查找每个单词。看一看谷歌Peter Norvig的一个拼写检查器的简单实现。无论采用哪种方式，都可以考虑使用n元语法索引以获得更好的性能，C++中有一些库可供参考。
谷歌和其他搜索引擎能够对短语进行拼写更正，因为它们有大量的查询和相关结果集索引，这使得它们能够计算出统计上良好的猜测。总体而言，使用上下文相关的更正和语音更正等方法，拼写更正问题可能会变得非常复杂。考虑到使用可能子项的排列可能会变得昂贵，您可以利用某些类型的启发式方法，但是这可能很快就会超出范围。
您还可以考虑使用现有的拼写库，例如aspell。
Stack Overflow用户
发布于 2011-03-23 10:15:27
一个想法的起点："iloevcokies“的L-distance中最热门的应该是"cookies”。如果您可以更改您的L-distance函数以跟踪并返回min-index和max-index (即，此匹配最好从第5个字符开始并转到第10个字符)，那么您可以删除该子字符串，并重新检查它之前和之后的字符串的L-distance，然后将它们连接起来以获得建议...
只是想一想，祝你好运...
Stack Overflow用户
发布于 2011-03-23 15:22:55
我假设您有一个现有的索引，您可以在其上运行levenshtein距离(例如，Trie，但任何排序的索引通常都可以很好地工作)。
这样你就可以得到相同的索引，几乎相同的路线，大致相同的遍历，而且它甚至不会对你的运行时间产生太大的影响。
https://stackoverflow.com/questions/5398722
复制相似问题
腾讯云开发者
