Quel algorithme utiliseriez-vous le mieux pour la similitude des chaînes?

Je conçois un plugin pour identifier de manière unique le contenu de diverses pages Web, en fonction des adresses.

Je peux donc avoir une adresse qui ressemble à:

1 someawesome street, anytown, F100 211

plus tard, je trouverai peut-être cette adresse dans un format légèrement différent.

1 someawesome street, F100 211,

ou peut-être aussi vague que

someawesome street F100

Ce sont techniquement la même adresse, mais avec un niveau de similitude. Je voudrais a) générer un identifiant unique pour chaque adresse pour effectuer des recherches, et b) savoir quand une adresse très similaire apparaît.

Quels algorithmes / techniques / métriques de chaîne dois-je examiner? La distance de Levenshtein semble être un choix évident, mais curieux de savoir s'il existe d'autres approches qui se prêteraient ici.

L'algorithme de Levenstein est basé sur le nombre d'insertions, de suppressions et de substitutions dans les chaînes.

Malheureusement, il ne prend pas en compte une faute d'orthographe courante qui est la transposition de 2 caractères (par exemple someawesome vs someaewsome). Je préfère donc l' algorithme Damerau-Levenstein plus robuste .

Je ne pense pas que ce soit une bonne idée d'appliquer la distance sur des cordes entières car le temps augmente brusquement avec la longueur des cordes comparées. Mais pire encore, lorsque des composants d'adresse, tels que ZIP, sont supprimés, des adresses complètement différentes peuvent mieux correspondre (mesurées à l'aide de la calculatrice Levenshtein en ligne ):

1 someawesome street, anytown, F100 211       (reference) 
1 someawesome st.,anytown                     (difference of 15, same address)     
1 otherplaces street,anytown,F100211          (difference of 13, different ddress) 
1 sameawesome street, othertown, CA98200      (difference of 13, different ddress)
anytown, 1 someawesome street                 (28 different same address)
anytown, F100 211, 1 someawesome street       (37 different same address)

Ces effets ont tendance à s'aggraver pour un nom de rue plus court.

Il vaut donc mieux utiliser des algorithmes plus intelligents. Par exemple, Arthur Ratz a publié sur CodeProject un algorithme de comparaison de texte intelligente. L'algorithme n'imprime pas une distance (il peut certainement être enrichi en conséquence), mais il identifie certaines choses difficiles telles que le déplacement de blocs de texte (par exemple, l'échange entre la ville et la rue entre mon premier exemple et mon dernier exemple).

Si un tel algorithme est trop général pour votre cas, vous devez alors vraiment travailler par composants et comparer uniquement des composants comparables. Ce n'est pas une chose facile si vous voulez analyser n'importe quel format d'adresse dans le monde. Mais si l'objectif est plus précis, par exemple aux États-Unis, il est certainement réalisable. Par exemple, "rue", "rue", "lieu", "place", et leurs fautes d'orthographe habituelles pourraient révéler la partie rue de l'adresse, dont la partie principale serait en principe le numéro. Le code postal pourrait aider à localiser la ville, ou bien il s'agit probablement du dernier élément de l'adresse, ou si vous n'aimez pas deviner, vous pouvez rechercher une liste de noms de villes (par exemple, télécharger une base de données gratuite de codes postaux). Vous pouvez ensuite appliquer Damerau-Levenshtein sur les composants concernés uniquement.

La distance de Levenshtein est meilleure pour les mots

Si les mots sont (principalement) orthographiés correctement, regardez le sac de mots . Je peux sembler trop tuer, mais TF-IDF et la similitude cosinus .

Ou vous pouvez utiliser gratuitement Lucene. Je pense qu'ils font la similitude cosinus.

Tout d'abord, vous devez analyser la page Web pour les adresses, RegEx est une lettre écrite à prendre, mais il peut être très difficile d'analyser les adresses à l'aide de RegEx. Vous finiriez probablement par avoir à parcourir une liste de formats d'adressage potentiels et une ou plusieurs expressions qui leur correspondent. Je ne suis pas trop familier avec l'analyse d'adresses, mais je recommanderais de jeter un coup d'œil à cette question qui suit une ligne de pensée similaire: Analyseur d'adresses général pour le texte de forme libre.

La distance Levenshtein est utile, mais seulement après avoir séparé l'adresse en ses parties. Considérez les adresses suivantes. 123 someawesome st.et 124 someawesome st.Ces adresses sont des emplacements totalement différents, mais leur distance Levenshtein n'est que de 1. Cela peut également être appliqué à quelque chose comme 8th st.et 9th st.Les noms de rues similaires n'apparaissent généralement pas sur la même page Web, mais ce n'est pas inconnu. La page Web d'une école peut avoir l'adresse de la bibliothèque de l'autre côté de la rue par exemple, ou l'église à quelques pâtés de maisons. Cela signifie que les seules données pour lesquelles la distance Levenshtein est facilement utilisable sont la distance entre 2 points de données, comme la distance entre la rue et la ville.

En ce qui concerne la façon de séparer les différents champs, c'est assez simple une fois que nous obtenons les adresses elles-mêmes. Heureusement, la plupart des adresses sont présentées dans des formats très spécifiques, avec un peu de magie RegEx, il devrait être possible de les séparer en différents champs de données. Même si l'adresse n'est pas bien formatée, il y a encore de l'espoir. Les adresses suivent toujours (presque) l'ordre de grandeur. Votre adresse doit se situer quelque part sur une grille linéaire comme celle-ci en fonction de la quantité d'informations fournies et de ce qu'elles sont:

StreetNumber < Street < City < State < Country

Il arrive rarement, voire pas du tout, que l'adresse saute d'un champ à un champ non adjacent. Vous n'allez pas voir une rue puis un pays, ou un numéro de rue puis une ville, très souvent.

Vous posez des questions sur les algorithmes de similitude des chaînes, mais vos chaînes sont des adresses. Je soumettrais les adresses à une API de localisation telle que Google Place Search et l'utiliserais formatted_addresscomme point de comparaison. Cela semble être l'approche la plus précise.

Pour les chaînes d'adresse qui ne peuvent pas être localisées via une API, vous pouvez alors revenir à des algorithmes de similitude.

Un algorithme cool qui est utile mais nécessite une base de données prédéfinie de réponses antérieures s'appelle: Distance d'édition de ligne.

La distance de modification de ligne, en tant que fonction, peut renvoyer "combien ces deux mots sont différents".

Un mot comme "dogme" et "chien", vous récupérerez une valeur de 3 (pour 3 caractères supplémentaires).

Ou "chat" et "chapeau", récupérez une valeur de 1 (pour un caractère différent).

(Source: https://en.wikipedia.org/wiki/Edit_distance )

En effet, l'utilisation d'une fonction de distance semble être une bonne approche. Mais le problème est alors de trouver la chaîne la plus proche d'une adresse donnée, ce qui est loin d'être trivial.

Vous décrivez ici une large catégorie d'algorithmes. Consultez la recherche du voisin le plus proche

Comme mentionné dans un commentaire, si vous trouvez un moyen de séparer les composants de l'adresse (nom de la rue, numéro, etc.), cela facilitera la tâche.

LongestCommonSubsequence (de Apache commons-text) peut être une autre approche pour essayer avec des adresses. Si vous définissez la similitude de deux comme le rapport " longueur de sous-séquence commune / max (longueurs d'adresse) ", alors vous pouvez appliquer un seuil de tolérance - par exemple 0,8 qui définira une correspondance / aucune correspondance. De cette façon, il vous permettra de faire correspondre des adresses comme " 1 someawesome st., Anytown " et " 1 someawesome street., Anytown ".

Ce n'est pas un algorithme super rapide, vous pouvez donc appliquer des reprises rapides pour minimiser les comparaisons. Exemple: éviter la comparaison si les codes postaux ne correspondent pas ou si la séquence de chiffres extraits uniquement est différente.