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

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

Explotar en espacios, ordenar la matriz, implosionar, luego hacer el Levenshtein.

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 1er y 2do son más similares que uno y tres y 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 2 o más lejos, 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 transposición. Si desea todas las transposiciones, tendría que trabajar para cada posición hacia atrás desde ese punto comparando

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

Así que 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 la búsqueda del diccionario en un trie, pero para hacer coincidir una sola palabra, es la misma idea. Estás haciendo rama y encuadernación, y en cualquier momento, puedes hacer cualquier cambio que quieras, siempre y cuando le des un costo.

Elimine las palabras duplicadas entre las dos cadenas y luego use 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 hay palabras diferentes 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 a una consulta, simplemente calcula su posición en el espacio vectorial, y sus resultados son los documentos más cercanos puedes encontrar. estoy seguro de que hay soluciones get-and-go para PHP por ahí.

Para difuminar los resultados del espacio vectorial, podría considerar hacer una técnica de procesamiento de lenguaje natural similar / stemming, 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 palabra que mejor coincida en B (usando levenshtein)
3. Elimine esa palabra de B y póngala en B* en el mismo índice que la palabra coincidente 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ía mejorar el paso 2 haciéndolo en múltiples pasadas, encontrando solo coincidencias exactas al principio, luego encontrando coincidencias cercanas para palabras en un que no tienes un compañero en B* todavía, luego menos partidos cercanos, etc.