Veröffentlicht · wird verbessert
Algorithm
Zeichenkettenalgorithmen finden Muster in Texten und Wörter über Präfixe; KMP, Rabin-Karp, Tries und der Z-Algorithmus sind die Kernverfahren.
Zeichenkettenalgorithmen vergleichen und durchsuchen Folgen von Zeichen schnell und korrekt. Das zentrale Problem ist die Mustersuche, also alle Stellen zu finden, an denen ein kurzes Muster in einem langen Text vorkommt. Auch die Suche nach allen Wörtern eines Wörterbuchs mit einem bestimmten Präfix und die gleichzeitige Suche nach vielen Mustern gehören dazu. Der naive Ansatz, jede Position einzeln zu prüfen, braucht im schlimmsten Fall Zeit proportional zu Textlänge mal Musterlänge.
Die Suchfunktion im Editor, Logsuche, Autovervollständigung im Suchfeld, Angriffserkennung, Dateisynchronisation und Genomanalyse beruhen alle auf Zeichenkettenalgorithmen. KMP nutzt bereits durchgeführte Vergleiche über eine Fehlertabelle und garantiert lineare Laufzeit, Rabin-Karp schiebt einen rollenden Hash über den Text und spart so die meisten Vergleiche, und ein Trie teilt gemeinsame Präfixe, sodass eine Präfixsuche nur von der Wortlänge abhängt. Das Thema kommt außerdem häufig in Coding-Interviews vor.
Lernen Sie zuerst die Begriffe Präfix, Suffix und Rand und prüfen Sie von Hand, warum die naive Suche langsam ist. Berechnen Sie dann die Präfixfunktion für ein kleines Muster selbst, implementieren Sie die KMP-Suche und einen Trie und vergleichen Sie die Ergebnisse mit der Standardbibliothek. Zum Schluss lohnt sich ein Blick auf typische Fallen in der Praxis wie Hash-Kollisionen und Unicode-Normalisierung.
Für jedes Präfix des Musters wird der längste Rand vorberechnet; bei einer Abweichung springt die Suche zu einem kürzeren Rand, ohne im Text zurückzugehen, und läuft in O(n + m).
Rabin-Karp aktualisiert den Hash jedes Fensters der Länge m in O(1), vergleicht ihn mit dem Hash des Musters und prüft die Zeichen nur bei gleichen Hashwerten.
Ein Baum, der Zeichen für Zeichen durchlaufen wird; gemeinsame Präfixe werden nur einmal gespeichert, daher hängen Präfixsuche und Autovervollständigung nur von der Wortlänge ab.
Das Z-Array liefert für jede Position in linearer Zeit das längste gemeinsame Präfix mit der ganzen Zeichenkette. Bei echten Texten müssen Normalisierung und Indexeinheiten beachtet werden.
prefix_function berechnet den längsten Rand jedes Musterpräfixes, und kmp_search liest den Text mit dieser Tabelle genau einmal von links nach rechts und sammelt alle Startpositionen. Da k nach einem Treffer auf pi[k - 1] gesetzt wird, werden auch überlappende Vorkommen wie bei 0 und 2 gefunden. Mit python string_search.py werden beide Ergebnisse ausgegeben.
string_search.py
def prefix_function(p: str) -> list[int]:
"""pi[i] = length of the longest proper border of p[:i + 1]."""
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
"""Start positions of every (possibly overlapping) occurrence."""
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1]
return hits
if __name__ == "__main__":
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababcabab", "abab")) # [0, 2, 7]
python string_search.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Zeichenkettenalgorithmen.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Zeichenkettenalgorithmen aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.