Python effizient String-Suche

Mögliche Duplizieren:
How is string.find implemented in CPython?Python effizient String-Suche

ich viele Beiträge hier im Stack-Überlauf gelesen haben, die Leistung von String-Suche zu vergleichen (zB Python string search efficiency, Is this the most efficient way to search for a substring?, substring in python, etc ...)

Ich habe auch auf die Quelle c geschaut ode Implementierung von enthält abstract.c.

Soweit ich die eingebaute in Implementierung sehen ist ein iterativer ein: python docs

Ist Python hat eine Implementierung von mehr ausreichend Techniken für die Suche nach einer Teilzeichen: Boyer–Moore Algorithm, Rabin–Karp algorithm, etc ... ?? ?

EDIT

Die Frage wurde erweitert: Python: Improving sub-string search by embedding sophisticated algorithms.

Quelle

2012-09-03 Michael

rel: http://stackoverflow.com/questions/681649/how-is-string-find-implemented-in-cpython – georg

+1 es wird interessant sein, es zu vergleichen mit Rabin-Karp – Michael

@Martijn Pieters: Bekanntmachung dass ich diese Frage gestellt habe, bevor Sie den Link zu string_contains hinzugefügt haben. – Michael

Die Implementierung tatsächliche CPython String-Suche ist hier:

http://hg.python.org/cpython/file/tip/Objects/stringlib/fastsearch.h

Es scheint Boyer-Moore zu verwenden.

Quelle

2012-09-03 09:05:29 georg

Danke, i Ich werde diese Antwort akzeptieren, obwohl ich interessiert bin, ob es eine solche Implementierung auch für Rabin Karp gibt. – Michael

Siehe den Kommentar auf der anderen Antwort, es ist nicht B-M, es ist inspiriert (vereinfacht) von B-M mit einigen Horspool und Sonntag geworfen. Siehe http://effbot.org/zone/stringlib.htm. –

Die Kernimplementierung bietet diese Funktionalität nicht.

Sie finden Implementierungen für Boyer-Moore oder Rabin-Karp für Python mit Google.

Quelle

2012-09-03 09:03:02

Während streng genommen CPYTHON BMRK nicht verwendet, kann es eine sublineare Leistung (gute Sache) mit Algorithmus basierend auf BM bieten: [Die stringlib Library] (http://effbot.org/zone/stringlib.htm) – jfs

Python effizient String-Suche

Antwort

Verwandte Themen