Mesure de similarité

En mathématiques et en informatique théorique, une mesure de similarité, plus exactement une mesure de distance entre mots, est une façon de représenter par un nombre la différence entre deux mots, ou plus généralement deux chaînes de caractères. Cela permet de comparer des mots ou chaines de façon simple et pratique. C'est donc une forme de distance mathématique et de métrique pour les chaînes de caractères. En programmation, la mesure la plus simple et la plus courante est la distance de Levenshtein : elle est obtenue en comptant le nombre de modification de caractères individuels (ajout, retrait, ou changement) pour passer d'une chaîne à l'autre. Elle est utilisée dans la recherche approximative ou la comparaison de chaînes, aussi appelée en anglais fuzzy string searching. Pour qu'une mesure de similarité soit une métrique de chaînes de caractères, elle doit satisfaire l'inégalité triangulaire. Le résultat fourni par une métrique est un nombre qui est une indication sur la distance, et peut varier d'un algorithme à l'autre. La mesure la plus connue est une mesure rudimentaire appelée distance de Levenshtein, aussi connue sous le terme distance d'édition. Elle opère sur deux chaînes données, et retourne un nombre qui est le nombre d'insertions, suppression ou substitutions de caractère nécessaires pour transformer l'une des chaînes en l'autre. De telles distances ont été étendues pour s'appliquer également à la comparaison phonétique, à l'analyse lexicale, aux comparaisons grammaticales et autres. Ce concept provient du concept informatique de similarité, notamment utilisé dans le cadre de tâche de classification non supervisée. Les domaines d'application de mesures de similarité sont nombreux. Elles sont utilisées couramment dans les techniques d'analyse des données pour la détection de fraudes, comme l'empreinte digitale, la détection du plagiat, et également dans l'analyse génétique, l', l'apprentissage automatique, la fusion d'ontologies et dans les bases de données notamment la déduplication et l'intégrité référentielle, enfin dans l'exploration de données, dans les interfaces Web comme les suggestions de complétion dans le style d'Ajax, intégration des représentations des connaissances.