Qual é o algoritmo de busca de subcadeia mais rápido?

OK, então eu não pareço um idiota, vou declarar o problema / requisitos mais explicitamente:

  • Agulha (padrão) e palheiro (texto a pesquisar) são sequências com terminação nula de estilo C. Nenhuma informação de comprimento é fornecida; se necessário, deve ser calculado.
  • A function deve retornar um ponteiro para a primeira correspondência ou NULL se nenhuma correspondência for encontrada.
  • Casos de falha não são permitidos. Isso significa que qualquer algoritmo com requisitos de armazenamento não constante (ou grande constante) precisará ter um caso de fallback para falha de alocação (e o desempenho no atendimento de fallback, portanto, contribui para o desempenho de pior caso).
  • A implementação deve ser em C, embora uma boa descrição do algoritmo (ou link para tal) sem código também seja boa.

… bem como o que quero dizer com “mais rápido”:

  • Determinístico O(n) onde n = comprimento do palheiro. (Mas pode ser possível usar idéias de algoritmos que são normalmente O(nm) (por exemplo, rolling haha) se eles são combinados com um algoritmo mais robusto para dar resultados O(n) ).
  • Nunca executa (mensuravelmente; alguns relógios para if (!needle[1]) etc. estão bem) pior que o algoritmo de força bruta ingênua, especialmente em agulhas muito curtas que são provavelmente o caso mais comum. (A sobrecarga de pré-processamento pesado incondicional é ruim, como está tentando melhorar o coeficiente linear de agulhas patológicas à custa de agulhas prováveis.)
  • Dada uma agulha arbitrária e palheiro, desempenho comparável ou melhor (não pior que 50% do tempo de busca) versus qualquer outro algoritmo amplamente implementado.
  • Além dessas condições, estou deixando a definição de “mais rápido” em aberto. Uma boa resposta deve explicar por que você considera a abordagem que está sugerindo como “mais rápida”.

Minha implementação atual é executada aproximadamente entre 10% mais lenta e 8 vezes mais rápida (dependendo da input) do que a implementação da Two-Way da glibc.

Atualização: Meu algoritmo ótimo atual é o seguinte:

  • Para agulhas de comprimento 1, use strchr .
  • Para agulhas de comprimento 2-4, use palavras de máquina para comparar de 2 a 4 bytes de uma só vez da seguinte forma: Pré-carregue a agulha em um inteiro de 16 ou 32 bits com bitshift e em bytes de saída de ciclo / bytes novos a partir do palheiro em cada iteração . Cada byte do palheiro é lido exatamente uma vez e recebe um cheque contra 0 (fim da string) e uma comparação de 16 ou 32 bits.
  • Para agulhas de comprimento> 4, use o algoritmo bidirecional com uma tabela de deslocamento ruim (como Boyer-Moore), que é aplicada somente ao último byte da janela. Para evitar a sobrecarga de inicializar uma tabela de 1kb, que seria uma perda líquida para muitas agulhas de comprimento moderado, mantenho um array de 32 bits marcando quais inputs na tabela de turnos foram inicializadas. Bits não ajustados correspondem a valores de byte que nunca aparecem na agulha, para os quais é possível um deslocamento de comprimento total da agulha.

As grandes questões que restam em minha mente são:

  • Existe uma maneira de fazer melhor uso da tabela de mudanças ruins? O Boyer-Moore faz o melhor uso dele digitalizando de trás para frente (da direita para a esquerda), mas o Two-Way requer uma varredura da esquerda para a direita.
  • Os dois únicos algoritmos candidatos viáveis ​​que encontrei para o caso geral (sem condições de falta de memory ou de desempenho quadrático) são Two-Way e String Matching on Ordered Alphabets . Mas há casos facilmente detectáveis ​​em que algoritmos diferentes seriam ótimos? Certamente muitos dos algoritmos O(m) (onde m é o comprimento da agulha) no espaço poderiam ser usados ​​para m<100 ou mais. Também seria possível usar algoritmos que são o pior caso de quadrática se houver um teste fácil para agulhas que provavelmente exigem apenas tempo linear.

Pontos de bônus para:

  • Você pode melhorar o desempenho assumindo que a agulha e o palheiro são ambos UTF-8 bem formados? (Com caracteres de comprimentos variados de bytes, o bem-formado impõe alguns requisitos de alinhamento de cordas entre a agulha e o palheiro e permite turnos automáticos de 2-4 bytes quando é encontrado um byte principal incompatível. Mas essas restrições o compram muito / qualquer coisa além do que cálculos de sufixo máximo, bons deslocamentos de sufixo, etc. já fornecem vários algoritmos?)

Nota: Estou bem ciente da maioria dos algoritmos por aí, não apenas como eles se saem bem na prática. Aqui está uma boa referência para que as pessoas não continuem me dando referências sobre algoritmos como comentários / respostas: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Construa uma biblioteca de testes de prováveis ​​agulhas e palheiros. Faça o perfil dos testes em vários algoritmos de pesquisa, incluindo a força bruta. Escolha aquele que apresenta melhor desempenho com seus dados.

Boyer-Moore usa uma tabela de maus caracteres com uma boa tabela de sufixos.

Boyer-Moore-Horspool usa uma tabela de caracteres ruins.

Knuth-Morris-Pratt usa uma tabela de correspondência parcial.

Rabin-Karp usa hashes em execução.

Todos eles trocam despesas gerais por comparações reduzidas em um grau diferente, então o desempenho no mundo real dependerá do comprimento médio da agulha e do palheiro. Quanto mais sobrecarga inicial, melhor com inputs mais longas. Com agulhas muito curtas, a força bruta pode vencer.

Editar:

Um algoritmo diferente pode ser melhor para encontrar pares de bases, frases em inglês ou palavras isoladas. Se houvesse um melhor algoritmo para todas as inputs, ele teria sido divulgado.

Pense na seguinte pequena mesa. Cada ponto de interrogação pode ter um melhor algoritmo de pesquisa.

  short needle long needle short haystack ? ? long haystack ? ? 

Este deve ser realmente um gráfico, com um intervalo de inputs mais curtas para mais longas em cada eixo. Se você plotasse cada algoritmo em tal gráfico, cada um teria uma assinatura diferente. Alguns algoritmos sofrem com muita repetição no padrão, o que pode afetar usos como procurar por genes. Alguns outros fatores que afetam o desempenho geral estão procurando o mesmo padrão mais de uma vez e procurando padrões diferentes ao mesmo tempo.

Se eu precisasse de um conjunto de amostras, acho que eu iria raspar um site como o google ou wikipedia, em seguida, tira o html de todas as páginas de resultados. Para um site de pesquisa, digite uma palavra e use uma das frases de pesquisa sugeridas. Escolha alguns idiomas diferentes, se aplicável. Usando páginas da web, todos os textos seriam de curto a médio, então mescle páginas suficientes para obter textos mais longos. Você também pode encontrar livros de domínio público, registros legais e outros grandes corpos de texto. Ou apenas gere um conteúdo random escolhendo palavras de um dictionary. Mas o objective da criação de perfil é testar o tipo de conteúdo que você pesquisará, portanto, use amostras do mundo real, se possível.

Eu deixei vago curto e longo. Para a agulha, penso em curto como abaixo de 8 caracteres, médio, com menos de 64 caracteres e por menos de 1k. Para o palheiro, eu penso de curto como abaixo de 2 ^ 10, meio como sob um 2 ^ 20, e longo como até um 2 ^ 30 caracteres.

O http://www-igm.univ-mlv.fr/~lecroq/string/index.html link para o qual você aponta é uma excelente fonte e resumo de alguns dos algoritmos de correspondência de sequências mais conhecidos e pesquisados.

As soluções para a maioria dos problemas de busca envolvem trocas com relação a sobrecarga de pré-processamento, requisitos de tempo e espaço. Nenhum algoritmo único será ideal ou prático em todos os casos.

Se o seu objective é projetar um algoritmo específico para busca de string, então ignore o resto do que eu tenho a dizer, se você quiser desenvolver uma rotina de serviço de busca de string generalizada, então tente o seguinte:

Passe algum tempo analisando os pontos fortes e fracos específicos dos algoritmos que você já referenciou. Realize a revisão com o objective de encontrar um conjunto de algoritmos que cubra o intervalo e o escopo das pesquisas de cadeias nas quais você está interessado. Em seguida, construa um seletor de pesquisa front-end com base em uma function classificadora para direcionar o melhor algoritmo para as inputs fornecidas. Desta forma você pode empregar o algoritmo mais eficiente para fazer o trabalho. Isso é particularmente eficaz quando um algoritmo é muito bom para determinadas pesquisas, mas degrada mal. Por exemplo, a força bruta é provavelmente a melhor para agulhas de comprimento 1, mas rapidamente se degrada à medida que o comprimento da agulha aumenta, e o algoritmo sustik-moore pode se tornar mais eficiente (em pequenos alfabetos), então para agulhas mais longas e alfabetos maiores, o KMP ou Boyer Algoritmos -More podem ser melhores. Estes são apenas exemplos para ilustrar uma possível estratégia.

A abordagem do algoritmo múltiplo não é uma ideia nova. Acredito que tenha sido empregado por alguns pacotes comerciais de sorting / pesquisa (por exemplo, SYNCSORT normalmente usado em mainframes implementa vários algoritmos de sorting e usa heurística para escolher o “melhor” para as inputs fornecidas)

Cada algoritmo de busca vem em diversas variações que podem fazer diferenças significativas em seu desempenho, como, por exemplo, este artigo ilustra.

Avalie seu serviço para categorizar as áreas em que são necessárias estratégias de pesquisa adicionais ou para ajustar com mais eficiência a function do seletor. Essa abordagem não é rápida ou fácil, mas, se bem feita, pode produzir resultados muito bons.

Publicado em 2011, acredito que pode muito bem ser o algoritmo “Correspondência simples em tempo-real de espaço-constante” de Dany Breslauer, Roberto Grossi e Filippo Mignosi.

Atualizar:

Em 2014, os autores publicaram este aprimoramento: Em busca da correspondência ideal de cordões compactados .

Fiquei surpreso ao ver nosso relatório de tecnologia citado nesta discussão; Eu sou um dos autores do algoritmo que foi chamado Sustik-Moore acima. (Nós não usamos esse termo em nosso trabalho.)

Eu queria aqui enfatizar que, para mim, a característica mais interessante do algoritmo é que é muito simples provar que cada letra é examinada no máximo uma vez. Nas primeiras versões de Boyer-Moore, eles provaram que cada letra é examinada no máximo 3 e mais tarde 2 vezes no máximo, e essas provas estavam mais envolvidas (ver cita no papel). Portanto, também vejo um valor didático em apresentar / estudar essa variante.

No artigo, também descrevemos outras variações voltadas para a eficiência, enquanto relaxamos as garantias teóricas. É um artigo curto e o material deve ser compreensível para um graduado médio em minha opinião.

Nosso principal objective foi trazer esta versão para a atenção de outras pessoas que podem melhorar ainda mais isso. A busca de cordas tem tantas variações e nós, sozinhos, não podemos pensar em tudo onde essa ideia poderia trazer benefícios. (Corrigido texto e mudança de padrão, padrão fixo de texto diferente, pré-processamento possível / não possível, execução paralela, encontrar subconjuntos correspondentes em textos grandes, permitir erros, perto de correspondências etc., etc.)

O algoritmo de pesquisa de substring mais rápido dependerá do contexto:

  1. o tamanho do alfabeto (por exemplo, DNA vs Inglês)
  2. o comprimento da agulha

O artigo de 2010 “O problema exato da correspondência de cordas: uma avaliação experimental abrangente” fornece tabelas com tempos de execução para 51 algoritmos (com diferentes tamanhos de alfabeto e comprimentos de agulha), para que você possa escolher o melhor algoritmo para o seu contexto.

Todos esses algoritmos possuem implementações C, bem como um conjunto de testes, aqui:

http://www.dmi.unict.it/~faro/smart/algorithms.php

Uma boa pergunta. Apenas adicione alguns pequenos pedaços …

  1. Alguém estava falando sobre correspondência de seqüência de DNA. Mas para a sequência de DNA, o que normalmente fazemos é construir uma estrutura de dados (por exemplo, matriz de sufixo, tree de sufixo ou índice FM) para o palheiro e combinar muitas agulhas contra ele. Esta é uma questão diferente.

  2. Seria ótimo se alguém quisesse comparar vários algoritmos. Existem benchmarks muito bons em compression e na construção de arrays de sufixos, mas eu não vi um benchmark sobre correspondência de strings. Potenciais palheiros candidatos poderiam ser do benchmark SACA .

  3. Alguns dias atrás eu estava testando a implementação Boyer-Moore da página que você recomendou (EDIT: eu preciso de uma chamada de function como memmem (), mas não é uma function padrão, então eu decidi implementá-lo). Meu programa de benchmarking usa palheiro random. Parece que a implementação do Boyer-Moore naquela página é mais rápida que o memmem da glibc () e o strnstr () do Mac. Caso você esteja interessado, a implementação está aqui e o código de benchmarking está aqui . Este definitivamente não é um benchmark realista, mas é um começo.

Eu sei que é uma questão antiga, mas a maioria das tabelas de mudança ruins são de caráter único. Se fizer sentido para o seu dataset (por exemplo, especialmente se forem palavras escritas), e se você tiver o espaço disponível, poderá obter uma aceleração dramática usando uma tabela de mudança ruim feita de n-gramas em vez de caracteres únicos.

Aqui está a implementação de pesquisa do Python , usada em todo o núcleo. Os comentários indicam que usa uma tabela boyer-moore delta 1 comprimida .

Fiz algumas experiências bastante extensas com a pesquisa de strings, mas foi para várias strings de pesquisa. As implementações de assembly do Horspool e do Bitap podem freqüentemente se manter contra algoritmos como o Aho-Corasick para baixas contagens de padrões.

Um algoritmo mais rápido “Procurar por um único caractere correspondente” (ala strchr ).

Anotações importantes:

  • Essas funções usam um “número / contagem de (zeros iniciais)” compilador gcc intrinsic- __builtin_ctz . Essas funções provavelmente só serão rápidas em máquinas que tenham instruções que executem essa operação (por exemplo, x86, ppc, arm).

  • Essas funções assumem que a arquitetura de destino pode executar cargas não alinhadas de 32 e 64 bits. Se a sua arquitetura de destino não suportar isso, você precisará adicionar alguma lógica de boot para alinhar corretamente as leituras.

  • Essas funções são neutras ao processador. Se a CPU de destino tiver instruções de vetor, você poderá fazer (muito) melhor. Por exemplo, a function strlen abaixo usa SSE3 e pode ser modificada trivialmente para XOR os bytes verificados para procurar um byte diferente de 0 . Benchmarks realizados em um laptop Core 2 de 2,66 GHz executando o Mac OS X 10.6 (x86_64):

    • 843,433 MB / s para strchr
    • 2656,742 MB / s para findFirstByte64
    • 13094,479 MB / s para strlen

… uma versão de 32 bits:

 #ifdef __BIG_ENDIAN__ #define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u) ? 0 : (__builtin_clz(_x) >> 3) + 1; }) #else #define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (__builtin_ctz(_x) + 1) >> 3; }) #endif unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) { uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8); byteMask32 |= byteMask32 << 16; while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; } return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1)); } 

... e uma versão de 64 bits:

 #ifdef __BIG_ENDIAN__ #define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; }) #else #define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (__builtin_ctzll(_x) + 1) >> 3; }) #endif unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) { uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8); byteMask64 |= byteMask64 << 16; byteMask64 |= byteMask64 << 32; while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; } return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1)); } 

Edit 2011/06/04 O OP assinala nos comentários que esta solução tem um "bug intransponível":

Ele pode ler além do byte desejado ou do terminador nulo, que pode acessar uma página ou página não mapeada sem permissão de leitura. Você simplesmente não pode usar leituras grandes em funções de string a menos que estejam alinhadas.

Isso é tecnicamente verdadeiro, mas se aplica a praticamente qualquer algoritmo que opera em blocos maiores que um único byte, incluindo o método sugerido pelo OP nos comentários:

Uma implementação típica do strchr não é ingênua, mas um pouco mais eficiente do que a que você deu. Veja o final disso para o algoritmo mais usado: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Também não tem nada a ver com o alinhamento per se. É verdade que isso poderia causar o comportamento discutido na maioria das arquiteturas comuns em uso, mas isso tem mais a ver com detalhes de implementação de microarquitetura - se a leitura desalinhada ultrapassar um limite de 4K (novamente, típico), essa leitura causará um programa falha de terminação se o próximo limite de página 4K não for mapeado.

Mas isso não é um "bug" no algoritmo dado na resposta - esse comportamento é porque funções como strchr e strlen não aceitam um argumento de length para vincular o tamanho da pesquisa. Pesquisando char bytes[1] = {0x55}; , que para os propósitos de nossa discussão, por acaso, é colocado no final de um limite de página de VM de 4K e a próxima página não é mapeada, com strchr(bytes, 0xAA) (onde strchr é um byte por vez implementação) irá falhar exactamente da mesma forma. Idem para primo strchr relacionado strlen .

Sem um argumento length , não há como saber quando você deve sair do algoritmo de alta velocidade e voltar para um algoritmo byte a byte. Um "bug" muito mais provável seria ler "passado o tamanho da alocação", o que tecnicamente resulta em undefined behavior acordo com os vários padrões da linguagem C, e seria sinalizado como um erro por algo como valgrind .

Em resumo, qualquer coisa que opere em trechos maiores que o byte para ir mais rápido, como o código de respostas faz e o código apontado pelo OP, mas deve ter semântica de leitura precisa de byte, provavelmente será "buggy" se não houver argumento de length para controlar o (s) canto (s) da "última leitura".

O código nesta resposta é um kernel para ser capaz de encontrar rapidamente o primeiro byte em um pedaço de tamanho de palavra de CPU natural se a CPU de destino tiver uma instrução rápida como ctz . É trivial adicionar coisas como certificar-se de que ele opera apenas em limites naturais corretamente alinhados, ou alguma forma de length limitado, o que permitiria que você alternasse para fora do kernel de alta velocidade e em uma verificação de byte a byte mais lenta.

O OP também afirma nos comentários:

Quanto à otimização do seu ctz, isso só faz diferença para a operação da cauda do O (1). Ele poderia melhorar o desempenho com strings minúsculas (por exemplo, strchr("abc", 'a'); mas certamente não com strings de qualquer tamanho maior.

O fato de essa afirmação ser ou não verdadeira depende muito da microarquitetura em questão. Usando o modelo de canalização RISC de 4 estágios canônicos, então é quase certo que seja verdade. Mas é extremamente difícil dizer se isso é verdade para um processador escalar super escalonado, em que a velocidade do núcleo pode reduzir a velocidade de streaming da memory. Nesse caso, não é apenas plausível, mas bastante comum, pois existe uma grande lacuna no "número de instruções que podem ser retiradas" em relação ao "número de bytes que podem ser transmitidos" para que você tenha "o número de bytes". número de instruções que podem ser retiradas para cada byte que pode ser transmitido ". Se isso for grande o suficiente, a ctz + shift pode ser feita "gratuitamente".

Basta procurar por “strstr mais rápido”, e se você ver algo de interesse é só me perguntar.

Na minha opinião, você impõe muitas restrições a si mesmo (sim, todos nós queremos lineares sub-lineares no max searcher), mas é preciso um programador real para entrar, até então eu acho que a abordagem hash é simplesmente uma solução bacana ( bem reforçado pelo BNDM para padrões mais curtos 2.166).

Apenas um exemplo rápido:

Buscando por Padrão (32bytes) em String (206908949bytes) como uma linha … Pular-Performance (maior-o-melhor): 3041%, 6801754 pular / iterações Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade performance: 3483KB / relógio

Buscando por Padrão (32bytes) em String (206908949bytes) como uma linha … Pular-Performance (maior-o-melhor): 1554%, 13307181 pular / iterações Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Desempenho de Boyer_Moore_Flensburg : 2434KB / relógio

Fazendo busca por padrão (32bytes) em String (206908949bytes) como uma linha … Skip-Performance (maior-o-melhor): 129%, 160239051 ignora / iterações Two-Way_hits / Two-Way_clocks: 0/816 Dois Desempenho -Way : 247KB / clock

Sanmayce,
Saudações

O Algoritmo de Duas Vias que você mencionou na sua pergunta (que por sinal é incrível!) Foi aprimorado recentemente para funcionar de forma eficiente em palavras de vários bytes de cada vez: Combinação de Cadeia Embalada Ótima .

Eu não li o artigo todo, mas parece que eles contam com algumas novas instruções especiais da CPU (incluídas, por exemplo, SSE 4.2) sendo O (1) para sua alegação de complexidade de tempo, mas se elas não estiverem disponíveis, elas podem simule-os no tempo O (log log w) para palavras w-bit que não parecem muito ruins.

Você poderia implementar, digamos, 4 algoritmos diferentes. Cada M minutos (a ser determinado empiricamente) executa todos os 4 nos dados reais atuais. Acumule statistics sobre N runs (também TBD). Em seguida, use apenas o vencedor pelos próximos M minutos.

Registre statistics em Vitórias para poder replace algoritmos que nunca ganham com novos. Concentre esforços de otimização na rotina mais vencedora. Preste atenção especial às statistics após qualquer alteração no hardware, database ou fonte de dados. Inclua essas informações no log de statistics, se possível, para que você não tenha que descobrir a partir da data / hora do log.

Eu recentemente descobri uma boa ferramenta para medir o desempenho dos vários algos disponíveis: http://www.dmi.unict.it/~faro/smart/index.php

Você pode achar util. Além disso, se eu tivesse que fazer uma chamada rápida no algoritmo de busca de substring, eu iria com Knuth-Morris-Pratt.

Você também pode querer ter diversos benchmarks com vários tipos de strings, pois isso pode ter um grande impacto no desempenho. Os algos executarão a diferença com base na busca da linguagem natural (e mesmo aqui ainda podem haver distinções refinadas devido às diferentes morfologías), cadeias de DNA ou cadeias aleatórias, etc.

O tamanho do alfabeto desempenhará um papel em muitos algos, assim como o tamanho da agulha. Por exemplo, o Horspool faz bem no texto em inglês, mas é ruim no DNA por causa do tamanho diferente do alfabeto, tornando a vida difícil para a regra do mau caráter. Introduzir o bom-sufixo alivia muito isso.

Use stdlib strstr :

 char *foundit = strstr(haystack, needle); 

It was very fast, only took me about 5 seconds to type.

I don’t know if it’s the absolute best, but I’ve had good experience with Boyer-Moore .