Resenha do Artigo: “Theoretical Analysis of Edit Distance Algorithms”

Resenha de Artigo: “Theoretical Analysis of Edit Distance Algorithms”, de autoria de Paul Medvedev

por João Pedro Ramires Esteves, em 6 de agosto de 2024

O problema da distância de edição é um clássico da Ciência da Computação, e nesse artigo o autor Paul Medvedev busca responder o questionamento se os algoritmos usados para resolvê-lo atingiram apropriadamente seus objetivos. Assim, o artigo traz à tona discussões sobre a interação dos campos práticos e teórico da Computação, tomando por base o problema que perpassa pelos corretores de texto e se estende até a áreas como Bioinformática.

Sendo assim, a abordagem utilizada por Medvedev baseia-se em comparar as avaliações dadas pelas análises teóricas de algoritmos de distância (de palavras, strings), para assim avaliar quão bem sucedidas são as implementações práticas. Ele também enfatiza que será abordada apenas a versão mais simples do problema: palavras de tamanho igual e sobre um alfabeto de tamanho constante. Ademais, os algoritmos analisados apenas retornam a “distância” entre as palavras. O autor dá então uma delineação de como será o estudo. Primeiro os algoritmos estado da arte serão sumarizados, e então diferentes tipos de análise teórica serão comparados, e por fim serão discutidos problemas em aberto, juntamente com potenciais soluções.

Em seguida, Paul lista os três principais algoritmos largamente utilizados, sendo eles Needleman-Wunsch, Doubling banded alignment (uma otimização do anterior), e a técnica bit-paralelo de Myers (empregada a nível de hardware). Todos esses se baseiam em programação dinâmica 2D, onde é utilizada uma matriz de prefixos entre duas palavras, solução muito utilizada em cursos de algoritmos para introduzir e exemplificar a técnica. Em relação às bibliotecas (de código) que devidamente os implementam, o autor cita Edlib, SeqAn e Parasail, as duas primeiras empregando Myers e a última se utilizando de técnicas de alto processamento como SIMD (Single Instruction, Multiple Data), multithreading e produção de código de máquina específico para a arquitetura do processador-alvo.

Comparando os tempos desenvolvidos pelos algoritmos - testados em cadeias longas de DNA - com o que foi previsto teoricamente, o autor afirma que houve o casamento da prática com teoria, apesar de ressaltar que, em aplicações que chamam as funções de distância milhões de vezes, eles ainda podem ser um gargalo de performance. Em sequência, são ilustradas análises teóricas de diferentes tipos: pior caso, pior caso parametrizado pela distância, pior caso parametrizado por entropia e compressibilidade, caso médio, e por fim modelos aleatórios.

Na análise de pior caso, surgem dois candidatos, o supracitado algoritmo de Needleman-Wunsch e sua otimização chamada de Four-Russians. Para o primeiro, o autor considera que a análise teórica obteve sucesso já que implementações difundidas o utilizam como pilar principal ou como sub rotina, pois sua performance foi garantida - mesmo que quadraticamente -, motivando otimizações. Quanto ao segundo, por conta dessas mesmas otimizações, a suposta melhoria teórica não teve um grande impacto, levando à não utilização da abordagem dos quatro russos. Sendo assim, Medvedev conclui que a análise "nos desviou" da aplicação prática eficiente. Porém, no que tange a predição da performance (ao invés da aplicabilidade), a teoria conseguiu prever bem o tempo dos algoritmos, e a seção conclui dizendo que a análise de pior caso tem barreiras, e novos algoritmos podem surgir caso sejam empregadas visões diferentes ao lidar com o problema.

Para a análise de pior caso parametrizada pela distância, tomamos por base o tempo não só em relação ao tamanho das palavras, mas também em distância. Nessa vertente, o principal algoritmo é doubling banded alignment (alinhamento em faixas duplicante), de fácil implementação e presente na Edlib. Sua análise teórica prevê avanços significativos, como sub-quadraticidade e tempos menores para inputs pequenos, refletidos empiricamente, sendo o algoritmo usado extensivamente nessa biblioteca, que é a mais performática. A única desvantagem é que quando quando k = Θ(n), o algoritmo é quadrático (também refletido na prática). Isto tem impactos negativos pois, geralmente, tende a ser o caso que conforme crescem as palavras, também cresce a distância entre elas. No caso da biocomputação, cenário explorado pelo artigo, os dados são genomas, então as entradas crescem aceleradamente. Porém, tirando esse empecilho, o doubling banded alignment viu grande sucesso, tanto na teoria quanto na prática. Paul também descreve uma parametrização por entropia e compressão, porém como são abordagens que requeririam um código mais complexo, não há implementações, tornando assim impossível a avaliação.

Nas duas últimas análises de desempenho, as métricas utilizadas foram caso médio e modelos semi-aleatórios. Para ambas, também não foi possível estabelecer uma comparação teórico-prática, já que ainda não existem implementações de algoritmos que tenham por design partir dessas bases. Como nota, porém, o autor deixa notado que uma análise com contexto (no sentido de apossar de conhecimento de domínio - sequências de DNA) parece promissora porque há uma certa facilidade de produzir o código, mesmo que seja algo ainda não feito.

Finalmente, a conclusão discute alguns problemas em aberto e possíveis soluções para eles. Nominalmente, achar soluções lineares, usar de mais contexto do domínio biológico do problema estudado, a junção da produção de código e medição de performance no mesmo processo, além do caso geral, repetir o mesmo estudo mas com problemas diferentes. Também é exposto que o artigo foi inspirado em uma série de aulas ministradas em 2014 por Tim Roughgarden, intitulada “Beyond the Worst-Case Analysis of Algorithms” (disponível no YouTube).