Qual algoritmo de pesquisa de string é realmente o mais rápido?

Depende do tipo de pesquisa que você deseja realizar. Cada um dos algoritmos tem um desempenho particularmente bom para certos tipos de pesquisa, mas você não especificou o contexto de suas pesquisas.

Aqui estão algumas idéias típicas sobre os tipos de pesquisa:

• Boyer-Moore: trabalha pré-analisando o padrão e comparando da direita para a esquerda. Se ocorrer uma incompatibilidade, a análise inicial é usada para determinar até que ponto o padrão pode ser deslocado w.r.t. o texto que está sendo pesquisado. Isso funciona particularmente bem para padrões de pesquisa longos. Em particular, pode ser sublinear, pois você não precisa ler todos os caracteres do seu texto.

• Knuth-Morris-Pratt: também pré-analisa o padrão , mas tenta reutilizar o que já foi correspondido na parte inicial do padrão para evitar ter que fazer uma nova correspondência. Isso pode funcionar muito bem, se o seu alfabeto for pequeno (por exemplo, bases de DNA), pois você tem uma chance maior de que seus padrões de pesquisa contenham subpadrões reutilizáveis.

• Aho- Corasick: Precisa de muito pré-processamento, mas para vários padrões. Se você sabe que procurará os mesmos padrões de pesquisa repetidamente, isso é muito melhor do que o outro, porque você precisa analisar os padrões apenas uma vez, não uma vez por pesquisa.

Portanto, como de costume no CS, não há uma resposta definitiva para o melhor geral . É mais uma questão de escolher a ferramenta certa para o trabalho em questão.

Outra observação sobre o seu raciocínio de pior caso: considere os tipos de pesquisas necessárias para criar esse pior caso e pense cuidadosamente se estes são realmente relevantes no seu caso. Por exemplo, a O(mn) complexidade de pior caso do algoritmo de Boyer-Moore deriva de um padrão de pesquisa e um texto em que cada um usa apenas um caractere (como encontrar aaa em aaaaaaaaaaaaaaaaaaaaa) – você realmente precisa ser rápido para pesquisas como essa?

Comentários

• Eu tenho todo o alfabeto inglês para usar e atualizei a pergunta, desculpe por não começar com isso no início.
• E sim, eu preciso ser rápido mesmo para pesquisas como que
• você pode, por favor, eloborar no algoritmo Z ‘ se manachar também?

Embora eu esteja um pouco atrasado para responder a essa pergunta, acho que Z-Algorithm é muito mais rápido do que qualquer um de seus equivalentes.Sua complexidade de pior caso é O (m + n) e não requer pré-processamento do padrão / texto. Também é muito fácil codificar em comparação com outros algoritmos.

Funciona da seguinte maneira.

Por exemplo, existe uma string S ="abaaba". Devemos encontrar z(i) valores para i=0 to len(S)-1. Antes de entrar na explicação, deixe-me colocar algumas definições primeiro.

z(i) = no. de caracteres do prefixo de S que corresponde ao prefixo de s(i).

s(i) = ith sufixo de S.

A seguir estão os s(i) valores para s = "abaaba".

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

Os valores z são respectivamente

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

Para entender os detalhes do algoritmo, consulte os links a seguir.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Agora é necessário O (N) para encontrar todos os valores z sem qualquer sobrecarga de pré-processamento. Alguém poderia estar se perguntando agora como você pode usar essa lógica para combinar o padrão em uma determinada string?

Vejamos com um exemplo. Padrão (P): aba, Texto (T): aacbabcabaad.

Coloque no formato P $ T. ($ – qualquer caractere que não apareça no padrão ou no texto. Chegarei à importância de $ daqui a pouco.)

P$T = aba$aacbabcabaad

Nós sabemos len(P) = 3.

Todos os valores z de P$T são

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

Agora que z(i) = len(P). Ans = 11. Portanto, nosso padrão está presente em Ans-len(P)-1 = 7. -1 é para $ caractere.

Agora, por que $ ou qualquer personagem especial é importante. Considere P = "aaa" e T = "aaaaaaa". Sem o caractere especial, todos os z(i) terão valores incrementais. Ainda é possível encontrar a posição do padrão no texto com as fórmulas abaixo:

Condição: z(i)> = len(P) e posição: Ans-len(P). Mas a condição, neste caso, torna-se um pouco complicada e confusa. Eu pessoalmente prefiro usar a técnica de caracteres especiais.

Comentários

• Você poderia explicar você mesmo aqui? Ter links para sites externos pode ser usado para elaborar, mas o núcleo de uma resposta deve estar na própria resposta, em vez de seguir um link para outro site.
• O algoritmo z é basicamente o mesmo que kmp. Duvido que seja muito mais rápido.
• Concordo com @ThomasAhle. Computação z é pré-processamento. No entanto, ‘ é uma boa explicação. Eu propus uma O(n) maneira de converter do pré-processamento KMP para o pré-processamento Z, devido a esta resposta. Aqui

Use memória endereçável de conteúdo , implementada em software na forma de endereçamento virtual (apontando letras para letras).

É meio supérfluo para um algoritmo de correspondência de string médio.

O CAM pode combinar um grande número de padrões simultaneamente, até cerca de 128 padrões de letras (se forem ASCII; se forem Unicode, apenas 64). E é uma chamada por comprimento de letra na string que você deseja corresponder e uma leitura aleatória da memória por comprimento do comprimento máximo do padrão. Portanto, se você estivesse analisando uma string de 100.000 letras, com até 90.000.000 de padrões simultaneamente (o que levaria cerca de 128 GiB para armazenar uma contagem de padrões tão grande), seriam necessárias 12.800.000 leituras aleatórias da RAM, de modo que aconteceria em 1 ms.

Veja como funciona o endereçamento virtual.

Se eu começar com 256 endereços iniciais, que representam a primeira letra, essas letras apontarão para 256 das próximas letras. Se for um padrão é inexistente, você não o armazena.

Então, se eu continuar vinculando letras a letras, é como ter 128 fatias de endereçamento virtual apontando para endereçamento virtual.

Isso vai trabalhe — mas para chegar a 900.000.000 de padrões correspondentes simultaneamente, há um último truque para adicionar a isso — e está aproveitando do fato de que você começa com muita reutilização desses buffers de letras, mas depois se espalha.Se você listar o conteúdo, em vez de alocar todos os 256 caracteres, ele diminuirá muito pouco e você “obterá um aumento de capacidade de 100 vezes, porque basicamente você terá apenas 1 letra usada em cada buffer de ponteiro de letra (que eu apelidei de” escape “).

Se você quiser obter uma correspondência de string do vizinho mais próximo, terá muitos deles em execução em paralelo e os coletará em uma hierarquia, de modo que espalhará seu erro imparcialmente. vizinho mais próximo com apenas um, então você “se inclina para o início da árvore.

Comentários

• @MagnusRobertCarlWoot, visto que você tem o mesmo gavatar como roucer81, ou é uma coincidência astronômica de colisão de código hash ou você tem o mesmo endereço de e-mail. Se você é a mesma pessoa responsável por ambas as contas, deve usar o formulário de ” entre em contato ” para combiná-los e obter o devido crédito por a reputação obtida por meio de votos positivos nesta resposta.