Algoritmo Hunt-Szymanski

Na ciência da computação, o algoritmo Hunt-Szymanski, 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 é $O(n^{2}\log n)$, mas na prática $O(n\log n)$ é esperado

História

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

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.

Algoritmo

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

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

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

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

$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}}$

Exemplo

Uma tabela mostrando os passos que um algoritmo básico de maior subsequência comum deve fazer.

Considere os arquivos $A$ e $B$

$A$ contém essas 3 linhas:

$A_{1}=a$

$A_{2}=b$

$A_{3}=c$

E $B$ contém essas outras 3:

$B_{1}=a$

$B_{2}=c$

$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.

Complexidade

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