Algoritmo de busca de strings

Na ciência da computação, os algoritmos de busca de strings, às vezes chamados de algoritmos de correspondência de strings, são uma classe importante de algoritmos de strings que tentam encontrar um local onde um ou vários strings (também chamadas de padrões) são encontradas dentro de uma string ou texto maior.

Um exemplo básico de pesquisa de strings é quando o padrão e o texto pesquisado são matrizes de elementos de um alfabeto (conjunto finito) Σ. Σ pode ser um alfabeto de linguagem humana, por exemplo, as letras A a Z e outras aplicações podem usar um alfabeto binário (Σ = {0,1}) ou um alfabeto de DNA (Σ = {A,C,G,T}) em bioinformática.

Na prática, o método viável do algoritmo de busca de strings pode ser afetado pela codificação da string. Em particular, se uma codificação de largura variável estiver em uso, então pode ser mais lento encontrar o Nésimo caractere, talvez exigindo um tempo proporcional a N. Isso pode retardar significativamente alguns algoritmos de pesquisa. Uma das muitas soluções possíveis é procurar a sequência de unidades de código, mas isso pode produzir correspondências falsas, a menos que a codificação seja especificamente projetada para evitá-la.

Visão geral

O caso mais básico de pesquisa de strings envolve uma string (geralmente muito longa), às vezes chamada de palheiro, e uma string (geralmente muito curta), às vezes chamada de agulha. O objetivo é encontrar uma ou mais ocorrências da agulha no palheiro. Por exemplo, pode-se procurar por to dentro de:

Alguns livros devem ser provados, outros a serem engolidos, e alguns poucos a serem mastigados e digeridos.

Pode-se solicitar a primeira ocorrência de "to", que é a quarta palavra; ou todas as ocorrências, das quais existem 3; ou a última, que é a quinta palavra a partir do final.

No entanto, é muito comum que várias restrições sejam adicionadas. Por exemplo, pode-se querer combinar a "agulha" somente quando consiste em uma (ou mais) palavras completas - talvez definido como não tendo outras letras imediatamente adjacentes em ambos os lados. Nesse caso, uma pesquisa por "hew" ou "baixo" deve falhar na frase de exemplo acima, mesmo que essas strings literais ocorram.

Outro exemplo comum envolve a "normalização". Para muitos propósitos, uma pesquisa por uma frase como "ser" deve ter sucesso mesmo em lugares onde há algo mais intervindo entre o "para" e o 'ser':

• Mais de um espaço
• Outros caracteres "whitespace" como abas, espaços não quebrados, quebras de linha, etc.
• Menos comumente, um hífen ou hífen macio
• Em textos estruturados, tags ou até mesmo arbitrariamente grandes mas "paticais" coisas como notas de rodapé, números de lista ou outros marcadores, imagens incorporadas, e assim por diante.

Muitos sistemas de símbolos incluem caracteres que são sinônimos (pelo menos para alguns propósitos):

• Os alfabetos baseados em latim distinguem minúsculas de minúsculas de maiúsculas, mas para muitas finalidades espera-se que a busca por cordas ignore a distinção.
• Muitas línguas incluem ligaduras, onde um personagem composto é equivalente a dois ou mais caracteres.
• Muitos sistemas de escrita envolvem marcas diacríticas, como acentos ou pontos de vogal, que podem variar em seu uso, ou ser de importância variável na correspondência.
• As sequências de DNA podem envolver segmentos não codificados que podem ser ignorados para alguns fins, ou polimorfismos que não levam a nenhuma mudança nas proteínas codificadas, o que pode não contar como uma verdadeira diferença para alguns outros propósitos.
• Algumas línguas têm regras onde um personagem diferente ou forma de caráter deve ser usado no início, no meio ou no fim das palavras.

Finalmente, para strings que representam linguagem natural, aspectos da própria linguagem são envolvidos. Por exemplo, pode-se desejar encontrar todas as ocorrências de uma "palavra" apesar de ter grafias, prefixos ou sufixos alternativos, etc.

Outro tipo de pesquisa mais complexo é a pesquisa de expressões regulares, onde o usuário constrói um padrão de caracteres ou outros símbolos, e qualquer correspondência ao padrão deve satisfazer a pesquisa. Por exemplo, para capturar a palavra do inglês americano "color" e o equivalente britânico "color", em vez de procurar por duas cadeias literais diferentes, pode-se usar uma expressão regular como:

Colou? R

onde está o "?" convencionalmente torna o caractere anterior ("u") opcional.

Este artigo discute principalmente algoritmos para tipos mais simples de pesquisa de strings.

Um problema semelhante introduzido no campo da bioinformática e genômica é o emparelhamento exato máximo (MEM). Dadas duas strings, os MEMs são substrings comuns que não podem ser estendidos para a esquerda ou para a direita sem causar incompatibilidade.

Exemplos de algoritmos de pesquisa

Pesquisa ingênua de strings

Uma maneira simples e ineficiente de ver onde uma string ocorre dentro de outra é verificar cada índice, um por um. Primeiro, vemos se existe uma cópia da agulha começando no primeiro caractere do palheiro; caso contrário, verificamos se há uma cópia da agulha começando no segundo caractere do palheiro e assim por diante. No caso normal, só precisamos olhar um ou dois caracteres para cada posição errada para ver que é uma posição errada, então, no caso médio, isso leva O(n + m) passos, onde n é o comprimento do palheiro e m é o comprimento da agulha; mas na pior das hipóteses, procurar uma string como "aaaab" em uma string como "aaaaaaaaab", leva O(nm)

Pesquisa baseada em autômatos de estados finitos

Nesta abordagem, o retrocesso é evitado através da construção de um autômato finito determinístico (DFA) que reconhece uma string de pesquisa armazenada. Eles são caros de construir – geralmente são criados usando a construção do powerset – mas são muito rápidos de usar. Por exemplo, o DFA mostrado à direita reconhece a palavra "MAMÃE". Esta abordagem é frequentemente generalizada na prática para procurar expressões regulares arbitrárias.

Esboços

Knuth–Morris–Pratt calcula um DFA que reconhece entradas com a string a ser pesquisada como um sufixo, Boyer–Moore começa a pesquisar a partir do final da agulha, de modo que geralmente pode avançar um comprimento inteiro da agulha em cada passo. Baeza–Yates monitora se os caracteres j anteriores eram um prefixo da string de pesquisa e, portanto, é adaptável à pesquisa de string difusa. O algoritmo bitap é uma aplicação do algoritmo de Baeza – Yates. abordagem.

Métodos de índice

Algoritmos de busca mais rápidos pré-processam o texto. Depois de construir um índice de substring, por exemplo, uma árvore de sufixo ou uma matriz de sufixo, as ocorrências de um padrão podem ser encontradas rapidamente. Como exemplo, uma árvore de sufixo pode ser construída em $(n)}$ tempo, e tudo $Não.$ ocorrências de um padrão podem ser encontradas em $O(m)}$ tempo sob a suposição de que o alfabeto tem um tamanho constante e todos os nós internos na árvore do sufixo sabem o que as folhas estão por baixo deles. Este último pode ser realizado executando um algoritmo DFS da raiz da árvore do sufixo.

Outras variantes

Alguns métodos de pesquisa, por exemplo, pesquisa de trigramas, têm como objetivo encontrar uma "proximidade" pontuação entre a string de pesquisa e o texto, em vez de uma "correspondência/não correspondência". Às vezes, eles são chamados de "difusos" pesquisas.

Classificação dos algoritmos de busca

Classificação por vários padrões

Os vários algoritmos podem ser classificados pelo número de padrões que cada um usa.

Algoritmos de padrão único

Na compilação a seguir, m é o comprimento do padrão, n o comprimento do texto pesquisável e k = |Σ | é o tamanho do alfabeto.

1.^ Os tempos assintóticos são expressos usando a notação O, Ω e Θ.

2.^ Usado para implementar o Eu... e funções de busca strstr nas bibliotecas padrão glibc e musl C.

3.^ Pode ser estendido para lidar com conjuntos de caracteres aproximados e (potencialmente infinitos) de padrões representados como línguas regulares.

O algoritmo de busca de strings Boyer-Moore tem sido o benchmark padrão para a literatura prática de busca de strings.

Algoritmos que usam um conjunto finito de padrões

Na compilação a seguir, M é o comprimento do padrão mais longo, m o comprimento total, n o comprimento do texto pesquisável, o o número de ocorrências.

Algoritmos usando um número infinito de padrões

Naturalmente, os padrões não podem ser enumerados finitamente neste caso. Eles são representados geralmente por uma gramática regular ou expressão regular.

Classificação pelo uso de programas de pré-processamento

Outras abordagens de classificação são possíveis. Um dos mais comuns usa o pré-processamento como critério principal.

Classificação por estratégias de correspondência

Outro classifica os algoritmos pela sua estratégia de correspondência:

• Combine o prefixo primeiro (Knuth–Morris–Pratt, Shift-And, Aho–Corasick)
• Combine o sufixo primeiro (Boyer-Moore e variantes, Commentz-Walter)
• Combine o melhor fator primeiro (BNDM, BOM, Set-BOM)
• Outras estratégias (Naïve, Rabin–Karp)