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

Question

He tenido éxito comparando 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 completamente nuevas.

Por ejemplo:

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

se trata como teniendo 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 crear una función de comparación que pueda identificar las subcadenas que han cambiado de posición como distintas a las ediciones?

Un posible enfoque 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. Sin embargo, una desventaja de esto es que cambiar solo la primera letra de una palabra puede crear una interrupción mucho mayor de lo que debería causar el cambio de una sola letra.

Lo que intento lograr es comparar dos hechos sobre personas que son cadenas de texto libre, y decidir qué tan probable es que estos hechos indiquen el mismo hecho. Los hechos podrían ser la escuela a la que asistió alguien, 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 la coincidencia debe ser algo confusa si queremos adivinar que se refieren a la misma escuela. Hasta ahora está funcionando muy bien para errores de ortografía (estoy usando un algoritmo phonetic similar al metaphone encima 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 " ;.

Answer 1

N-gramos

Utilice N-gramos , que admiten múltiples- transposiciones de caracteres en todo el texto .

La idea general es que divida las dos cadenas en cuestión en todas las posibles subcadenas de 2-3 caracteres (n-gramos) y trate el número de n-gramos compartidos entre las dos cadenas como su métrica de similitud. Esto se puede normalizar dividiendo el número compartido por el número total de n-gramos 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-grams

A y C solo comparten 8 2 gramos

de 20 total posible.

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

tf-idf y similitud de 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 de documento inversa (tf-idf) para pesar los tokens, construir vectores de oración y luego usar similitud de coseno como la métrica de similitud.

El algoritmo es:

1. Calcular frecuencias de token de 2 caracteres (tf) por oración.
2. Calcular 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 aparece un token en particular en todas las oraciones. En este caso, th está en todas las oraciones, por lo que tiene contenido de información cero (log (3/3) = 0).
3. Produzca la matriz tf-idf multiplicando las celdas correspondientes en las tablas tf e idf.
4. Finalmente, calcule la matriz de similitud de coseno para todos los pares de oraciones, donde A y B son pesos de la tabla tf-idf para los tokens correspondientes. El rango es de 0 (no similar) a 1 (igual).
   
   

Modificaciones de Levenshtein y Metaphone

Con respecto a otras respuestas. Damerau – Levenshtein la modificación solo admite la transposición de dos adyacentes personajes. Metaphone fue diseñado para que coincida con palabras que suenan igual y no para coincidencias de similitud.

Answer 2

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

Answer 3

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

Answer 4

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

$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 primero y el segundo son más similares que uno y tres y dos y tres.

Answer 5

He estado implementando levenshtein en un corrector ortográfico.

Lo que está 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 las palabras 2 o más, la adición al algoritmo es el peor de los casos ! (Max (wordorder1.length (), wordorder2.length ())) . Agregar un 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 desea todas las transposiciones, tendría que trabajar en cada posición hacia atrás desde ese punto comparando

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

Entonces puede ver por qué no incluyen esto en el método estándar.

Answer 6

Tome esta respuesta y realice 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 la búsqueda de diccionario en un trie, pero para hacer coincidir una sola palabra, es la misma idea. Estás haciendo ramificaciones, y en cualquier momento, puedes hacer cualquier cambio que desees, siempre y cuando le des un costo.

Answer 7

Elimine palabras duplicadas entre las dos cadenas y luego use Levenshtein.

Answer 8

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 palabras diferentes en todo el corpus; documentos similares luego 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 calcule 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 para llevar para PHP.

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

Answer 9

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

1. Divide 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

Podrías mejorar el paso 2 haciéndolo en múltiples pases, encontrando solo coincidencias exactas al principio, luego encontrando coincidencias cercanas para palabras en A que aún no tienen un compañero en B *, luego menos coincidencias cercanas, etc.