Representación intermedia / de codificación para la distancia de Levenshtein

Las frases:

El rápido zorro marrón salta sobre el perro perezoso [A]

y

El zorro marrón de Uick salta sobre el perro perezoso [B]

se puede comparar usando el algoritmo de distancia de Levenshtein para determinar la similitud calculando el número mínimo de adiciones, eliminaciones o reemplazos de un solo carácter necesarios para transformar A en B.

Estoy interesado en saber si hay una representación intermedia, o posiblemente un esquema de codificación para la distancia de Levenshtein. No debe usarse entre dos frases, sino solo una codificación aplicada a una sola frase, de modo que el índice de caracteres no afecte las comparaciones.

En B, falta la 'q' en comparación con A. Una comparación de cadena normal coincidiría 'The 'y luego fallaría 'uick brown fox...'simplemente debido a un desplazamiento de un solo carácter. La distancia de Levenshtein podría usarse para compararla con la frase original A para una comparación más indulgente, pero en mi caso, no tendré dos frases, solo una.

Entonces, estoy buscando alguna forma de codificar inequívocamente una oración en paquetes de información, pequeños átomos de verdad (¿estoy pensando en un paquete por carácter?) Que mantengan un orden local y así sucesivamente, pero si algunos de los paquetes están mal, no afecta a los personajes posteriores.

Cada frase única debe correlacionarse con una y solo una codificación única / representación intermedia, Conjuntos A'y B'. Calcular la distancia de Levenshtein de A y B sería lo mismo que calcular la intersección de conjuntos A' = B'.

Alternativamente, si este problema no tiene una solución (y esto seguramente se correlaciona con un área de investigación bien pisada, no me sorprendería), algún argumento / prueba convincente de su insolubilidad.

De hecho, hay algunas investigaciones en este sentido para la distancia de edición con algunos resultados positivos y algunos negativos. (Es posible que no esté entendiendo la pregunta con precisión, por lo que trataré de responder preguntas que sé responder).

Aquí hay una interpretación: (I1) que desea calcular, para cada cadena A un conjunto f (A) tal que, para cualesquiera dos cadenas A, B, la distancia de edición ed (A, B) es igual a la diferencia simétrica entre f (A) yf (B) (en cierto sentido lo opuesto a la intersección de los dos conjuntos). Esta pregunta ha sido bien estudiada (aunque de lejos no está resuelta), y se conoce como la cuestión de incrustar la distancia de edición en la distancia de Hamming ( )$\ell_1$ . En particular, lograr (I1) con precisión no es posible, pero es posible hasta cierta aproximación (es decir, aproximamos ed (A, B) hasta cierto factor):

• Krauthgamer y Rabani demuestran que se requiere una aproximación de ( n es la longitud de las cadenas);$\Omega(\log n)$$n$

• Ostrovsky y Rabani prueban que aproximación es alcanzable.$2^{O(\sqrt{\log n\log\log n})}$

Aquí hay una interpretación un poco más liberal: (I2) producimos un bosquejo f (A) para cada cadena A, y estimamos la distancia ed (A, B) a través de algún cálculo en f (A), f (B) (es decir, no necesariamente tomando la diferencia simétrica). La pregunta es que f (A) sea mucho más corta que la longitud de la cadena original, (de lo contrario, uno tiene una solución trivial por f (A) = A). Esta interpretación (I2) es más general que (I1) (= más fácil de lograr), aunque no conocemos ninguna solución estrictamente mejor. Hay un progreso parcial , donde la estimación de ed (A, B) se realiza a partir de f (A) y B (es decir, una cadena, por ejemplo B, es completamente conocida).$n$

Seguramente hay más literatura en este sentido, pero avísame primero si esto se acerca a lo que querías decir.

Si lo único que puede suceder es que los personajes desaparezcan, creo que solo necesita resolver el problema de subsecuencia común más largo . (Una subsecuencia es una generalización de una subcadena: puede haber múltiples ubicaciones en la subsecuencia donde el material se eliminó de la secuencia más grande, no solo al principio y / o al final).

Más allá de eso, ¿has visto esta lista de métricas ?

Puedo estar malentendiendo su enunciado del problema, pero me parece que si define con precisión cómo pueden ocurrir los errores (eliminación, transposición, etc.) y luego construye un árbol de sufijos, debería ser posible tener un algoritmo bastante rápido, después de pagar el costo de memoria y preprocesamiento de construir el árbol de sufijos.

Esto es solo un pensamiento, no una solución, pero es demasiado largo para un comentario.

¿Podría su conjunto / representación ser un edificio alfabético de la cadena?
Ejemplo (para A):

1. Start with the empty string (^$) 
2. Insert a between 1st ^ and 1st $ (now: ^a$)
3. Insert b between 1st ^ and 1st a (now: ^ba$) 
4. Insert c between 1st ^ and 1st b (now: ^cba$) 
5. Insert d between 1st b and 1st a (now: ^cbda$) 
6. Insert d between 1st a and 1st ^ (now: ^cbdad$) 

y así...

Su representación sería los pasos que siguió para construir la cadena (en orden alfabético):

El elemento {a, {1, ^}, {1, $}} representa el paso 2, mientras que {d, {1, b}, {1, a}} representa el quinto paso.

Siempre que haga esto alfabéticamente en cada caso, es posible que tenga algo que pueda usar.

Un pensamiento complementario: comience con suficientes copias de cada letra "abcdd" (para los primeros 4) y luego haga un seguimiento de sus transposiciones para construir la cadena. Ahora nos estamos moviendo vagamente hacia la teoría de la permutación.

[Por cierto, son "saltos", no "saltados", de lo contrario no hay 's' - sí, me doy cuenta de que nunca dijiste que era un pangrama]

Me parece que tu cosa simple debería funcionar. Cada paquete contiene la posición y el carácter, p. Ej.

The = <1, T>, <2, h>, <3, e>

Luego comparas el primer par de A con el primer par de B, etc. Esto debería darte Levenshtein.