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

Estou preso há algum tempo no qual é o algoritmo de pesquisa de string mais rápido, ouvi muitas opiniões, mas no final não tenho certeza.

Ouvi algumas pessoas dizendo que o algoritmo mais rápido é Boyer-Moore e outras dizendo que Knuth-Morris-Pratt é realmente mais rápido.

Eu procurei pela complexidade de ambos, mas eles geralmente parecem iguais O(n+m). Descobri que, no pior cenário, Boyer-Moore tem uma O(nm)complexidade em comparação com Knuth-Morris-Pratt, que possui O (m + 2 * n). Onde n = comprimento do texto em = comprimento do padrão.

Até onde eu sei, Boyer-Moore tem um pior caso linear se eu usasse a Regra de Galil.

Minha pergunta: Sobre tudo o que é realmente o algoritmo de busca de String mais rápido (Esta pergunta inclui todos os algoritmos de picada possíveis, não apenas Boyer-Moore e Knuth-Morris-Pratt).

Edit: Devido a esta resposta

O que estou procurando exatamente é:

Dado um texto Te um padrão P, tenho que encontrar todas as aparências de Pin T.

Também o comprimento de P e T é de [1,2 000 000]e o programa deve ser executado em 0,15 s.

Eu sei que o KMP e o Rabin-Karp são suficientes para obter uma pontuação de 100% no problema, mas eu queria tentar implementar o Boyer-Moore. Qual seria o melhor para esse tipo de pesquisa de padrões?

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

Aqui estão alguns pensamentos típicos 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 no texto pesquisado. Isso funciona particularmente bem para padrões de pesquisa longos. Em particular, pode ser sub-linear, 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 revendê-lo. Isso pode funcionar muito bem, se o seu alfabeto for pequeno (por exemplo, bases de DNA), pois você terá uma chance maior de que seus padrões de pesquisa contenham sub-padrões reutilizáveis.

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

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

Outra observação sobre o seu pior argumento: considere os tipos de pesquisas necessárias para criar esse pior caso e pense bem se são realmente relevantes para o seu caso. Por exemplo, a O(mn)complexidade do pior caso do algoritmo Boyer-Moore decorre de um padrão de pesquisa e um texto que cada uso apenas um caractere (como encontrar aaaem aaaaaaaaaaaaaaaaaaaaa) - você realmente precisa ser rápido para pesquisas como essa?

Embora eu esteja um pouco atrasado para responder a essa pergunta, mas acho que Z-Algorithmé muito mais rápido do que qualquer um de seus colegas. Sua pior complexidade é 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, há 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)= não. de caracteres do prefixo de Sque corresponde ao prefixo de s(i).

s(i)= ithsufixo 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 uma compreensão detalhada do algoritmo, consulte os seguintes links.

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

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

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

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

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

P$T = aba$aacbabcabaad

Nós sabemos len(P)= 3.

Todos os valores z de P$Tsã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 qual z(i)= len(P). Ans = 11.Portanto, nosso padrão está presente em Ans-len(P)-1= 7. -1é para $personagem.

Agora, por que $ou qualquer caractere especial é importante. Considere P = 'aaa'e T = 'aaaaaaa'. Sem o caractere especial, todos 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 se torna um pouco complicada e confusa. Pessoalmente, prefiro usar a técnica de caracteres especiais.

Usar 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 corresponder a um grande número de padrões simultaneamente, até cerca de 128 letras (se forem ASCII; se forem apenas Unicode 64). E é uma chamada por comprimento de letra na sequência com a qual você deseja corresponder e uma leitura aleatória da memória por comprimento do tamanho máximo do padrão. Portanto, se você estivesse analisando uma sequência de 100.000 letras, com até 90.000.000 de padrões simultaneamente (o que levaria cerca de 128 GiB para armazenar uma quantidade de padrões tão grande), seriam necessárias 12.800.000 leituras aleatórias da RAM, o que ocorreria em 1ms.

Veja como o endereçamento virtual funciona.

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

Portanto, se eu continuar ligando letras a letras, é como ter 128 fatias de endereçamento virtual apontando para endereçamento virtual.

Isso funcionará - mas para obter 900.000.000 de padrões coincidentes simultaneamente, há um último truque a ser adicionado - e está tirando vantagem do fato de você começar muito com a 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ê só recebe uma letra em cada buffer de ponteiro de letra (que eu chamei de ' escapar').

Se você deseja obter uma correspondência de string do vizinho mais próximo, você tem muitas delas em execução paralela e você coleta em uma hierarquia, para espalhar seu erro de maneira imparcial. se você tentar o vizinho mais próximo com apenas um, estará inclinado para o início da árvore.