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

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

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

• Sift3 距离
• 编辑距离
• 最佳字符串对齐距离
• Damerau-Levenshtein 距离
• Qwerty 键盘距离

一些有用的链接包括:

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

在撰写本文时，基于 Debian 的 Linux 发行版还包括 agrep 和 TRE-agrep在他们的存储库中。