Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Wyszukiwanie wzorca w tekscie

Ostatnio zmodyfikowano 2016-05-18 13:52
Autor Wiadomość
mrci
Temat założony przez niniejszego użytkownika
Wyszukiwanie wzorca w tekscie
» 2016-05-18 12:02:59
Witam mam do napisania program wyszukujący wzorzec w tekscie na podstawie algorytmu Karpa-Rabina wykorzystujący dwie różne funkcje haszujące(suma cyfr oraz mnożenie z potęgami) i zliczyć ilość alertów w obu przypadkach i porównać. Tekst składa się z cyfr 0,1 lub 2, jesli chodzi o sposób z sumowaniem cyfr to nie mam problemu z wyliczeniem wartosci następnego hasza na podstawie poprzedniego, po prostu odejmuje początek i dodaje nową "końcówkę". Natomiast w przypadko haszowania sposobem mnożenia z potęgami nie jest już tak prosto. Schemat wygląda następująco:

tekst: 1201
wzor: 120

hasz(120) = 3^2 * 1 + 3^1 * 2 + 3^0 * 0 = 9 + 6 + 0 = 15

porownujemy z haszem pierwszych 3 cyfr i też wychodzi nam 15 wiec ok i lecimy dalej

hasz(201)=3^2 * 2 + 3^1 * 0 + 3^0 * 1= 18 + 0 + 1 = 19

Przechodząc do sedna problemu. Nie mam pojęcia jak na podstawie poprzedniego haszu obliczyć następny. Mógłbym odjąć od 15 wartość (3^2*1)
i dodać (3^0*1), ale należało by jeszcze cyfry 2 oraz 0 pomnożyć raz jeszcze przez 3 do potęgi o 1 wyższej, lecz tu nastepuje problem bo chciałbym aby wykonywało się to liniowo, a nie w zlozonosci
[dlugoscTekstu * (dlugoscWzorca-2)].
Jeśli ktoś z was miał styczność z takim oto programem lub wie gdzie mógłbym znaleźć jakieś wytłumaczenie jak należało by rozmiwązać ten problem(Google przeleciałem od A do Z :) ) to z góry dziękuję za odpowiedź :)

P-148366
darko202
» 2016-05-18 12:55:03
>> Nie mam pojęcia jak na podstawie poprzedniego haszu obliczyć następny.
patrząc na
http://www.algorytm.org​/przetwarzanie-tekstu​/algorytm-kr-karpa-rabina.html
h(z)=(z[1]r^m−1 +z[2]r^m−2+...+z[m])mod q
np. dla tekstu "abcdefgh"  podciągu z o długości np. 3

z1="abc"
z2="bcd"

czym się różnią przy liczeniu h(z)
h(z1) = ('a'* r^2 + 'b'* r + 'c' ) mod q
h(z2) = ('b'* r^2 + 'c'* r + 'd' ) mod q

chcemy aby
h(z2) = (h(z1) + coś ) mod q

czyli rozwiązać równanie
('b'* r^2 + 'c'* r + 'd' ) mod q = (h(z1) + coś ) mod q
i uogólnić to dla dowolnej długości

najprościej to rozwiązać dodając i odejmując h(z1) i rozwijając jeden z nich
('b'* r^2 + 'c'* r + 'd' ) mod q =
('b'* r^2 + 'c'* r + 'd' + h(z1) - (h(z1) ) mod q =
( h(z1) + 'b'* r^2 + 'c'* r + 'd' - 'a'* r^2 - 'b'* r - 'c'  ) mod q =
( h(z1) + ('b'* r)*(r-1) + ('c'* r)*(r-1) + 'd' - 'a'* r^2 ) mod q =
( h(z1) + (('b' + 'c')*(r-1) - 'a'* r)*r + 'd' ) mod q              //a*r*r  = (a*(r-1)+ a)*r
( h(z1) + (('b' + 'c' - 'a')*(r-1) - 'a')*r + 'd' ) mod q

mamy już jakiś wynik który pokazuje uogólnienie na to 'coś'

h(z2) = ( h(z1) - (((z[2] +...+ z[m-1]- z[-1])*(r-1) - z[-1])*r + z[m] ) mod q

jakoś tak jeśli gdzieś się nie pomyliłem :-)

sprawdź i ewentualnie popraw 





P-148367
mrci
Temat założony przez niniejszego użytkownika
» 2016-05-18 13:32:06
Dzięki bardzo, ale z tego co widzę to jednak nie rozwiązuje problemu. Bo mamy teraz uogólnienie na to "coś" co jednak wymaga podania pewnej sumy wyrazow od ilości elementów która nie jest z góry ustalona. Dla dlugosci 3 sumujemy dwa znaki (b i c), dla dlugosci 4 będą to 3 elementy dla 5 mamy 4 itd itd. Wynika z tego, że nie znając ilości sumowanych elementów, potrzebnych do wyliczenia "coś" będziemy musieli użyć pętli sumującej o długości
[0,dlugoscWzorca-1], a jako że to wszystko będzie opatrzone pętlą, która przeczesuje cały tekst o długości N, to przy każdym następnym kroku wyliczamy następny hash na podstawie poprzedniego, który uruchamia pętlę
for(i=0;i<dlugoscWzorca-1;i++)
co za tym wracamy do punktu wyjscia czyli złożoność N*dlugoscWzorca-1
P-148368
darko202
» 2016-05-18 13:38:09
Zastanawiając się nad tym problemem znalazłem prostsze rozwiązanie

h(z1)= ( h(z2)*r + z1[0]*r^(m-1) -z[m]*r ) mod q


P-148369
mrci
Temat założony przez niniejszego użytkownika
» 2016-05-18 13:52:16
mógłbym raz jeszcze opisać wszystkie zmienne. I chyba wyliczamy z2 na podstawie z1
P-148371
« 1 »
  Strona 1 z 1