Porównanie algorytmu Aho-Corasicka z algorytmem Rabina-Karpa

Pracuję nad algorytmami wyszukiwania ciągów, które obsługują wyszukiwanie wielu wzorców. Znalazłem dwa algorytmy, które wydają się najsilniejszymi kandydatami pod względem czasu działania, a mianowicie Aho-Corasick i Rabin-Karp . Nie udało mi się jednak znaleźć kompleksowego porównania między dwoma algorytmami. Który algorytm jest bardziej wydajny? Który z nich jest bardziej odpowiedni do obliczeń równoległych i wyszukiwania wielu wzorców? Wreszcie, który z nich wymaga mniej zasobów sprzętowych?

W przypadku algorytmu prądu przemiennego faza wyszukiwania zajmuje czas , natomiast dla RK jest to O ( n m ) . Jednak czas działania dla RK wynosi O ( n + m ), co czyni go podobnym do AC. Mój wstępny wniosek jest taki, że RK wydaje się praktycznie lepszy, ponieważ nie potrzebuje tyle pamięci, co AC. Czy to jest poprawne?$O(n+m)$$O(nm)$$O(n+m)$

Analiza asymptotycznego czasu pracy prawdopodobnie nie będzie najlepszym narzędziem do wyboru między tymi dwoma algorytmami: analiza asymptotyczna ignoruje czynniki stałe, a czynniki stałe będą tutaj kluczowe. Te dwa algorytmy mają zasadniczo taki sam asymptotyczny czas działania, więc analiza asymptotyczna prawdopodobnie nie jest zbyt pomocna w wyborze między nimi.

Zamiast tego właściwym wyborem między dwoma algorytmami jest analiza eksperymentalna. Zidentyfikuj reprezentatywne obciążenie, a następnie sprawdź wydajność obu algorytmów pod kątem obciążenia na rodzajach maszyn, których zamierzasz używać w praktyce.

Nawiasem mówiąc, wygląda na to, że możesz mieć niewielkie zamieszanie co do asymptotycznego czasu działania Rabin-Karp. Z jednej strony mówisz, że Rabin-Karp ma czas , ale w następnym zdaniu mówisz, że Rabin-Karp ma czas O ( n + m ) . Być może jesteś zdezorientowany różnicą między oczekiwanym (średni przypadek) a czasem najgorszym przypadku.$O(nm)$$O(n+m)$

$O(n+m)$$c\cdot(n+m)$$c$$O(n+m)$

$O(n+m)$$O(nm)$

Nie udało mi się jednak znaleźć kompleksowego porównania między dwoma algorytmami.

$O(n + m)$$O(n m)$

ale napisz swoje ukryte zapytanie o „kompleksowe porównanie”, niektóre artykuły zostały napisane eksperymentalnie / empirycznie, porównując te dwa i inne algorytmy na rzeczywistych danych i obejmują analizę / porównanie zalet / wad / kompromisów różnych algorytmów, np .:

• Metodologie dopasowywania ciągów wielu wzorców: analiza porównawcza / Khan, Pateriya

• BADANIE PORÓWNAWCZE DOTYCZĄCE ŁĄCZĄCYCH ALGORYTMÓW SEKWENCJI BIOLOGICZNYCH / Pandiselvam, Marimuthu, Lawrance