La distancia de edición de Levenshtein-Distance entre listas es un problema bien estudiado. Pero no puedo encontrar mucho sobre posibles mejoras si se sabe que ningún elemento ocurre más de una vez en cada lista .
Supongamos también que los elementos son comparables / ordenables (pero las listas para comparar no están ordenadas para empezar).
Más formalmente,
¿Qué tan eficientemente podemos calcular la distancia de edición entre dos cadenas dadas con la promesa de que no tienen letras repetidas?
es un alfabeto muy grande.
algorithms
strings
string-metrics
edit-distance
usuario362178
fuente
fuente
Respuestas:
TL; DR: un tipo de distancia de edición un poco más restrictivo, en el que solo podemos insertar y eliminar caracteres individuales, puede calcularse en tiempo lineal lineal cuando ambas (o incluso una) de las cadenas tienen caracteres únicos. Esto proporciona límites superiores e inferiores útiles en la distancia de edición de Levenshtein.
Insertar / eliminar distancia de edición y subsecuencias comunes más largas
La distancia de edición de Levenshtein permite inserciones, eliminaciones y sustituciones de un solo carácter, asignando a cada una un costo de 1. Si restringimos solo las inserciones y eliminaciones, obtenemos una medida de distancia similar que ahora hace que las sustituciones tengan un costo de 2 (ya que cualquier sustitución puede ser imitado usando una inserción y una eliminación). No conozco un nombre estándar para este tipo de distancia de edición más restrictiva, así que lo llamaré "insertar / eliminar distancia de edición". Que se corresponde estrechamente con el problema más larga subsecuencia común (LCS) , en la que se nos dan dos cadenas, de longitud y , respectivamente, y queremos saber la longitud de la subsecuencia más larga que aparece en ambos. Si dos cadenas tienen LCSm n L , luego tienen una distancia de edición de inserción / eliminaciónn+m−2L : la forma más fácil de ver esto es alinear las cadenas para que los caracteres en el LCS aparezcan apilados uno encima del otro, mientras que los caracteres que no están en el LCS aparecen enfrente de un
-
espacio personaje. Entonces será evidente que podemos editar la primera cadena en la segunda haciendo una inserción donde haya una-
en la fila superior y una eliminación donde haya una-
en la fila inferior. Por ejemplo:Aquí el LCS de6+7−2∗4=5
CIRCLE
yTRICKLE
,ICLE
tiene una longitud 4, y la distancia de edición es de hecho .Subsecuencias crecientes más largas
La razón de este desvío es que hay una forma muy eficiente de calcular el LCS (y, por lo tanto, la distancia de edición de inserción / eliminación) cuando al menos una de las secuencias contiene solo caracteres distintos: en este caso, el problema de LCS se puede transformar en El problema de encontrar una subsecuencia creciente más larga , que se puede resolver en el tiempo . Supongamos que se nos dan dos cadenas y , y la cadena tiene caracteres distintos. Podemos cambiar el nombre del primer carácter en a 1, el segundo a 2 y así sucesivamente, haciendo un seguimiento de qué número asignamos a cada carácter en una tabla. Entonces enO(nlogn) A B A A B , cambiamos el nombre de sus caracteres usando esta tabla (es decir, cada aparición de lo que fue el primer carácter O(n+mlogm) A B n m
A
se cambia a 1, etc.). Finalmente, buscamos una subsecuencia cada vez mayor enB
. Esto corresponde a un LCS entreA
yB
, y desde allí podemos calcular inmediatamente la distancia de edición de inserción / eliminación. El tiempo total necesario es solo si y tienen longitudes y , respectivamente.Límites en Levenshtein editar distancia
La distancia de inserción / eliminación proporciona claramente un límite superior en la distancia de Levenshtein (ya que cualquier secuencia válida de operaciones de edición bajo la distancia de inserción / eliminación también es una secuencia válida de operaciones de edición de Levenshtein). Dividir la distancia de edición de inserción / eliminación por 2 también proporciona un límite inferior, ya que en el peor de los casos, cualquier operación de edición de Levenshtein se puede cambiar a 2 operaciones de edición de inserción / eliminación.
Generalizaciones
Ya en 1977, Hunt y Szymanski idearon un algoritmo que puede verse como una generalización del algoritmo de subsecuencia de mayor crecimiento. Es eficiente cuando el número de pares de posiciones de caracteres coincidentes entre las dos cadenas es pequeño. Si hay tales pares, su algoritmo tarda tiempo. (Observe que si todos los caracteres en una cadena son distintos). Este algoritmo fue la base del programa original , que trató líneas enteras de texto como caracteres individuales. más tarde cambió a usar el algoritmo de tiempo Myers , donder O((r+n)logn) r≤n O(nd) d es la distancia de edición de inserción / eliminación, ya que funciona mejor cuando las diferencias generales son pequeñas pero algunos "caracteres" (líneas de texto) aparecen con frecuencia (como una línea que contiene solo una llave de apertura en el código del programa C).
diff
diff
fuente