Qual é o algoritmo de pesquisa de substring mais rápido?

165

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

  • Agulha (padrão) e palheiro (texto a ser pesquisado) são seqüências terminadas em nulo no estilo C. Nenhuma informação de comprimento é fornecida; se necessário, deve ser calculado.
  • A função deve retornar um ponteiro para a primeira correspondência, ou NULLse 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 cuidado de fallback contribui para o pior desempenho).
  • A implementação deve ser em C, embora uma boa descrição do algoritmo (ou link para tal) sem código também seja adequada.

... 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, hash rotativo) se elas forem combinadas com um algoritmo mais robusto para fornecer O(n)resultados determinísticos ).
  • Nunca apresenta desempenho (mensurável; alguns relógios if (!needle[1])são aceitáveis) pior que o algoritmo ingênuo de força bruta, especialmente em agulhas muito curtas, que provavelmente são o caso mais comum. (A sobrecarga pesada de pré-processamento incondicional é ruim, pois está tentando melhorar o coeficiente linear para agulhas patológicas às custas de prováveis ​​agulhas.)
  • Dada uma agulha e um palheiro arbitrários, desempenho comparável ou melhor (não inferior a 50% do tempo de pesquisa) em comparação com 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 sugerida como "mais rápida".

Minha implementação atual é aproximadamente 10% mais lenta e 8 vezes mais rápida (dependendo da entrada) do que a implementação de duas vias da glibc.

Atualização: Meu algoritmo ideal atual é o seguinte:

  • Para agulhas de comprimento 1, use strchr.
  • Para agulhas de comprimento 2 a 4, use palavras de máquina para comparar 2 a 4 bytes de uma vez da seguinte maneira: Pré-carregue a agulha em um número inteiro de 16 ou 32 bits com deslocamento de bits e faça o ciclo de saída de bytes antigos / novos bytes do palheiro a cada iteração . Cada byte do palheiro é lido exatamente uma vez e incorre em uma verificação contra 0 (final 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 apenas ao último byte da janela. Para evitar a sobrecarga de inicializar uma tabela de 1kb, o que seria uma perda líquida para muitas agulhas de comprimento moderado, mantenho uma matriz de bits (32 bytes) marcando quais entradas na tabela de deslocamento são inicializadas. Os bits não configurados correspondem aos valores de bytes que nunca aparecem na agulha, para os quais é possível uma mudança no comprimento total da agulha.

As grandes questões que me restam são:

  • Existe uma maneira de fazer melhor uso da tabela de turnos ruim? A Boyer-Moore faz o melhor uso possível, digitalizando para trás (da direita para a esquerda), mas o Two-Way exige uma digitalização da esquerda para a direita.
  • Os únicos dois algoritmos candidatos viáveis ​​que encontrei para o caso geral (sem condições de desempenho quadrático ou de falta de memória) são a Correspondência de duas vias e a seqüência de caracteres em alfabetos ordenados . Mas existem casos facilmente detectáveis ​​em que algoritmos diferentes seriam ótimos? Certamente muitos dos algoritmos O(m)(onde mestá o comprimento da agulha) no espaço podem ser usados ​​para m<100isso. Também seria possível usar algoritmos quadráticos, na pior das hipóteses, se houver um teste fácil para agulhas que provavelmente requer apenas tempo linear.

Pontos de bônus por:

  • Você pode melhorar o desempenho assumindo que a agulha e o palheiro são UTF-8 bem formados? (Com caracteres de tamanhos variáveis ​​de bytes, a boa formação impõe alguns requisitos de alinhamento de cordas entre a agulha e o palheiro e permite trocas automáticas de 2-4 bytes quando um byte incompatível é encontrado. Mas essas restrições compram muito / qualquer coisa além do que cálculos máximos de sufixos, boas mudanças de sufixos, etc. já oferecem vários algoritmos?)

Nota: Conheço bem a maioria dos algoritmos existentes, mas não o desempenho deles na prática. Aqui está uma boa referência para que as pessoas não continuem me fornecendo referências sobre algoritmos como comentários / respostas: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

R .. GitHub PARE DE AJUDAR O GELO
fonte
Existem vários algoritmos de busca de strings listados em Algorithms on Strings . Você pode descrever quais algoritmos você considerou nesta lista.
Greg Hewgill
61
Esse link no final é ouro!
Carlos
4
Não acredito que você ainda não aceitou uma resposta.
user541686
1
@ Mehrdad: Eu estava prestes a dizer que não há respostas que realmente abordem a pergunta, mas a sua parece. No momento em que você respondeu, eu segui em frente e deixei melhorias adicionais strstrcomo algo para mais tarde, então eu realmente não consegui ler corretamente o artigo que você vinculou, mas parece muito promissor. Obrigado e desculpe por não voltar para você.
R .. GitHub Pare de ajudar o gelo

Respostas:

37

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

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

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

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

Rabin-Karp usa hashes em execução.

Todos eles trocam custos indiretos por comparações reduzidas em um grau diferente; portanto, o desempenho no mundo real dependerá dos comprimentos médios da agulha e do palheiro. Quanto mais sobrecarga inicial, melhor com entradas 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 únicas. Se houvesse um melhor algoritmo para todas as entradas, ele teria sido divulgado.

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

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

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

Se eu precisasse de um conjunto de amostras, acho que rasparia um site como o google ou a wikipedia e retiraria 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 curtos a médios; portanto, 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 conteúdo aleatório escolhendo palavras de um dicionário. Mas o objetivo do perfil é testar o tipo de conteúdo que você estará pesquisando; portanto, use amostras do mundo real, se possível.

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

desenhado
fonte
1
Você tem boas sugestões para uma biblioteca de teste? A pergunta anterior que fiz no SO estava relacionada a isso e nunca obtive respostas reais. (exceto o meu ...) Deve ser extenso. Mesmo se a minha ideia de um pedido de strstr está à procura texto em Inglês, outra pessoa pode estar à procura de genes em sequências de pares de bases ...
R .. GitHub parar de ajudar ICE
3
É um pouco mais complicado do que curto / longo. Para a agulha, as grandes questões relevantes para o desempenho da maioria dos algoritmos são: Comprimento? Existe alguma periodicidade? A agulha contém todos os caracteres únicos (sem repetições)? Ou todo o mesmo personagem? Existe um grande número de caracteres no palheiro que nunca aparecem na agulha? Existe uma chance de ter que lidar com agulhas fornecidas por um invasor que deseja explorar o pior desempenho possível para prejudicar seu sistema? Etc ..
R .. GitHub Pare de ajudar o gelo 07/07
31

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

Atualizar:

Em 2014, os autores publicaram essa melhoria: Rumo à correspondência ideal de cadeias compactadas .

user541686
fonte
1
Uau, obrigado. Estou lendo o jornal. Se for melhor do que eu tenho, definitivamente aceitarei sua resposta.
R .. GitHub Pare de ajudar o gelo
1
@R ..: Claro! :) Falando nisso, se você conseguir implementar o algoritmo, considere publicá-lo no StackOverflow para que todos possam se beneficiar! Não encontrei nenhuma implementação em nenhum lugar e não sou bom em implementar algoritmos que encontro em trabalhos de pesquisa haha.
user541686
2
É uma variante do algoritmo "bidirecional" que já estou usando, portanto, adaptar meu código para usar isso pode ser realmente fácil. No entanto, terei que ler o artigo com mais detalhes e preciso avaliar se as alterações feitas são compatíveis com o uso de uma "tabela de caracteres incorretos" que acelera bastante o caso comum.
R .. GitHub PARE DE AJUDAR O GELO 13/08
11
E você ainda não aceitou a resposta de @ Mehrdad! :-)
lifebalance
3
@DavidWallace: O quê? Possui os títulos dos trabalhos e os autores. Mesmo se o link ficar inoperante, você poderá encontrar os papéis. O que você está esperando que eu faça, escreva pseudocódigo para o algoritmo? O que faz você pensar que eu entendo o algoritmo?
user541686
23

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

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

Se seu objetivo é projetar um algoritmo específico para pesquisa de strings, ignore o restante do que tenho a dizer: se você deseja desenvolver uma rotina de serviço de pesquisa de strings generalizada, tente o seguinte:

Passe algum tempo revisando os pontos fortes e fracos dos algoritmos que você já referenciou. Conduza a revisão com o objetivo de encontrar um conjunto de algoritmos que cubram o alcance e o escopo das pesquisas de cadeia de caracteres nas quais você está interessado. Em seguida, crie um seletor de pesquisa de front-end com base em uma função classificadora para direcionar o melhor algoritmo para as entradas fornecidas. Dessa forma, você pode empregar o algoritmo mais eficiente para fazer o trabalho. Isso é particularmente eficaz quando um algoritmo é muito bom para determinadas pesquisas, mas se degrada pouco. Por exemplo, a força bruta é provavelmente a melhor para agulhas de comprimento 1, mas se degrada rapidamente à medida que o comprimento da agulha aumenta, e o algoritmo sustik-moorepode se tornar mais eficiente (em alfabetos pequenos), então para agulhas mais longas e alfabetos maiores, os algoritmos KMP ou Boyer-Moore podem ser melhores. Estes são apenas exemplos para ilustrar uma possível estratégia.

A abordagem de algoritmos múltiplos não é uma idéia nova. Acredito que ele tenha sido empregado por alguns pacotes comerciais de classificação / pesquisa (por exemplo, o SYNCSORT geralmente usado em mainframes implementa vários algoritmos de classificação e usa heurística para escolher o "melhor" para as entradas fornecidas)

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

Faça uma avaliação comparativa do 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 função do seletor. Essa abordagem não é rápida ou fácil, mas se bem feita, pode produzir resultados muito bons.

NealB
fonte
1
Obrigado pela resposta, especialmente o link para Sustik-Moore, que eu não tinha visto antes. A abordagem de múltiplos algoritmos é certamente amplamente utilizada. O Glibc basicamente executa strchr, Bidirecional sem tabela de troca de caracteres incorreta ou Bidirecional com tabela de troca de caracteres incorreta, dependendo de se agulha_len é 1, <32 ou> 32. Minha abordagem atual é a mesma, exceto que eu sempre uso a tabela de turnos; Substituí o memset de 1kb necessário para fazê-lo por um memset de 32 bytes em um conjunto de bits usado para marcar quais elementos da tabela foram inicializados e recebo o benefício (mas não a sobrecarga), mesmo para pequenas agulhas.
R .. GitHub Pare de ajudar o gelo
1
Depois de pensar sobre isso, estou realmente curioso para saber qual é a aplicação pretendida para Sustik-Moore. Com alfabetos pequenos, você nunca consegue fazer mudanças significativas (todos os caracteres do alfabeto quase certamente aparecem perto do final da agulha) e as abordagens de autômatos finitos são muito eficientes (tabela de transição de estado pequena). Portanto, não posso imaginar nenhum cenário em que Sustik-Moore possa ser o ideal ...
R .. GitHub PARE DE AJUDAR O GELO
ótima resposta - se eu pudesse estrelar esta resposta em particular, eu o faria.
Jason S
1
@R .. A teoria por trás do algoritmo sustik-moore é que ele deve fornecer maiores quantidades médias de turno quando a agulha é relativamente grande e o alfabeto é relativamente pequeno (por exemplo, procurando sequências de DNA). Maior neste caso significa apenas maior do que o algoritmo básico de Boyer-Moore produziria com as mesmas entradas. Quanto mais eficiente isso é em relação a uma abordagem finita de autômatos ou a alguma outra variação de Boyer-Moore (das quais existem muitas) é difícil dizer. É por isso que enfatizei o tempo gasto em pesquisa dos pontos fortes / fracos de seus algoritmos candidatos.
NealB 07/07
1
Acho que fiquei preso pensando em mudanças apenas no sentido de más mudanças de caráter de Boyer-Moore. Com uma melhoria nas boas mudanças de sufixo da BM, a Sustik-Moore poderia superar as abordagens do DFA para a pesquisa de DNA. Coisa legal.
R .. GitHub Pare de ajudar o gelo
21

Fiquei surpreso ao ver nosso relatório técnico citado nesta discussão; Eu sou um dos autores do algoritmo que foi nomeado Sustik-Moore acima. (Não usamos esse termo em nosso artigo.)

Queria enfatizar aqui que, para mim, a característica mais interessante do algoritmo é que é bastante simples provar que cada letra é examinada ao mesmo tempo. Para versões anteriores de Boyer-Moore, eles provaram que cada letra é examinada no máximo 3 e depois 2 vezes no máximo, e essas provas estavam mais envolvidas (ver citações em papel). Portanto, também vejo um valor didático na apresentação / estudo dessa variante.

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

Nosso principal objetivo era chamar a atenção desta versão para outras pessoas que possam aprimorá-la ainda mais. A pesquisa de strings tem muitas variações e, por si só, não conseguimos pensar em tudo em que essa idéia poderia trazer benefícios. (Texto fixo e padrão de alteração, texto diferente de padrão fixo, pré-processamento possível / não possível, execução paralela, localizando subconjuntos correspondentes em textos grandes, permitir erros, correspondências próximas etc., etc.)

Matyas
fonte
1
Você conhece uma implementação C ou C ++ disponível? Estou pensando em usar isso para alguma pesquisa de motivo de DNA (correspondências de motivo exato). Se não, talvez eu vou tentar desenvolver uma implementação mim e submeter-se a impulsionar algoritmo
JDiMatteo
4
Com nenhuma implementação disponível conhecida, o algoritmo Sustik-Moore / 2BLOCK parece improvável de ser usado na prática e continua sendo omitido dos resultados em documentos resumidos como "O Problema de Correspondência Exata de Cordas: uma Avaliação Experimental Abrangente"
JDiMatteo
18

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 de 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 agulhas), para que você possa escolher o melhor algoritmo para o seu contexto.

Todos esses algoritmos têm implementações em C, além de um conjunto de testes aqui:

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

JDiMatteo
fonte
4

Uma pergunta muito boa. Basta adicionar alguns pedacinhos ...

  1. Alguém estava falando sobre a correspondência da sequência de DNA. Mas para a sequência de DNA, o que geralmente fazemos é construir uma estrutura de dados (por exemplo, matriz de sufixos, árvore de sufixos ou índice FM) para o palheiro e combinar muitas agulhas contra ele. Esta é uma pergunta diferente.

  2. Seria realmente ótimo se alguém gostaria de comparar vários algoritmos. Existem benchmarks muito bons na compactação e na construção de matrizes de sufixos, mas eu não vi um benchmark na correspondência de strings. Os possíveis candidatos a palheiros podem ser do benchmark da SACA .

  3. Alguns dias atrás, eu estava testando a implementação de Boyer-Moore na página que você recomendou (EDIT: preciso de uma chamada de função como memmem (), mas não é uma função padrão, por isso decidi implementá-la). Meu programa de benchmarking usa palheiro aleatório. Parece que a implementação de Boyer-Moore nessa página é vezes mais rápida que o memmem da glibc () e a strnstr do Mac (). Caso você esteja interessado, a implementação está aqui e o código de benchmarking está aqui . Definitivamente, essa não é uma referência realista, mas é um começo.

user172818
fonte
Se você tiver algumas boas agulhas para testar junto com os candidatos a palheiro do benchmark da SACA, poste-os como resposta à minha outra pergunta e, antes de obter uma resposta melhor, marcarei como aceita.
R .. GitHub Pare de ajudar o gelo
3
Sobre seu memmem e Boyer-Moore, é muito provável que Boyer-Moore (ou melhor, um dos aprimoramentos de Boyer-Moore) tenha melhor desempenho em dados aleatórios. Os dados aleatórios têm uma probabilidade extremamente baixa de periodicidade e longas correspondências parciais que levam ao pior caso quadrático. Estou procurando uma maneira de combinar Boyer-Moore e Bidirecional ou detectar com eficiência quando Boyer-Moore é "seguro de usar", mas até agora não tive sucesso. Aliás, eu não usaria o memmem da glibc como comparação. Minha implementação do que é basicamente o mesmo algoritmo do glibc é várias vezes mais rápida.
R .. GitHub Pare de ajudar o gelo
Como eu disse, não é minha implementação. Crédito para Christian Charras e Thierry Lecroq. Posso imaginar por que a entrada aleatória é ruim para o benchmarking e tenho certeza que a glibc escolhe algoritmos por razões. Eu também acho que o memmem () não é implementado com eficiência. Eu vou tentar. Obrigado.
precisa saber é o seguinte
4

Eu sei que é uma pergunta antiga, mas a maioria das tabelas de turnos ruins é de um único personagem. Se fizer sentido para o seu conjunto de dados (por exemplo, especialmente se houver palavras escritas), e se você tiver espaço disponível, poderá obter uma aceleração dramática usando uma tabela de deslocamento ruim feita de n-gramas em vez de caracteres únicos.

Timothy Jones
fonte
3

Use stdlib strstr:

char *foundit = strstr(haystack, needle);

Foi muito rápido, levei apenas 5 segundos para digitar.

Conrad Meyer
fonte
26
E, se você lesse minha pergunta, veria que era fácil superá-la. Eu gosto do seu sarcasmo o suficiente, mas vou pular o -1.
R .. GitHub Pare de ajudar o gelo
3

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

Fiz algumas experiências bastante extensas com a busca por cadeias de caracteres, mas foi para várias cadeias de busca. As implementações de montagem do Horspool e Bitap geralmente podem se defender de algoritmos como o Aho-Corasick, para contagens de padrões baixos.

Matt Joiner
fonte
3

Um strchralgoritmo "Procurar por um único caractere correspondente" (ala ) mais rápido .

Anotações importantes:

  • Essas funções usam um gcccompilador "número / contagem de zeros (à esquerda | à direita)" intrínseco __builtin_ctz. É provável que essas funções sejam rápidas apenas em máquinas com instruções que executam essa operação (por exemplo, x86, ppc, arm).

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

  • Essas funções são neutras no processador. Se a CPU de destino tiver instruções vetoriais, você poderá fazer (muito) melhor. Por exemplo, a strlenfunção 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));
}

Editar 2011/06/04 O OP indica nos comentários que esta solução possui um "bug intransponível":

pode ler além do byte procurado ou do terminador nulo, o que poderia 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 strchrimplementação típica não é ingênua, mas é um pouco mais eficiente do que o que você deu. Veja o final disso para o algoritmo mais utilizado: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Também não tem nada a ver com o alinhamento propriamente dito. É verdade que isso pode 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 de 4K não estiver mapeado.

Mas isso não é um "erro" no algoritmo dado na resposta - esse comportamento ocorre porque funções como strchre strlennão aceitam um lengthargumento para limitar o tamanho da pesquisa. A pesquisa char bytes[1] = {0x55};, que, para os propósitos de nossa discussão, acaba por ser colocada 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é uma implementação de byte por vez) falha exatamente mesma maneira. O mesmo vale para o strchrprimo relacionado strlen.

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

Em resumo, qualquer coisa que opere em pedaços maiores que bytes deve ser mais rápida, como esse código de respostas faz e o código indicado pelo OP, mas deve ter uma semântica de leitura precisa de bytes, provavelmente será "buggy" se não houver lengthargumento para controlar os casos de canto da "última leitura".

O código nesta resposta é um kernel para poder encontrar rapidamente o primeiro byte em um pedaço natural de tamanho de palavra da CPU, se a CPU de destino tiver uma ctzinstrução rápida . É trivial adicionar coisas como garantir que ele funcione apenas nos limites naturais alinhados corretamente ou em alguma forma de lengthlimite, o que permitiria que você saísse do kernel de alta velocidade e passasse a uma verificação mais lenta, byte a byte.

O OP também declara nos comentários:

Quanto à sua otimização ctz, isso só faz diferença para a operação de cauda O (1). Poderia melhorar o desempenho com pequenas seqüências de caracteres (por exemplo, strchr("abc", 'a');mas certamente não com sequências de qualquer tamanho maior).

Se essa afirmação é verdadeira ou não, depende muito da microarquitetura em questão. Usando o modelo de pipeline RISC canônico de 4 estágios, é quase certamente verdade. Mas é extremamente difícil dizer se isso é verdade para uma CPU super escalar contemporânea fora de ordem, em que a velocidade do núcleo pode minar totalmente a velocidade de streaming da memória. Nesse caso, não é apenas plausível, mas bastante comum, que exista 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 instruções que podem ser retiradas para cada byte que pode ser transmitido ". Se isso for grande o suficiente, a ctzinstrução + shift pode ser feita "de graça".

johne
fonte
"Para agulhas de comprimento 1, use strchr." - Você solicitou os algoritmos mais rápidos de busca de substring. Encontrar uma substring de comprimento 1 é apenas um caso especial, que também pode ser otimizado. Se você trocar seu código de caso especial atual por substrings de comprimento 1 ( strchr) por algo como o acima, as coisas (possivelmente, dependendo de como strchré implementado) serão mais rápidas. O algoritmo acima é quase 3x mais rápido que uma strchrimplementação ingênua típica .
Johne
2
O OP disse que a string foi corretamente nula e, portanto, sua discussão sobre char bytes[1] = {0x55};é irrelevante. Muito relevante é o seu comentário sobre isso ser verdadeiro para qualquer algoritmo de leitura de palavras que não saiba o tamanho de antemão.
Seth Robertson
1
O problema não se aplica à versão que citei porque você a usa apenas em indicadores alinhados - pelo menos é o que as implementações corretas fazem.
R .. GitHub Pare de ajudar o gelo
2
@R, não tem nada a ver com "ponteiros alinhados". Hipoteticamente, se você tivesse uma arquitetura que suportava a proteção da VM com granularidade no nível de bytes, e cada mallocalocação era "suficientemente acolchoada" em ambos os lados e o sistema da VM aplicava a proteção granular de bytes para essa alocação ... independentemente de o ponteiro estar alinhado ( supondo que o intalinhamento natural trivial de 32 bits ) seja discutível - ainda é possível que essa leitura alinhada leia além do tamanho da alocação. QUALQUER leitura além do tamanho da alocação undefined behavior.
Johne
5
@johne: +1 para comentar. Conceitualmente, você está certo, mas a realidade é que as proteções de granularidade de bytes são tão caras tanto para armazenar quanto para impor que elas não existem e nunca existirão. Se você souber que o armazenamento subjacente é um mapeamento de granularidade de página obtido do equivalente a mmap, o alinhamento é suficiente.
R .. GitHub Pare de ajudar o gelo
3

Basta procurar "strstr mais rápido" e, se vir algo de interesse, pergunte-me.

Na minha opinião, você impõe muitas restrições a si mesmo (sim, todos queremos linear sub-linear no max searcher); no entanto, é preciso um programador real para intervir; até então, acho que a abordagem de hash é simplesmente uma solução bacana para o limbo ( bem reforçado pelo BNDM para padrões mais curtos de 2 a 16).

Apenas um exemplo rápido:

Fazendo Pesquisar por padrão (32bytes) em String (206908949bytes) como-um-line ... Skip-Performance (maior-the-melhor): 3041%, 6801754 salta / iterações Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade desempenho: 3483KB / relógio

Fazendo Pesquisar por padrão (32bytes) em String (206908949bytes) como-um-line ... Skip-Performance (maior-the-melhor): 1,554%, 13307181 salta / iterações Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg desempenho: 2434KB / relógio

Fazendo Pesquisa de Padrão (32 bytes) na Cadeia de caracteres (206908949 bytes) como uma linha ... Desempenho em Saltos (maior o melhor): 129%, 160239051 ignora / iterações Hits de duas vias / relógios de duas vias: 0/816 Dois - Desempenho de maneira: 247KB / relógio

Sanmayce,
Atenciosamente

Georgi
fonte
3

O algoritmo bidirecional que você mencionou na sua pergunta (que por sinal é incrível!) Foi recentemente aprimorado para trabalhar com eficiência em palavras multibyte ao mesmo tempo: Correspondência otimizada de cadeias compactadas .

Não li o artigo inteiro, mas parece que eles dependem de algumas instruções especiais novas da CPU (incluídas no SSE 4.2), sendo O (1) por sua complexidade de tempo, embora, se não estiverem disponíveis, possam simule-os no tempo O (log log w) para palavras em w bits que não soem muito ruins.

j_random_hacker
fonte
3

Você pode implementar, digamos, 4 algoritmos diferentes. A cada M minutos (a ser determinado empiricamente), execute todos os 4 nos dados reais atuais. Acumule estatísticas sobre N execuções (também TBD). Em seguida, use apenas o vencedor pelos próximos M minutos.

Registre estatísticas no Wins para poder substituir algoritmos que nunca vencem por novos. Concentre os esforços de otimização na rotina mais vencedora. Preste atenção especial às estatísticas após qualquer alteração no hardware, banco de dados ou fonte de dados. Inclua essas informações no registro de estatísticas, se possível, para que você não precise descobrir isso a partir da data / hora do registro.

Guy Gordon
fonte
3

Descobri recentemente 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 precisasse atender rapidamente o algoritmo de pesquisa de substring, usaria Knuth-Morris-Pratt.

Sandeep Giri
fonte
Obrigado pelo link. Os testes parecem interessantes para o tempo típico dos casos, mas não para os piores momentos.
R .. GitHub Pare de ajudar o gelo
2

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 terão desempenho diferenciado com base na pesquisa de linguagem natural (e mesmo aqui ainda pode haver distinções refinadas por causa das diferentes morfologias), seqüências de DNA ou seqüências aleatórias etc.

O tamanho do alfabeto terá um papel importante em muitos algos, assim como o tamanho da agulha. Por exemplo, Horspool faz bem no texto em inglês, mas prejudica o DNA por causa do tamanho diferente do alfabeto, dificultando a vida da regra dos caracteres ruins. A introdução do sufixo bom alivia muito isso.


fonte
0

Não sei se é o melhor, mas tive uma boa experiência com Boyer-Moore .

R Samuel Klatchko
fonte
Você conhece uma maneira de combinar a mesa de turno ruim da Boyer-Moore com a Two-Way? O Glibc faz uma variante disso para agulhas longas (> 32 bytes), mas apenas verifica o último byte. O problema é que o Two-Way precisa pesquisar a parte direita da agulha da esquerda para a direita, enquanto o deslocamento ruim de Boyer-Moore é mais eficiente ao pesquisar da direita para a esquerda. Tentei usá-lo da esquerda para a direita em Bidirecional (avançar pela tabela de turno ou meia incompatibilidade normal bidirecional, o que for maior), mas na maioria dos casos, tive uma desaceleração de 5 a 10% em relação à bidirecional normal. Não foi possível encontrar nenhum caso em que melhorou o desempenho.
R .. GitHub Pare de ajudar o gelo
0

Isso não responde diretamente à pergunta, mas se o texto for muito grande, que tal dividi-lo em seções sobrepostas (sobreposição pelo comprimento de um padrão), procure simultaneamente as seções usando threads. No que diz respeito ao algoritmo mais rápido, Boyer-Moore-Horspool, acho que é um dos mais rápidos, senão o mais rápido, entre as variantes de Boyer-Moore. Publiquei algumas variantes de Boyer-Moore (não sei o nome delas) neste tópico Algoritmo mais rapidamente que a pesquisa BMH (Boyer-Moore-Horspool) .

Roy Alilin
fonte
0

O mais rápido atualmente é o EPSM, de S. Faro e OM Kulekci. Veja http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

"Correspondência exata de sequência compactada" otimizada para SIMD SSE4.2 (x86_64 e aarch64). Ele executa estável e melhor em todos os tamanhos.

O site ao qual eu vinculei compara 199 algoritmos de pesquisa rápida em cadeia, com os usuais (BM, KMP, BMH) sendo bastante lentos. O EPSM supera todos os outros aqui mencionados nessas plataformas. Também é o mais recente.

suburbano
fonte