Rabin-Karps algoritm

Wikipedia

Rabin-Karps algoritm är en algoritm för textsökning där man önskar finna samtliga förekomster av en söksträng i en text. Algoritmen presenterades 1981 av Michael O. Rabin och Richard M. Karp.

Innehåll 1 Beskrivning 1.1 Jämförelse på högre abstraktionsnivå 1.2 Hantering av stora tal 2 Pseudokod 3 Komplexitet 4 Referenser

[redigera] Beskrivning

[redigera] Jämförelse på högre abstraktionsnivå

En naiv textsökningsalgoritm kan konstrueras genom att jämföra varje enskilt tecken i en angiven söksträng, bestående av m tecken, med tecknet på motsvarande position i varje möjlig delsträng av längd m i texten som genomsöks. Om texten består av n tecken finns det n -m + 1 sådana delsträngar, och för varje delsträng krävs upp till m jämförelser. (Om söksträngen och en delsträng är identiska måste varje tecken i söksträngen jämföras med motsvarande tecken i delsträngen för att avgöra detta.) Denna komplexitet kan reduceras om hela söksträngen och en hel delsträng kan jämföras i ett steg.

I ett alfabet Σ med |Σ| tecken kan varje tecken ses som ett numeriskt värde uttryckt i ett talsystem med |Σ| som bas. Om alfabetet består av tecknen 0 till 9 så kan strängen "12345" tolkas som det numeriska värdet 12 345, det vill säga drygt tolvtusen. Om alfabetet istället består av tecknen i ascii-tabellen kan strängen "ABCDE" tolkas som det numeriska värdet (69) + (68 × 128) + (67 × 128²) + (66 × 128³) + (65 × 128⁴) = 17 587 823 173, det vill säga drygt 17,5 miljarder, eftersom tecknet "A" motsvarar 65 i ascii-tabellen, och denna tabell har 128 tecken.

Efter förbehandlingen, som beräknar värdena för söksträngens samt för delsträngen bestående av de första m tecknen i texten, kan dessa värden jämföras i ett steg. Det beräknade värdet för delsträngen kan sedan användas för att enkelt räkna ut nästa delsträngs värde inför vidare jämförelser.

[redigera] Hantering av stora tal

Problemet med denna metod är att även relativt korta söksträngar översätts till heltal av sådan storlek att de inte kan hanteras av normala datorer. För att lösa detta problem använder Rabin-Karps algoritm i varje steg resten av divisionen av den föregående beräkningen med en lämplig nämnare. Denna nämnare brukar väljas så att produkten av nämnaren och basen (alfabetets storlek) precis ryms i ett ord i datorns minne. För att detta ska utgöra en så effektiv hashfunktion som möjligt väljs oftast ett primtal.

Det går snabbt att avgöra att två strängar inte är identiska om värdet som representerar den ena strängen inte ger samma rest när det delas med nämnaren som när den andra strängen delas med samma nämnare. Dessvärre är två tal som ger samma rest när de delas med en nämnare inte nödvändigtvis samma tal. Därför måste man vid varje sådan träff återgå till att, som i den naiva metoden, jämföra strängarna tecken för tecken. Sådana falska träffar är dock i praktiken inte alltför vanliga om nämnaren är väl vald.

[redigera] Pseudokod

 1  algoritm  RABIN-KARP
 2  indata:   txt,     texten som ska genomsökas
 3            sök,     strängen som ska sökas i text
 4            bas,     antal tecken i det alfabet som används
 5            nämnare, ett primtal så att minnesstorlek( nämnare × bas ) < minnesstorlek( ord )
 6  resultat: Ett meddelande skrivs ut vid varje förekomst
 7 
 8  n ← txt.längd
 9  m ← sök.längd
10
11  sökvärde  ← 0
12  txtvärde0 ← 0
13
14  // Förbehandling 
15  för index i från 0 till m - 1
16      sökvärde  ← ( bas × sökvärde  + sök[i] ) mod nämnare
17      txtvärde0 ← ( bas × txtvärde0 + txt[i] ) mod nämnare
18
19  // h bestämmer vikten av det första tecknet i en sträng av m tecken
20  h ← basm-1 mod nämnare
21
22  // Sökning
23  för förskjutning s från 0 till n - m
24      om sökvärde = txtvärdes
25          // Jämför tecken för tecken
26          om txt[s .. s + m - 1] = sök[0 .. m - 1]
27              skriv "Söksträngen finns med förskjutning s"
28      om s < n - m
29          txtvärdes+1 ← ( bas × ( txtvärdes - txt[s] × h ) + txt[s + m] ) mod nämnare

[redigera] Komplexitet

Beräkningen av värdet som söksträngen representerar görs med hjälp av Horners algoritm, vilken har komplexitet Θ(m), där m är antalet tecken i söksträngen. På samma sätt kan det värde som representeras av de första m tecknen i texten som genomsöks beräknas med samma komplexitet. (Rad 14–17.)

Förutsatt att ett värde beräknats för m tecken i texten med en förskjutning s från dess början tar det konstant tid att beräkna det värde som representeras av m tecken med förskjutning s + 1 (rad 29) samt att jämföra detta med söksträngens beräknade värde (rad 24). Således kan värden för samtliga delsträngar av längd m i en text av längd n beräknas och jämföras med söksträngens värde med komplexitet Θ(n - m + 1). (Normalt sett anger man inte konstanter i ordo-uttryck, men i detta fall är konstanten signifikant därför att komplexiteten inte är Θ(0) när m = n.)

Sammanlagt ger detta en komplexitet på Θ(m) för förbehandlingen och Θ(n - m + 1) för sökningen. Om det inte vore för behovet att basera jämförelserna på resten av heltalsdivision skulle detta vara algoritmens totala komplexitet. Dock kvarstår den viktiga uppgiften att för varje överensstämmande textvärde och sökvärde undersöka om de enskilda tecknen stämmer överens (rad 26), vilken har komplexitet Θ(m). I värsta fall består texten som ska genomsökas och söksträngen av repetitioner av ett och samma tecken. (Till exempel kan texten bestå av "aaaaaaaaaa" och söksträngen av "aa".) Om så är fallet är Rabin-Karps algoritm lika ineffektiv som den naiva algoritmen.

Därför har Rabin-Karp, till viss besvikelse, i värsta fall samma komplexitet som den naiva algoritmen, nämligen Θ((n - m + 1)m). I många verkliga genomsnitta tillämpningar är dock situationen bättre. Om antalet förekomster av söksträngen i texten som genomsöks är få och nämnaren är större än söksträngens längd kan den genomsnittliga komplexiteten uppskattas till O(n).^[1]

[redigera] Referenser

1. ^ Cormen, T.H., Leiserson, E.L., Rivest, R.L., Stein, C, Introductions to Algorithms (2001), 2 utgåvan. USA: MIT Press. sid. 911–915. ISBN 0-262-03293-7.