Was ist der schnellste Teilstring-Suchalgorithmus?

OK, also ich klinge nicht wie ein Idiot. Ich werde das Problem / die Anforderungen expliziter darlegen:

• Nadel (Muster) und Heuhaufen (zu durchsuchender Text) sind nullterminierte Zeichenfolgen im C-Stil. Es werden keine Längeninformationen bereitgestellt. Bei Bedarf muss es berechnet werden.
• Die Funktion sollte einen Zeiger auf die erste Übereinstimmung zurückgeben oder NULLwenn keine Übereinstimmung gefunden wird.
• Fehlerfälle sind nicht zulässig. Dies bedeutet, dass jeder Algorithmus mit nicht konstanten (oder großen konstanten) Speicheranforderungen einen Fallback-Fall für einen Zuordnungsfehler haben muss (und die Leistung in der Fallback-Pflege dadurch zur Worst-Case-Leistung beiträgt).
• Die Implementierung soll in C erfolgen, obwohl eine gute Beschreibung des Algorithmus (oder der Verknüpfung mit einem solchen) ohne Code ebenfalls in Ordnung ist.

... sowie was ich mit "am schnellsten" meine:

• Deterministisch O(n)wo n= Heuhaufenlänge. (Es kann jedoch möglich sein, Ideen von Algorithmen zu verwenden, die normalerweise verwendet werden O(nm)(z. B. rollierender Hash), wenn sie mit einem robusteren Algorithmus kombiniert werden, um deterministische O(n)Ergebnisse zu erzielen .)
• Niemals if (!needle[1])schlechter (messbar; ein paar Uhren usw. sind in Ordnung) schlechter als der naive Brute-Force-Algorithmus, insbesondere bei sehr kurzen Nadeln, die wahrscheinlich der häufigste Fall sind. (Der bedingungslose hohe Vorverarbeitungsaufwand ist schlecht, ebenso wie der Versuch, den linearen Koeffizienten für pathologische Nadeln auf Kosten wahrscheinlicher Nadeln zu verbessern.)
• Bei einer beliebigen Nadel und einem beliebigen Heuhaufen ist die Leistung vergleichbar oder besser (nicht schlechter als 50% längere Suchzeit) als bei jedem anderen weit verbreiteten Algorithmus.
• Abgesehen von diesen Bedingungen lasse ich die Definition von "schnellstem" unbefristet. Eine gute Antwort sollte erklären, warum Sie den von Ihnen vorgeschlagenen Ansatz als "am schnellsten" betrachten.

Meine aktuelle Implementierung läuft ungefähr 10% langsamer und 8-mal schneller (abhängig von der Eingabe) als die Implementierung von Two-Way von glibc.

Update: Mein aktueller optimaler Algorithmus lautet wie folgt:

• Verwenden Sie für Nadeln der Länge 1 strchr.
• Verwenden Sie für Nadeln der Länge 2-4 Maschinenwörter, um 2-4 Bytes gleichzeitig wie folgt zu vergleichen: Laden Sie die Nadel in einer 16- oder 32-Bit-Ganzzahl mit Bitverschiebungen vor und wechseln Sie bei jeder Iteration alte Bytes aus / neue Bytes aus dem Heuhaufen . Jedes Byte des Heuhaufens wird genau einmal gelesen und es wird eine Prüfung gegen 0 (Ende der Zeichenfolge) und ein 16- oder 32-Bit-Vergleich durchgeführt.
• Verwenden Sie für Nadeln mit einer Länge> 4 den Zwei-Wege-Algorithmus mit einer schlechten Verschiebungstabelle (wie Boyer-Moore), die nur auf das letzte Byte des Fensters angewendet wird. Um den Aufwand für die Initialisierung einer 1-KB-Tabelle zu vermeiden, der für viele Nadeln mittlerer Länge einen Nettoverlust darstellen würde, behalte ich ein Bit-Array (32 Byte) bei, das markiert, welche Einträge in der Verschiebungstabelle initialisiert werden. Nicht gesetzte Bits entsprechen Bytewerten, die niemals in der Nadel erscheinen, für die eine Verschiebung um die gesamte Nadellänge möglich ist.

Die großen Fragen, die mir noch im Kopf bleiben, sind:

• Gibt es eine Möglichkeit, den schlechten Schichttisch besser zu nutzen? Boyer-Moore nutzt es am besten, indem er rückwärts (von rechts nach links) scannt, für Two-Way ist jedoch ein Scan von links nach rechts erforderlich.
• Die einzigen zwei brauchbaren Kandidatenalgorithmen, die ich für den allgemeinen Fall gefunden habe (keine Speichermangel- oder quadratischen Leistungsbedingungen), sind Zweiwege- und String-Matching für geordnete Alphabete . Aber gibt es leicht erkennbare Fälle, in denen unterschiedliche Algorithmen optimal wären? Sicherlich könnten viele der O(m)(wo mist die Nadellänge) im Weltraum-Algorithmen für m<100oder so verwendet werden. Es wäre auch möglich, Algorithmen zu verwenden, die im schlimmsten Fall quadratisch sind, wenn es einen einfachen Test für Nadeln gibt, die nachweislich nur eine lineare Zeit benötigen.

Bonuspunkte für:

• Können Sie die Leistung verbessern, indem Sie davon ausgehen, dass Nadel und Heuhaufen beide gut geformte UTF-8 sind? (Bei Zeichen mit unterschiedlichen Bytelängen stellt die Formgebung einige Anforderungen an die Ausrichtung der Zeichenfolge zwischen Nadel und Heuhaufen und ermöglicht automatische Verschiebungen von 2 bis 4 Bytes, wenn ein nicht übereinstimmendes Kopfbyte auftritt Maximale Suffixberechnungen, gute Suffixverschiebungen usw. geben Ihnen bereits verschiedene Algorithmen?)

Hinweis: Mir sind die meisten Algorithmen bekannt, nur nicht, wie gut sie in der Praxis funktionieren. Hier ist eine gute Referenz, damit mir die Leute nicht immer Referenzen zu Algorithmen als Kommentare / Antworten geben: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Bauen Sie eine Testbibliothek mit wahrscheinlichen Nadeln und Heuhaufen auf. Profilieren Sie die Tests anhand mehrerer Suchalgorithmen, einschließlich Brute Force. Wählen Sie diejenige aus, die mit Ihren Daten am besten funktioniert.

Boyer-Moore verwendet eine schlechte Zeichentabelle mit einer guten Suffix-Tabelle.

Boyer-Moore-Horspool verwendet eine Tabelle mit schlechten Charakteren.

Knuth-Morris-Pratt verwendet eine teilweise Übereinstimmungstabelle.

Rabin-Karp verwendet laufende Hashes.

Sie alle tauschen Overhead gegen reduzierte Vergleiche in unterschiedlichem Maße, sodass die tatsächliche Leistung von der durchschnittlichen Länge von Nadel und Heuhaufen abhängt. Je höher der anfängliche Overhead, desto besser bei längeren Eingaben. Mit sehr kurzen Nadeln kann Brute Force gewinnen.

Bearbeiten:

Ein anderer Algorithmus ist möglicherweise am besten geeignet, um Basenpaare, englische Phrasen oder einzelne Wörter zu finden. Wenn es einen besten Algorithmus für alle Eingaben gegeben hätte, wäre er veröffentlicht worden.

Denken Sie an die folgende kleine Tabelle. Jedes Fragezeichen hat möglicherweise einen anderen besten Suchalgorithmus.

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

Dies sollte eigentlich ein Diagramm sein, mit einem Bereich von kürzeren bis längeren Eingaben auf jeder Achse. Wenn Sie jeden Algorithmus in einem solchen Diagramm darstellen würden, hätte jeder eine andere Signatur. Einige Algorithmen leiden unter vielen Wiederholungen im Muster, was sich auf Anwendungen wie die Suche nach Genen auswirken kann. Einige andere Faktoren, die sich auf die Gesamtleistung auswirken, sind die mehrfache Suche nach demselben Muster und die gleichzeitige Suche nach verschiedenen Mustern.

Wenn ich ein Beispielset benötige, würde ich wahrscheinlich eine Website wie Google oder Wikipedia kratzen und dann das HTML von allen Ergebnisseiten entfernen. Geben Sie für eine Suchwebsite ein Wort ein und verwenden Sie einen der vorgeschlagenen Suchbegriffe. Wählen Sie gegebenenfalls einige verschiedene Sprachen aus. Bei Verwendung von Webseiten sind alle Texte kurz bis mittelgroß. Führen Sie daher genügend Seiten zusammen, um längere Texte zu erhalten. Sie können auch gemeinfreie Bücher, juristische Aufzeichnungen und andere große Textkörper finden. Oder generieren Sie einfach zufälligen Inhalt, indem Sie Wörter aus einem Wörterbuch auswählen. Bei der Profilerstellung geht es jedoch darum, anhand der Art des Inhalts zu testen, nach dem Sie suchen. Verwenden Sie daher nach Möglichkeit Beispiele aus der Praxis.

Ich ging kurz und lang vage. Für die Nadel denke ich an kurze als unter 8 Zeichen, mittlere als unter 64 Zeichen und lange als unter 1k. Für den Heuhaufen denke ich an kurz als unter 2 ^ 10, mittel wie unter 2 ^ 20 und lang bis zu 2 ^ 30 Zeichen.

Ich glaube, dass es sich um den 2011 veröffentlichten Algorithmus "Simple Real-Time Constant-Space String Matching" von Dany Breslauer, Roberto Grossi und Filippo Mignosi handelt.

Aktualisieren:

2014 veröffentlichten die Autoren diese Verbesserung: Auf dem Weg zu einem optimalen Matching gepackter Strings .

Der Link http://www-igm.univ-mlv.fr/~lecroq/string/index.html , auf den Sie verweisen, ist eine hervorragende Quelle und Zusammenfassung einiger der bekanntesten und erforschten Algorithmen für den String-Abgleich.

Lösungen für die meisten Suchprobleme beinhalten Kompromisse hinsichtlich des Vorverarbeitungsaufwands, des Zeit- und Platzbedarfs. Kein einzelner Algorithmus ist in allen Fällen optimal oder praktisch.

Wenn Sie einen bestimmten Algorithmus für die Zeichenfolgensuche entwerfen möchten, ignorieren Sie den Rest meiner Aussagen. Wenn Sie eine allgemeine Routine für die Zeichenfolgensuche entwickeln möchten, versuchen Sie Folgendes:

Nehmen Sie sich etwas Zeit, um die spezifischen Stärken und Schwächen der Algorithmen zu überprüfen, auf die Sie bereits verwiesen haben. Führen Sie die Überprüfung mit dem Ziel durch, eine Reihe von Algorithmen zu finden, die den Bereich und den Umfang der Zeichenfolgensuche abdecken, an denen Sie interessiert sind. Erstellen Sie anschließend einen Front-End-Suchselektor basierend auf einer Klassifizierungsfunktion, um den besten Algorithmus für die angegebenen Eingaben zu ermitteln. Auf diese Weise können Sie den effizientesten Algorithmus verwenden, um die Aufgabe zu erledigen. Dies ist besonders effektiv, wenn ein Algorithmus für bestimmte Suchvorgänge sehr gut ist, sich jedoch nur schlecht verschlechtert. Zum Beispiel ist Brute Force wahrscheinlich die beste für Nadeln der Länge 1, nimmt jedoch mit zunehmender Nadellänge schnell ab, woraufhin das Sustik-Moore-Algoritimkann effizienter werden (gegenüber kleinen Alphabeten), dann sind bei längeren Nadeln und größeren Alphabeten die KMP- oder Boyer-Moore-Algorithmen möglicherweise besser. Dies sind nur Beispiele zur Veranschaulichung einer möglichen Strategie.

Der Ansatz mit mehreren Algorithmen ist keine neue Idee. Ich glaube, es wurde von einigen kommerziellen Sortier- / Suchpaketen verwendet (z. B. implementiert SYNCSORT, das üblicherweise auf Großrechnern verwendet wird, mehrere Sortieralgorithmen und verwendet Heuristiken, um den "besten" für die gegebenen Eingaben auszuwählen).

Jeder Suchalgorithmus ist in verschiedenen Varianten erhältlich, die die Leistung erheblich verbessern können, wie beispielsweise in diesem Artikel dargestellt.

Benchmarking Ihres Dienstes, um die Bereiche zu kategorisieren, in denen zusätzliche Suchstrategien erforderlich sind, oder um Ihre Auswahlfunktion effektiver zu optimieren. Dieser Ansatz ist nicht schnell oder einfach, kann aber bei guter Ausführung zu sehr guten Ergebnissen führen.

Ich war überrascht zu sehen, dass unser technischer Bericht in dieser Diskussion zitiert wurde. Ich bin einer der Autoren des Algorithmus, der oben Sustik-Moore genannt wurde. (Wir haben diesen Begriff in unserer Arbeit nicht verwendet.)

Ich wollte hier betonen, dass für mich das interessanteste Merkmal des Algorithmus ist, dass es ziemlich einfach ist zu beweisen, dass jeder Buchstabe höchstens einmal untersucht wird. Für frühere Boyer-Moore-Versionen haben sie bewiesen, dass jeder Brief höchstens dreimal und später höchstens zweimal geprüft wird, und diese Beweise waren stärker involviert (siehe Zitate in Papierform). Daher sehe ich auch einen didaktischen Wert darin, diese Variante zu präsentieren / zu studieren.

In der Arbeit beschreiben wir auch weitere Variationen, die auf Effizienz ausgerichtet sind und gleichzeitig die theoretischen Garantien lockern. Es ist eine kurze Arbeit und das Material sollte meiner Meinung nach für einen durchschnittlichen Abiturienten verständlich sein.

Unser Hauptziel war es, andere auf diese Version aufmerksam zu machen, die sie weiter verbessern können. Die Suche nach Zeichenfolgen hat so viele Variationen, und wir allein können unmöglich an alle denken, bei denen diese Idee Vorteile bringen könnte. (Fester Text und sich änderndes Muster, fester Muster, anderer Text, Vorverarbeitung möglich / nicht möglich, parallele Ausführung, Finden übereinstimmender Teilmengen in großen Texten, Zulassen von Fehlern, Beinahe-Übereinstimmungen usw. usw.)

Der schnellste Suchalgorithmus für Teilzeichenfolgen hängt vom Kontext ab:

1. die Alphabetgröße (zB DNA vs Englisch)
2. die Nadellänge

Das 2010 erschienene Papier "The Exact String Matching Problem: Eine umfassende experimentelle Bewertung" enthält Tabellen mit Laufzeiten für 51 Algorithmen (mit unterschiedlichen Alphabetgrößen und Nadellängen), sodass Sie den besten Algorithmus für Ihren Kontext auswählen können.

Alle diese Algorithmen verfügen hier über C-Implementierungen sowie eine Testsuite:

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

Eine wirklich gute Frage. Fügen Sie einfach ein paar winzige Teile hinzu ...

1. Jemand sprach über DNA-Sequenz-Matching. Für die DNA-Sequenz erstellen wir normalerweise eine Datenstruktur (z. B. Suffix-Array, Suffix-Baum oder FM-Index) für den Heuhaufen und passen viele Nadeln daran an. Dies ist eine andere Frage.

2. Es wäre wirklich großartig, wenn jemand verschiedene Algorithmen vergleichen möchte. Es gibt sehr gute Benchmarks für die Komprimierung und die Konstruktion von Suffix-Arrays, aber ich habe keinen Benchmark für die Zeichenfolgenübereinstimmung gesehen. Potenzielle Heuhaufenkandidaten könnten aus dem SACA-Benchmark stammen .

3. Vor ein paar Tagen habe ich die Boyer-Moore-Implementierung von der von Ihnen empfohlenen Seite aus getestet (BEARBEITEN: Ich benötige einen Funktionsaufruf wie memmem (), aber es ist keine Standardfunktion, daher habe ich beschlossen, sie zu implementieren). Mein Benchmarking-Programm verwendet zufälligen Heuhaufen. Es scheint, dass die Boyer-Moore-Implementierung auf dieser Seite zeitweise schneller ist als glibcs ​​memmem () und Macs strnstr (). Falls Sie interessiert sind, ist die Umsetzung hier und der Benchmarking - Code ist hier . Dies ist definitiv kein realistischer Maßstab, aber es ist ein Anfang.

Ich weiß, dass es eine alte Frage ist, aber die meisten schlechten Schichttabellen bestehen aus einzelnen Zeichen. Wenn es für Ihren Datensatz sinnvoll ist (z. B. wenn es sich um geschriebene Wörter handelt) und wenn Sie über genügend Speicherplatz verfügen, können Sie eine dramatische Beschleunigung erzielen, indem Sie eine schlechte Verschiebungstabelle aus n-Gramm anstelle einzelner Zeichen verwenden.

Verwenden Sie stdlib strstr:

char *foundit = strstr(haystack, needle);

Es war sehr schnell, ich brauchte nur 5 Sekunden, um zu tippen.

Hier ist die Suchimplementierung von Python , die im gesamten Kern verwendet wird. Die Kommentare zeigen an, dass eine komprimierte Boyer-Moore-Delta-1-Tabelle verwendet wird .

Ich habe selbst ziemlich ausführlich mit der Suche nach Zeichenfolgen experimentiert, aber es war für mehrere Suchzeichenfolgen. Assembly-Implementierungen von Horspool und Bitap können sich häufig gegen Algorithmen wie Aho-Corasick für niedrige Musterzahlen behaupten .

Ein schnellerer strchrAlgorithmus "Suche nach einem einzelnen übereinstimmenden Zeichen" (ala ).

Wichtige Notizen:

• Diese Funktionen verwenden einen "Anzahl / Anzahl von (führenden | nachfolgenden) Nullen" gcc-Compiler __builtin_ctz. Diese Funktionen sind wahrscheinlich nur auf Computern schnell, die über Anweisungen verfügen, die diese Operation ausführen (z. B. x86, ppc, arm).

• Diese Funktionen setzen voraus, dass die Zielarchitektur nicht ausgerichtete 32- und 64-Bit-Ladevorgänge ausführen kann. Wenn Ihre Zielarchitektur dies nicht unterstützt, müssen Sie eine Startlogik hinzufügen, um die Lesevorgänge ordnungsgemäß auszurichten.

• Diese Funktionen sind prozessorneutral. Wenn die Ziel-CPU über Vektoranweisungen verfügt, können Sie dies möglicherweise (viel) besser machen. Die folgende strlenFunktion verwendet beispielsweise SSE3 und kann trivial so geändert werden, dass die gescannten Bytes XOR-verknüpft werden, um nach einem anderen Byte als zu suchen 0. Benchmarks auf einem 2,66-GHz-Core-2-Laptop unter Mac OS X 10.6 (x86_64):

  • 843,433 MB / s für strchr
  • 2656.742 MB / s für findFirstByte64
  • 13094,479 MB / s für strlen

... eine 32-Bit-Version:

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

... und eine 64-Bit-Version:

#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 Das OP weist in den Kommentaren darauf hin, dass diese Lösung einen "unüberwindbaren Fehler" aufweist:

Es kann über das gesuchte Byte oder den Null-Terminator hinaus lesen, der ohne Leseberechtigung auf eine nicht zugeordnete Seite oder Seite zugreifen kann. Sie können große Lesevorgänge in Zeichenfolgenfunktionen nur verwenden, wenn sie ausgerichtet sind.

Dies ist technisch richtig, gilt jedoch für praktisch jeden Algorithmus, der mit Blöcken arbeitet, die größer als ein einzelnes Byte sind, einschließlich der vom OP in den Kommentaren vorgeschlagenen Methode :

Eine typische strchrImplementierung ist nicht naiv, aber wesentlich effizienter als das, was Sie angegeben haben. Am Ende finden Sie den am häufigsten verwendeten Algorithmus: http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

Es hat auch wirklich nichts mit der Ausrichtung an sich zu tun . Dies könnte zwar das Verhalten verursachen, das bei den meisten gängigen Architekturen diskutiert wird. Dies hat jedoch mehr mit Details der Implementierung der Mikroarchitektur zu tun. Wenn der nicht ausgerichtete Lesevorgang eine 4K-Grenze überschreitet (wiederum typisch), verursacht dieser Lesevorgang ein Programm Beenden des Fehlers, wenn die nächste 4K-Seitengrenze nicht zugeordnet ist.

Dies ist jedoch kein "Fehler" in dem in der Antwort angegebenen Algorithmus. Dieses Verhalten liegt daran, dass Funktionen ein Argument mögen strchrund strlennicht akzeptieren length, um die Größe der Suche zu begrenzen. Die Suche char bytes[1] = {0x55};, die für die Zwecke unserer Diskussion zufällig ganz am Ende einer 4K-VM-Seitengrenze platziert wird und deren nächste Seite nicht zugeordnet ist, mit strchr(bytes, 0xAA)(wo strchrsich jeweils eine Byte-Implementierung befindet) stürzt genau ab gleicher Weg. Das Gleiche gilt für strchrverwandte Cousins strlen.

Ohne ein lengthArgument gibt es keine Möglichkeit zu sagen, wann Sie vom Hochgeschwindigkeitsalgorithmus zu einem Byte-für-Byte-Algorithmus zurückkehren sollten. Ein viel wahrscheinlicherer "Fehler" wäre, "über die Größe der Zuordnung hinaus" zu lesen, was technisch undefined behaviorzu den verschiedenen C-Sprachstandards führt und von so etwas als Fehler gekennzeichnet würde valgrind.

Zusammenfassend lässt sich sagen, dass alles, was mit Blöcken größer als Byte arbeitet, um schneller zu werden, wie dies der Antwortcode tut und der Code vom OP angegeben wird, aber eine bytegenaue Lesesemantik aufweisen muss, wahrscheinlich "fehlerhaft" ist, wenn es kein lengthArgument dafür gibt Kontrollieren Sie die Eckfälle des "letzten Lesevorgangs".

Der Code in dieser Antwort ist ein Kernel, mit dem das erste Byte in einem natürlichen CPU-Wortgrößenblock schnell gefunden werden kann, wenn die Ziel-CPU einen schnellen ctzBefehl hat. Es ist trivial, Dinge hinzuzufügen, wie sicherzustellen, dass nur korrekt ausgerichtete natürliche Grenzen oder irgendeine Form von lengthBindung funktionieren , die es Ihnen ermöglichen würden, aus dem Hochgeschwindigkeitskern heraus und zu einer langsameren Byte-für-Byte-Prüfung zu wechseln.

Das OP sagt auch in den Kommentaren:

Die ctz-Optimierung macht nur für die O (1) -Schwanzoperation einen Unterschied. Es könnte die Leistung mit winzigen Saiten verbessern (zB strchr("abc", 'a');aber sicherlich nicht mit Saiten größerer Größe).

Ob diese Aussage wahr ist oder nicht, hängt stark von der jeweiligen Mikroarchitektur ab. Bei Verwendung des kanonischen 4-stufigen RISC-Pipeline-Modells ist dies mit ziemlicher Sicherheit der Fall. Es ist jedoch äußerst schwer zu sagen, ob dies für eine moderne, nicht in Ordnung befindliche superskalare CPU zutrifft, bei der die Kerngeschwindigkeit die Speicher-Streaming-Geschwindigkeit völlig in den Schatten stellen kann. In diesem Fall ist es nicht nur plausibel, sondern durchaus üblich, dass es eine große Lücke in der "Anzahl der Befehle, die zurückgezogen werden können" im Verhältnis zu "der Anzahl der Bytes, die gestreamt werden können" gibt, so dass Sie "die" haben Anzahl der Anweisungen, die für jedes gestreamte Byte zurückgezogen werden können ". Wenn dies groß genug ist, kann der ctz+ Shift-Befehl "kostenlos" ausgeführt werden.

Suchen Sie einfach nach "schnellster strstr" und wenn Sie etwas Interessantes sehen, fragen Sie mich einfach.

Meiner Ansicht nach legen Sie sich selbst zu viele Einschränkungen auf (ja, wir alle wollen bei maximalem Sucher sublinear linear), aber es braucht einen echten Programmierer, um einzugreifen. Bis dahin denke ich, dass der Hash-Ansatz einfach eine raffinierte Lösung ist ( gut verstärkt durch BNDM für kürzere 2..16 Muster).

Nur ein kurzes Beispiel:

Doing Suche nach Muster (32bytes) in String (206908949bytes) as-one-line ... Überspringen-Leistung (größer-the-besser): 3041%, 6.801.754 Überspringen / Iterationen Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade Leistung: 3483KB / Uhr

Doing Suche nach Muster (32bytes) in String (206908949bytes) as-one-line ... Überspringen-Leistung (größer-the-besser): 1.554%, 13.307.181 Überspringen / Iterationen Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg Leistung: 2434KB / Uhr

Suche nach Muster (32 Byte) in String (206908949 Byte) als einzeilige ... Sprungleistung (größer, desto besser): 129%, 160239051 überspringt / iteriert Zwei-Wege-Hits / Zwei-Wege-Uhren: 0/816 Zwei -Wegleistung : 247KB / Uhr

Sanmayce,
Grüße

Der Zwei-Wege-Algorithmus, den Sie in Ihrer Frage erwähnen (was übrigens unglaublich ist!), Wurde kürzlich verbessert, um effizient mit Multibyte-Wörtern gleichzeitig zu arbeiten: Optimal Packed String Matching .

Ich habe nicht das ganze Papier gelesen, aber es scheint, dass sie sich darauf verlassen, dass ein paar neue, spezielle CPU-Anweisungen (z. B. in SSE 4.2 enthalten) O (1) für ihren Anspruch auf Zeitkomplexität sind. Wenn sie jedoch nicht verfügbar sind, können sie dies simulieren Sie sie in O-Zeit (log log w) für w-Bit-Wörter, die nicht schlecht klingen.

Sie könnten beispielsweise 4 verschiedene Algorithmen implementieren. Führen Sie alle M Minuten (empirisch zu bestimmen) alle 4 auf aktuellen realen Daten aus. Sammeln Sie Statistiken über N Läufe (auch TBD). Verwenden Sie dann nur den Gewinner für die nächsten M Minuten.

Protokollieren Sie Statistiken zu Wins, damit Sie Algorithmen, die niemals gewinnen, durch neue ersetzen können. Konzentrieren Sie die Optimierungsbemühungen auf die erfolgreichste Routine. Achten Sie nach Änderungen an der Hardware, Datenbank oder Datenquelle besonders auf die Statistiken. Fügen Sie diese Informationen nach Möglichkeit in das Statistikprotokoll ein, damit Sie sie nicht anhand des Datums- / Zeitstempels des Protokolls ermitteln müssen.

Ich habe kürzlich ein nützliches Tool entdeckt, um die Leistung der verschiedenen verfügbaren Algen zu messen: http://www.dmi.unict.it/~faro/smart/index.php

Vielleicht finden Sie es nützlich. Wenn ich mich kurz mit dem Suchalgorithmus für Teilzeichenfolgen befassen müsste, würde ich mich für Knuth-Morris-Pratt entscheiden.

Möglicherweise möchten Sie auch verschiedene Benchmarks mit verschiedenen Arten von Zeichenfolgen haben, da dies einen großen Einfluss auf die Leistung haben kann. Die Algen werden unterschiedliche Leistungen erbringen, basierend auf der Suche nach natürlicher Sprache (und selbst hier kann es aufgrund der unterschiedlichen Morphologien immer noch feinkörnige Unterscheidungen geben), DNA-Strings oder zufälligen Strings usw.

Die Alphabetgröße spielt in vielen Algen eine Rolle, ebenso wie die Nadelgröße. Zum Beispiel kann Horspool aufgrund der unterschiedlichen Alphabetgröße gut mit englischem Text umgehen, aber schlecht mit DNA, was der Regel für schlechte Charaktere das Leben schwer macht. Die Einführung des Good-Suffix erleichtert dies erheblich.

Ich weiß nicht, ob es das absolut Beste ist, aber ich habe gute Erfahrungen mit Boyer-Moore gemacht .

Dies beantwortet die Frage nicht direkt, aber wenn der Text sehr groß ist, wie wäre es, wenn Sie ihn in überlappende Abschnitte (Überlappung um eine Musterlänge) unterteilen und dann gleichzeitig die Abschnitte mithilfe von Threads durchsuchen. In Bezug auf den schnellsten Algorithmus ist Boyer-Moore-Horspool meiner Meinung nach einer der schnellsten, wenn nicht der schnellste unter den Varianten von Boyer-Moore. Ich habe in diesem Thema einige Boyer-Moore-Varianten (deren Namen ich nicht kenne) veröffentlicht. Algorithmus schneller als BMH-Suche (Boyer-Moore-Horspool) .

Das schnellste ist derzeit EPSM von S. Faro und OM Kulekci. Siehe http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=EPSM&code=epsm

"Exact Packed String Matching" optimiert für SIMD SSE4.2 (x86_64 und aarch64). Es arbeitet stabil und am besten auf allen Größen.

Die Site, auf die ich verlinkt habe, vergleicht 199 schnelle String-Suchalgorithmen, wobei die üblichen (BM, KMP, BMH) ziemlich langsam sind. EPSM übertrifft alle anderen, die hier auf diesen Plattformen erwähnt werden. Es ist auch das Neueste.