Distancia Levenshtein: ¿cómo manejar mejor las palabras intercambiando posiciones?

He tenido cierto éxito al comparar cadenas usando la función PHP levenshtein .

Sin embargo, para dos cadenas que contienen subcadenas que tienen posiciones intercambiadas, el algoritmo las cuenta como subcadenas nuevas completas.

Por ejemplo:

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

se tratan como tener menos en común que:

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

Preferiría un algoritmo que viera que los primeros dos eran más similares.

¿Cómo podría hacer una función de comparación que pueda identificar las subcadenas que han cambiado de posición para que sean distintas a las ediciones?

Un posible enfoque en el que he pensado es poner todas las palabras en la cadena en orden alfabético, antes de la comparación. Eso toma el orden original de las palabras completamente fuera de la comparación. Una desventaja de esto, sin embargo, es que cambiar solo la primera letra de una palabra puede crear una interrupción mucho más grande que lo que un cambio de una sola letra debería causar.

Lo que estoy tratando de lograr es comparar dos hechos sobre las personas que son cadenas de texto libre, y decidir qué tan probable es que estos hechos indiquen el mismo hecho. Los hechos pueden ser la escuela a la que asistió, el nombre de su empleador o editor, por ejemplo. Dos registros pueden tener la misma escuela deletreada de manera diferente, palabras en un orden diferente, palabras adicionales, etc., por lo que el emparejamiento debe ser confuso si queremos adivinar que se refieren a la misma escuela. Hasta ahora está funcionando muy bien para los errores ortográficos (estoy usando un algoritmo phoenetic similar al metafonía en la parte superior de todo esto) pero muy mal si cambia el orden de las palabras que parecen comunes en una escuela: “xxx college” vs “colegio de xxx”.

N-grams

Use N-grams , que admite transposiciones de múltiples caracteres en todo el texto .

La idea general es dividir las dos cadenas en cuestión en todas las posibles subcadenas de 2-3 caracteres (n-grams) y tratar el número de n-grams compartidos entre las dos cadenas como su métrica de similitud. Esto se puede normalizar dividiendo el número compartido por la cantidad total de n-grams en la cadena más larga. Esto es trivial de calcular, pero bastante poderoso.

Para las oraciones de ejemplo:

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

A y B comparten 18 2 gramos

A y C comparten solo 8 2 gramos

de 20 totales posibles.

Esto se ha discutido con más detalle en Gravano et al. papel .

tf-idf y similitud coseno

Una alternativa no tan trivial, pero basada en la teoría de la información, sería usar el término término frecuencia-frecuencia inversa del documento (tf-idf) para pesar los tokens, construir vectores de oraciones y luego usar la similitud del coseno como la métrica de similitud.

El algoritmo es:

  1. Calcula frecuencias de token de 2 caracteres (tf) por oración.
  2. Calcule las frecuencias de oraciones inversas (idf), que es un logaritmo de un cociente del número de todas las oraciones en el corpus (en este caso 3) dividido por el número de veces que un token en particular aparece en todas las oraciones. En este caso, th está en todas las oraciones, por lo que tiene cero contenido de información (log (3/3) = 0). fórmula idf
  3. Produzca la matriz tf-idf multiplicando las celdas correspondientes en las tablas tf e idf. tfidf
  4. Finalmente, calcule la matriz de similitud del coseno para todos los pares de oraciones, donde A y B son ponderaciones de la tabla tf-idf para los tokens correspondientes. El rango es de 0 (no similar) a 1 (igual).
    similitud coseno
    matriz de similitud

Modificaciones de Levenshtein y Metaphone

En cuanto a otras respuestas. La modificación de Damerau-Levenshtein solo admite la transposición de dos caracteres adyacentes . Metaphone fue diseñado para combinar palabras que suenan igual y no para coincidencias de similitud.

Es fácil. Solo usa la distancia Damerau-Levenshtein en las palabras en lugar de letras.

Explota en espacios, ordena la matriz, implosiona, luego haz el Levenshtein.

También puedes probar esto. (solo una sugerencia extra)

 $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 

Esto mostrará que el 1 ° y 2 ° son más similares que uno, tres, dos y tres.

He estado implementando levenshtein en un corrector ortográfico.

Lo que estás pidiendo es contar las transposiciones como 1 edición.

Esto es fácil si solo desea contar las transposiciones de una palabra de distancia. Sin embargo, para la transposición de palabras a 2 o más de distancia, la adición al algoritmo es el peor de los casos !(max(wordorder1.length(), wordorder2.length())) . Agregar una subalgoritmo no lineal a un algoritmo ya cuadrático no es una buena idea.

Así es como funcionaría.

 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); } 

SOLO para tocar transposiciones. Si quieres todas las transposiciones, tendrías que para cada posición trabajar hacia atrás desde ese punto comparando

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

Entonces, ves por qué no incluyen esto en el método estándar.

Toma esta respuesta y haz el siguiente cambio:

 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]); } } 

Esto es para búsqueda de diccionario en un trie, pero para hacer coincidir una sola palabra, es la misma idea. Está haciendo una bifurcación y, en cualquier punto, puede hacer cualquier cambio que desee, siempre que le dé un costo.

Elimina las palabras duplicadas entre las dos cuerdas y luego usa Levenshtein.

Creo que este es un excelente ejemplo para usar un motor de búsqueda de espacio vectorial .

en esta técnica, cada documento se convierte esencialmente en un vector con tantas dimensiones como diferentes palabras en todo el corpus; documentos similares ocupan áreas vecinas en ese espacio vectorial. Una buena propiedad de este modelo es que las consultas también son solo documentos: para responder una consulta, simplemente calcula su posición en el espacio vectorial, y sus resultados son los documentos más cercanos que puede encontrar. Estoy seguro de que hay soluciones fáciles de usar para PHP.

para difuminar los resultados del espacio vectorial, podría considerar hacer una técnica similar de procesamiento de lenguaje natural, y usar levenshtein para construir consultas secundarias para palabras similares que ocurren en su vocabulario general.

Si la primera cadena es A y la segunda es B:

  1. Dividir A y B en palabras
  2. Para cada palabra en A, encuentre la mejor palabra coincidente en B (usando levenshtein)
  3. Elimine esa palabra de B y colóquela en B * en el mismo índice que la palabra correspondiente en A.
  4. Ahora compare A y B *

Ejemplo:

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

Puede mejorar el paso 2 si lo hace en múltiples pasadas, al encontrar solo las coincidencias exactas al principio, y luego encontrar coincidencias cercanas para las palabras en A que no tienen un acompañante en B *, luego menos coincidencias cercanas, etc.