Algoritmos de busca aproximada

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (401 palavras )
  • Download(s) : 0
  • Publicado : 7 de abril de 2012
Ler documento completo
Amostra do texto
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 comobiologia, 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 é umacondiçã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çãodinâ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 algoritmoconstró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 deque 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 representemerros.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 ocasamento 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 formamuito 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...
tracking img