Szybki algorytm wyszukiwania podciągów w łańcuchu
Chciałbym wydajnego algorytmu (lub biblioteki), którego mogę używać w Javie do wyszukiwania podciągów w łańcuchu.
Chciałbym zrobić:
Podany ciąg wejściowy -INSTR:
„BCDEFGH”
Oraz zestaw ciągów kandydatów -CAND:
„AB”, „CDE”, „FG”, „H”, „IJ”
Znajdź jakikolwiekCAND ciągi, które pasują do podciągów wewnątrzINSTR
W tym przykładzie pasowałbym do „CDE”, „FG” i „H” (ale nie „AB” i „IJ”)
Może być wiele tysięcy ciągów kandydujących (w CAND), ale co ważniejsze, będę wykonywał to wyszukiwanie wiele milionów razy, więc potrzebuję go FAST.
Chciałbym pracować z tablicami znaków. Nie jestem też zainteresowany rozwiązaniami architektonicznymi, takimi jak dystrybucja wyszukiwania - po prostu najbardziej wydajna funkcja / algorytm do robienia tego lokalnie.
Ponadto wszystkie łańcuchy w CAND i INSTR będą stosunkowo małe (<50 znaków) - tj. Docelowy ciąg INSTR nie jest długi w stosunku do ciągów kandydujących.
Aktualizacja Powinienem był wspomnieć, że zestaw łańcuchów CAND jest niezmienny dla wszystkich wartości INSTR.
Aktualizacja Muszę tylko wiedzieć, że był mecz - i nie muszę wiedzieć, jaki był mecz.
Ostatnia aktualizacja Zdecydowałem się wypróbować AhoCorsick i Rabina-Karp, ze względu na prostotę implementacji. Ponieważ mam wzory o zmiennej długości, użyłem zmodyfikowanego Rabina-Karpa, który miesza pierwsze n znaków każdego wzorca, gdzie n jest długością najmniejszego wzorca, N był wtedy długością okna wyszukiwania mojego podciągającego podciągu. Do Aho Corsick użyłemto
W moim teście przeszukałem 1000 wzorów w dwóch dokumentach prasowych, uśrednionych dla 1000 iteracji itp. Normalizowane czasy ukończenia to:
AhoCorsick: 1
RabinKarp: 1.8
Wyszukiwanie naiwne (sprawdź każdy wzorzec i użyj string.contains): 50
* Niektóre zasoby opisujące algi wymienione w poniższych odpowiedziach:
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html
http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf