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 距離
• レーベンシュタイン距離
• 最適な弦の整列距離
• ダメラウ・レーベンシュタイン距離
• Qwerty キーボードの距離

次のような便利なリンクがあります。

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

これを書いている時点で、Debian ベースの Linux ディストリビューションには、リポジトリに agrep とTRE-agrepも含まれています。