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:
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.
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
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 17 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 2 | |
Tomasz Lubiński | Java | .java | .java | ***** / 2 |
Poprawiony: 15 sierpnia 2012 13:22