Gibt es einen guten Suchalgorithmus für ein einzelnes Zeichen?

Ich kenne einige grundlegende Algorithmen für den String-Abgleich wie KMP oder Boyer-Moore, aber alle analysieren das Muster vor der Suche. Wenn jedoch ein einzelnes Zeichen vorhanden ist, gibt es nicht viel zu analysieren. Gibt es einen besseren Algorithmus als die naive Suche, bei der jedes Zeichen des Textes verglichen wird?

Es versteht sich, dass es im schlimmsten Fall O(N)einige sehr schöne Mikrooptimierungen gibt.

Die naive Methode führt für jedes Zeichen einen Zeichenvergleich und einen Textende-Vergleich durch.

Durch die Verwendung eines Sentinels (dh einer Kopie des Zielzeichens am Ende des Texts) wird die Anzahl der Vergleiche auf 1 pro Zeichen reduziert.

Auf der Ebene des Bit Twiddling gibt es:

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

um zu wissen, ob ein Byte in einem Wort ( x) einen bestimmten Wert ( n) hat.

Der Unterausdruck v - 0x01010101ULwird zu einem hohen Bit ausgewertet, das in einem beliebigen Byte gesetzt ist, wenn das entsprechende Byte in vNull oder größer als ist 0x80.

Der Unterausdruck wird ~v & 0x80808080ULzu hohen Bits ausgewertet, die in Bytes gesetzt sind, bei denen das hohe Bit des Bytes vnicht gesetzt ist (das Byte war also kleiner als 0x80).

Durch UND-Verknüpfung dieser beiden Unterausdrücke ( haszero) wird das High-Bit-Set erhalten, bei dem die Bytes vNull waren, da die High-Bits, die aufgrund eines höheren Wertes als 0x80im ersten Unterausdruck gesetzt wurden, vom zweiten maskiert werden (27. April). 1987 von Alan Mycroft).

Jetzt können wir den zu testenden Wert ( x) mit einem Wort XOR-verknüpfen, das mit dem Byte-Wert gefüllt ist, an dem wir interessiert sind ( n). Da das XOR-Verknüpfen eines Werts mit sich selbst zu einem Null-Byte und zu einem Wert ungleich Null führt, können wir das Ergebnis an übergeben haszero.

Dies wird häufig in einer typischen strchrImplementierung verwendet.

(Stephen M Bennet schlug dies am 13. Dezember 2009 vor. Weitere Details in den bekannten Bit Twiddling Hacks ).

PS

Dieser Code ist für jede Kombination von 1111 's neben a ungültig0

Der Hack besteht den Brute-Force-Test (nur etwas Geduld):

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

Viele positive Stimmen für eine Antwort, die von einem Zeichen = einem Byte ausgeht, was heutzutage nicht mehr der Standard ist

Danke für die Bemerkung.

Die Antwort sollte alles andere als ein Aufsatz über Multi-Byte- / Variable-Width-Codierungen sein :-) (Fairerweise ist das nicht mein Fachgebiet und ich bin nicht sicher, ob es das ist, wonach das OP gesucht hat).

Jedenfalls scheint es mir, dass die obigen Ideen / Tricks etwas an MBE angepasst werden könnten (insbesondere selbstsynchronisierende Codierungen ):

• wie in Johans Kommentar vermerkt der Hack 'leicht' erweitert werden, um für Doppelbytes oder irgendetwas zu arbeiten (natürlich kann man ihn nicht zu sehr dehnen).
• Eine typische Funktion, die ein Zeichen in einer Multibyte-Zeichenfolge findet:
  • enthält Aufrufe von strchr/ strstr(zB GNUlib coreutils mbschr )
  • erwartet, dass sie gut gestimmt sind.
• Die Sentinel-Technik kann mit ein wenig Weitsicht angewendet werden.

Jeder Textsuchalgorithmus, der nach jedem Vorkommen eines einzelnen Zeichens in einem bestimmten Text sucht, muss jedes Zeichen des Textes mindestens einmal lesen, das sollte offensichtlich sein. Und da dies für eine einmalige Suche ausreicht, kann es keinen besseren Algorithmus geben (wenn man in Bezug auf die Laufzeitreihenfolge denkt, der in diesem Fall als "linear" oder O (N) bezeichnet wird, wobei N die Anzahl der Zeichen ist) zu durchsuchen).

Für echte Implementierungen sind jedoch sicherlich viele Mikrooptimierungen möglich, die die Laufzeitreihenfolge nicht insgesamt ändern, sondern die tatsächliche Laufzeit verringern. Und wenn das Ziel nicht darin besteht, jedes Vorkommen eines einzelnen Zeichens zu finden, sondern nur das erste, können Sie natürlich beim ersten Vorkommen aufhören. Selbst in diesem Fall besteht der schlimmste Fall immer noch darin, dass das gesuchte Zeichen das letzte Zeichen im Text ist. Die Laufzeitreihenfolge im schlimmsten Fall für dieses Ziel lautet daher immer noch O (N).

Wenn Ihr "Heuhaufen" mehr als einmal durchsucht wird, wird ein Histogramm-basierter Ansatz extrem schnell sein. Nachdem das Histogramm erstellt wurde, benötigen Sie nur eine Zeigersuche, um Ihre Antwort zu finden.

Wenn Sie nur wissen müssen, ob das gesuchte Muster vorhanden ist, kann ein einfacher Zähler helfen. Es kann erweitert werden, um die Position (en), an der sich jedes Zeichen im Heuhaufen befindet, oder die Position des ersten Vorkommens einzuschließen.

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

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

Wenn Sie in derselben Zeichenfolge mehr als einmal nach Zeichen suchen müssen, besteht ein möglicher Ansatz darin, die Zeichenfolge in kleinere Teile zu unterteilen, möglicherweise rekursiv, und für jeden dieser Teile Bloom-Filter zu verwenden.

Da ein Bloom-Filter Ihnen sicher sagen kann, ob sich ein Zeichen nicht in dem Teil der Zeichenfolge befindet, der vom Filter "dargestellt" wird, können Sie bei der Suche nach Zeichen einige Teile überspringen.

Als Beispiel: Für die folgende Zeichenfolge könnte man sie in 4 Teile (jeweils 11 Zeichen lang) aufteilen und für jeden Teil einen Bloom-Filter (möglicherweise 4 Byte groß) mit den Zeichen dieses Teils füllen:

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

Sie können Ihre Suche beschleunigen, z. B. nach dem Charakter a: Wenn Sie gute Hash-Funktionen für die Bloom-Filter verwenden, erfahren Sie, dass Sie mit hoher Wahrscheinlichkeit weder im ersten noch im zweiten oder dritten Teil suchen müssen. So ersparen Sie sich die Prüfung von 33 Zeichen und müssen stattdessen nur 16 Bytes prüfen (für die 4 Bloom-Filter). Das ist immer noch soO(n) nur mit einem konstanten (gebrochenen) Faktor (und damit dies effektiv ist, müssen Sie größere Teile auswählen, um den Aufwand für die Berechnung der Hash-Funktionen für das Suchzeichen zu minimieren).

Die Verwendung eines rekursiven baumartigen Ansatzes sollte Sie in die Nähe O(log n)folgender Punkte bringen :

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

In dieser Konfiguration muss man (wiederum unter der Annahme, dass wir Glück hatten und von keinem der Filter ein falsches Positiv erhalten haben) überprüfen

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

um zum letzten Teil zu gelangen (wo man 3 Zeichen überprüfen muss, bis man das findet) a ).

Wenn Sie ein gutes (besser als das obige) Unterteilungsschema verwenden, sollten Sie damit ziemlich gute Ergebnisse erzielen. (Hinweis: Blütenfilter an der Wurzel des Baumes sollten, wie im Beispiel gezeigt, größer als in der Nähe der Blätter sein, um eine niedrige Wahrscheinlichkeit für falsch positive Ergebnisse zu erhalten.)

Wenn die Zeichenfolge mehrmals durchsucht werden soll (typisches "Such" -Problem), kann die Lösung O (1) sein. Die Lösung besteht darin, einen Index zu erstellen.

Z.B :

Map, wobei Key das Zeichen und Value eine Liste der Indizes für dieses Zeichen in der Zeichenfolge ist.

Mit dieser Funktion kann eine einzelne Kartensuche die Antwort liefern.