Algoritmos de busca aproximada

Trabalho: Algoritmos de Busca Aproximada

A pesquisa eficiente para solucionar o problema de pesquisa aproximada de padrões em um texto influencia o desenvolvimento de aplicações em áreas como biologia, computacional e pesquisa textual em grandes massas de dados. Mas para o tratamento de volumes de informações de magnitude envolvida nessas aplicações, o uso eficiente de tempo e espaço é uma condição essencial.
Foi desenvolvido um algoritmo de complexidade θ(kn) para o problema da pesquisa aproximada de padrões com k erros, melhorando dessa forma a complexidade da solução de programação dinâmica, onde n e m são os comprimentos do texto e do padrão, respectivamente. O algoritmo é dividido em duas fases: uma fase de pré – processamento e uma fase de iteração.Na primeira fase o algoritmo constrói uma árvore de sufixos T para as palavras P e T e processa T para que seja possível calcular o LCA de quaisquer de suas folhas em tempo O .Na fase de iteração o algoritmo usa a observação de que ocorrências do padrão no texto serão representados por caminhos ao longo das diagonais da tabela de programação dinâmica intercalados com trechos na vertical,horizontal e diagonais que representem erros.Assim o algoritmo percorre as diagonais da tabela de programação dinâmica fazendo saltos em tempo constante ao longo das diagonais, e o comprimento de cada salto é calculado a partir do LCA na árvore de sufixos de suas folhas correspondentes aos sufixos envolvidos de P e T.

Shift –And-Aproximado
Esse algoritmo simula de forma interessante um Non-Deterministic DFA, limitado para fazer o casamento de padrões em texto.Seu grande atrativo é que com pouquíssimas alterações é possível fazer buscas aproximadas.Ele utiliza o paralelismo de bits das palavras de um computador , de forma muito engenhosa, tanto para representar as transições possíveis entre estados como para representar o próprio estado do autômato.

Boyer-Moore-Horspool
Esse algoritmo é bem parecido ao de força