algorytm.org

Algorytm KR (Karpa-Rabina)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm KR (Karpa-Rabina)
Ocena użytkowników:***** / 15
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 16 listopada 2006 23:46

Podstawowym problemem dotyczącym tekstów jest problem wyszukiwania wzorca. Polega on na znalezieniu wszystkich wystąpień tekstu wzorzec, w tekście tekst. Przyjmujemy ponadto, że: |wzorzec|=m, |tekst|=n oraz n>=m.

W Algorytmie tym stosujemy funkcję haszującą (mieszającą) h, dzięki, której będziemy obliczać pewną wartość (kod) podsłowa teksti=tekst[i..i+m-1] tekstu wejściowego. Jeśli h(teksti)=h(wzorzec), to z bardzo dużym prawdopodobieństwem wzorzec występuje w tekscie na i-tym miejscu. Efektywność algorytmu wynika z możliwości szybkiego obliczenia wartości h(teksti+1), jeżeli wartość h(teksti) jest już znana.
Zakładamy, że alfabet składa się z r symboli i każdemu z nich przypisana jest wartość liczbowa (np.: z tablicy znaków ASCII). Niech q będzie pewną, bardzo dużą liczbą pierwszą (np.: taką, że q(r+1) nie powoduje nadmiaru). Jeśli z jest tekstem o długości m, to wówczas funkcję haszującą h definiujemy jako:
h(z)=(z[1]r^{m-1}+z[2]r^{m-2}+ ... +z[m]) \mod q
Prawdopodobieństwo, że wartości h będą takie same dla dwóch różnych argumentów jest bardzo małe i wynosi: 1/q, gdyż należy pamiętać, że q jest bardzo duże. W oryginalnej wersji liczba pierwsza q wybierana jest losowo. Do znajdowania liczb pierwszych zastosować możemy sito Eratostenesa.

Algorytm ma postać:
h1=h(wzorzec);
rm=rm-1;
h2=h(tekst[1..m]);
while i<=n-m+1 do
begin
  j:=0;
  if h2=h1 then while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
  if j=m then writeln((IntToStr(i)));//wypisanie indeksu, w którym istnieje dopasowanie
  h2:=((h2-tekst[i])*rm) * r + tekst[i+m]) mod q;
  i:=i+1;
end;

W pierwszej i trzeciej lini algorytmu do obliczenia wartości h1 oraz h2 możemy użyć algorytmu Hornera. W literaturze spotkać można się z określeniem, iż algorytm KR jest agorytmem praktycznym. Należy jednak podkreślić, że możemy napotkać trudności podczas obliczania dużych wartości. Na przykła dla alfabetu złożonego z wszystkich znaków ASCII (256) i wzorca długości 10 znaków zmienna rm ma wartość 1208925819614629174706174, należałoby zatem użyć algorytmu szybkiego potęgowania modularnego.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 11
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 2
Tomasz LubińskiJava
.java
.java
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 15 sierpnia 2012 13:22
Dodaj komentarz