Distance Levenshtein: comment mieux gérer les échanges de mots?

Question

J'ai eu quelques succès en comparant des chaînes en utilisant la fonction PHP levenshtein .

Cependant, pour deux chaînes contenant des sous-chaînes ayant des positions permutées, l'algorithme les comptabilise en tant que nouvelles sous-chaînes.

Par exemple:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

sont considérés comme ayant moins de points communs que:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

Je préférerais un algorithme qui verrait que les deux premiers étaient plus similaires.

Comment puis-je créer une fonction de comparaison permettant d'identifier les sous-chaînes qui ont changé de position comme étant distinctes des modifications?

Une approche possible à laquelle j'ai pensé consiste à mettre tous les mots de la chaîne dans l'ordre alphabétique, avant la comparaison. Cela élimine complètement l'ordre initial des mots de la comparaison. Cependant, un inconvénient à cela est que le fait de ne changer que la première lettre d'un mot peut créer une perturbation bien plus importante que ne le ferait le changement d'une seule lettre.

Ce que j'essaie de faire est de comparer deux faits sur des personnes qui sont des chaînes de texte libres et de décider de la probabilité que ces faits indiquent le même fait. Les faits peuvent être l’école fréquentée, le nom de leur employeur ou de leur éditeur, par exemple. Deux enregistrements peuvent avoir la même école orthographiée différemment, des mots dans un ordre différent, des mots supplémentaires, etc., de sorte que la correspondance doit être un peu floue si nous voulons bien deviner qu'ils font référence à la même école. Jusqu'ici, il fonctionne très bien pour les fautes d'orthographe (j'utilise un algorithme phénétique similaire à un métaphone en plus de tout cela), mais très mal si vous inversez l'ordre des mots qui paraissent fréquents dans une école: "xxx college". vs "collège de xxx".

Answer 1

N-grammes

Utilisez N-grammes , qui prend en charge plusieurs- transpositions de caractères sur l'ensemble du texte .

L’idée générale est que vous divisez les deux chaînes en question en toutes les sous-chaînes possibles de 2 à 3 caractères (n-grammes) et que vous traitiez le nombre de n-grammes partagés entre les deux chaînes comme leur métrique de similarité. Cela peut ensuite être normalisé en divisant le nombre partagé par le nombre total de n-grammes dans la chaîne la plus longue. C’est simple à calculer, mais assez puissant.

Pour les exemples de phrase:

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A et B partagent 18 2 grammes

Les parts A et C ne partagent que 8 2 grammes

sur un 20 total possible.

Ceci a été discuté plus en détail dans le Gravano et al. papier .

similitude tf-idf et cosinus

Une alternative pas si triviale, mais fondée sur la théorie de l'information, serait d'utiliser le terme terme fréquence – fréquence de document inverse (tf-idf) pour peser les jetons, construire des vecteurs de phrase, puis utiliser similarité cosinus en tant que métrique de similarité.

L'algorithme est:

1. Calculez la fréquence des jetons de 2 caractères (tf) par phrase.
2. Calculez la fréquence des phrases inverses (idf), qui correspond au logarithme du quotient du nombre total de phrases du corpus (ici 3) divisé par le nombre de fois qu'un jeton particulier apparaît dans toutes les phrases. Dans ce cas, th est dans toutes les phrases et n'a donc aucun contenu d'information (log (3/3) = 0).
3. Produisez la matrice tf-idf en multipliant les cellules correspondantes dans les tables tf et idf.
4. Enfin, calculez la matrice de similarité des cosinus pour toutes les paires de phrases, où A et B sont les poids de la table tf-idf pour les jetons correspondants. La plage va de 0 (pas similaire) à 1 (égal).
   
   

Modifications Levenshtein et Metaphone

Concernant les autres réponses. La modification de Damerau – Levenshtein ne prend en charge que la transposition de deux adjacents personnages. Le Metaphone a été conçu pour faire correspondre des mots qui ont le même son et qui ne le sont pas. pour la correspondance de similarité.

Answer 2

C'est facile. Utilisez simplement la distance Damerau-Levenshtein au lieu de lettres.

Answer 3

Exploser sur des espaces, trier le tableau, imploser, puis faire le Levenshtein.

Answer 4

Vous pouvez aussi essayer ceci. (juste une suggestion supplémentaire)

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

Cela montrera que le 1er et le 2ème ressemblent plus à un et trois et deux et trois.

Answer 5

Je suis en train de mettre en place levenshtein dans un correcteur orthographique.

Ce que vous demandez, c'est de compter les transpositions comme une édition.

C’est facile si vous ne souhaitez compter que les transpositions d’un mot. Toutefois, pour la transposition de deux mots ou plus, l’ajout à l’algorithme est le pire des cas ! (Max (wordorder1.length (), wordorder2.length ())) . Ajouter un sous-algorithme non linéaire à un algorithme déjà quadratique n’est pas une bonne idée.

Voici comment cela fonctionnerait.

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

JUST pour toucher les transpositions. Si vous voulez toutes les transpositions, il vous faudrait pour chaque position revenir en arrière à partir de ce point, en comparant

1[n] == 2[n-2].... 1[n] == 2[0]....

Vous voyez donc pourquoi ils n'incluent pas cela dans la méthode standard.

Answer 6

Prenez cette réponse et apportez les modifications suivantes:

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

Il s’agit de la recherche par dictionnaire dans un test, mais pour la correspondance avec un seul mot, c’est la même idée. Vous faites branche-et-lié, et à tout moment, vous pouvez faire tout changement que vous aimez, aussi longtemps que vous lui donnez un coût.

Answer 7

Éliminez les mots en double entre les deux chaînes, puis utilisez Levenshtein.

Answer 8

Je pense que c'est un excellent exemple d'utilisation d'un moteur de recherche d'espace vectoriel .

dans cette technique, chaque document devient essentiellement un vecteur avec autant de dimensions qu'il y a de mots différents dans tout le corpus; des documents similaires occupent alors les zones voisines de cet espace vectoriel. Une des propriétés intéressantes de ce modèle est que les requêtes ne sont que des documents: pour répondre à une requête, il vous suffit de calculer leur position dans un espace vectoriel et vos résultats sont les documents les plus proches que vous puissiez trouver. Je suis sûr qu'il existe des solutions rapides PHP.

Pour fuzzifier les résultats de l’espace vectoriel, vous pouvez envisager de faire appel à une technique de traitement du langage naturel similaire et utiliser levenshtein pour construire des requêtes secondaires pour des mots similaires figurant dans votre vocabulaire général.

Answer 9

Si la première chaîne est A et la seconde B:

1. Découpez A et B en mots
2. Pour chaque mot de A, recherchez le mot correspondant le mieux à B (en utilisant levenshtein)
3. Supprimez ce mot de B et mettez-le dans B * au même index que le mot correspondant dans A.
4. Comparez maintenant A et B *

Exemple:

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

Vous pouvez améliorer l'étape 2 en effectuant plusieurs passes, en ne recherchant que des correspondances exactes dans un premier temps, puis en recherchant les correspondances proches des mots en A qui n'ont pas encore de compagnon en B *, puis des correspondances moins rapprochées, etc.