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

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距離
• Levenshtein距離
• 優化線對齊距離
• 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。