Algoritmo de Aho-Corasick
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Abril de 2013) |
O algoritmo de Aho-Corasick é um algoritmo de pesquisa em strings inventado por Alfred V. Aho e Margaret J. Corasick, ambos pesquisadores do Bell Labs, em 1975.
O objetivo do algoritmo é localizar todas as palavras chaves em textos, a partir de uma única interação, utilizando para tanto um dicionário contendo um conjunto finito de palavras chaves. A complexidade do algoritmo é linear
Uma outra abordagem para este problema, seria utilizar um Algoritmo guloso, que faria a iteração de palavra por palavra comparando com as chaves existentes no dicionário. Esta técnica não seria aplicável a grandes dicionários por ser muito lenta - complexidade , onde nc é o número de palavras chaves e np é o número de palavras.
Referências editar
- Aho, Alfred V.; Margaret J. Corasick (junho de 1975). «Efficient string matching: An aid to bibliographic search». Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855 (O acesso ao texto completo pode ser restrito.)