Vergleich zwischen Aho-Corasick-Algorithmus und Rabin-Karp-Algorithmus

Ich arbeite an String-Suchalgorithmen, die die Suche nach mehreren Mustern unterstützen. Ich habe zwei Algorithmen gefunden, die hinsichtlich der Laufzeit als die stärksten Kandidaten erscheinen, nämlich Aho-Corasick und Rabin-Karp . Ich konnte jedoch keinen umfassenden Vergleich zwischen den beiden Algorithmen finden. Welcher Algorithmus ist effizienter? Welches eignet sich auch besser für paralleles Rechnen und die Suche nach mehreren Mustern? Welches benötigt weniger Hardwareressourcen?

Für den AC-Algorithmus benötigt die Suchphase Zeit, während sie für RK O ( n m ) ist . Die Laufzeit für RK beträgt jedoch O ( n + m ) , wodurch es AC ähnlich ist. Meine vorläufige Schlussfolgerung ist, dass RK praktisch besser zu sein scheint, da es nicht so viel Speicher benötigt wie AC. Ist das korrekt?$O(n+m)$$O(nm)$$O(n+m)$

Die asymptotische Laufzeitanalyse ist wahrscheinlich nicht das beste Werkzeug, um zwischen diesen beiden Algorithmen zu wählen: Die asymptotische Analyse ignoriert konstante Faktoren, und die konstanten Faktoren sind hier kritisch. Die beiden Algorithmen haben im Grunde die gleiche asymptotische Laufzeit, so dass eine asymptotische Analyse wahrscheinlich nicht sehr hilfreich ist, um zwischen ihnen zu wählen.

Stattdessen ist die richtige Wahl zwischen den beiden Algorithmen die experimentelle Analyse. Identifizieren Sie eine repräsentative Arbeitslast und vergleichen Sie dann die Leistung beider Algorithmen für Ihre Arbeitslast mit den Arten von Maschinen, die Sie in der Praxis verwenden möchten.

$O(nm)$$O(n+m)$

$O(n+m)$$c\cdot(n+m)$$c$$O(n+m)$

$O(n+m)$$O(nm)$

Ich konnte jedoch keinen umfassenden Vergleich zwischen den beiden Algorithmen finden.

$O(n + m)$$O(n m)$ Rabin-Karp im Fall großer Datengrenzen / asymptotisch , aber wo diese Grenze erreicht wird, ist Implementierung und datenabhängig und der Kompromiss zwischen Such- / Laufzeiten.

Für Ihre implizite Abfrage nach einem "umfassenden Vergleich" wurden jedoch einige Artikel verfasst, in denen diese beiden und andere Algorithmen experimentell / empirisch anhand realer Daten verglichen wurden. Dazu gehört die Analyse / der Vergleich der Vor- / Nachteile / Kompromisse der verschiedenen Algorithmen, z.

• Matching-Methoden für mehrere Musterzeichenfolgen: Eine vergleichende Analyse / Khan, Pateriya

• VERGLEICHENDE STUDIE ÜBER STRING-PASSENDE ALGORITHMEN BIOLOGISCHER SEQUENZEN / Pandiselvam, Marimuthu, Lawrance