pyton wyszukiwania wydajny podciąg

Powiel możliwe:
How is string.find implemented in CPython?pyton wyszukiwania wydajny podciąg

Czytałem wiele postów tutaj na przepełnienie stosu porównującym skuteczność wyszukiwania podciągu (np Python string search efficiency, Is this the most efficient way to search for a substring?, substring in python, itp ...)

Sprawdziłem również źródło c implementacja zawiera zawiera abstract.c.

O ile widzę wbudowanej realizacja jest iteracyjny jeden: python docs

Czy Pythona mają implementacja bardziej odpowiednich technik w celu znalezienia podciąg: Boyer–Moore Algorithm, Rabin–Karp algorithm, etc ... ?? ?

EDIT

Kwestia została rozszerzona: Python: Improving sub-string search by embedding sophisticated algorithms.

Źródło

2012-09-03 Michael

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

+1 będzie interesujące porównanie go do Rabin-Karp – Michael

@Martijn Pieters: informacja że zadałem to pytanie, zanim dodasz link do string_contains. – Michael

Faktyczna realizacja wyszukiwania CPython łańcuch jest tutaj:

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

Wydaje użyciu Boyer-Moore.

Źródło

2012-09-03 09:05:29 georg

Dzięki, ja przyjmie tę odpowiedź, chociaż jestem zainteresowany, czy taka jest implementacja również dla Rabina Karpa. – Michael

Zobacz komentarz do drugiej odpowiedzi, to nie jest B-M, jest zainspirowany (uproszczony) przez B-M z Horspoolem i niedzielą wrzuconą. Zobacz http://effbot.org/zone/stringlib.htm. –

Podstawowa implementacja nie zapewnia takiego poziomu funkcjonalności.

Znajdziesz implementacje dla Boyer-Moore lub Rabin-Karp dla Pythona za pomocą Google.

Źródło

2012-09-03 09:03:02

Podczas gdy ściśle mówiąc, CPython nie używa BMRK, może dostarczać sublinearną wydajność (dobrze) za pomocą algorytmu opartego na BM: [The Stringlib Library] (http://effbot.org/zone/stringlib.htm) – jfs

Odpowiedz

Powiązane problemy