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ę, iż 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, iż 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ę, iż 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
szukamy najdłuższego podsłowa w ciągu ̇ 
będącego prefiksem ciągu 
(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
Brzmi skomplikowanie, ale przykład powinien nam wszystko wyjaśnić
Najpierw ustalmy nasze n (bufor słownika) i m (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ę, iż 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, iż 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, iż do zakodowaniu podwojonego ciągu potrzebowaliśmy tylko jednej 'trójki’ więcej. I to jest własnie adekwatność, na której nam zależy, a której nie mają LZ78 i LZW. Chcemy wykrywać plagiaty, więc powinniśmy założyć, iż 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ę’.
data class CodedTriple<T>(val shift: Int, val length: Int, val next: T)Banał
Teraz niestety trochę magii…
package pl.lantkowiak.plagdetector.algorithm.compressor class Compressor<T> { fun encode(input: List<T>): List<CodedTriple<T>> { // tworzymy liste, do ktorej bedziemy dodawac nasze 'trojki' val coded = mutableListOf<CodedTriple<T>>() // dodajemy pierwsza 'trojke' zawierajaca pierwszy znak z wejscia coded.add(CodedTriple(0, 0, input[0])) var i = 1; while (i < input.size) { // pobieramy bufor slownika val dictionary = this.getDictionary(i, input) // znajdujemy najdluzsze dopasowanie ze slownika val codedTriple = this.findLongestPrefix(i, input, dictionary) // dodajemy znaleziona 'trojke' coded.add(codedTriple) // przesuwamy wskaznik pozycji i += codedTriple.length + 1 } return coded } private fun getDictionary(index: Int, input: List<T>): List<T> { return input.subList(0, index) } private fun findLongestPrefix(position: Int, input: List<T>, dictionary: List<T>): CodedTriple<T> { var i = position + 1 var last = ShiftLength(0, 0) var positionLength = this.findSequence(input.subList(position, i), dictionary) while (i < input.size && positionLength.shift > 0) { i++ last = positionLength positionLength = this.findSequence(input.subList(position, i), dictionary) } return CodedTriple(last.shift, last.length, input[position + last.length]) } // naive algorithm is used... it is slow... private fun findSequence(sequence: List<T>, dictionary: List<T>): ShiftLength { var found = false for (i in 0 until dictionary.size) { for (j in 0 until sequence.size) { if (sequence[j] != (this.getDictionaryElement(i + j, dictionary))) { found = false break } else { found = true } } if (found) { return ShiftLength(dictionary.size - i, sequence.size) } } return ShiftLength(0, 0) } private fun getDictionaryElement(position: Int, dictionary: List<T>): T { return dictionary[position % dictionary.size] } data class ShiftLength(val shift: Int, val length: Int) }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
