Który algorytm wyszukiwania ciągów znaków jest faktycznie najszybszy?

Zależy to od rodzaju wyszukiwania, które chcesz przeprowadzić. Każdy z algorytmów działa szczególnie dobrze w określonych typach wyszukiwania, ale nie podałeś kontekstu swoich wyszukiwań.

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

• Boyer-Moore: działa poprzez wstępną analizę wzoru i porównywanie od prawej do lewej. Jeśli wystąpi niezgodność, początkowa analiza służy do określenia, jak daleko można przesunąć wzór w.r.t. przeszukiwany tekst. Działa to szczególnie dobrze w przypadku długich wzorców wyszukiwania. W szczególności może być nieliniowy, ponieważ nie musisz czytać każdego pojedynczego znaku w swoim tekście.

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

• Aho- Corasick: Wymaga dużo wstępnego przetwarzania, ale robi to dla wielu wzorców. Jeśli wiesz, że będziesz ciągle szukał tych samych wzorców wyszukiwania, to jest to o wiele 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 . To raczej kwestia wyboru odpowiedniego narzędzia do danego zadania.

Kolejna uwaga na temat rozumowania najgorszego przypadku: rozważ rodzaje wyszukiwań wymaganych do stworzenia tego najgorszego przypadku i dokładnie zastanów się, czy są one naprawdę istotne w Twoim przypadku. Na przykład O(mn) złożoność najgorszego przypadku algorytmu Boyera-Moorea wynika z wzorca wyszukiwania i tekstu, z których każdy używa tylko jednego znaku (np. Znalezienie aaa w aaaaaaaaaaaaaaaaaaaaa) – czy naprawdę musisz być szybki w takich wyszukiwaniach?

Komentarze

• Mam mniej więcej cały alfabet angielski i zaktualizowałem Pytanie, przepraszam, że nie zaczynam od tego na początku.
• I tak, muszę być szybki, nawet w przypadku wyszukiwań takich jak że
• czy możesz omówić algorytm Z ' s, a także manachar?

Chociaż trochę się spóźniłem, aby odpowiedzieć na to pytanie, ale myślę, że Z-Algorithm jest znacznie szybsze niż jakiekolwiek jego odpowiedniki.Jego najgorsza złożoność wynosi O (m + n) i nie wymaga wstępnego przetwarzania wzorca / tekstu. Jest również bardzo łatwy do kodowania w porównaniu z innymi algorytmami.

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

Na przykład istnieje ciąg znaków S ="abaaba". Mamy znaleźć z(i) wartości dla i=0 to len(S)-1. Zanim przejdę do wyjaśnienia, pozwólcie, że najpierw przedstawię kilka definicji.

z(i) = nie. znaków prefiksu S, który odpowiada prefiksowi s(i).

s(i) = ith przyrostek S.

Poniżej znajdują się 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 to odpowiednio

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

Aby uzyskać szczegółowe informacje na temat algorytmu, zapoznaj się z poniższymi linkami.

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

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

Teraz potrzeba O (N), aby znaleźć wszystkie wartości z bez narzutu wstępnego przetwarzania. Można by się teraz zastanawiać, jak można użyć tej logiki do dopasowania wzorca w danym ciągu?

Zobaczmy na przykładzie. Wzorzec (P): aba, Text (T): aacbabcabaad.

Umieść to w postaci P $ T. ($ – dowolny znak, który nie pojawia się ani we wzorcu, ani w tekście. Za chwilę dojdę do znaczenia $.)

P$T = aba$aacbabcabaad

Znamy len(P) = 3.

Wszystkie wartości z P$T to

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 z(i) = len(P). Ans = 11. Zatem nasz wzorzec znajduje się w Ans-len(P)-1 = 7. -1 jest dla $ znaku.

Dlaczego $ lub każdy 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. W dalszym ciągu można znaleźć pozycję wzorca w tekście za pomocą poniższych formuł:

Warunek: z(i)> = len(P) i pozycja: Ans-len(P). Ale stan w tym przypadku staje się trochę skomplikowany i zagmatwany. Osobiście wolę używać specjalnej techniki postaci.

Komentarze

• Czy mógłbyś sam to wyjaśnić? Posiadanie linków do zewnętrznych stron może posłużyć do opracowania, ale sedno odpowiedzi powinno być w samej odpowiedzi, a nie w podążaniu za linkiem do innej witryny.
• Algorytm z jest zasadniczo taki sam jak kmp. Wątpię, żeby był dużo szybszy.
• Zgadzam się z @ThomasAhle. Obliczanie z jest przetwarzane wstępnie. Jednak ' jest dobrym wyjaśnieniem. Z powodu tej odpowiedzi wprowadziłem O(n) sposób konwersji z przetwarzania wstępnego KMP na przetwarzanie wstępne Z. Tutaj

Użyj pamięć adresowalna treści , zaimplementowana programowo w postaci adresowania wirtualnego (wskazywanie liter na litery).

To trochę zbyteczne dla przeciętnego algorytmu dopasowującego ciągi znaków.

CAM może dopasować ogromną liczbę wzorców jednocześnie, do około 128-literowych wzorców (jeśli są to ASCII; jeśli są to tylko 64 Unicode). Jest to jedno wywołanie na długość litery w ciągu, do którego chcesz dopasować, i jeden losowy odczyt z pamięci na długość maksymalnej długości wzoru. Więc gdybyś analizował ciąg znaków o długości 100 000 liter, zawierający do 90 000 000 wzorów jednocześnie (co wymagałoby około 128 GiB do zapisania tak dużej liczby wzorców), wymagałoby 128 000 000 losowych odczytów z pamięci RAM, więc zajmie to 1 ms.

Oto jak działa wirtualne adresowanie.

Jeśli zacznę od 256 adresów początkowych, które reprezentują pierwszą literę, te litery wskazują na 256 następnych liter. Jeśli wzorzec nie istnieje, nie przechowujesz go.

Więc jeśli będę nadal łączyć litery z literami, to tak, jakbyś miał 128 fragmentów adresu wirtualnego wskazującego na adres wirtualny.

To będzie działa —, ale aby uzyskać 900 000 000 pasujących wzorców jednocześnie, jest jeszcze jedna sztuczka, którą można dodać do tego — i już to wykorzystuje faktu, że zaczynasz od ponownego użycia wielu buforów liter, ale później to się rozprasza.Jeśli wypiszesz zawartość, zamiast alokować wszystkie 256 znaków, to zwalnia bardzo mało i „uzyskasz 100-krotny wzrost pojemności, ponieważ w zasadzie otrzymujesz tylko 1 literę używaną w buforze wskaźnika na każdą literę (który nazwałem” escape „).

Jeśli chcesz uzyskać dopasowanie ciągu najbliższego sąsiada, masz wiele z nich działających równolegle i zbierasz w hierarchii, więc rozkładasz swój błąd na bezstronny. Jeśli spróbujesz najbliższego sąsiada tylko z jednym, wtedy jesteś „nastawiony na początek drzewa.

Komentarze

• @MagnusRobertCarlWoot, biorąc pod uwagę, że masz to samo gavatar as roucer81, albo jest to astronomiczny zbieg okoliczności kolizji kodu skrótu, albo masz ten sam adres e-mail. Jeśli jesteś tą samą osobą za obydwoma kontami, użyj ” formularza kontaktowego „, aby je scalić, aby uzyskać odpowiedni kredyt za reputację uzyskaną dzięki głosom za tę odpowiedź.