Algoritmo de Wagner-Fischer

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 una historia de múltiples invenciones . Navarro enumera a los siguientes inventores, 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 almacenar 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 mediante el llenado por inundación de la matriz y, por lo tanto, encontrar la distancia entre las dos cadenas completas como el último valor calculado.

Una implementación sencilla, como pseudocódigo para una función llamada Distance que toma dos cadenas, s de longitud m y t de longitud n , y devuelve la distancia de Levenshtein entre ellas, se ve así. Las cadenas de entrada están indexadas desde uno, mientras que la matriz d está indexada desde cero y [i..k]es un rango cerrado.

función Distancia ( char s [ 1 .. m ] , char t [ 1 .. n ]) : // para todo i y j, d[i,j] contendrá la distancia entre // los primeros i caracteres de s y los primeros j caracteres de t // tenga en cuenta que d tiene (m+1)*(n+1) valores declare int d [ 0 .. m , 0 .. n ] establezca cada elemento en d a cero // los prefijos de origen se pueden transformar en una cadena vacía // eliminando todos los caracteres para i desde 1 hasta m : d [ i , 0 ] := i // los prefijos de destino se pueden alcanzar desde un prefijo de origen vacío // insertando cada carácter para j desde 1 hasta n : d [ 0 , j ] := j para j desde 1 hasta n : para i desde 1 hasta m : si s [ i ] = t [ j ] : substitutionCost := 0 sino : substitutionCost := 1d [ i , j ] := mínimo ( d [ i - 1 , j ] + 1 , // eliminación d [ i , j - 1 ] + 1 , // inserción d [ i - 1 , j - 1 ] + costo de sustitución ) // sustitución return d [ m , n ]

Dos ejemplos de la matriz resultante (al pasar el cursor sobre un número subrayado se muestra la operación realizada para obtener ese número):

La constante que se mantiene a lo largo del algoritmo es que podemos transformar el segmento inicial s[1..i]con t[1..j]un mínimo de d[i,j]operaciones. Al final, el elemento inferior derecho del array contiene la respuesta.

Prueba de corrección

Como se mencionó anteriormente, la invariante es que podemos transformar el segmento inicial s[1..i]utilizando t[1..j]un mínimo de d[i,j]operaciones. Esta invariante se cumple ya que:

Inicialmente es cierto en la fila y columna 0 porque s[1..i]se puede transformar en la cadena vacía t[1..0]simplemente eliminando todos ilos caracteres. De manera similar, podemos transformarlo s[1..0]simplemente t[1..j]agregando todos jlos caracteres.
Si s[i] = t[j], y podemos transformar s[1..i-1]en t[1..j-1]operaciones k, entonces podemos hacer lo mismo con s[1..i]y simplemente dejar el último carácter sin modificar, dando koperaciones.
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]en t[1..j-1]operaciones k, entonces podemos simplemente agregar t[j]después para obtener t[1..j]en k+1operaciones (inserción).
- Si podemos transformar s[1..i-1]en t[1..j]operaciones k, entonces podemos eliminar s[i]y luego hacer la misma transformación, para un total de k+1operaciones (eliminación).
- Si podemos transformar s[1..i-1]en t[1..j-1]operaciones k, entonces podemos hacer lo mismo con s[1..i], e intercambiar el original s[i]por t[j]después, para un total de k+1operaciones (sustitución).
Las operaciones necesarias para transformar s[1..n]en t[1..m]es, por supuesto, el número necesario para transformar todo sen todo t, y por lo tanto d[n,m]contiene nuestro resultado.

Esta prueba no logra validar que el número colocado d[i,j]sea de hecho mínimo; esto es más difícil de demostrar e implica un argumento por contradicción en el que asumimos d[i,j]que es menor que el mínimo de los tres, y usamos esto para demostrar que uno de los tres no es mínimo.

Posibles modificaciones

Las posibles modificaciones a este algoritmo incluyen:

Podemos adaptar el algoritmo para que utilice menos espacio, O ( m ) en lugar de O ( mn ), ya que solo requiere que la columna anterior y la columna 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 siempre es j.
Podemos normalizar la distancia al intervalo [0,1].
Si solo nos interesa la distancia si es menor que un umbral $k$ , entonces basta con calcular una franja diagonal de ancho ⁠ $2k+1$ en la matriz. De esta forma, el algoritmo se puede ejecutar entiempo $O (kl) , donde$ $l$ es la longitud de la cadena más corta.^{[ 2 ]}
Podemos asignar diferentes costos de penalización a la inserción, eliminación y sustitución. También podemos asignar costos de penalización que dependan de los caracteres que se inserten, eliminen o sustituyan.
Este algoritmo se paraleliza mal debido a la gran cantidad de dependencias de datos . Sin embargo, todos los costvalores se pueden calcular en paralelo, y el algoritmo se puede adaptar para realizar la minimumfunción por fases y así eliminar las dependencias.
Al examinar las diagonales en lugar de las filas y al usar la evaluación perezosa , podemos encontrar la distancia de Levenshtein en un tiempo de O ( m (1 + d )) (donde d es la distancia de Levenshtein), lo cual 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 la búsqueda de cadenas

Al inicializar la primera fila de la matriz con ceros, obtenemos una variante del algoritmo de Wagner-Fischer que puede utilizarse para la búsqueda difusa de una cadena en un texto. ^{[ 1 ]} Esta modificación proporciona la posición final de las subcadenas coincidentes del texto. Para determinar la posición inicial de las subcadenas coincidentes, se puede almacenar por separado el número de inserciones y eliminaciones y utilizarlo para calcular la posición inicial a partir de la posición final. ^{[ 4 ]}

El algoritmo resultante no es en absoluto eficiente, pero en el momento de su publicación (1980) fue uno de los primeros algoritmos que realizaban búsquedas aproximadas. ^{[ 1 ]}

Referencias

1 2 3 Navarro, Gonzalo (2001). "Una visita guiada a la coincidencia aproximada de cadenas" (PDF) . ACM Computing Surveys . 33 (1): 31– 88. CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .
↑ 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 entusiasta" . Inf. Proc. Letters . 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. Archivado el 8 de mayo de 2013 en Wayback Machine . Sección de estudiantes de la Escuela Europea de Verano en Lógica, Lenguaje e Información ( ESSLLI ), 2007.

[navarro-1] 1 2 3 Navarro, Gonzalo (2001). "Una visita guiada a la coincidencia aproximada de cadenas" (PDF) . ACM Computing Surveys . 33 (1): 31– 88. CiteSeerX 10.1.1.452.6317 . doi : 10.1145/375360.375365 . S2CID 207551224 .

[2] 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.

[3] Allison L (septiembre de 1992). "La programación dinámica perezosa puede ser entusiasta" . Inf. Proc. Letters . 43 (4): 207– 12. doi : 10.1016/0020-0190(92)90202-7 .

[4] Bruno Woltzenlogel Paleo. Un nomenclátor aproximado para GATE basado en la distancia de Levenshtein. Archivado el 8 de mayo de 2013 en Wayback Machine . Sección de estudiantes de la Escuela Europea de Verano en Lógica, Lenguaje e Información ( ESSLLI ), 2007.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]