AED3 12 04 Casamento de padrões por Boyer Moore - Deslocamento por Caractere Ruim

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 Boyer Moore compara os símbolos do padrão com os do documento da direita para a esquerda, começando pelo último símbolo. Para determinar o deslocamento a cada teste, são empregadas duas formas de cálculo: deslocamento por caractere ruim e deslocamento por sufixo bom.
----------------------

Um dos algoritmos mais eficientes de reconhecimento exato de padrões é o algoritmo Boyer-Moore, criado em 1977 por Robert S. Boyer e J. Strother Moore. Versões simplificadas ou completas dele normalmente são implementadas nos mecanismos de localização e substituição dos softwares modernos, como os editores de texto e os navegadores.

O algoritmo busca pelos caracteres do padrão da direita para esquerda, começando pelo último caractere. No caso de uma diferença (ou casamento completo do padrão), ele usa duas regras pré-calculadas para determinar o deslocamento para a próxima comparação. Estas duas regras são chamadas de deslocamento por caractere ruim e deslocamento por sufixo bom. Assim, como o KMP, esse algoritmo tem uma fase de pré-processamento.

O algoritmo de Boyer Moore acabou se tornando um dos algoritmos de casamento de padrões mais famosos e serve como comparação para novas ideias. Quando alguém bola um algoritmo novo, ele deve ser melhor que o Boyer Moore. E isso é possível? Claro, mas em situações específicas.

O vídeo apresenta a primeira forma de cálculo de deslocamento usada no algoritmo: o deslocamento por caractere ruim.