En informática , el algoritmo Hunt-Szymanski , [1] [2] también conocido como algoritmo Hunt-McIlroy , es una solución al problema de subsecuencia común más largo . Fue uno de los primeros algoritmos no heurísticos utilizados en diff . Hasta el día de hoy, las variaciones de este algoritmo se encuentran en sistemas de control de versiones incrementales , motores wiki y software de investigación de filogenia molecular .
La complejidad del peor de los casos para este algoritmo es O ( n 2 log n ) , pero en la práctica se espera 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 lista 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, finalmente se publicó una variante del algoritmo en un artículo conjunto de Hunt y Szymanski. [5] [8]
Algoritmo
El algoritmo de Hunt-Szymanski es una modificación de una solución básica para el problema de subsecuencia común más largo que tiene complejidad O ( n 2 ) . La solución se modifica para que haya menores requisitos de tiempo y espacio para el algoritmo cuando trabaja con entradas típicas.
Solución básica de subsecuencia común más larga
Algoritmo
Sea A i la línea i del primer archivo.
Sea B j la j- ésima línea del segundo archivo.
Sea P ij la longitud de la subsecuencia común más larga para las primeras i líneas del primer archivo y las primeras j líneas del segundo archivo.
Ejemplo
Considere los archivos A y B .
A contiene tres líneas:
B contiene tres líneas:
Los pasos que realizaría el algoritmo anterior para determinar la longitud de la subsecuencia común más larga para ambos archivos se muestran en el diagrama. El algoritmo informa correctamente que la subsecuencia común más larga de los dos archivos tiene dos líneas.
Complejidad
El algoritmo anterior tiene tiempo del peor caso y la complejidad de espacio de O ( mn ) ( ver grande notación O ), donde m es el número de líneas en el archivo de A y n es el número de líneas en el archivo B . El algoritmo de Hunt-Szymanski modifica este algoritmo para tener una complejidad temporal en el peor de los casos de O ( mn log m ) y una complejidad espacial de O ( mn ) , aunque normalmente supera el peor de los casos con entradas típicas.
Partidos esenciales
k -candidatos
El algoritmo de Hunt-Szymanski solo considera lo que los autores llaman coincidencias esenciales o k -candidatos. k -candidatos son pares de índices ( i , j ) tales que:
El segundo punto implica dos propiedades de k -candidatos:
- Hay una subsecuencia común de longitud k en los primeros i líneas de archivo A y los primeros j líneas de archivo B .
- No hay subsecuencias comunes de longitud k para cualquier menos de i líneas de archivo de A o j líneas de archivo B .
Conectando k -candidatos
Para crear la subsecuencia común más larga a partir de una colección de candidatos k , se crea una cuadrícula con el contenido de cada archivo en cada eje. Los k -candidatos están marcados en la cuadrícula. Se puede crear una subsecuencia común uniendo las coordenadas marcadas de la cuadrícula de modo que cualquier aumento de i vaya acompañado de un aumento de j .
Esto se ilustra en el diagrama adyacente.
Los puntos negros representan candidatos que tendrían que 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.
Ver también
Referencias
- ^ "El algoritmo de Hunt-Szymanski para LCS" (PDF) . Departamento de Matemáticas e Informática, Universidad del Sur de Dinamarca. 12 de enero de 2017.
- ^ Grabowski, Szymon (2016). "Nuevas técnicas basadas en tabulación y programación dinámica dispersa para problemas de similitud de secuencia". Matemáticas aplicadas discretas . 212 (C): 96–103. ISSN 0166-218X .
- ^ Aho, A .; Hirschberg, D .; Ullman, J. (1976). "Límites de la complejidad del problema posterior común más largo" (PDF) . Revista de la ACM . 23 (1): 1–12. ISSN 0004-5411 .
- ^ Consulte la sección 5.6 de Aho, AV , Hopcroft, JE , Ullman, JD , Estructuras de datos y algoritmos. Addison-Wesley, 1983. ISBN 0-201-00023-7
- ^ a b c d Hunt, James W .; McIlroy, M. Douglas (junio de 1976). "Un algoritmo para la comparación diferencial de archivos" (PDF) . Informe Técnico en Ciencias de la Computación . Bell Laboratories. 41 .
- ^ Imre Simon (2 de abril de 1988). "Comparación de secuencia: algo de teoría y práctica" . Universidade de São Paulo.
- ^ 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.
- ^ 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. ISSN 0001-0782 .