Algoritam Rabin-Karp algoritam je podudaranja / pretraživanja niza koji su razvili Michael O. Rabin i Richard M. Karp. Za usporedbu koristi tehniku raspršivanja i grubu silu te je dobar kandidat za otkrivanje plagijarizma.
Važni pojmovi
- pattern je niz koji se traži. Uzmite u obzir duljinu uzorka kao M znakova.
- tekst je cijeli tekst iz kojeg se traži obrazac. Duljinu teksta uzmite u obzir kao N znakova.
Što je usporedba grube sile?
U usporedbi grube sile svaki znak uzorka uspoređuje se sa svakim znakom teksta dok se ne pronađu znakovi koji se ne podudaraju.
Kako djeluje Rabin-Karpov algoritam
- Izračunajte hash vrijednost uzorka
- Izračunajte hash vrijednost prvih M znakova teksta
- Usporedite obje hash vrijednosti
- Ako su nejednake, izračunajte hash vrijednost za sljedećih M znakova teksta i ponovo usporedite.
- Ako su jednaki, izvedite usporedbu grube sile.
hash_p = hash value of pattern hash_t = hash value of first M letters in body of text do if (hash_p == hash_t) brute force comparison of pattern and selected section of text hash_t= hash value of next section of text, one character over while (end of text or brute force comparison == true)Prednost nad algoritmom podudaranja naivnog niza
Ova tehnika rezultira samo jednom usporedbom po pod slijedu teksta, a gruba sila potrebna je samo kada se vrijednosti hasha podudaraju.