是否有任何算法可以从字符串集合中找到与字符串最接近的匹配项？

Question

是否有任何算法可以从字符串集合中找到与字符串最接近的匹配项？例如：

string_to_match = 'What color is the sky?'

strings = [
  'What colour is the sea?', 
  'What colour is the sky?', 
  'What colour is grass?', 
  'What colour is earth?'
]

answer = method_using_string_matching_algorithm(string_to_match, strings)
answer # returns strings[1] 'What colour is the sky?'

Answer 1

您要查找的搜索词是“字符串距离算法”和“近似字符串匹配”。快速检查一下谷歌就会发现一些有趣的选项，例如：

• Sift3 距离
• 编辑距离
• 最佳串对齐距离
• 达默劳-莱文斯坦距离
• Qwerty 键盘距离

一些有用的链接包括：

• https://github.com/Kicksend/mailcheck/wiki/String-Distance-Algorithms
• http://en.wikipedia.org/wiki/Approximate_string_matching

截至撰写本文时，基于 Debian 的 Linux 发行版还在其存储库中包含 agrep 和TRE-agrep。