Czas na trochę kompresji!

W poprzednim wpisie na temat PlagDetectora opisaliśmy tokenizacje kodu źródłowego. Był to pierwszy z trzech etapów całego algorytmu. Dzisiaj zajmiemy się drugim krokiem, czyli kompresją tokenów.

Kilka słów o samej kompresji

Kompresja, jak sama nazwa wskazuje ;), jest to przetworzenie pewnej informacji w taki sposób, aby można było zapisać tą informacje w krótszy sposób. Przez słowo krótszy mam na myśli przy użyciu mniejszej ilości bajtów. Operacją odwrotną do kompresji jest dekompresja.

Rodzaje kompresji

Kompresje możemy podzielić na stratną oraz bezstratną. Jak sama nazwa wskazuje, w przypadku kompresji stratnej tracimy część informacji, dzięki czemu powinniśmy uzyskać większy współczynnik kompresji (przynajmniej w teorii ;)).

Oczywiście istnieje wiele algorytmów kompresji, które możemy przyporządkować do kompresji stratnej lub bezstratnej.

Spójrzmy na poniższy podział algorytmów.

  • Kompresja bezstratna
    • Kodowanie Huffmana
    • Kodowanie arytmetyczne
    • Kodowanie Shannona
    • Algorytmy słownikowe
      • LZ77
      • LZ78
      • LZW
    • PNG
  • Kompresja stratna
    • Kodowanie transformatowe
    • Kompresja falkowa
    • JPEG
    • MPEG

Oczywiście to nie są wszystkie istniejące algorytmy kompresji, ale wydaję mi się, że te najbardziej znane 🙂

Który algorytm wybrać?

Jak widzieliśmy, jest wiele algorytmów kompresji bezstratnej. Który zatem powinniśmy wybrać? Sugerując się tym co wybrali twórcy algorytmu SID (opisanym w jednym z poprzednich wpisów), również skupimy się na kodowaniu słownikowym, a konkretnie LZ77. Czemu własnie LZ77, a nie żaden z innych algorytmów kodowania słownikowego jak LZ78 czy LZW, które są rozwinięciem LZ77 (i często działają lepiej)? Zaraz wszystko powinno się wyjaśnić 🙂

Trochę teorii 🙂

Spójrzmy najpierw jak działa LZ77.

Jak wcześniej wspomnieliśmy, LZ77 jest algorytmem słownikowym? Znaczy to dokładnie tyle, że do zakodowania/odkodowania tekstu używamy słownika. W LZ77 słownik jest dynamiczny, czyli taki słownik, który jest tworzony w trakcie kodowania. Słownik tego typu ma również tę zaletę, że dostosowuje się do charakteru danych. W LZ77 słownikiem jest zakodowana/odkodowana część tekstu.

I teraz sam algorytm w teorii:

  • Dla zakodowanej części długości n i niezakodowanej długości m, czyli dla ciągu {x_1 \ldots x_nx_{n+1} \ldots x_{n+m}} szukamy najdłuższego podsłowa w ciągu ̇ {x_1 \ldots x_n} będącego prefiksem ciągu {x_{n+1} \ldots x_{n+m}} (dopasowanie).
  • Jako kod podajemy trzy liczby:
    • wielkość przesunięcia w lewo
    • ilość kopiowanych znaków
    • kod pierwszej niepasującej litery
  • Jeżeli pojawia się nowa litera, której nie można znaleźć w zakodowanej części to do słownika dodajemy {(0, 0, LITERA)}

Brzmi skomplikowanie, ale przykład powinien nam wszystko wyjaśnić 🙂

Najpierw ustalmy nasze n (bufor słownika) i (bufor kodowania). Przyjmijmy odpowiednio 7 i 8. Spróbujmy teraz zakodować następujący ciąg: abccba-abba.

  • abccba-abba    (0, 0, a)
  • abccba-abba    (0, 0, b)
  • abccba-abba    (0, 0, c)
  • abccba-abba    (1, 1, b)
  • abccba-abba    (5, 1, -)
  • abccba-abba    (7, 2, b)
  • abccba-abba    (0, 0, a)

Zatem ostatecznie nasz zakodowany ciąg ma postać powyższych siedmiu ‚trójek’, czyli: (0, 0, a), (0, 0, b), (0, 0, c), (1, 1, b), (5, 1, -), (7, 2, b), (0, 0, a).

Czemu właśnie LZ77?

I teraz wracamy do kwestii wyboru algorytmu. Dlaczego właśnie LZ77? Tak jak pisaliśmy w jednym z poprzednich wpisów, musimy ustawić nieskończony bufor słownika i bufor kodowania. Wiążę się to oczywiście z wydłużeniem czasu kompresji, ale dzięki temu możemy uzyskać większy stopień kompresji.

W tym samum wpisie, w kolejnej sekcji, jest opisana część z aproksymacją złożoności Kołmogorowa. W jednym ze wzorów możemy dopatrzeć się, że kompresji będzie również poddana lista składająca się z tokenów z dwóch porównywanych kodów źródłowych. Jakie to ma znaczenie przy wyborze algorytmu kompresji?

Wróćmy do naszego przykładu i zastanówmy się co by się stało jakbyśmy przyjęli, że n i m są nieskończone oraz mieli do zakodowania ciąg: abccba-abbaabccba-abba (podwojony ciąg z naszego przykładu).

Pierwsze sześć kroków kodowania wygląda identycznie, więc możemy zacząć ten przykład od własnie szóstego kroku.

  • abccba-abbaabccba-abba    (7, 2, b)
  • abccba-abbaabccba-abba    (3, 1, a)
  • abccba-abbaabccba-abba    (11, 9, a)

Zauważmy, że do zakodowaniu podwojonego ciągu potrzebowaliśmy tylko jednej ‚trójki’ więcej. I to jest własnie właściwość, na której nam zależy, a której nie mają LZ78 i LZW. Chcemy wykrywać plagiaty, więc powinniśmy założyć, że tokeny porównywanych kodów źródłowych mogą być takie same lub bardzo podobne ;).

I trochę praktyki!

I w końcu trochę kodu! 🙂

Zacznijmy od stworzenia klasy, która będzie nam reprezentować zakodowaną ‚trójkę’.

Banał 😉

Teraz niestety trochę magii…

Powyżej zaimplementowaliśmy algorytm LZ77 z nieograniczonym buforem słownika i kodowania. Użyty algorytm jest napisany dosyć ‚prostacko’, ale działa 🙂 Przy najbliższej okazji wrócimy do niego i go zrefaktorujemy 😉

Podsumowanie

Dzisiaj zajęliśmy się drugim etapem w naszym algorytmie do wykrywania plagiatów., a mianowicie kompresją tokenów. Zobaczyliśmy jak wygląda LZ77 i zobaczyliśmy jak działa. Na koniec w trochę prostacki sposób zaimplementowaliśmy LZ77 z nieograniczonym buforem słownikowym i kodowania w Kotlinie ;). W następnym wpisie związanym z PlagDetectorem zajmiemy się trzecim etapem czyli aproksymacją złożoności Kołmogorowa 🙂

Jedno przemyślenie nt. „Czas na trochę kompresji!”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *