Existe algum bom algoritmo de pesquisa para um único caractere?

Conheço vários algoritmos básicos de correspondência de strings, como KMP ou Boyer-Moore, mas todos analisam o padrão antes de pesquisar. No entanto, se um tiver um único caractere, não há muito o que analisar. Então, existe algum algoritmo melhor do que a busca ingênua de comparar todos os caracteres do texto?

Entendendo-se que o pior caso é O(N), existem algumas micro-otimizações muito boas.

O método ingênuo realiza uma comparação de caracteres e uma comparação de final de texto para cada caractere.

O uso de uma sentinela (ou seja, uma cópia do caractere alvo no final do texto) reduz o número de comparações para 1 por caractere.

No nível de rodízio de bits, há:

#define haszero(v)      ( ((v) - 0x01010101UL) & ~(v) & 0x80808080UL )
#define hasvalue(x, n)  ( haszero((x) ^ (~0UL / 255 * (n))) )

para saber se algum byte em uma palavra ( x) tem um valor específico ( n).

A subexpressão é v - 0x01010101ULavaliada como um conjunto de bits alto em qualquer byte sempre que o byte correspondente vfor zero ou maior que 0x80.

A subexpressão é ~v & 0x80808080ULavaliada como bits altos definidos em bytes onde o byte de vnão possui seu conjunto de bits alto (portanto, o byte era menor que 0x80).

Ao ANDing essas duas subexpressões ( haszero), o resultado é o conjunto de bits altos em que os bytes vforam zero, pois os bits altos configurados devido a um valor maior que 0x80na primeira subexpressão são mascarados no segundo (27 de abril de 1987 por Alan Mycroft).

Agora podemos XOR o valor para testar ( x) com uma palavra que foi preenchida com o valor de bytes em que estamos interessados ​​( n). Como XORing um valor em si resulta em zero byte e diferente de zero, caso contrário, podemos passar o resultado para haszero.

Isso geralmente é usado em uma strchrimplementação típica .

(Stephen M Bennet sugeriu isso em 13 de dezembro de 2009. Mais detalhes no conhecido Bit Twiddling Hacks ).

PS

esse código está quebrado para qualquer combinação de 1111s ao lado de um0

O hack passa no teste de força bruta (apenas seja paciente):

#include <iostream>
#include <limits>

bool haszero(std::uint32_t v)
{
  return (v - std::uint32_t(0x01010101)) & ~v & std::uint32_t(0x80808080);
}

bool hasvalue(std::uint32_t x, unsigned char n)
{
  return haszero(x ^ (~std::uint32_t(0) / 255 * n));
}

bool hasvalue_slow(std::uint32_t x, unsigned char n)
{
  for (unsigned i(0); i < 32; i += 8)
    if (((x >> i) & 0xFF) == n)
      return true;

  return false;
}

int main()
{
  const std::uint64_t stop(std::numeric_limits<std::uint32_t>::max());

  for (unsigned c(0); c < 256; ++c)
  {
    std::cout << "Testing " << c << std::endl;

    for (std::uint64_t w(0); w != stop; ++w)
    {
      if (w && w % 100000000 == 0)
        std::cout << w * 100 / stop << "%\r" << std::flush;

      const bool h(hasvalue(w, c));
      const bool hs(hasvalue_slow(w, c));

      if (h != hs)
        std::cerr << "hasvalue(" << w << ',' << c << ") is " << h << '\n';
    }
  }

  return 0;
}

Muitos votos positivos para uma resposta que torna a suposição um caractere = um byte, que hoje em dia não é mais o padrão

Obrigado pela observação.

A resposta era para ser apenas um ensaio sobre codificações de vários bytes / largura variável :-) (com toda a justiça, essa não é a minha área de especialização e não tenho certeza de que é o que o OP estava procurando).

De qualquer forma, parece-me que as idéias / truques acima poderiam ser adaptados ao MBE (especialmente codificações auto-sincronizáveis ):

• como observado no comentário de Johan, o hack pode 'facilmente' ser estendido para trabalhar com bytes duplos ou qualquer coisa (é claro que você não pode esticá-lo demais);
• uma função típica que localiza um caractere em uma cadeia de caracteres multibyte:
  • contém chamadas para strchr/ strstr(por exemplo, GNUlib coreutils mbschr )
  • espera que eles estejam bem sintonizados.
• a técnica sentinela pode ser usada com um pouco de previsão.

Qualquer algoritmo de pesquisa de texto que procure todas as ocorrências de um único caractere em um determinado texto deve ler cada caractere do texto pelo menos uma vez, isso deve ser óbvio. E como isso é suficiente para uma pesquisa única, não pode haver um algoritmo melhor (quando se pensa em termos de ordem de tempo de execução, que é chamada "linear" ou O (N) para este caso, em que N é o número de caracteres para pesquisar).

No entanto, para implementações reais, certamente existem muitas micro otimizações possíveis, que não alteram a ordem do tempo de execução como um todo, mas diminuem o tempo de execução real. E se o objetivo não é encontrar todas as ocorrências de um único personagem, mas apenas o primeiro, você pode parar na primeira ocorrência, é claro. No entanto, mesmo nesse caso, o pior caso ainda é que o personagem que você está procurando é o último caractere no texto, portanto, a pior ordem de tempo de execução para esse objetivo ainda é O (N).

Se o seu "palheiro" for pesquisado mais de uma vez, uma abordagem baseada em histograma será extremamente rápida. Após a construção do histograma, você só precisa de uma pesquisa de ponteiro para encontrar sua resposta.

Se você só precisa saber se o padrão pesquisado está presente, um contador simples pode ajudar. Pode ser estendido para incluir as posições em que cada personagem é encontrado no palheiro ou a posição da primeira ocorrência.

string haystack = "agtuhvrth";
array<int, 256> histogram{0};
for(character: haystack)
     ++histogram[character];

if(histogram['a'])
    // a belongs to haystack

Se você precisar procurar caracteres nessa mesma string mais de uma vez, uma possível abordagem é dividir a string em partes menores, possivelmente recursivamente, e usar filtros de bloom para cada uma dessas partes.

Como um filtro de bloom pode dizer com certeza se um caractere não está na parte da string "representada" pelo filtro, você pode pular algumas partes enquanto procura por caracteres.

Como exemplo: Para a sequência a seguir, é possível dividi-la em 4 partes (cada uma com 11 caracteres) e preencher para cada parte um filtro de bloom (talvez com 4 bytes de largura) com os caracteres dessa parte:

The quick brown fox jumps over the lazy dog 
          |          |          |          |

Você pode acelerar sua pesquisa, por exemplo, para o personagem a: Usando boas funções de hash para os filtros de bloom, eles dirão que - com alta probabilidade - você não precisa pesquisar nem na primeira, na segunda nem na terceira parte. Assim, você evita verificar 33 caracteres e, em vez disso, precisa verificar apenas 16 bytes (para os 4 filtros de bloom). Ainda O(n)assim, apenas com um fator constante (fracionário) (e para que isso seja eficaz, você precisará escolher partes maiores, para minimizar a sobrecarga de cálculo das funções de hash para o caractere de pesquisa).

Usando uma abordagem recursiva em forma de árvore, você deve chegar perto de O(log n):

The quick brown fox jumps over the lazy dog 
   |   |   |   |   |   |   |   |---|-X-|   |  (1 Byte)
       |       |       |       |---X---|----  (2 Byte)
               |               |-----X------  (3 Byte)
-------------------------------|-----X------  (4 Byte)
---------------------X---------------------|  (5 Byte)

Nesta configuração, é necessário (novamente, supondo que tivemos sorte e não obtivemos um falso positivo de um dos filtros) para verificar

5 + 2*4 + 3 + 2*2 + 2*1 bytes

para chegar à parte final (onde é necessário verificar 3 caracteres até encontrar o a).

Usando um bom esquema de subdivisão (melhor que o acima), você deve obter bons resultados com isso. (Nota: Os filtros de flor na raiz da árvore devem ser maiores que perto das folhas, como mostrado no exemplo, para obter uma baixa probabilidade de falsos positivos)

Se a string for pesquisada várias vezes (problema típico de "pesquisa"), a solução poderá ser O (1). A solução é criar um índice.

Por exemplo :

Mapa, onde Chave é o Caractere e Valor, é uma lista de índices para esse caractere na sequência.

Com isso, uma única pesquisa de mapa pode fornecer a resposta.