Wyszukiwanie wzorca w tekscie
Ostatnio zmodyfikowano 2016-05-18 13:52
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ź :)
|
|
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.htmlh(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 |
|
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 |
|
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
|
|
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 |
|
« 1 » |