php - para - levenshtein mysql

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

Question

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

Sin embargo, para dos cadenas que contienen subcadenas que han intercambiado posiciones, el algoritmo las cuenta como subcadenas completamente nuevas.

Por ejemplo:

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

Se tratan 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 dos primeros eran más similares.

¿Cómo podría idear una función de comparación que pueda identificar las subcadenas que han cambiado de posición como distintas de 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 quita 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 mayor de lo que debería causar un cambio de una sola letra.

Lo que estoy tratando de 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 pueden ser la escuela a la que asistió, el nombre de su empleador o editor, por ejemplo. Dos registros pueden tener la misma escuela escrita de manera diferente, palabras en un orden diferente, palabras adicionales, etc., por lo que la coincidencia debe ser algo confusa si queremos hacer una buena suposición de que se refieren a la misma escuela. Hasta ahora está funcionando muy bien para los errores de ortografía (estoy usando un algoritmo fenicio similar al metáfono, pero muy mal si cambias el orden de las palabras que parecen comunes en una escuela: "xxx college" vs "colegio de xxx".

Answer 1

N-gramos

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

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

de un total de 20 posibles.

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

Similitud de tf-idf y coseno

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

El algoritmo es:

1. Calcule 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 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).
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 ponderaciones de la tabla tf-idf para los tokens correspondientes. El rango es de 0 (no similar) a 1 (igual).
   
   

Modificaciones de levenshtein y metáfono.

Respecto a otras respuestas. Damerau–Levenshtein solo admite la transposición de dos caracteres adyacentes . Metaphone fue diseñado para unir palabras que suenan igual y no para coincidencias de similitud.

Answer 2

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 cuerpo; Documentos similares ocupan áreas vecinas en ese espacio vectorial. Una buena característica de este modelo es que las consultas también son solo documentos: para responder a 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 PHP disponibles.

para difuminar los resultados del espacio vectorial, puede considerar la posibilidad de utilizar una técnica de procesamiento de lenguaje natural similar y usar levenshtein para construir consultas secundarias para palabras similares que aparecen en su vocabulario general.

Answer 3

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

Answer 4

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

Answer 5

Explote en espacios, ordene la matriz, implosione, luego haga Levenshtein.

Answer 6

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 escenario posible !(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 las 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]....

Así que ya ves por qué no incluyen esto en el método estándar.

Answer 7

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 coincidente en A.
4. Ahora compara 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 varias pasadas, encontrando solo coincidencias exactas al principio, luego encontrando coincidencias cercanas para las palabras en A que aún no tienen un compañero en B *, luego menos coincidencias cercanas, etc.

Answer 8

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

Answer 9

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 la búsqueda de diccionarios en un trie, pero para coincidir con una sola palabra, es la misma idea. Lo estás haciendo por ramas, y en cualquier momento, puedes hacer cualquier cambio que desees, siempre y cuando le des un costo.