AED3 12 07 Casamento de padrões por Aho Corasick

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2019

----------------------
O algoritmo de casamento de padrões de Aho-Corasick é um algoritmo que tenta localizar vários padrões em um documento passando apenas uma vez por esse documento.
----------------------

Em 1975, Alfred V. Aho e Margaret J. Corasick elaboraram uma variação do algoritmo de casamento de padrões KMP, que permite a busca simultânea de um determinado conjunto de padrões em um conjunto de dados. A ideia era ajustar a ideia da máquina de estados na busca para que fosse possível se buscar vários padrões sem ter que passar pelo documento várias vezes — independentemente da quantidade de padrões que fossem buscados. A solução proposta por eles é baseada em uma árvore TRIE e você pode ver como tudo funciona no vídeo.

O algoritmo de Aho-Corasick é apenas um representante da categoria de algoritmos de casamento de conjuntos. Outros exemplos são Commentz-Walter, Set-BOM e Rabin-Karp. Mas o algoritmo que acabamos de ver é suficiente parra dar uma ideia dessa possibilidade de busca simultânea de vários padrões.

E que tal experimentar usá-lo nas suas próprias buscas? Faça isso por meio de dessas visualizações:

Visualização do Jovi Huang - http://jovilab.sinaapp.com/visualizat...

Visualização do Christoph Walcher - https://wiomoc.de/aho-corasick-viz/