Algoritmo de Hunt-Szymanski

En informática , el algoritmo Hunt–Szymanski , ^{[1] [2]} también conocido como algoritmo Hunt–McIlroy , es una solución al problema de la subsecuencia común más larga . Fue uno de los primeros algoritmos no heurísticos utilizados en diff , que compara un par de archivos, cada uno representado como una secuencia de líneas. Hasta el día de hoy, se encuentran variaciones de este algoritmo en sistemas de control de versiones incrementales , motores wiki y software de investigación de filogenética molecular .

La complejidad del peor caso para este algoritmo es O ( n ² log n ) , pero en la práctica se espera que O ( n log n ) sea igual a O ( n log n ) . ^{[3] [4]}

Historia

El algoritmo fue propuesto por Harold S. Stone como una generalización de un caso especial resuelto por Thomas G. Szymanski. ^{[5] [6] [7]} James W. Hunt refinó la idea, implementó la primera versión del algoritmo de listado de candidatos utilizado por diff y lo incorporó a un marco más antiguo de Douglas McIlroy . ^[5]

La descripción del algoritmo apareció como un informe técnico de Hunt y McIlroy en 1976. ^[5] Al año siguiente, una variante del algoritmo fue finalmente publicada en un artículo conjunto de Hunt y Szymanski. ^{[5] [8]}

Algoritmo

El algoritmo Hunt–Szymanski es una modificación de una solución básica para el problema de la subsecuencia común más larga que tiene una complejidad O ( n ² ) . La solución se modifica de modo que los requisitos de tiempo y espacio para el algoritmo sean menores cuando funciona con entradas típicas.

Solución básica de la subsecuencia común más larga

Algoritmo

Sea A _i el i- ésimo elemento de la primera secuencia.

Sea B _j el j- ésimo elemento de la segunda secuencia.

Sea P _ij la longitud de la subsecuencia común más larga para los primeros i elementos de A y los primeros j elementos de B.

${\displaystyle P_{ij}={\begin{cases}0&{\text{ if }}\ i=0{\text{ or }}j=0\\1+P_{i-1,j-1}&{\text{ if }}A_{i}=B_{j}\\\max(P_{i-1,j},P_{i,j-1})&{\text{ if }}A_{i}\neq B_{j}\end{cases}}}$

Ejemplo

Una tabla que muestra los pasos recursivos que toma el algoritmo básico de subsecuencia común más larga

Consideremos las secuencias A y B.

A contiene tres elementos:

${\displaystyle {\begin{aligned}A_{1}=a\\A_{2}=b\\A_{3}=c\end{aligned}}}$

B contiene tres elementos:

${\displaystyle {\begin{aligned}B_{1}=a\\B_{2}=c\\B_{3}=b\end{aligned}}}$

En el diagrama se muestran los pasos que llevaría a cabo el algoritmo anterior para determinar la longitud de la subsecuencia común más larga de ambas secuencias. El algoritmo informa correctamente que la subsecuencia común más larga de las dos secuencias tiene una longitud de dos elementos.

Complejidad

El algoritmo anterior tiene complejidades temporales y espaciales de peor caso de O ( mn ) ( ver notación O grande ), donde m es el número de elementos en la secuencia A y n es el número de elementos en la secuencia B. El algoritmo Hunt–Szymanski modifica este algoritmo para tener una complejidad temporal de peor caso de O ( mn log m ) y una complejidad espacial de O ( mn ) , aunque regularmente supera al peor caso con entradas típicas.

Partidos imprescindibles

a-Candidatos

El algoritmo Hunt–Szymanski sólo considera lo que los autores llaman coincidencias esenciales, o k -candidatos. Los k -candidatos son pares de índices ( i , j ) tales que:

${\displaystyle A_{i}=B_{j}}$

${\displaystyle P_{ij}>max(P_{i-1,j},P_{i,j-1})}$

El segundo punto implica dos propiedades de los k -candidatos:

• Hay una subsecuencia común de longitud k en los primeros i elementos de la secuencia A y los primeros j elementos de la secuencia B.
• No existen subsecuencias comunes de longitud k para menos de i elementos de la secuencia A o j elementos de la secuencia B.

Conectandoa-Candidatos

Un diagrama que muestra cómo el uso de k -candidatos reduce la cantidad de tiempo y espacio necesarios para encontrar la subsecuencia común más larga de dos secuencias.

Para crear la subsecuencia común más larga a partir de una colección de k candidatos, se crea una cuadrícula con el contenido de cada secuencia en cada eje. Los k candidatos se marcan en la cuadrícula. Se puede crear una subsecuencia común uniendo las coordenadas marcadas de la cuadrícula de modo que cualquier aumento en i esté acompañado por un aumento en  j .

Esto se ilustra en el diagrama adyacente.

Los puntos negros representan candidatos que deberían ser considerados por el algoritmo simple y las líneas negras son conexiones que crean subsecuencias comunes de longitud 3.

Los puntos rojos representan k candidatos que son considerados por el algoritmo de Hunt–Szymanski y la línea roja es la conexión que crea una subsecuencia común de longitud 3.

Véase también

• Distancia de Levenshtein
• Problema de la subsecuencia común más larga
• Algoritmo de Wagner-Fischer

Referencias

1. "El algoritmo Hunt-Szymanski para LCS" (PDF) . Departamento de Matemáticas y Ciencias de la Computación, Universidad del Sur de Dinamarca. 12 de enero de 2017.
2. Grabowski, Szymon (2016). "Nuevas técnicas basadas en tabulación y programación dinámica dispersa para problemas de similitud de secuencias". Matemáticas Aplicadas Discretas . 212 (C): 96–103. arXiv : 1312.2217 . doi : 10.1016/j.dam.2015.10.040 . ISSN  0166-218X. S2CID  14005194.
3. Aho, A.; Hirschberg, D.; Ullman, J. (1976). "Límites de la complejidad del problema de la subsecuencia común más larga" (PDF) . Revista de la ACM . 23 (1): 1–12. doi :10.1145/321921.321922. ISSN  0004-5411. S2CID  10957346.
4. Véase la Sección 5.6 de Aho, AV , Hopcroft, JE y Ullman , JD , Estructuras de datos y algoritmos. Addison-Wesley, 1983. ISBN 0-201-00023-7 
5. Hunt, James W.; McIlroy, M. Douglas (junio de 1976). "Un algoritmo para la comparación diferencial de archivos" (PDF) . Informe técnico sobre ciencias de la computación . 41. Bell Laboratories.
6. Imre Simon (2 de abril de 1988). "Comparación de secuencias: algo de teoría y algo de práctica". Universidad de São Paulo.
7. Szymanski, TG (1975) Un caso especial del problema de la subsecuencia común máxima. Informe técnico TR-170, Laboratorio de Ciencias de la Computación, Universidad de Princeton.
8. Hunt, James W; Szymanski, Thomas G. (1977). "Un algoritmo rápido para calcular las subsecuencias comunes más largas" (PDF) . Comunicaciones de la ACM . 20 (5): 350–353. doi :10.1145/359581.359603. ISSN  0001-0782. S2CID  3226080.