Existe-t-il des algorithmes permettant de trouver la correspondance la plus proche d'une chaîne de caractères dans une collection de chaînes de caractères ?

Question

Existe-t-il des algorithmes permettant de trouver la correspondance la plus proche d'une chaîne de caractères dans une collection de chaînes de caractères ? Par exemple :

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

Les termes de recherche que vous recherchez sont "algorithmes de distance entre chaînes de caractères" et "correspondance approximative entre chaînes de caractères". Une vérification rapide sur Google permet de trouver des options intéressantes telles que :

• Distance Sift3
• Distance de Levenshtein
• Distance optimale d'alignement des chaînes
• Distance Damerau-Levenshtein
• Distance du clavier Qwerty

Voici quelques liens utiles :

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

À ce jour, les distributions Linux basées sur Debian comprennent également agrep et TRE-agrep dans leurs référentiels.