kmp - find substring in c



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

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 .

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

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 função 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 contribui, assim, 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 preprocessamento pesado incondicional é ruim, como está tentando melhorar o coeficiente linear para 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% mais tempo de busca) do que 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 entrada) 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 maneira: Pré-carregue a agulha em um inteiro de 16 ou 32 bits com bitshift e anula bytes antigos em volta 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 entradas na tabela de turnos foram inicializadas. Bits não ajustados correspondem a valores de bytes que nunca aparecem na agulha, para os quais é possível uma mudança 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 memória ou de desempenho quadrático) são Two-Way e String Matching on Ordered Alphabets . Mas há casos facilmente detectáveis ​​em que diferentes algoritmos 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 sejam o pior caso de quadrático 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 bem formados UTF-8? (Com caracteres de comprimentos de byte variados, 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 um byte da cabeça incorreto é encontrado. Mas essas restrições 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 que estão por aí, mas não do quão bem eles se comportam 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


Answer #1

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 sobre 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çada 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 de 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


Answer #2

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.


Answer #3

Eu sei que é uma questão antiga, mas a maioria das tabelas de mudança ruins são de caráter único. Se isso fizer sentido para o seu conjunto de dados (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.


Answer #4

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 mais conhecidos e pesquisados ​​algoritmos de correspondência de strings.

As soluções para a maioria dos problemas de pesquisa 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 objetivo é 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 revendo os pontos fortes e fracos específicos dos algoritmos que você já referenciou. Realize a revisão com o objetivo 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 função classificadora para atingir o melhor algoritmo para as entradas 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 -Moore 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 ele tenha sido empregado por alguns pacotes comerciais de classificação / pesquisa (por exemplo, SYNCSORT normalmente usado em mainframes implementa vários algoritmos de classificação e usa heurística para escolher o "melhor" para os dados fornecidos)

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

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


Answer #5

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

Eu não li o artigo inteiro, mas parece que eles contam com algumas novas e especiais instruções de 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 soam muito ruins.



Answer #7

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 gcc compilador gcc intrinsic- __builtin_ctz . Essas funções provavelmente só serão rápidas em máquinas que tenham instruções que realizem 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 a 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 de vetor, você poderá fazer (muito) melhor. Por exemplo, a função 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 verdade, 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), então 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 strchr primo 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 ctz natural de tamanho de palavra da CPU 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ê mudasse do kernel de alta velocidade para 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.

Se esta afirmação é 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 memória. 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".


Answer #8

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

Registre estatísticas em Vitórias para poder substituir algoritmos que nunca ganham com novos. Concentre os esforços de otimização na rotina mais vitoriosa. 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 log de estatísticas, se possível, para que você não tenha que descobrir a partir da data / hora do log.


Answer #9

Eu não sei se é o melhor absoluto, mas eu tive uma boa experiência com Boyer-Moore .


Answer #10

Use stdlib strstr:

char *foundit = strstr(haystack, needle);

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


Answer #11

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 de linguagem natural (e mesmo aqui ainda pode 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.





substring