Który algorytm wyszukiwania ciągu jest w rzeczywistości najszybszy?

Utknąłem na pewien czas, który jest najszybszym algorytmem wyszukiwania ciągów, słyszałem wiele opinii, ale ostatecznie nie jestem pewien.

Słyszałem, jak niektórzy mówią, że najszybszym algorytmem jest Boyer-Moore, a niektórzy twierdzą, że Knuth-Morris-Pratt jest rzeczywiście szybszy.

Szukałem złożoności obu z nich, ale w większości wyglądają tak samo O(n+m). Odkryłem, że w najgorszym przypadku Boyer-Moore ma O(nm)złożoność w porównaniu do Knuth-Morris-Pratt, która ma O (m + 2 * n). Gdzie n = długość tekstu im = długość wzoru.

O ile wiem Boyer-Moore ma liniowo najgorszy przypadek, gdybym użył Reguły Galila.

Moje pytanie, w sumie, który jest w rzeczywistości najszybszym algorytmem wyszukiwania ciągu (To pytanie obejmuje wszystkie możliwe algorytmy żądła, nie tylko Boyer-Moore i Knuth-Morris-Pratt).

Edycja: Z powodu tej odpowiedzi

To czego dokładnie szukam to:

Biorąc pod uwagę tekst Ti wzór, Pmuszę znaleźć wszystkie wyglądy Pw T.

Również długość P i T pochodzi z, [1,2 000 000]a program musi działać poniżej 0,15 sekundy.

Wiem, że KMP i Rabin-Karp są wystarczające, aby uzyskać 100% wynik w tym problemie, ale ja chciałem wdrożyć Boyera-Moore'a. Który byłby najlepszy dla tego rodzaju wyszukiwania wzorców?

To zależy od rodzaju wyszukiwania, które chcesz przeprowadzić. Każdy z algorytmów sprawdza się szczególnie dobrze w przypadku niektórych rodzajów wyszukiwania, ale nie podałeś kontekstu wyszukiwania.

Oto kilka typowych przemyśleń na temat typów wyszukiwania:

• Boyer-Moore: działa poprzez wstępną analizę wzoru i porównanie od prawej do lewej. Jeśli wystąpi niedopasowanie, wstępna analiza służy do określenia, jak daleko można przesunąć wzór względem przeszukiwanego tekstu. Działa to szczególnie dobrze w przypadku długich wzorców wyszukiwania. W szczególności może być subliniowy, ponieważ nie musisz czytać każdego znaku tekstu.

• Knuth-Morris-Pratt: również wstępnie analizuje wzór, ale próbuje ponownie użyć wszystkiego, co już było dopasowane w początkowej części wzoru, aby uniknąć konieczności jego ponownego odtworzenia. Może to działać całkiem dobrze, jeśli twój alfabet jest mały (np. Zasady DNA), ponieważ masz większą szansę, że twoje wzorce wyszukiwania zawierają wznowienia wielokrotnego użytku.

• Aho-Corasick: Wymaga dużo wstępnego przetwarzania, ale robi to z wieloma wzorami. Jeśli wiesz, że będziesz szukał wciąż tych samych wzorców wyszukiwania, jest to znacznie lepsze niż inne, ponieważ musisz analizować wzorce tylko raz, a nie raz na wyszukiwanie.

Stąd, jak zwykle w CS, nie ma jednoznacznej odpowiedzi na ogólnie najlepsze . Chodzi raczej o wybranie odpowiedniego narzędzia do danego zadania.

Kolejna uwaga na temat uzasadnienia najgorszego przypadku: Rozważ rodzaje wyszukiwań wymaganych do stworzenia tego najgorszego przypadku i dokładnie przemyśl, czy są one naprawdę istotne w twoim przypadku. Na przykład O(mn)najgorsza złożoność algorytmu Boyera-Moore'a wynika z wzorca wyszukiwania i tekstu, w którym każdy używa tylko jednego znaku (np. Szukanie aaaw aaaaaaaaaaaaaaaaaaaaa) - czy naprawdę musisz być szybki w przypadku takich wyszukiwań?

Chociaż jestem nieco spóźniony, aby odpowiedzieć na to pytanie, ale myślę, że Z-Algorithmjest znacznie szybszy niż jakikolwiek inny. Jego najgorsza złożoność to O (m + n) i nie wymaga wstępnego przetwarzania wzoru / tekstu. Jest również bardzo łatwy do kodowania w porównaniu do innych algorytmów.

Działa w następujący sposób.

Na przykład jest ciąg S ='abaaba'. Mamy znaleźć z(i)wartości dla i=0 to len(S)-1. Zanim przejdę do wyjaśnienia, pozwól mi najpierw ułożyć kilka definicji.

z(i)= nie znaków tego prefiksu Sodpowiada przedrostkowi s(i).

s(i)= ithprzyrostek S.

Poniżej podano s(i)wartości dla s = 'abaaba'.

s(0) = 'abaaba' = S
s(1) = 'baaba'
s(2) = 'aaba'
s(3) = 'aba'
s(4) = 'ba'
s(5) = 'a'

Wartości Z wynoszą odpowiednio

z(0) = 6 = length(S)
z(1) = 0
z(2) = 1
z(3) = 3
z(4) = 0
z(5) = 1

Szczegółowe informacje na temat algorytmu znajdują się w poniższych linkach.

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

Teraz potrzeba O (N), aby znaleźć wszystkie zwartości bez żadnego narzutu związanego z przetwarzaniem wstępnym. Można by się teraz zastanawiać, jak wykorzystać tę logikę do dopasowania wzorca w danym ciągu?

Zobaczmy na przykładzie. Wzór (P) aba, Text (T) aacbabcabaad.

Umieść to w formie P $ T. ( $- każdy znak, który nie pojawia się ani we wzorze, ani w tekście. Za chwilę dojdę do znaczenia $.)

P$T = aba$aacbabcabaad

Wiemy len(P)= 3.

Wszystkie wartości Z P$Tsą

z(0) = 16 = len(P$T)
z(1) = 0
z(2) = 1
z(3) = 0
z(4) = 1
z(5) = 1
z(6) = 0
z(7) = 0
z(8) = 2
z(9) = 0
z(10) = 0
z(11) = 3
z(12) = 0
z(13) = 1
Z(14) = 1
Z(15) = 0

Teraz co z(i)= len(P). Ans = 11.Więc nasz wzór jest obecny w Ans-len(P)-1= 7. -1jest dla $postaci.

Teraz dlaczego $lub jakikolwiek taki specjalny charakter jest ważny. Rozważ P = 'aaa'i T = 'aaaaaaa'. Bez znaku specjalnego wszystkie z(i)będą miały wartości przyrostowe. Nadal można znaleźć pozycję wzoru w tekście za pomocą poniższych wzorów:

Stan: z(i)> = len(P)oraz stanowisko: Ans-len(P). Ale stan w tym przypadku staje się nieco trudny i zagmatwany. Ja osobiście wolę korzystać ze specjalnej techniki postaci.

Użyj zawartości adresowalnej pamięci , zaimplementowanej w oprogramowaniu w postaci wirtualnego adresowania (skierowanie liter do liter).

Jest to trochę zbyteczne w stosunku do algorytmu dopasowywania średniego ciągu.

CAM może dopasować ogromną liczbę wzorów jednocześnie, do około 128-literowych wzorów (jeśli są ASCII; jeśli są one Unicode tylko 64). I jest to jedno wywołanie na długość litery w ciągu, do którego chcesz dopasować i jedno losowe odczytanie z pamięci na długość maksymalnej długości wzorca. Więc jeśli analizujesz ciąg 100 000 liter, z maksymalnie 90 000 000 wzorców jednocześnie (co zajęłoby około 128 GiB, aby zapisać tak dużą liczbę wzorów), zajęłoby 12 800 000 losowych odczytów z pamięci RAM, więc nastąpiłoby to w ciągu 1ms.

Oto jak działa adresowanie wirtualne.

Jeśli zacznę od 256 adresów początkowych, które reprezentują pierwszą literę, litery te wskazują 256 kolejnych liter. Jeśli wzór nie istnieje, nie przechowujesz go.

Więc jeśli nadal łączę litery z literami, to tak, jakby 128 plasterków wirtualnego adresowania wskazywało na adresowanie wirtualne.

To zadziała - ale aby uzyskać jednoczesne dopasowanie do 900 000 000 wzorów, należy dodać jeszcze jedną sztuczkę - i wykorzystuje to fakt, że zaczynasz od ponownego użycia tych buforów liter, ale później się rozprasza. Jeśli podasz zawartość, zamiast przydzielić wszystkie 256 znaków, to spowalnia ona bardzo niewiele, a otrzymasz 100-krotny wzrost pojemności, ponieważ w zasadzie w końcu dostajesz tylko 1 literę w każdym buforze wskaźnika liter (który nazwałem „ ucieczka').

Jeśli chcesz dopasować ciąg najbliższego sąsiada, wiele z nich działa równolegle i gromadzisz w hierarchii, więc rozkładasz swój błąd na obiektywny. jeśli spróbujesz zbliżyć się do sąsiada za pomocą tylko jednego, to jesteś stronniczy w kierunku początku drzewa.