Wyszukiwanie wzorca a wielomiany

29.01.2010
TrudnośćTrudność

Dzisiaj na zajęciach wróciliśmy do problemu wyszukiwania wzorca, tym razem poznając pewne bardzo dobre w praktyce algorytmy oraz drogę rozumowania potrzebną do ich wymyślenia.

Najpierw zauważyliśmy, że porównywanie dwóch dużych obiektów, można rozpocząć od porównania wartości ich funkcji hashujących. Powiedzieliśmy sobie, że funkcje hashujące występują w informatyce w dwóch kontekstach znaczeniowych:

  • w kryptografii, są to funkcje jednokierunkowe, czyli takie, że obliczenie przeciwobrazu jest obliczeniowo bardzo trudnym zadaniem. Często oprócz tego warunku chcemy także, aby trudno było wskazać jakiekolwiek dwa argumenty mające tę samą wartość
  • w probabilistycznych algorytmach i strukturach danych, funkcji hashujących używa się jako czegoś co z jednej strony jest na tyle losowe, aby równomiernie rozrzucało dane między kubełki, ale z drugiej strony na tyle deterministyczne, by dla tych samych danych zawsze dostawać ten sam wynik

Oczywiście jeśli obiektów jest nieskończenie wiele, a wartości funkcji hashującej tylko 2^32, to z pewnością kolizje się zdarzają (Zasada Szufladkowa Dirichleta :D ), ale jeśli uwierzymy, że funkcja hashująca jest w miarę losowa, to szansa false positive (czyli fałszywego wyniku pozytywnego porównania) jest znikoma. W praktyce jednak testy układają ludzie znający się trochę na algebrze. Zaproponowaliśmy kilka prostych funkcji hashujących stringi:

  • suma wszystkich bajtów
    • okazuje się wykazywać podobne właściwości jak dwie kostki do gry: wartości koncentrują się formując rozkład podobny do normalnego
    • łatwo ją oszukać zamieniając kolejność literek, albo zwiększając jedną literkę a drugą zmniejszając, czy nawet zapalając jeden bit drugi gasząc
  • xor wszystkich bajtów (czy ewentualnie: xor par bajtów, czy całych intów)
    • lepszy o tyle, że rozkład jest bardziej równomierny, ale równie łatwo, albo i łatwiej go "oszukać"
  • for(h=0,i=0;t[i];++i)h=h*5+t[i];
    • powiedzieliśmy sobie o podobieństwach do przeliczania z jednej podstawy na inną, czy do schematu Hornera, a więc dopatrzyliśmy się tutaj pewnego wielomianu w o współczynnikach t[], dla którego obliczamy wartość w(5)
    • powiedzieliśmy sobie, że wartość "5" warto zastąpić np. 17 czy 27, aby mieć mniej kolizji dla tekstów alfanumerycznych
    • znacznie trudniej przyszło nam tu "oszukać" funkcję, prosta zamiana literek zadziałała dopiero gdy zamieniliśmy literkę i-tą z i+j-tą, gdzie j to rząd elementu 5 w grupie multiplikatywnej Z_{2^32}*, czyli liczba kroków po jakiej zapętla się ciąg 1,5,25,125,...modulo 2^32. Zachęcam do wynalezienia algorytmu, który dla zadanego X i N powie jaki jest rząd elementu X w grupie multiplikatywnej modulo N. Czeka nagroda!
  • for(h=0,i=0;t[i];++i)h=h+ t[i]*(i+1);
    • o tej funkcji sobie nie powiedzieliśmy i może szkoda, bo jest bardzo prosta i odporna na zamianę literek. Dopiero zamienienie miejscami literek odległych o 2^32 jest niezauważalne

Powiedzieliśmy sobie, że z reguły liczenie funkcji hashującej wymaga czasu co najmniej Omega(n), ponieważ jeśli funkcja hashująca nie czyta całego obiektu (np. stringa) to najwyraźniej nie jest użyteczna. Stąd zaczęliśmy się zastanawiać czy funkcje hashujące faktycznie są w stanie ułatwić porównywanie obiektów?

Odpowiedź jest jak najbardziej pozytywna, choć na zajęciach liznęliśmy tylko czubek góry lodowej.

  • Jedną z głównych zalet funkcji hashujących jest to, że można je dla danego obiektu policzyć raz a dobrze i przykleić (otagować) do tego obiektu. W niektórych językach programowania stringi zawsze mają do siebie dolepioną funkcję hashującą, dzięki czemu można je porównywać bardzo szybko.
  • Czasem dwa obiekty które chcemy porównać znajdują się w odległych miejscach np. na różnych komputerach, wtedy policzenie najpierw lokalnie funkcji hashujących a potem przesłanie tylko tych 32 bitów przez sieć może zaoczędzić wiele gigabajtów. Np. Wasza przeglądarka zanim pobierze obrazek ze strony www najpierw pyta się serwera czy E-tag (funkcja hashująca) z tego obrazka nie jest czasem taki sam jak tydzień temu. Swego czasu (miałem to dziś opowiedzieć ale zabrakło czasu na osobiste wynurzenia) zdarzyło mi się odkryć na nowo algorytm rsync, używany na większości systemów linuxowych do zdalnej synchronizacji całych katalogów
  • Częstym rozwiązaniem wybieranym na zawodach gdy trzeba przechowywać pary klucz-wartość jest map<key,value> tymczasem logiczniejszym wyborem powinno być hash_map<key,value> czyli tablica hashująca wymagająca znacznie mniejszego czasu wyszukiwania (w teori!! przetestujcie najpierw)

A my skupiliśmy się na tym, że akurat w problemie wyszukiwania wzorca w tekscie przyjdzie nam liczyć funkcję hashującą dla podsłów pewnego jednego dużego słowa, więc być może da się to robić efektywniej.

Pomysł z sali był genialny: policzyć "hashe prefixowe" i starać się odtworzyć wartość funkcji hashującej na przedziale na podstawie prefiksów. Jest to piękne zastosowanie bardzo popularnego paradygmatu: jeśli problem dotyczy podprzedziałów zredukuj go do problemu dla prefiksów. Łatwo przekonaliśmy się, że wszystkie zaproponowane przez nas funkcje hashujące dają się tak liczyć. Co ciekawe da się też tak postępować w przypadku tej ostatniej propozycji którą podałem czyli t[i]*i, wymaga to jednak policzenia pewnych pomocniczych wartości.

Oryginalny pomysł (Rabin-Karp) jest być może jeszcze prostszy: zauważamy, że okienko przesuwa się zawsze o jedną literkę, więc w czasie stałym umiemy uaktualnić wartość funkcji hashującej o:

  • skasowanie literki, która wypadła z okienka - w przypadku w(5) wymagało to szybkiego potęgowania modulo 2^32, oraz dzielenia modulo 2^32. Tu przypomnę, że "5" musi być liczbą względnie pierwszą z 2^32 aby to działało, ale z reguły i tak jest nieparzyste, bo gdyby było parzyste to nie byłaby funkcja hashująca
  • przesunięcie zawartości okienka w lewo (co polega z reguły na wykonaniu jakiegoś mnożenia)
  • dodaniu nowej literki (to z reguły jest proste i zdefiniowane w samej funkcji hashującej)

Jak już pogodziliśmy się z dość abstrakcyjną koncepcją, że tekst t[] można interpretować jako ciąg współczynników wielomianu, to zeszliśmy do poziomu pojedynczych bitów. Powiedzieliśmy sobie, że ciąg bitów b[] można interpretować jako ciąg współcznników pewnego wielomianu nad Z_2, albo jeśli ktoś woli po polsku: ciąg reszt z dzielenia przez dwa współczynników pewnego wielomianu.

Przypomnieliśmy sobie szkolne dzielenie pisemne liczb i dostrzegliśmy różnice między nim a dzieleniem pisemnym wielomianów: przy dzieleniu liczb czasem bierzemy prefiks o długości o jeden większej niż liczba przez, którą dzielimy, podczas gdy przy dzieleniu wielomianów wystarcza nam prefiks o dokładnie takiej długości. Dzielenie polega z grubsza na porównywaniu wiodących współczynników wielomianu (dzieleniu ich przez siebie). Zauważyliśmy, że jeśli zwykłe dzielenie liczb (wpółczynników) przeniesiemy na świat modulo 2, to okaże się, że dzielenie sprowadza się do xorowania.

Wszystko to było nam potrzebne do tego, że skoro porównywanie stringów to porównywanie wielomianów, to być może zamiast patrzeć na to czy w(5)=v(5), moglibyśmy jakoś bardziej sensownie porównać te wielomiany.

Genialna obserwacja z sali była taka, że dwa wielomiany mimo, że się różnią mogą udawać, że mają tę samą wartość dla n różnych punktów. Oznacza to, że jeśli porównujemy dwa stringi o długości n, które się różnią, to szansa, że przez pomyłkę uznamy, że są równe,, czyli, że w(5)=v(5) jest taka jak to, że "5" jest jedną z tych O(n) pechowych wartości, dla których wielomiany się zgadzają. A że zamiast 5 możemy wziąć dowolną liczbę nieparzystą, to szansa, że juri ułoży testy które nas zmylą jest jak n/2^31 czyli nikła, nie mniej i tak możemy mieć pecha, zwłaszcza, że my wcale nie sprawdzamy czy w(5)=v(5) tylko raczej czy są sobie równe modulo 2^32 a na to szansa jest nieco większa.

Padła więc propozycja, aby mieżyć wartości funkcji hashującej dla "kilku różnych punktów wykresu", czyli nie tylko w(5), ale też np. w(17) i w(-1). Pomysł dobry, ale i tak nie da pewności, dopóki nie będziemy mięć tych funkcji hashujących O(n), co zabija całą optymalizację.

Przeszliśmy w reszcie do prawdziwej algebry i zamiast porównywać wartości wielomianów, zaczęliśmy porównywać całe wielomiany. A dokładniej reszty z dzielenia tych wielomianów przez pewien mały ustalony wielomian. Dostrzeżcie tu analogie do liczb. To tak jakby zamiast porównywać dwie duże liczby, porównywać tylko ich reszty z dzielenia przez jakąś małą liczbę. Podobnie tutaj, mamy jakiś jeden mały ustalony wielomian i patrzymy na reszty modulo ten wielomian.

Jeśli kogoś przeraża teoria wielomianów, która za tym wszystkim stoi, może myśleć po prostu o xorowaniu. Funkcja licząca w(x) MOD crc32(x) jest bowiem implementowana bardzo prosto:

  • wczytaj do okienka pierwszych 32 bity liczby
  • jeśli pierwszy bit to jeden (czyli sprawdź czy liczba jest ujemna), to zxoruj okienko ze stałą CRC32
  • przesuń zawartość okienka w lewo
  • dopisz nowy bit textu do okienka

W praktyce jest trochę inaczej. Po pierwsze czyta się po kilka bitów (np. cały bajt) na raz.

Po drugie CRC32 to wielomian 32 stopnia, czyli ma 33 współczynniki. Chodzi o to, że skoro wiadomo, że najstarszy współczynnik wielomianu to zawsze jedynka, to głupio byłoby marnować ten jeden bit skoro daje on wymierne korzyści w bezpieczeństwie transmisji. Stąd ta 32-bitowa stała, której byście używali to tak naprawdę tylko dolne 32 bity tego wielomianu, a ten najstarszy 33 domyślamy się, że jest jedynką. Nie jest on nam do niczego potrzebny w tym całym xorowaniu okienka, bo przecież wiemy jaki będzie wynik: xorujemy tylko wtedy gdy bit wiodący okienka był jedynką.

Koniec końców prawdziwa implementacja CRC32 przyprawia o ciarki na plecach przy czytaniu, bo jest na maxa haxiorska, ale to Wam raczej niepotrzebne.

Powiedzieliśmy sobie, że sum kontrolnych takich jak CRC32 używa się do weryfikowania czy przesył danych się powiódł. Przy odrobinie sprytu można odróżnić czy błąd transmisji był w danych czy w samej sumie kontrolnej.

Istnieją kody znacznie bardziej skomplikowane i pozwalające wykrywać znacznie więcej uszkodzonych bitów a nawet automatycznie naprawiać ewentualne błędy. Przykładem mogą być kody Hamminga. Jak Was nie przerażą, to po czytajcie sobie o kodach Reed-Solomona, czyli standardzie Red Book używanym dla CD. Do każdych 223 bitów dodawane jest 32bity sumy kontrolnej i to wystarcza, aby móc wytrzymać uszkodzenie 3,500 bitów pod rząd:D

Główna zaleta tego typu funkcji to właśnie ta łatwość ich updetowania. Zastanówcie się co trzeba zrobić aby uaktualnić sumę kontrolną pliku gdy:

  • dopiszecie coś na końcu
  • skasujecie coś na początku
  • zmienicie jeden bajt na inny
  • usuniecie jakiś bajt ze środka
  • dopiszecie jakiś bajt ze środka

Okazuje się, że wszystkie te operacje można robić w czasie rzeczywistym, co jest ważne dla systemów plików np.

 

 

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com