webentwicklung-frage-antwort-db.com.de

Was ist der schnellste Teilstringsuchalgorithmus?

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

  • Nadel (Muster) und Heuhaufen (zu suchender Text) sind beide nullterminierte Strings im C-Stil. Es werden keine Längenangaben gemacht. Bei Bedarf muss es berechnet werden.
  • Die Funktion sollte einen Zeiger auf die erste Übereinstimmung zurückgeben oder NULL, wenn 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 Zuweisungsfehler haben muss (und die Leistung in der Fallback-Pflege trägt somit zur Leistung im ungünstigsten Fall bei).
  • Die Implementierung soll in C erfolgen, obwohl auch eine gute Beschreibung des Algorithmus (oder eines Links zu einem solchen) ohne Code in Ordnung ist.

... sowie was ich unter "am schnellsten" verstehe:

  • Deterministische O(n) wobei n = Heuhaufenlänge. (Es kann jedoch möglich sein, Ideen aus Algorithmen zu verwenden, die normalerweise O(nm) sind (z. B. Rolling Hash), wenn sie mit einem robusteren Algorithmus kombiniert werden, um deterministische O(n) Ergebnisse zu erzielen.).
  • Nie funktioniert (messbar; ein paar Takte für if (!needle[1]) usw. sind in Ordnung) schlechter als der naive Brute-Force-Algorithmus, insbesondere bei sehr kurzen Nadeln, die wahrscheinlich der häufigste Fall sind. (Bedingungsloser hoher Overhead für die Vorverarbeitung ist schlecht, ebenso wie der Versuch, den linearen Koeffizienten für pathologische Nadeln auf Kosten der wahrscheinlichen Nadeln zu verbessern.)
  • Bei einer beliebigen Nadel und einem beliebigen Heuhaufen vergleichbare oder bessere Leistung (nicht schlechter als 50% längere Suchzeit) im Vergleich zu jedem anderen weit verbreiteten Algorithmus.
  • Abgesehen von diesen Bedingungen lasse ich die Definition von "am schnellsten" unbefristet. Eine gute Antwort sollte erklären, warum Sie den Ansatz für "am schnellsten" halten.

Meine aktuelle Implementierung läuft ungefähr 10% langsamer bis 8-mal schneller (je nach Eingabe) als die Implementierung von Two-Way durch 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 auf einmal 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 dem Heuhaufen heraus/neue Bytes hinein . Jedes Byte des Heuhaufens wird genau einmal gelesen und gegen 0 (Ende des Strings) und einen 16- oder 32-Bit-Vergleich geprüft.
  • Verwenden Sie für Nadeln mit einer Länge> 4 den Zwei-Wege-Algorithmus mit einer fehlerhaften 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 bedeuten würde, behalte ich ein Bitarray (32 Byte) bei, das angibt, welche Einträge in der Verschiebungstabelle initialisiert werden. Nicht gesetzte Bits entsprechen Bytewerten, die niemals in der Nadel vorkommen und für die eine Verschiebung um die gesamte Nadellänge möglich ist.

Die großen Fragen, die ich noch habe, sind:

  • Gibt es eine Möglichkeit, die schlechte Schichttabelle besser zu nutzen? Boyer-Moore nutzt es am besten, indem er rückwärts (von rechts nach links) scannt, aber Zwei-Wege-Scannen erfordert einen Scan von links nach rechts.
  • Die einzigen zwei brauchbaren Kandidatenalgorithmen, die ich für den allgemeinen Fall gefunden habe (keine nicht ausreichenden Speicherkapazitäten oder quadratischen Leistungsbedingungen), sind bidirektional und String Matching on Ordered Alphabets . Aber gibt es leicht erkennbare Fälle, in denen unterschiedliche Algorithmen optimal wären? Sicher könnten viele der O(m) (wobei m die Nadellänge ist) in Raumalgorithmen für m<100 Oder so verwendet werden. Es wäre auch möglich, Algorithmen zu verwenden, die im ungünstigsten 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 gut geformtes UTF-8 sind? (Bei Zeichen unterschiedlicher Bytelänge erfordert die Formgebung einige Anforderungen an die Ausrichtung der Zeichenfolgen zwischen Nadel und Heuhaufen und ermöglicht automatische Verschiebungen von 2 bis 4 Bytes, wenn ein nicht übereinstimmendes Kopfbyte auftritt. Aber verschaffen Ihnen diese Einschränkungen viel/alles, was darüber hinausgeht Maximale Suffixberechnungen, gute Suffixverschiebungen etc. gibt es schon mit diversen Algorithmen?)

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

157
R..

Erstellen Sie eine Testbibliothek mit möglichen Nadeln und Heuhaufen. Profilieren Sie die Tests mit mehreren Suchalgorithmen, einschließlich Brute Force. Wählen Sie die aus, die mit Ihren Daten am besten funktioniert.

Boyer-Moore verwendet eine schlechte Zeichentabelle mit einer guten Suffixtabelle.

Boyer-Moore-Horspool verwendet eine schlechte Zeichentabelle.

Knuth-Morris-Pratt verwendet eine Teilübereinstimmungstabelle.

Rabin-Karp verwendet laufende Hashes.

Sie alle tauschen Overhead-Kosten aus, um Vergleiche in unterschiedlichem Maße zu reduzieren, 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. Bei sehr kurzen Nadeln kann rohe Gewalt 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 gäbe, wäre dieser 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 eine Grafik mit einem Bereich von kürzeren bis längeren Eingaben auf jeder Achse sein. Wenn Sie jeden Algorithmus in einem solchen Diagramm darstellen, hat jeder eine andere Signatur. Einige Algorithmen leiden unter vielen Wiederholungen im Muster, was sich auf Verwendungen wie das Suchen nach Genen auswirken kann. Einige andere Faktoren, die sich auf die Gesamtleistung auswirken, sind die mehrmalige Suche nach demselben Muster und die gleichzeitige Suche nach verschiedenen Mustern.

Wenn ich ein Beispielset brauchte, würde ich wahrscheinlich eine Site wie Google oder Wikipedia entfernen und dann den HTML-Code von allen Ergebnisseiten entfernen. Geben Sie für eine Suchsite ein Wort ein und verwenden Sie dann einen der vorgeschlagenen Suchbegriffe. Wählen Sie gegebenenfalls einige andere Sprachen aus. Bei der Verwendung von Webseiten wären alle Texte kurz bis mittelgroß, führen Sie also genügend Seiten zusammen, um längere Texte zu erhalten. Sie können auch gemeinfreie Bücher, juristische Aufzeichnungen und andere große Textmengen finden. Oder generieren Sie einfach zufälligen Inhalt, indem Sie Wörter aus einem Wörterbuch auswählen. Bei der Profilerstellung müssen Sie jedoch die Art des zu durchsuchenden Inhalts testen. Verwenden Sie daher nach Möglichkeit Beispiele aus der realen Welt.

Ich ließ kurz und lang vage. Für die Nadel stelle ich mir kurz unter 8 Zeichen, mittel unter 64 Zeichen und lang unter 1 KB vor. Für den Heuhaufen stelle ich mir kurz unter 2 ^ 10, mittel unter 2 ^ 20 und lang bis zu 2 ^ 30 Zeichen vor.

37
drawnonward

Veröffentlicht im Jahr 2011, ich glaube, es kann sehr gut sein, die "Einfache Echtzeit-Konstante-Raum-String-Matching" Algorithmus von Dany Breslauer, Roberto Grossi und Filippo Mignosi.

Aktualisieren:

2014 haben die Autoren diese Verbesserung veröffentlicht: Auf dem Weg zu einer optimalen Übereinstimmung der gepackten Zeichenfolgen .

25
Mehrdad

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 Overheads, der Zeit und des Platzbedarfs vor der Verarbeitung. Kein einziger Algorithmus ist in allen Fällen optimal oder praktisch.

Wenn Sie einen bestimmten Algorithmus für die Suche nach Zeichenfolgen entwerfen möchten, ignorieren Sie den Rest meiner Ausführungen. Wenn Sie eine allgemeine Routine für die Suche nach Zeichenfolgen entwickeln möchten, versuchen Sie Folgendes:

Überprüfen Sie einige Zeit lang die spezifischen Stärken und Schwächen der Algorithmen, 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 Zeichenfolgensuchen abdecken, an denen Sie interessiert sind. Erstellen Sie dann einen Front-End-Suchselektor auf der Grundlage einer Klassifikatorfunktion, um den besten Algorithmus für die angegebenen Eingaben zu ermitteln. Auf diese Weise können Sie den effizientesten Algorithmus verwenden, um die Arbeit auszuführen. Dies ist besonders effektiv, wenn ein Algorithmus für bestimmte Suchvorgänge sehr gut ist, sich jedoch nur schlecht verschlechtert. Beispielsweise ist Brute Force bei Nadeln der Länge 1 wahrscheinlich am besten, nimmt jedoch mit zunehmender Nadellänge schnell ab, wodurch der sustik-moore-Algorithmus effizienter werden kann (über kleine Alphabete). Bei längeren Nadeln und größeren Alphabeten sind die Algorithmen KMP oder Boyer-Moore möglicherweise besser. Dies sind nur Beispiele, um eine mögliche Strategie zu veranschaulichen.

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

Jeder Suchalgorithmus ist in verschiedenen Varianten erhältlich, die die Leistung erheblich beeinträchtigen können. Dies wird beispielsweise in diesem Artikel veranschaulicht.

Vergleichen Sie Ihren Service anhand eines Benchmarks, 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 Durchführung sehr gute Ergebnisse erzielen.

23
NealB

Ich war überrascht, dass unser technischer Bericht in dieser Diskussion zitiert wurde. Ich bin einer der Autoren des Algorithmus, der oben Sustik-Moore genannt wurde. (Diesen Begriff haben wir 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. Bei früheren Boyer-Moore-Versionen wurde nachgewiesen, dass jeder Buchstabe höchstens dreimal und später höchstens zweimal geprüft wurde und dass diese Beweise eine größere Rolle spielten (siehe Zitate in Papierform). Daher sehe ich auch einen didaktischen Wert darin, diese Variante vorzustellen/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 Abhandlung 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 können uns unmöglich alle vorstellen, bei denen diese Idee Vorteile bringen könnte. (Feste Texte und sich ändernde Muster, festes Muster, anderer Text, Vorverarbeitung möglich/nicht möglich, parallele Ausführung, Finden passender Teilmengen in großen Texten, Zulassen von Fehlern, Annähern an Übereinstimmungen usw. usw.)

18
Matyas

Der schnellste Teilstringsuchalgorithmus hängt vom Kontext ab:

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

Die Veröffentlichung von 2010 "Das Problem der exakten Zeichenfolgenübereinstimmung: eine umfassende experimentelle Auswertung" 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 haben C-Implementierungen sowie eine Testsuite, hier:

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

15
JDiMatteo

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

4
Timothy Jones

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

  1. Jemand sprach über DNA-Sequenz-Matching. Bei DNA-Sequenzen müssen wir jedoch normalerweise eine Datenstruktur (z. B. Suffix-Array, Suffix-Baum oder FM-Index) für den Heuhaufen erstellen und mit vielen Nadeln abgleichen. Das 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 den Aufbau von Suffix-Arrays, aber ich habe keinen Benchmark für den String-Matching gesehen. Potenzielle Heuhaufen-Kandidaten könnten aus dem SACA-Benchmark stammen.

  3. Vor ein paar Tagen habe ich die Boyer-Moore-Implementierung von der Seite aus getestet, die Sie empfohlen haben (BEARBEITEN: Ich brauche 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 um ein Vielfaches schneller ist als die von glibc memmem () und strnstr () für Mac. Falls Sie interessiert sind, finden Sie die Implementierung hier und den Benchmarking-Code hier . Dies ist definitiv kein realistischer Maßstab, aber es ist ein Anfang.

4
user172818

Ich habe kürzlich ein Nizza-Tool entdeckt, mit dem die Leistung der verschiedenen verfügbaren Algen gemessen werden kann: http://www.dmi.unict.it/~faro/smart/index.php

Vielleicht finden Sie es nützlich. Wenn ich mich kurz mit dem Teilstringsuchalgorithmus befassen muss, würde ich mich auch für Knuth-Morris-Pratt entscheiden.

3
Sandeep Giri

Hier ist Pythons Suchimplementierung , das im gesamten Kern verwendet wird. Aus den Kommentaren geht hervor, dass eine komprimierte Boyer-Moore-Delta-1-Tabelle verwendet wird.

Ich habe einige ziemlich umfangreiche Experimente mit der Suche nach Zeichenfolgen durchgeführt, aber es war für mehrere Suchzeichenfolgen. Assembly-Implementierungen von Horspool und Bitap können sich oft gegen Algorithmen wie Aho-Corasick für niedrige Musterzahlen behaupten.

3
Matt Joiner

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

Protokollieren Sie die Gewinnstatistiken, damit Sie Algorithmen, die niemals gewinnen, durch neue ersetzen können. Konzentrieren Sie Ihre Optimierungsbemühungen auf die beste Routine. Achten Sie besonders auf die Statistiken, nachdem Sie Änderungen an der Hardware, der Datenbank oder der Datenquelle vorgenommen haben. Nehmen Sie diese Informationen, wenn möglich, in das Statistikprotokoll auf, damit Sie sie nicht anhand des Datums-/Zeitstempels des Protokolls ermitteln müssen.

3
Guy Gordon

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

Ich habe das ganze Papier noch nicht gelesen, aber es scheint, dass sie auf ein paar neue, spezielle CPU-Anweisungen angewiesen sind (die zB in SSE 4.2 enthalten sind), die O(1) sind Komplexitätsanspruch, aber wenn sie nicht verfügbar sind, können sie sie in O-Zeit (log log w) für w-Bit-Wörter simulieren, was nicht allzu schlecht klingt.

3
j_random_hacker

Verwenden Sie stdlib strstr:

char *foundit = strstr(haystack, needle);

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

2
Conrad Meyer

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

Die Alphabetgröße spielt bei vielen Algen eine Rolle, ebenso wie die Nadelgröße. Zum Beispiel ist Horspool gut für englischen Text, aber schlecht für DNA aufgrund der unterschiedlichen Alphabetgröße, was der Regel des schlechten Charakters 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.

0

Dies beantwortet die Frage nicht direkt, aber wenn der Text sehr groß ist, wie wäre es, ihn in überlappende Abschnitte zu unterteilen (Überlappung durch eine Musterlänge), dann durchsuchen Sie die Abschnitte gleichzeitig mit Hilfe von Threads. 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 ein paar Boyer-Moore-Varianten (deren Namen ich nicht kenne) in diesem Thema gepostet Algorithmus schneller als BMH-Suche (Boyer-Moore-Horspool) .

0
Roy Alilin