Algoritmo de Aho-Corasick

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde abril de 2013)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

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 O(nc * np), onde nc é o número de palavras chaves e np é o número de palavras.

Referências[editar | editar código-fonte]

  • Aho, Alfred V.; Margaret J. Corasick (June 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.)
Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.