8:22
13/11/2012

* XOR search

Przydatne narzędzie, teraz także na OS X.

Przeczytaj także:

Ten wpis pochodzi z naszego linkbloga *ptr, dlatego nie widać go na głównej.
*ptr możesz czytać przez RSS albo przez sidebar po prawej stronie serwisu.

5 komentarzy

Dodaj komentarz
  1. Trochę nieoptymalne to szukanie, po prostu 256 razy szuka xorując sobie bufor za każdym razem inną stałą. A wystarczyłoby wyliczyć stałą xorującą na podstawie kolejnych znaków z pliku xorując je z pierwszym znakiem szukanego stringu (pierwszy znak dla tej stałej już się będzie zgadzał).

    • A znasz bajke o Tymi Tu?

    • A jeszcze lepiej: zrobić xor sąsiednich znaków w pliku i szukanym tekście, wtedy można użyć dowolnego algorytmu szukania (np. użytego tam KMP). Oczywiście raz zamiast 256 razy.

      A bajkę o Tymitumie znam, tylko jakoś nie widzę zastosowania ;)

    • Mik, mógłbyś rozwinąć te metody albo podrzucić link do jakichś materiałów???

    • Może zbyt skrótowo to wytłumaczyłem. Lepiej na przykładzie. Dla uproszczenia binarnie.
      Plik: 10101001010101001001
      Szukany string: 11011
      Metoda 1:
      Wiemy że szukany string zaczyna się od 1, więc stała xorująca na pierwszej pozycji pliku musi być 0 żeby szukany string mógł się tam znaleźć (bo w pliku jest tam też 1), dla drugiej pozycji pliku stała xorująca = 1 (bo w pliku jest 0) itd. Ogólnie stała xorująca = pierwszy znak szukanego stringu xor znak z pliku gdzie akurat spodziewamy się tego znaku.
      Metoda 2:
      Xorujemy sąsiednie znaki w pliku i szukanym stringu (skraca nam to oba o 1 znak):
      Plik: 10101001010101001001 => 1111101111111101101
      Szukany string: 11011 => 0110
      no i “od razu widać” (znaczy się: używamy dowolnej metody szukania) że szukany string występuje pod koniec.
      Dowód poprawności obu metod pozostawiam czytelnikowi :)

Twój komentarz

Zamieszczając komentarz akceptujesz regulamin dodawania komentarzy. Przez moderację nie przejdą: wycieczki osobiste, komentarze nie na temat, wulgaryzmy.

RSS dla komentarzy: