Welcher String-Suchalgorithmus ist eigentlich der schnellste?

Dies hängt von der Art der Suche ab, die Sie durchführen möchten. Jeder der Algorithmen funktioniert besonders gut für bestimmte Suchtypen, aber Sie haben den Kontext Ihrer Suche nicht angegeben.

Hier einige typische Gedanken zu Suchtypen:

• Boyer-Moore: arbeitet mit einer Voranalyse des Musters und einem Vergleich von rechts nach links. Wenn eine Nichtübereinstimmung auftritt, wird die anfängliche Analyse verwendet, um zu bestimmen, wie weit das Muster w.r.t. verschoben werden kann. der gesuchte Text. Dies funktioniert besonders gut bei langen Suchmustern. Insbesondere kann es sublinear sein, da Sie nicht jedes einzelne Zeichen Ihres Textes lesen müssen.

• Knuth-Morris-Pratt: Analysiert das Muster auch vorab , versucht jedoch, alles, was bereits im ersten Teil des Musters gefunden wurde, wiederzuverwenden, um zu vermeiden, dass dies erneut abgeglichen werden muss. Dies kann recht gut funktionieren, wenn Ihr Alphabet klein ist (z. B. DNA-Basen), da Sie eine höhere Wahrscheinlichkeit haben, dass Ihre Suchmuster wiederverwendbare Untermuster enthalten.

• Aho- Corasick: Benötigt viel Vorverarbeitung, aber für eine Reihe von Mustern. Wenn Sie wissen, dass Sie immer wieder nach denselben Suchmustern suchen, ist dies viel besser als die anderen, da Sie Muster nur einmal und nicht einmal pro Suche analysieren müssen.

Daher gibt es, wie in CS üblich, keine eindeutige Antwort auf das insgesamt beste . Es geht vielmehr darum, das richtige Werkzeug für den jeweiligen Job auszuwählen.

Ein weiterer Hinweis zu Ihrer Argumentation im schlimmsten Fall: Überlegen Sie, welche Arten von Suchen erforderlich sind, um diesen schlimmsten Fall zu erstellen, und überlegen Sie gründlich, ob Diese sind in Ihrem Fall wirklich relevant. Beispielsweise beruht die O(mn) Worst-Case-Komplexität des Boyer-Moore-Algorithmus auf einem Suchmuster und einem Text, die jeweils nur ein Zeichen verwenden (wie das Finden von in aaaaaaaaaaaaaaaaaaaaa) – Müssen Sie für solche Suchvorgänge wirklich schnell sein?

Kommentare

• Ich habe das gesamte englische Alphabet oder so zu verwenden und habe die Frage aktualisiert. Tut mir leid, dass ich beim Betteln nicht damit angefangen habe.
• Und ja, ich muss schnell sein, auch für Suchanfragen wie das
• können Sie bitte auf Z ‚ s Algorithmus und Manachar auch erläutern?

Obwohl ich etwas spät dran bin, um diese Frage zu beantworten, denke ich, dass Z-Algorithm viel schneller ist als alle seine Gegenstücke.Die Komplexität im ungünstigsten Fall ist O (m + n) und es ist keine Vorverarbeitung des Musters / Textes erforderlich. Im Vergleich zu den anderen Algorithmen ist es auch sehr einfach zu codieren.

Es funktioniert folgendermaßen.

Beispielsweise gibt es eine Zeichenfolge S ="abaaba". Wir sollen z(i) -Werte für i=0 to len(S)-1 finden. Bevor ich auf die Erklärung eingehe, möchte ich zunächst einige Definitionen festlegen.

z(i) = no. Anzahl der Zeichen des Präfixes von S, das dem Präfix von s(i) entspricht.

s(i) = ith Suffix von S.

Das Folgende ist das s(i) -Werte für s = "abaaba".

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

Die z-Werte sind jeweils

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

Ausführliche Informationen zum Algorithmus finden Sie unter den folgenden Links.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Jetzt ist O (N) erforderlich, um alle z -Werte ohne Vorverarbeitungsaufwand zu finden. Man würde sich jetzt fragen, wie man diese Logik verwenden kann, um Muster in einer bestimmten Zeichenfolge abzugleichen.

Sehen wir uns ein Beispiel an. Muster (P): aba, Text (T): aacbabcabaad.

Geben Sie dies in die Form P $ T ein. ($ – Jedes Zeichen, das weder in einem Muster noch in einem Text vorkommt. Ich werde gleich auf die Bedeutung von $ eingehen.)

P$T = aba$aacbabcabaad

Wir kennen len(P) = 3.

Alle z-Werte von P$T sind

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

Nun, welche z(i) = len(P). Ans = 11. Unser Muster ist also bei Ans-len(P)-1 = 7 vorhanden. -1 steht für $ Zeichen.

Warum $ oder Ein solcher Sondercharakter ist wichtig. Betrachten Sie P = "aaa" und T = "aaaaaaa". Ohne das Sonderzeichen haben alle z(i) inkrementelle Werte. Die Position des Musters im Text kann immer noch mit den folgenden Formeln gefunden werden:

Bedingung: z(i)> = len(P) und Position: Ans-len(P). Aber der Zustand wird in diesem Fall etwas schwierig und verwirrend. Ich persönlich bevorzuge die Spezialcharaktertechnik.

Kommentare

• Können Sie es hier selbst erklären? Links zu externen Sites können zur Ausarbeitung verwendet werden, aber der Kern einer Antwort sollte in der Antwort selbst liegen, anstatt einem Link zu einer anderen Site folgen zu müssen.
• Der Z-Algorithmus ist im Grunde der gleiche wie kmp. Ich bezweifle, dass es viel schneller geht.
• Ich stimme @ThomasAhle zu. Das Berechnen von z ist eine Vorverarbeitung. ‚ ist jedoch eine gute Erklärung. Aufgrund dieser Antwort habe ich eine O(n) Methode zum Konvertieren von der KMP-Vorverarbeitung in die Z-Vorverarbeitung eingerichtet. Hier

Verwenden Sie inhaltsadressierbarer Speicher , implementiert in Software in Form einer virtuellen Adressierung (Zeigen von Buchstaben auf Buchstaben).

Es ist ein bisschen überflüssig für einen durchschnittlichen String-Matching-Algorithmus.

CAM kann eine große Anzahl von Mustern gleichzeitig mit bis zu 128-Buchstaben-Mustern abgleichen (wenn sie ASCII sind; wenn sie nur Unicode 64 sind). Und es ist ein Aufruf pro Buchstabenlänge in der Zeichenfolge, mit der Sie übereinstimmen möchten, und ein zufälliger Lesevorgang aus dem Speicher pro Länge der maximalen Musterlänge. Wenn Sie also eine Zeichenfolge mit 100.000 Buchstaben mit bis zu 90.000.000 Mustern gleichzeitig analysieren würden (was ungefähr 128 GiB erfordern würde, um eine Anzahl so großer Muster zu speichern), wären 12.800.000 zufällige Lesevorgänge aus dem RAM erforderlich, sodass dies in 1 ms geschehen würde / p>

So funktioniert die virtuelle Adressierung.

Wenn ich mit 256 Startadressen beginne, die den ersten Buchstaben darstellen, zeigen diese Buchstaben auf 256 der nächsten Buchstaben. Wenn ein Muster ist nicht vorhanden, Sie speichern es nicht.

Wenn ich also weiterhin Buchstaben mit Buchstaben verknüpfe, ist es so, als ob 128 virtuelle Adressierungsscheiben auf virtuelle Adressierung verweisen.

Das wird Arbeite —, aber um 900.000.000 gleichzeitig übereinstimmende Muster zu erhalten, gibt es einen letzten Trick, den du hinzufügen kannst — und der nutzt von der Tatsache, dass Sie mit einer Menge Wiederverwendung dieser Buchstabenpuffer beginnen, aber später streut es heraus.Wenn Sie den Inhalt auflisten, anstatt alle 256 Zeichen zuzuweisen, verlangsamt er sich sehr wenig und Sie erhalten eine 100-fache Kapazitätserhöhung, da Sie im Grunde genommen nur 1 Buchstaben in jedem Buchstabenzeigerpuffer verwenden (den ich synchronisiert habe). Escape „).

Wenn Sie eine Zeichenfolgenübereinstimmung mit dem nächsten Nachbarn erhalten möchten, werden viele davon parallel ausgeführt und in einer Hierarchie gesammelt, sodass Sie Ihren Fehler unvoreingenommen verteilen, wenn Sie dies versuchen nächster Nachbar mit nur einem, dann sind Sie „zum Anfang des Baums voreingenommen.

Kommentare

• @MagnusRobertCarlWoot, vorausgesetzt, Sie haben das gleiche gavatar as roucer81, es ist entweder ein astronomischer Zufall einer Hash-Code-Kollision oder Sie haben dieselbe E-Mail-Adresse. Wenn Sie dieselbe Person hinter beiden Konten haben, sollten Sie das “ Kontaktformular “ verwenden, um sie zusammenzuführen, damit Sie die richtige Gutschrift erhalten den Ruf, der durch positive Bewertungen dieser Antwort gewonnen wurde.