En informática , el algoritmo de Wagner-Fischer es un algoritmo de programación dinámica que calcula la distancia de edición entre dos cadenas de caracteres.
Historia
El algoritmo de Wagner-Fischer tiene un historial de múltiples inventos . Navarro enumera los siguientes inventores del mismo, con fecha de publicación, y reconoce que la lista está incompleta: [1] : 43
- Vintsyuk , 1968
- Needleman y Wunsch , 1970
- Sankoff , 1972
- Vendedores, 1974
- Wagner y Fischer , 1974
- Lowrance y Wagner, 1975
Calcular la distancia
El algoritmo de Wagner-Fischer calcula la distancia de edición basándose en la observación de que si reservamos una matriz para contener las distancias de edición entre todos los prefijos de la primera cadena y todos los prefijos de la segunda, entonces podemos calcular los valores en la matriz llenando la matriz, y así encontrar la distancia entre las dos cadenas completas como último valor calculado.
Una implementación sencilla, como pseudocódigo para una función Distancia que toma dos cadenas, s de longitud m , yt de longitud n , y devuelve la distancia de Levenshtein entre ellas, se ve como sigue. Tenga en cuenta que las cadenas de entrada tienen un índice, mientras que la matriz d tiene un índice cero y [i..k]
es un rango cerrado.
function Distancia ( char s [ 1 .. m ], char t [ 1 .. n ]) : // para todo i y j, d [i, j] mantendrá la distancia entre // los primeros i caracteres de sy los primeros j caracteres de t // tenga en cuenta que d tiene (m + 1) * (n + 1) valores declaran int d [ 0 .. m , 0 .. n ] establecer cada elemento en d en cero // los prefijos de origen se pueden transformar en una cadena vacía // eliminando todos los caracteres para i de 1 a m : d [ i , 0 ] : = i // se puede acceder a los prefijos de destino desde el prefijo de origen vacío // insertando todos los caracteres para j de 1 a n : d [ 0 , j ] : = j para j de 1 a n : para i de 1 a m : si s [ i ] = t [ j ] : substitutionCost : = 0 otra cosa : substitutionCost : = 1 d [ i , j ] : = mínimo ( d [ i -1 , j ] + 1 , // eliminación d [ i , j -1 ] + 1 , // inserción d [ i -1 , j -1 ] + coste de sustitución ) // sustitución volver d [ m , n ]
Dos ejemplos de la matriz resultante (al pasar el cursor sobre un número subrayado, se revela la operación realizada para obtener ese número):
|
|
La invariante que se mantiene a lo largo del algoritmo es que podemos transformar el segmento inicial s[1..i]
en t[1..j]
un mínimo de d[i,j]
operaciones. Al final, el elemento inferior derecho de la matriz contiene la respuesta.
Prueba de corrección
Como se mencionó anteriormente, el invariante es que podemos transformar el segmento inicial s[1..i]
en el t[1..j]
uso de un mínimo de d[i,j]
operaciones. Este invariante se mantiene desde:
- Inicialmente es cierto en la fila y la columna 0 porque
s[1..i]
se puede transformar en una cadena vacíat[1..0]
simplemente eliminando todos losi
caracteres. De manera similar, podemos transformarnoss[1..0]
ent[1..j]
simplemente agregando todos losj
caracteres. - Si
s[i] = t[j]
, y podemos transformars[1..i-1]
at[1..j-1]
enk
las operaciones, entonces podemos hacer lo mismo cons[1..i]
y acaba de salir el último carácter solo, dandok
operaciones. - De lo contrario, la distancia es el mínimo de las tres formas posibles de realizar la transformación:
- Si podemos transformar
s[1..i]
at[1..j-1]
enk
operaciones, a continuación, simplemente podemos añadirt[j]
después de obtenert[1..j]
enk+1
las operaciones (inserción). - Si podemos transformar
s[1..i-1]
at[1..j]
enk
las operaciones, entonces podemos eliminars[i]
y luego hacer lo mismo transformación, para un total dek+1
operaciones (supresión). - Si podemos transformar
s[1..i-1]
at[1..j-1]
enk
operaciones, entonces podemos hacer lo mismos[1..i]
e intercambiar el originals[i]
port[j]
después, por un total dek+1
operaciones (sustitución).
- Si podemos transformar
- Las operaciones necesarias para transformar
s[1..n]
ent[1..m]
es, por supuesto, el número necesario para transformar todos
en todot
, y por lo tanto,d[n,m]
nuestro resultado.
Esta prueba no puede validar que el número colocado d[i,j]
es, de hecho, mínimo; esto es más difícil de mostrar e involucra un argumento por contradicción en el que asumimos que d[i,j]
es menor que el mínimo de los tres, y usamos esto para mostrar que uno de los tres no es mínimo.
Posibles modificaciones
Las posibles modificaciones a este algoritmo incluyen:
- Podemos adaptar el algoritmo para usar menos espacio, O ( m ) en lugar de O ( mn ), ya que solo requiere que la fila anterior y la fila actual se almacenen en cualquier momento.
- Podemos almacenar el número de inserciones, eliminaciones y sustituciones por separado, o incluso las posiciones en las que ocurren, que es siempre
j
. - Podemos normalizar la distancia al intervalo
[0,1]
. - Si solo nos interesa la distancia si es menor que un umbral k , entonces es suficiente calcular una franja diagonal de ancho 2k + 1 en la matriz. De esta forma, el algoritmo se puede ejecutar en tiempo O ( kl ), donde l es la longitud de la cadena más corta. [2]
- Podemos dar diferentes costos de penalización por inserción, eliminación y sustitución. También podemos dar costos de penalización que dependen de qué caracteres se inserten, eliminen o sustituyan.
- Este algoritmo se paraleliza mal, debido a una gran cantidad de dependencias de datos . Sin embargo, todos los
cost
valores se pueden calcular en paralelo y el algoritmo se puede adaptar para realizar laminimum
función en fases para eliminar dependencias. - Al examinar diagonales en lugar de filas, y al usar la evaluación diferida , podemos encontrar la distancia de Levenshtein en O ( m (1 + d )) tiempo (donde d es la distancia de Levenshtein), que es mucho más rápido que el algoritmo de programación dinámica regular si la distancia es pequeña. [3]
Variante del vendedor para búsqueda de cadenas
Al inicializar la primera fila de la matriz con ceros, obtenemos una variante del algoritmo de Wagner-Fischer que se puede utilizar para la búsqueda de cadenas difusas de una cadena en un texto. [1] Esta modificación da la posición final de las subcadenas coincidentes del texto. Para determinar la posición inicial de las subcadenas coincidentes, el número de inserciones y eliminaciones puede almacenarse por separado y usarse para calcular la posición inicial a partir de la posición final. [4]
El algoritmo resultante no es de ninguna manera eficiente, pero fue en el momento de su publicación (1980) uno de los primeros algoritmos que realizó una búsqueda aproximada. [1]
Referencias
- ^ Gusfield, Dan (1997). Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional . Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-58519-4.
- ^ Allison L (septiembre de 1992). "La programación dinámica perezosa puede ser ansiosa" . Inf. Proc. Cartas . 43 (4): 207-12. doi : 10.1016 / 0020-0190 (92) 90202-7 .
- ^ Bruno Woltzenlogel Paleo. Un nomenclátor aproximado para GATE basado en la distancia de levenshtein . Sección de estudiantes de la Escuela Europea de Verano en Lógica, Lenguaje e Información ( ESSLLI ), 2007.