Roe*_*ler 5 string algorithm statistics search pattern-matching
我需要为某个需求编写解决方案,我想知道是否有人熟悉可以实现它的现成的库,或者可以指导我的最佳实践.描述:
用户输入一个应该是几个固定选项之一的单词(我在列表中保存选项).我知道输入必须在列表中的成员中,但由于它是用户输入,他/她可能犯了一个错误.我正在寻找一种算法,告诉我用户最可能的单词是什么意思.我没有任何上下文,我不能强迫用户从列表中选择(即他必须能够自由和手动输入单词).
例如,假设该列表包含单词"water","quarter","beer","beet","hell","hello"和"aardvark".
解决方案必须考虑到不同类型的"正常"错误:
显而易见的解决方案是逐个字母地比较,并给每个不同的字母,额外的字母和遗失的字母赋予"惩罚权重".但是这个解决方案忽略了数千个"标准"错误,我肯定会在某处列出.我确信那里有针对所有案例的启发式方法,包括具体和一般情况,可能使用标准不匹配的大型数据库(我对数据量大的解决方案持开放态度).
我在Python编码,但我认为这个问题与语言无关.
有什么建议/想法吗？
bay*_*yer 10
你想了解谷歌如何做到这一点:http://norvig.com/spell-correct.html
编辑:有些人提到了定义用户给定单词和候选单词(levenshtein,soundex)之间的度量的算法.然而,这不是问题的完整解决方案,因为人们还需要数据结构来有效地执行非欧几里得最近邻搜索.这可以通过封面树来完成:http://hunch.net/~jl/projects/cover_tree/cover_tree.html