Algoritmo Hunt-Szymanski

Na ciência da computação, o algoritmo Hunt-Szymanski,^[1][2] também conhecido como algoritmo Hunt-McIlroy, é uma solução para o problema de maior subsequência comum. Foi um dos primeiros algoritmos não heurísticos usados no diff. Até hoje, variações desse algoritmo são encontradas em sistemas de controle de versão incrementais, software wiki e softwares de pesquisa da filogenética molecular.

O pior caso de complexidade para este algoritmo é ${\displaystyle O(n^{2}\log n)}$, mas na prática ${\displaystyle O(n\log n)}$ é esperado^[3][4]

O algoritmo foi proposto por Harold S. Stone como uma generalização do caso especial resolvido por Thomas G. Szymanski. James W. Hunt refinou a ideia, implementando a primeira versão do algoritmo proposto usado pelo diff em um modelo mais antigo de Douglas McIlroy^[5][6][7]

A descrição do algoritmo surgiu como um relatório técnico por Hunt e McIlroy. No ano seguinte, uma variação do algoritmo foi publicada em um artigo em conjunto de Hunt e Szymanski.

O algoritmo Hunt-Szymanski é uma modificação da solução básica ao problema da maior subsequência comum, de complexidade ${\displaystyle O(n^{2})}$. A modificação precisa de menos espaço e menos tempo para as entradas típicas.

Consideremos que ${\displaystyle A_{i}}$ seja a i-ésima linha do primeiro arquivo

E que ${\displaystyle B_{j}}$ seja a j-ésima linha do segundo arquivo.

Então ${\displaystyle P_{ij}}$ será o tamanho da maior subsequência comum para as primeiras ${\displaystyle i}$ linhas do primeiros arquivo e as primeiras ${\displaystyle j}$ linhas do segundo arquivo

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

Considere os arquivos ${\displaystyle A}$ e ${\displaystyle B}$

${\displaystyle A}$ contém essas 3 linhas:

${\displaystyle A_{1}=a}$

${\displaystyle A_{2}=b}$

${\displaystyle A_{3}=c}$

E ${\displaystyle B}$ contém essas outras 3:

${\displaystyle B_{1}=a}$

${\displaystyle B_{2}=c}$

${\displaystyle B_{3}=b}$

Os passos que o algoritmo deve seguir para determinar o tamanho da maior subsequência comum para ambos os arquivos são mostrados no diagrama. O algoritmo mostra corretamente que a maior subsequência de ambos os arquivos são 2 linhas.

O primeiro algoritmo tinha no pior caso uma complexidade de tempo e espaço de ${\displaystyle O(mn)}$(veja a notação grande-O), onde ${\displaystyle m}$ é o número de linhas do arquivo ${\displaystyle A}$ e ${\displaystyle n}$ é o número de linhas para um arquivo ${\displaystyle B}$. Enquanto o algoritmo de Hunt-Szymanski tem no pior caso uma complexidade de tempo de ${\displaystyle O(mn\log m)}$ e uma complexidade de espaço de ${\displaystyle O(mn)}$, embora ele supere regularmente o pior caso com entradas típicas