Existe-t-il un bon algorithme de recherche pour un seul caractère?

Je connais plusieurs algorithmes de correspondance de chaînes de base tels que KMP ou Boyer-Moore, mais tous analysent le modèle avant de rechercher.Cependant, si l'on n'a qu'un seul caractère, il n'y a pas grand-chose à analyser. Existe-t-il donc un meilleur algorithme que la recherche naïve de comparaison de chaque caractère du texte?

Étant entendu que le pire des cas est O(N), il y a de très belles micro-optimisations.

La méthode naïve effectue une comparaison de caractères et une comparaison de fin de texte pour chaque caractère.

L'utilisation d'une sentinelle (c'est-à-dire une copie du caractère cible à la fin du texte) réduit le nombre de comparaisons à 1 par caractère.

Au niveau du bit twiddling, il y a:

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

pour savoir si un octet dans un mot ( x) a une valeur spécifique ( n).

La sous v - 0x01010101UL- expression est évaluée à un bit élevé défini dans n'importe quel octet chaque fois que l'octet correspondant dans vest nul ou supérieur à 0x80.

La sous-expression est ~v & 0x80808080ULévaluée à des bits élevés définis en octets où l'octet de vn'a pas son bit élevé défini (donc l'octet était inférieur à 0x80).

En ANDant ces deux sous-expressions ( haszero), le résultat est l'ensemble des bits élevés où les octets vétaient nuls, car les bits élevés définis en raison d'une valeur supérieure à celle 0x80de la première sous-expression sont masqués par la seconde (27 avril, 1987 par Alan Mycroft).

Maintenant, nous pouvons XOR la ​​valeur à tester ( x) avec un mot qui a été rempli avec la valeur d'octet qui nous intéresse ( n). Étant donné que XOR une valeur avec elle-même entraîne un octet nul et sinon différent de zéro, nous pouvons transmettre le résultat à haszero.

Ceci est souvent utilisé dans une strchrimplémentation typique .

(Stephen M Bennet l'a suggéré le 13 décembre 2009. Plus de détails dans les fameux Bit Twiddling Hacks ).

PS

ce code est rompu pour toute combinaison de à 1111côté d'un0

Le hack passe le test de force brute (soyez patient):

#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;
}

Beaucoup de votes positifs pour une réponse qui fait l'hypothèse un caractère = un octet, ce qui n'est plus la norme de nos jours

Merci pour la remarque.

La réponse devait être autre chose qu'un essai sur les codages multi-octets / à largeur variable :-) (en toute honnêteté, ce n'est pas mon domaine d'expertise et je ne suis pas sûr que ce soit ce que l'OP recherchait).

Quoi qu'il en soit, il me semble que les idées / astuces ci-dessus pourraient être quelque peu adaptées au MBE (en particulier les encodages auto-synchronisés ):

• comme indiqué dans le commentaire de Johan, le hack peut être «facilement» étendu pour fonctionner sur deux octets ou autre (bien sûr, vous ne pouvez pas trop l'étirer);
• une fonction typique qui localise un caractère dans une chaîne de caractères multi-octets:
  • contient des appels à strchr/ strstr(par exemple GNUlib coreutils mbschr )
  • s'attend à ce qu'ils soient bien réglés.
• la technique sentinelle peut être utilisée avec un peu de prévoyance.

Tout algorithme de recherche de texte qui recherche chaque occurrence d'un seul caractère dans un texte donné doit lire chaque caractère du texte au moins une fois, cela devrait être évident. Et comme cela suffit pour une recherche unique, il ne peut y avoir de meilleur algorithme (en pensant en termes d'ordre d'exécution, qui est appelé "linéaire" ou O (N) dans ce cas, où N est le nombre de caractères rechercher).

Cependant, pour les implémentations réelles, il y a sûrement beaucoup de micro-optimisations possibles, qui ne modifient pas l'ordre du temps d'exécution dans son ensemble, mais réduisent le temps d'exécution réel. Et si le but n'est pas de trouver chaque occurrence d'un seul personnage, mais seulement la première, vous pouvez bien sûr vous arrêter à la première occurrence. Néanmoins, même dans ce cas, le pire des cas est toujours que le caractère que vous recherchez est le dernier caractère du texte, donc l'ordre d'exécution du pire des cas pour cet objectif est toujours O (N).

Si votre "meule de foin" est recherchée plus d'une fois, une approche basée sur l'histogramme va être extrêmement rapide. Une fois l'histogramme créé, il vous suffit de rechercher un pointeur pour trouver votre réponse.

Si vous avez seulement besoin de savoir si le motif recherché est présent, un simple compteur peut vous aider. Il peut être étendu pour inclure la ou les positions auxquelles chaque personnage se trouve dans la botte de foin, ou la position de la première occurrence.

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

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

Si vous devez rechercher plusieurs fois des caractères dans cette même chaîne, une approche possible consiste à diviser la chaîne en parties plus petites, éventuellement de manière récursive, et à utiliser des filtres de bloom pour chacune de ces parties.

Puisqu'un filtre de floraison peut vous dire avec certitude si un caractère ne se trouve pas dans la partie de la chaîne qui est "représentée" par le filtre, vous pouvez ignorer certaines parties lors de la recherche de caractères.

À titre d'exemple: pour la chaîne suivante, on pourrait la diviser en 4 parties (chacune de 11 caractères de long), et remplir pour chaque partie un filtre de bloom (peut-être 4 octets de large) avec les caractères de cette partie:

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

Vous pouvez accélérer votre recherche, par exemple pour le personnage a: en utilisant de bonnes fonctions de hachage pour les filtres de floraison, ils vous diront que - avec une forte probabilité - vous n'avez pas à chercher dans la première, la deuxième ou la troisième partie. Ainsi, vous vous évitez de vérifier 33 caractères et vous n'avez qu'à vérifier 16 octets (pour les 4 filtres de floraison). C'est toujours O(n), juste avec un facteur (fractionnel) constant (et pour que cela soit efficace, vous devrez choisir des parties plus grandes, afin de minimiser la surcharge de calcul des fonctions de hachage pour le caractère de recherche).

L'utilisation d'une approche récursive et arborescente devrait vous rapprocher 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)

Dans cette configuration, il faut (encore une fois, en supposant que nous avons eu de la chance et que nous n'avons pas obtenu de faux positif de l'un des filtres) pour vérifier

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

pour arriver à la dernière partie (où il faut vérifier 3 caractères jusqu'à trouver le a).

En utilisant un bon schéma de subdivision (meilleur que celui ci-dessus), vous devriez obtenir de très bons résultats avec cela. (Remarque: les filtres de floraison à la racine de l'arbre doivent être plus grands que près des feuilles, comme indiqué dans l'exemple, pour obtenir une faible probabilité de faux positifs)

Si la chaîne doit être recherchée plusieurs fois (problème de "recherche" typique), la solution peut être O (1). La solution est de construire un index.

Par exemple :

Carte, où Key est le caractère et Value est une liste d'index pour ce caractère dans la chaîne.

Avec cela, une seule recherche de carte peut fournir la réponse.