Рабин-Карп алгоритам

У информатици Рабин-Карп алгоритам је алгоритам за претрагу ниски који су створили Мајкл О. Рабин и Ричард Карп 1987. године, који користи хеширање да пронађе било коју комбинацију ниски у тексту. За текст дужине n и p комбинација дужине m, просечна и најбоља временска сложеност износи О (n + n) у простору О (p), ​​али је његова најгора временска сложеност О (nm). Насупрот томе, Ахо-Корасик алгоритам за проналажење ниски има асимптотску најгору временску сложеност О (n +m) у простору О (m).

Практична примена Рабин-Карп алгоритма је откривање плагијата. Узимајући у обзир изворни материјал, Рабин-Карп може брзо да врши претрагу преко папира за локацију реченица изворног материјала, занемарујући детаље као што су величина слова и знакове интерпункције. Због обиља тражених ниски, алгоритми за претрагу појединачних ниски су непрактични.

Претрага подниске у покрету и конкурентски алгоритми

Алгоритам грубе силе за претрагу подниске проверава све могуће позиције: 

function NaiveSearch(string s[1..n], string sub[1..m])
   for i from 1 to n-m+1
      for j from 1 to m
         if s[i+j-1] ≠ sub[j]
            jump to next iteration of outer loop
      return i
   return not found

Овај алгоритам ради добро у многим практичним случајевима, али може да се извршава релативно дуго за одређене примере, као што је претрага низа од 10.000 слова a, након којег следи слово b у низу од 10 милиона слова a , у том случају он испољава најгору временску сложеност О (mn).

Кнут-Морис-Прат алгоритам смањује ову сложеност на О (n) користећи рачунање унапред да би испитао сваки текстуални карактер само једном, Бојер Мур-алгоритам за претрагу ниске прескаче не 1, већ што је више могуће да би претрага успела, и ефикасно смањује број пута који смо итеративно приступили слољашњој петљи, тако да број карактера који су испитани тежи ка n / m у најбољем случају. Рабин-Карп алгоритам се уместо тога фокусира на убрзању линија 3-6.

Употреба хеширања за претрагу подниске у покрету

Уместо да спроводи префињеније прескакање, Рабин-Карп алгоритам покушава да убрза тестирање подударања образаца подниски у тексту употребом хеш функција. Хеш функција је функција која претвара све ниске у нумеричку вредност, која се зове хеш вредност, на пример, да имамо хеш ("здраво") = 5. Рабин-Карп користи чињеницу да ако су две ниске једнаке, њихове хеш вредности су једнаке. Дакле, чини се да све што треба да урадимо је да израчунамо хеш вредност подниске коју тражимо, а затим пронађемо подниску са истом вредношћу.

Међутим, овде постоје два проблема. Први, зато што постоји толико различитих ниски, да би хеш вредности биле мале морамо доделити неким нискама исти број. То значи да ако се хеш вредности поклапају, ниске не морају да се поклапају; морамо да потврдимо да се поклапају, што може да потраје дуго времена за дуже ниске. Срећом, добра хеш функција нам обећава да се за најразумније улазе ово неће догодити превише често, што нам даје добро просечно време претраге.

Алгоритам је приказан: 

function RabinKarp(string s[1..n], string sub[1..m])
hsub := hash(sub[1..m]); hs := hash(s[1..m])
for i from 1 to n-m+1
  if hs = hsub
    if s[i..i+m-1] = sub
      return i
  hs := hash(s[i+1..i+m])
  return not found

Линије 2, 5, 7 О (m) времена. Међутим, линија 2 ће се извршити само једном, а линија 5 ће се извршити само ако се хеш вредности подударају, што је мало вероватно да ће се догодити више од неколико пута. Линија 4 се извршава n пута, али захтева константно време. Дакле, једини проблем је линија 7.

Ако наивно поново израчунамо хеш вредност за подниску s[i+1..i+m], то би захтевало О (m) времена, а пошто се извршава за сваку петљу, алгоритам би захтевао О (mn) времена, исто као и најнаивнији алгоритами. Трик за решавање овога је да променљива hs већ садржи хеш вредност s[i..i+m-1]. Ако можемо искористити ово да израчунамо наредну хеш вредност у константном времену, онда је наш проблем решен.

Овде користимо нешто што се зове котрљајући хеш. Котрљајући хеш је хеш функција специјално направљена да омогући ову операцију. Један једноставан пример је сабирање вредности сваког карактера у подстрингу. Затим, можемо да користимо ову формулу за израчунавање следеће хеш вредност у константном времену: 

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Ова једноставна функција ради, али ће довести до тога да се 5. ред извршава чешће од других сложених котрљајућих хеш функција.

Приметимо да ако баш немамо среће, или имамо веома лошу хеш функцију као што је константна функција, постоји добра шанса да ће се 5. линија извршити n пута, при свакој итерацији петље. Зато што захтева О (m) времена, цео алгоритам има временску сложеност у најгорем случају О (mn).

Коришћена хеш функција

Главна ствар код извођења Рабин-Карп алгоритма је ефикасно израчунавање хеш вредност узастопних подниски у тексту. Коришћена и ефикасна котрљајућа хеш функција третира сваку подниску као број у некој бази, а база је обично велики прост број. На пример, ако је подниска "hi", а база је 101, хеш вредност ће бити 104 × 101 1 + 105 × 101 0 = 10609 (ASCII од 'h' је 104, а од 'i' је 105).

Технички, овај алгоритам је само сличан стварном броју у не-децималном систему, јер на пример можемо имати "базу" са мање од једне "цифре“. Суштинска корист постигнута таквим приказивањем је да је могуће да се израчуна хеш вредност следеће подниске од претходне користећи само константан број операција, независно од дужине подниске.

На пример, ако имамо текст "абракадабра" и ми смо у потрази за узорком дужине 3, можемо израчунати хеш од "бра" из хеша од "абр" (претходна подниска) одузимањем броја који је додат за прво "а" у "абр", односно 97 × 101 2 (97 је ASCII за "а" и 101 је база коју користимо), множењем базе и додавањем последњег 'а' од "бра", односно 97 × 101 0 = 97. Ако су у питању подниске које су дугачке, овај алгоритам постиже велике уштеде у поређењу са многим другим хеширањима.

Теоретски, постоје и други алгоритми који могу да обезбеде погодно израчунавање, нпр. множењем ASCII вредности свих знакова, тако да померајући подниз би подразумевао само дељење првим знаком и множењем последњим. Ограничење, међутим, је ограничена величина int и неопходност коришћења модуларне аритметике ради смањивања хеш резултата. Наивне хеш функције, које не би могле да произведу велике бројеве великом брзином, као нпр додавање ASCII вредности, вероватно ће изазвати многе хеш колизије а и самим тим успорити алгоритам. Отуда је обично најупотребљивија Рабин-Карп хеш функција.

Рабин-Карп и претрага по више образаца

Рабин-Карп је за претрагу појединачних образаца лошији од Кнут-Морис-Прат алгоритма, Бојер Мооре алгоритма за претрагу ниски и неких других алгоритама због свог спорог понашања у најгорем случају. Ипак, Рабин-Карп је алгоритам избора за претрагу по више образаца.

То јест, ако желимо да пронађете било који образац фиксне дужине у тексту, нпр к, можемо да направите једноставну варијанту Рабин-Карп који користи Блум филтер или сет структуре података да би проверили да ли хеш датог низа припада скупу хеш вредности образаца које тражимо: 

function RabinKarpSet(string s[1..n], set of string subs, m):
    set hsubs := emptySet
    foreach sub in subs
        insert hash(sub[1..m]) into hsubs
    hs := hash(s[1..m])
    for i from 1 to n-m+1
        if hs ∈ hsubs and s[i..i+m-1] ∈ subs
            return i
        hs := hash(s[i+1..i+m])
    return not found

Претпостављамо да све подниске имају фиксну дужину m.

Наивни начин претраге за к образаца је да се понови претрага појединачних образаца која се извршава за О (n) времена, у укупном износу од О (nk). Насупрот томе, варијанта Рабин-Карп од малопре може да пронађе све к обрасце у О (n + k) времену, јер хеш табела проверава да ли је хеш подниске једнак неком од шаблона хешева у О (1).

Референце

Литература

Спољашње везе