Hashing stringova

Od svega što se može susresti na natjecanjima stringovi su uvjerljivo najčešće žrtve hashiranja. Usporedbe stringova znak po znak nisu uvijek dovoljno efikasne, pa ćemo zato sada proučiti jednu vrlo popularnu metodu hashiranja stringova koja dozvoljava brzo izdvajanje pojedinih podstringova (tj. dobivanje njihovih hash vrijednosti). Također ćemo vidjeti vrlo efikasan način leksikografskog uspoređivanja podstringova.

Hash funkcija za stringove

Hash funkcija koju obično koristimo za stringove također ima oblik polinoma, gdje su koeficijenti znakovi samog stringa. Vrijednosti ćemo pohranjivati u intove, ovaj puta bez direktnog računanja nekog ostatka (za to će se pobrinuti sama implementacija tipa podatka int, odnosno njegov overflow).

Nazovimo string s kojim radimo , njegovu duljinu i odaberimo prosti broj . Pomoćne nizove i definiramo rekurzivno na sljedeći način:

Niz je niz potencija broja (po nekom modulu, obično uz overflow). No što nam predstavlja niz ? Izgleda kao da ima veze s polinomima, preciznije jako je sličan Hornerovom algoritmu za evaluiranje polinoma u nekoj točki. Isti taj niz zato možemo zapisati u nešto preglednijem obliku:

Kao hash vrijednost zadanog stringa podrazumijevamo , a ostale članove niza nazivamo prefiks hashevima. Ovdje ćemo još napomenuti kako za samu hash vrijednost ovdje uzimamo vrijednost pripadajućeg znaka. Također nećemo brinuti o overflow problemima koji bi eventualno nastali i jednostavno ćemo ih ignorirati. Možete se uvjeriti kako se sve operacije u tom slučaju slične onima modulo .

Sljedeći korak je izdvajanje hash vrijednosti podstringova stringa S. Označimo sa podstring stringa koji se provlači od znaka do znaka . Po našoj definiciji hash vrijednosti stringa dobivamo sljedeću sumu:

Začudo tu vrijednost možemo jednostavno dobiti iz već izračunatog pomoćnog niza .

Sljedeća formula daje nam tu poveznicu:

Ideja kojom dolazimo do te formule je ta da prvo uzmemo prefiks i tada od njega jednostavno odrežemo prefiks . Kako je znak u odnosu na znak na potenciji višoj za (što odgovara duljini podstringa), taj drugi prefiks potrebno je pomnožiti s . Pri konkretnoj implementaciji ove formule naravno moramo paziti na to da ne gledamo negativne indekse.

Sada već posjedujemo puno alata i bacamo se na neke jednostavnije primjene.

Traženje malog string u većem

Pretpostavimo da imamo dva stringa i s duljinama redom i , i neka je manje od tj. tražimo u . Za početak izračunamo hash vrijednost stringa - i pomoćne nizove i za string . Tada se ovo traženje svodi na ispitivanje je li jednak za sve odgovarajuće indekse (ima ih ).

Ova ideja čini osnovu Rabin-Karp algoritma za traženje patterna. Primijetite i da je ovo moguće izvesti i bez pomoćnih nizova za string ako pri pomicanju na sljedeći indeks održavamo vrijednost kao hash vrijednost trenutno promatranog podstringa. Tada pomoću niza izbacujemo prvi znak iz trenutnog hasha i dodajemo novi znak na kraj.

Kako bismo bili potpuno sigurni da nemamo slučaj kolizije potrebno je i ručno provjeriti svaki podstring koji se pokaže jednak po hash vrijednosti, no to će se uz zadanu hash funkciju događati vrlo rijetko. Zbog toga se čak možemo praviti da hash vrijednost predstavlja sam string.

Sličan princip možemo primijeniti na višedimenzionalne nizove. U 2d slučaju možemo na primjer prvo izračunati hash vrijednosti stupaca (i njihovih podstringova), i zatim te podstringove promatrati kao jednodimenzionalne nizove. Također možemo lako prebrojavati podstringove određene fiksne duljine i još mnogo toga.

Palindrom i periodičnosti

Palindromi su još jedan primjer gdje hashing može dobro doći. Ako umijesto samo jednog pomoćnog niza konstruiramo i niz kao niz prefiks hasheva obrnutog stringa. Označimo obrnuti string sa . Tada ispitivanje je li podstring palindrom svodi na ispitivanje jednakosti i .

Periodičnost stringa također je jednostavna za provjeriti, uzmemo svaki prefiks stringa, pomičemo se za njegovu duljinu i pritom testiramo jednakost. Budući da duljina mora biti djeljiva duljinom perioda broj početnih prefiksa je prilično ograničen.

Najdulji zajednički prefiks

Najdulji zajednički prefiks (engl. longest common prefix, LCP) dvaju stringova definira se kao najdulji prefiks prvog stringa koji je ujedno i prefiks drugog stringa. Rubni slučaj je naravno onaj u kojem je jedan od stringova prefiks drugoga. Traženje LCP-a može se vrlo efikasno izvesti korištenjem već opisane hash funkcije i binarnog pretraživanja. Uistinu ako je string prefiks stringa tada je svaki prefiks stringa također prefiks stringa . Pretpostavimo da su nam zadana dva podstringa stringa , redom i .

Tada bi odsječak za računanje duljine njihovog LCP-a išao otprilike ovako:

int LCP (int x0, int y0, int x1, int y1) {
  if (S[x0] != S[x1]) {
    return 0;
  }
  int lo = 1, hi = std::min(y0-x0+1, y1-x1+1);
  while (lo < hi) {
    int mid = (lo + hi + 1) / 2;        
    if (hash(x0, x0+mid-1) == hash(x1, x1+mid-1)) {
      lo = mid; 
    } else { 
      hi = mid-1;
    }
  }
  return lo; 
}

Leksikografska usporedba podstringova

Usporedba dva podstringa vrlo je jednostavno i efikasno izvediva koristeći LCP.

bool cmp(int x0, int y0, int x1, int y1) { 
  int L = LCP(x0, y0, x1, y1);
  if (L == y0  x0 + 1) return 1;
  if (L == y1  x1 + 1) return 0;
  return (S[x0+L] < S[x1+L]);
}

Funkcija cmp dakle vraća vrijednost true ukoliko je prvi podstring leksikografski manji od drugog. Složenost jedne komparacije je . Primjer zadatka u kojem se ovakva leksikografska komparacija može iskoristiti je pronalaženje leksikografski minimalne rotacije nekog stringa. Ako tražimo takvu rotaciju u stringu onda je jedno elegantno rješenje promatrati string . Kao početne pozicije promatramo prvih pola i uspoređujemo podstringove leksikografski s onima već viđenim.

Još jedna primjena ovog komparatora je izgradnja jedne od najvažnijih struktura za obradu stringova tzv. suffix arraya. Ideja je sortirati sve sufikse leksikografski (koristeći njihove početne indekse). U takvom nizu sufiksa možemo vrlo efikasno tražiti podstringove, kao i rješavati još nebrojene teške probleme. Nažalost ta struktura daleko nadilazi ovaj kratki uvod, no pozivam sve zainteresirane da strukturu prouče na webu.

Zadaci

http://www.spoj.com/problems/LPS/ (najdulji palindromski podstring)

http://www.spoj.com/problems/MINMOVE/ (leksikografski minimalna rotacija)

http://www.spoj.pl/problems/TREEISO/

http://www.spoj.pl/problems/HSEQ/

http://www.spoj.pl/problems/LSQF/

http://www.spoj.pl/problems/DISUBSTR/

Hintovi

© 2014. Gustav Matula, Matija Šantl Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License