Jak dobre są Twoje testy? Czyli kilka słów o testowaniu mutacyjnym.

Załóżmy, że mamy pewną aplikacje, o którą bardzo się troszczymy i robimy wszystko, żeby zapewnić jak najlepszą jakość kodu tejże aplikacji. Pokrycie kodu testami jednostkowymi jest jednym ze sposobów, którego możemy użyć, aby ‚zabezpieczyć’ nasz kod przed błędami. Dwoimy się i troimy, aż w końcu udaję nam się pokryć nasz kod w 100% i teraz mamy pewność, że żaden bug nie wkradł się do naszej aplikacji! Ale czy na pewno?

Stwórzmy aplikacje, o którą zadbamy!

Zacznijmy od ‚zewnętrznego’ serwisu, który będziemy wstrzykiwać do naszej klasy.

Teraz stwórzmy główną klasę naszej aplikacji:

Jak widzimy, nie ma tutaj żadnego ‚Rocket Science’ 🙂 Pobieramy z zewnętrznego serwisu dwie liczby, a następnie je porównujemy. Jeżeli pierwsza z nich jest większa to odejmujemy od niej drugą liczbę i otrzymaną liczbę zwracamy jako wynik. W przeciwnym przypadku jako rezultat zwracamy sumę dwóch pobranych liczb.

Pora przetestować naszą aplikacje!

Stwórzmy najpierw pomocniczą klasę, która będzie implementować interfejs naszego zewnętrznego serwisu.

I teraz pierwsza metoda testowa:

W powyższej metodzie testowej sprawdziliśmy pierwszy przypadek, czyli sytuacje gdzie pierwsza pobrana liczba z zewnętrznego serwisu jest większa od kolejnej.

Teraz pora na drugi przypadek:

Tutaj pokryliśmy drugi przypadek, czyli sytuacje gdy druga liczba jest większa od pierwszej.

Wygląda na to, że pokryliśmy wszystkie ‚branche’ i nasz kod jest w pełni przetestowany, ale skąd mamy wiedzieć jak dobre są nasze testy jednostkowe?

Testy mutacyjne

Tutaj w pomocą przychodzą nam testy mutacyjne. Czym zatem są owe testy? Jest to technika polegająca na wprowadzaniu małych i losowych zmian w kodzie naszej aplikacji. Zmiany te powinny zostać wykryte przez nasze testy jednostkowe. Jeżeli, któraś ze zmian nie została wykryta oznacza to, że nasze testy mogą nie być tak dobre jak nam się wydawało 😉

Jakie zmiany?

Poniżej znajduję się lista z przykładowymi zmianami, które mogą zostać wprowadzone w naszym kodzie.

  • Zmiana granicy w warunkach, np. > zostanie zmienione na >=, >= na >, itd.
  • Negacja warunków, np. == zostanie zmienione na !=, <= na >, itd.
  • Usunięcie warunków i zastąpienie ich stałą wartością, np. a > b zostanie zmienione na true
  • Zmiana operacji matematycznych, np. dodawanie zostanie zamienione na odejmowanie, a mnożenie na dzielenie
  • Zmiana wartości zmiennych na wartości defaultowe lub stałe, np. int zostanie ustawiony na 0 lub inną losową wartość
  • Zwrócenie null zamiast obiektu
  • Pominięcie wywołania metody typu void

Właśnie zapoznaliśmy się z przykładowymi modyfikacja, które mogą zostać wprowadzone do naszej aplikacji podczas testów mutacyjnych. Nasze testy jednostkowe powinny być napisane w taki sposób, aby zmiany te spowodowały to, że nasze testy nie przejdą.

Testy mutacyjne w praktyce

Wróćmy teraz do naszego kodu, który napisaliśmy na początku i spróbujmy przeprowadzić testy mutacyjne. Z pomocą przyjdzie nam biblioteka PIT!

Konfiguracja

Konfiguracja i uruchomienie PIT są banalnie proste! Pierwsze co musimy zrobić to dodać plugin do naszego poma:

Domyślnie wszystkie klasy z naszej aplikacji zostaną poddane testom mutacyjnym. Jeżeli chcemy to zmienić to możemy skonfigurować pakiety klas/testów, które będą wzięte pod uwagę.

Uruchomienie

Aby przeprowadzić testy mutacyjne wystarczy wywołać następujące polecenie:

Gdy operacja zakończy się sukcesem zostanie wygenerowany raport z wynikami. Znajduje się on pod następującą ścieżką: target/pit-reports/yyyyMMddHHmm.

Zmutujmy naszą aplikacje!

Pora wrócić do naszej aplikacji i wykonać na niej testy mutacyjne 🙂

Po zakończeniu testów otrzymamy wygenerowany raport.

Możemy z niego wyczytać, że nasz kod jest w pełni pokryty przez nasze testy jednostkowe (Line Coverage). Możemy również zobaczyć trochę czerwonego koloru przy pokryciu mutacyjnych testów, a jak możemy się domyślać czerwony kolor nie oznacza nic dobrego 😉

Po wklikaniu się trochę głębiej będziemy mogli zobaczyć poniższy ekran.

Możemy na nim zobaczyć, która linia naszego programu nie jest wystarczająco dobrze przetestowana, a poniżej listę mutacji, które zostały przeprowadzone w poszczególnych liniach kodu. Na zielono są zaznaczone mutacje, które zostały wykryte przez testy, natomiast na czerwono mutacje, które przeżyły i nasze testy ich nie wychwyciły.

W naszym przypadku nie została wychwycona zmiana warunku w if’ie z > na >=. Czyli w tym przypadku został wykryty warunek brzegowy, który nie został sprawdzony w testach.

Poprawy w takim razie nasz drugi test tak, aby pokrył warunek brzegowy.

Po tej modyfikacji żadne mutacje nam nie straszne i nasze testy mutacyjne przejdą na zielono 🙂

Podsumowanie

Dzisiaj zapoznaliśmy się z podstawami testów mutacyjnych. Testy te mogą nam pomóc w sprawdzeniu jak dobre są nasze testy jednostkowe. Sama koncepcja testów mutacyjnych nie jest niczym nowym, ale dopiero stosunkowo od niedawna jest używana w praktyce, ponieważ testy mutacyjne są dosyć kosztowne i wymagają sporej czasu procesora, żeby przeprowadzić wszystkie kombinacje mutacji i dopiero od niedawna nasze komputery są na tyle szybkie, żeby robić to w rozsądnym czasie 🙂

Krótkie podsumowanie DSP2017

Tym razem będzie krótka nietechniczna notka 🙂

Ponownie udało mi się dotrwać do końca konkursu Daj Się Poznać! 🙂

Napisałem 20 postów, z czego:

  • 10 na temat projektu, który tworzyliśmy razem w ramach konkursu :),
  • 9 na temat związane z Javą lub około programistyczne,
  • 1 na temat moich wrażeń z warsztatów programistycznych.

Co do założeń projektu to udało się ukończyć ‚core’ aplikacji – czyli w sumie najważniejszą część, ta która wykrywa nam plagiaty 🙂

Niestety nie udało się skończyć (a właściwie zacząć ;)) REST API, które wystawiałoby odpowiednie metody do wykonania obliczenia prawdopodobieństwa oraz samego GUI. Mam nadzieję, że mimo wszystko te części i tak powstaną 🙂

To by było na tyle 🙂 Do usłyszenia w kolejnych wpisach! 🙂

Testowania część druga!

Dzisiaj przetestujemy nasz algorytm po raz kolejny!

Zestaw testowy

Tym razem jako zestaw testowy posłużą nam kody źródłowe z kursu programowania z moich studiów. Podczas kursu trzeba było między innymi napisać programy, które rozłożą liczbę na czynniki pierwsze oraz wyliczą sito Eratostenesa. I właśnie kody źródłowe do tych dwóch zadań poddamy testom.

Udało mi się skolekcjonować po 5 różnych rozwiązań dla każdego z tych zadań. Wszystkie kody źródłowe są dostępne tutaj.

Testowanie

Przetestujmy kody źródłowe dla każdego zadania osobno.

Rozkład liczby na czynniki pierwsze

Zacznijmy najpierw od wczytania kodów źródłowych i wyliczenia prawdopodobieństw.

Po wywołaniu powyższego kodu otrzymaliśmy następujące wyniki:

Przeglądając wyniki możemy zauważyć, że kody źródłowe programów 4 i 5 zostały wskazane jako bardzo podobne do siebie. Zachęcam, aby przejrzeć te kody oraz porównać również z innymi. Łatwo możemy zauważyć, że te dwa kody źródłowe wykazują bardzo dużo cech wspólnych 😉

Podobnie sprawa wygląda w przypadku kodów 1 i 2, lecz podobieństwo jest już trochę mniej widoczne.

Sito Eratostenesa

Kolejnym zestawem będą programy, które implementują algorytm Sita Eratostenesa. Podobnie jak poprzednio zacznijmy od wczytania kodów źródłowych i wyliczenia podobieństw pomiędzy nimi.

I wyniki, które otrzymaliśmy po uruchomieniu powyższego kodu:

Tutaj możemy dostrzec, że największe prawdopodobieństwo plagiatu zachodzi pomiędzy programami 1 i 2. I ponownie gdy obejrzymy oba kody źródłowe znajdziemy widoczne podobieństwo.

Podsumowanie

Dzisiaj przetestowaliśmy nasz algorytm na zestawie kodów źródłowych z moich studiów. Analizując wyniki mogliśmy wskazać kody, które wykazywały nieprzeciętne podobieństwo 😉 Wydaje się, że algorytm działa dosyć dobrze i całkiem nieźle wskazuję podobne kody źródłowe.

XStream, czyli taka lepsza serializacja!

Dzisiaj omówimy bibliotekę służącą do serializacji obiektów w Javie – XStream.

Serializacja w Javie

Po co nam biblioteka do serializacji skoro sama Java dostarcza nam taki mechanizm? Spójrzmy zatem jak to wygląda w Javie.

Na początku stwórzmy sobie prostą klasę z kilkoma polami, której instancje będziemy serializować.

Teraz stwórzmy instancje naszej klasy i ją zserializujmy, a następnie zdeserializujmy.

Jak widzimy sama serializacja jest dosyć prosta i możemy ją łatwo wykonać w kilku liniach kodu.

Zerknijmy teraz do naszego pliku, który zawiera zserializowany obiekt.

Jak widzimy nie jest to zbyt czytelne 😉

Niestety z tego pliku nie jesteśmy w stanie w łatwy sposób odczytać zserializowanych wartości, nie mówiąc o ich edycji.

XStream w akcji!

I tutaj z pomocą przychodzi XStream!

Na początku musimy dodać zależność do naszego projektu:

Zróbmy teraz najprostszą serializacje i deserializacje naszego obiektu.

Jak widać operacje te przy użyciu XStream również możemy wykonać przy użyciu kilku linii kodu.

Na samym początku musimy stworzyć instancje XStream, a następnie wywołać na niej odpowiednio metody toXML lub fromXML. Pierwsza metoda przyjmuje jako parametry obiekt, który ma być zserializowany oraz OutputStream, do którego zserializowany obiekt ma być zapisany. Druga metoda natomiast na wejście przyjmuje InputStream, z którego ma być odczytany zserializowany obiekt, a na wyjściu otrzymujemy nasz zdeserializowany obiekt.

Zajrzyjmy teraz do pliku z zserializowanym obiektem.

Jak widać plik jest w formacie XML (co mogła sugerować nazwa metody toXML ;)). Z pliku możemy odczytać, która klasa jest zserializowana – pl.lantkowiak.SerializableClass. Widzimy też pełną strukturę klasy wraz z wartościami poszczególnych pól. Dzięki temu bez problemu możemy odczytać jak wygląda zapisany obiekt, a w razie potrzeby możemy go bez problemy edytować.

Podsumowanie

Dzisiaj zapoznaliśmy się z biblioteką XStream, której możemy użyć do serializacji obiektów do XMLa, dzięki czemu zserializowany obiekt będzie dla nas czytelny i łatwy do modyfikacji.

XStream posiada jeszcze bardziej zaawansowane opcje, z którymi warto się w przyszłości zapoznać 🙂

Przetestujmy skuteczność algorytmu – część pierwsza!

Dzisiaj zajmiemy się przetestowaniem naszego algorytmu do wykrywania plagiatów w praktyce. Miejmy nadzieję, że to chociaż trochę zadziała 😉

Zestaw testowy

Musimy najpierw zacząć od przygotowania danych, na których będziemy testować naszą aplikacje.

Dzisiaj przygotujemy specjalnie spreparowane kody źródłowe i zobaczymy jak z nimi poradzi sobie nasza aplikacja.

Zacznijmy od stworzenia naszej wyjściowej klasy, która będzie zawierała kilka pól oraz metod.

Będzie to nasz wyjściowy kod, od którego będziemy robić wszystkie modyfikacje.

Wykonajmy następujące modyfikacje kodu:

  1. Zmieńmy nazwy metod i pól
  2. Przenieśmy operacje z metod do metody main, a same metody usuńmy
  3. Dodajmy kilka nieużywanych metod
  4. Czwartym kodem do porównania, będzie kopia oryginalnego kodu

Testujemy!

Stwórzmy prostą metodę, która wczyta nasze kody źródłowe oraz wywoła naszą aplikacje i wyliczy prawdopodobieństwo.

Omówmy wyniki!

Pora na krótką analizę wyników.

  1. Zmienione nazwy metod i pól
    Program zwrócił następujący wynik:

    Tutaj możemy zauważyć, że program poradził sobie całkiem nieźle. Wskaźniki są bardzo bliskie 1, więc możemy z dużą dozą prawdopodobieństwa stwierdzić, że porównywane programy zawierają ten sam kod.
  2. Kod z metod przeniesiony do głównej metody
    Zwrócony wynik:

    Tutaj niestety algorytm poradził sobie dużo gorzej. Wystarczyła drobna zmiana w kodzie i stopień wykrywalności jest o wiele mniejszy. Może to byś spowodowane tym, że testowany kod jest krótki i nawet takie małe zmiany znacząco wpływają na wyniki. Warto na pewno się temu przyjrzeć w przyszłości.
  3. Kod z nieużywanymi metodami
    Wyliczone podobieństwo:

    Na tym przykładzie możemy zobaczyć w praktyce wykorzystanie wskaźników px oraz py. O ile główny wskaźnik wynosi tylko 0.63 i nie musi wydawać się podejrzany, o tyle wartość wskaźnika px (0.92) mocno wskazuje, że jeden z porównywanych kodów zawiera dużą część drugiego kodu, oraz że mógł zajść plagiat.
  4. Porównanie dwóch identycznych kodów źródłowych
    Wynik:

    Tutaj podobnie jak w pierwszym przypadku algorytm poradził sobie bardzo dobrze i wyliczył wskaźniki bliskie 1.

Podsumowanie

Dzisiaj wykonaliśmy pierwsze testy naszego algorytmu. Do testów użyliśmy kilka spreparowanych kodów źródłowych. Pierwsze wyniki wskazują, że algorytm jakieś prawdopodobieństwo wylicza 😉

W następnym wpisie odnośnie PlagDetectora przeprowadzimy testy na kodach źródłowych z28za czasów studenckich 😉

Wrażenia z warsztatów ReactJS

Dzisiaj opowiem o swoich wrażeniach z warsztatów ReactJS, na których ostatnio byłem.

Jakie warsztaty?

Warsztaty, o których miałem przyjemność być to  „React.js dla programistów znających JS”. Spotkanie był organizowane przez DevMeetings, we Wrocławiu. Celem warsztatów, jak sama nazwa wskazuję ;), było wprowadzenie nas do Reacta oraz zbudowanie naszej pierwszej aplikacji w Reactie.

Jaki był materiał?

Teraz kilka słów o samym materiale, który był poruszony w czasie warsztatów.

Krótkie przypomnienie JSa

Na początku zostało przypomniane kilka użytecznych funkcji JSowych, które miały się przydać w dalszej części kursu. Przypomnieliśmy sobie o takich funkcjach jak:

  • map
  • filter
  • arrow functions
  • classes

I w końcu React!

Czyli pora na mięso 🙂

  • pierwsza funkcja w ReactJS
  • Komponenty
  • Klasy
  • Obsługa eventów
  • Obiekty stanowe
  • Routing

    Redux

    Czyli dodatek do Reacta, który służy do zarządzania stanem. aplikacji. Został on wspomniany raczej na zasadzie ciekawostki czego się używa w poważnych aplikach ;). My nie mieliśmy okazji go używać na warsztatach.

Moje wrażenia

I na końcu kilka słów o moich subiektywnych wrażeniach z warsztatów 🙂

Był to dla mnie pierwszy kontakt z Reactem. Na tych kilku-godzinnych warsztatach dostałem wystarczająco informacji, żeby mieć jakiekolwiek pojęcie z czym to się je. Warsztaty dla mnie były prowadzone w fajnej formie i wyglądało na to, że prowadzący się zna na rzeczy 🙂

Jedynym minusem, który odnotowałem był brak wcześniejszej informacji o wymaganych toolach. Przez to na początku straciliśmy około 30 minut czekając, aż wszystkie osoby będą miały zainstalowane nodeJS itd. Po za tą drobnostką wszystko było ok 🙂

Podsumowując – jestem zadowolony z warsztatów i w przyszłości z chęcią pójdę na nie jeszcze raz jak pojawi się interesujący temat 🙂

Wyliczmy podobieństwo!

W poprzednim wpisie dotyczącym PlagDetectora zajmowaliśmy się kompresją tokenów. Dzisiaj zajmiemy się trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobieństwa pomiędzy kodami źródłowymi.

Mała powtórka

Na początku wróćmy do wpisu gdzie omawialiśmy cały algorytm i przypomnijmy sobie kilka wzorów.

Wartość aproksymacji Kołmogorowa będziemy przybliżać przy pomocy poniższego wzoru.
{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}.

Przez {\emph{K(x)}} będziemy rozumieć wielkość (w bajtach) skompresowanego kodu źródłowego i będziemy oznaczać jako {\emph{Comp(x)}}. W związku z tym wzór na przybliżenie aproksymacji Kołmogorowa przyjmie postać:

{d(x,y) = 1 - \frac{Comp(x)-Comp(x|y)}{Comp(xy)}}.

Wartość {\emph{Comp(x|y)}} obliczymy w następujący sposób:
{Comp(x|y) = Comp(xy) - Comp(y)}.

Zatem ostatecznie wartość aproksymacji Kołmogorowa obliczymy z następującego wzoru:
{d(x,y) = 1 - \frac{Comp(x)+Comp(y)-Comp(x|y)}{Comp(xy)}}.

Tak obliczona wartość aproksymacji złożoności Kołmogorowa przeliczymy na współczynnik {\emph{D}} według wzoru:
{D = 1 - d(x,y)}.

I ten właśnie wskaźnik będzie naszym głównym wyznacznikiem, którego będziemy używać do oceny prawdopodobieństwa zajścia plagiatu.  Im wartość {\emph{D}} jest większa, tym prawdopodobieństwo plagiatu jest większe.

Dodatkowo dla każdej pary programów obliczymy wartości {\emph{px}} oraz {\emph{py}}. Wartości te będą przedstawiać procentową zawartość informacji z jednego kodu źródłowego zawartych w drugim. Wartości te obliczymy używając następujących wzorów:
{px=\frac{D(\alpha + 1)}{D+1}},
{py=\frac{D(\frac{1}{\alpha} + 1)}{D+1}}, gdzie:
{\alpha = \frac{Comp(y)}{Comp(x)}}.

Wskaźniki {\emph{px}} i {\emph{py}} posłużą nam jako dodatkowa informacja, wskazująca na zawartość jednego ciągu w drugim. Wartości te pomogą nam wskazać zajście plagiatu, w przypadku gdy jeden z programów zawiera w sobie kod drugiego, lecz sam program jest o wiele bardziej rozbudowany i wartość współczynnika {\emph{D}} może nie wskazać zajścia plagiatu.

I teraz kodowanie!

Zacznijmy od klasy, która przechowa nasze wyniki.

Podobnie jak przy tworzeniu klasy do przechowywania wyników kompresji – banał 😉

Teraz pora na obliczenia!

Tym razem nie zobaczymy żadnej magii w kodzie. Mamy tylko zwykłe przepisanie wzoru na Kotlina 😉

Podsumowanie

Dzisiaj zajęliśmy się ostatnim krokiem algorytmu, a mianowicie aproksymacją złożoności Kołmogorowa. Przypomnieliśmy sobie wzory potrzebne do obliczeń, a następnie zaadoptowaliśmy te wzory do naszego kodu. W następnym wpisie wykonamy w końcu nasze 3 kroki razem i przetestujemy działanie algorytmu 🙂

Działanie na kilka frontów – czyli o wątkach słów kilka

Dzisiaj porozmawiamy sobie o działaniu na kilka frontów 😉 Czyli zobaczymy co to jest wątek i z czym to się je 🙂

W tym wpisie zajmiemy się głównie sposobami tworzenia wątków.

Czym zatem jest ten wątek?

Wątek jest niezależną ścieżką wykonania działającą w ramach procesu.

Czym zatem jest proces? Proces jest to egzemplarz wykonywanego programu.

Jak zatem widzimy wątek jest wykonywany w ramach procesu. W ramach jednego procesu może być wykonywanych wiele wątków.

Powinniśmy również wiedzieć, że wątki dzielą zasoby pomiędzy sobą w ramach jednego procesu, natomiast każdy proces ma przydzielone swoje zasoby.

Wątki w Javie

W Javie wątki są reprezentowane przez klasę Thread.

Nowy wątek możemy utworzyć w Javie na 3 sposoby:

  1. Rozszerzając klasę Thread
  2. Implementując interfejs Runnable
  3. Implementując interfejs Callable

Czym się różnią te podejścia?

Rozszerzenie klasy Thread

Aby utworzyć wątek musimy rozszerzyć klasę Thread oraz nadpisać metodę run.

W metodzie run umieszczamy nasz kod, który zostanie wykonany w naszym nowym wątku.

Implementacja interfejsu Runnable

Interfejs Runnable wymaga przez nas zaimplementowania jednej  metody – run.

Podobnie jak w poprzednim przypadku kod, który ma być wykonany w wątku umieszczamy w metodzie run.

Implementacja interfejsu Callable

Interfejs Callable jest generyczny i dostarcza metodę call, która zwraca obiekt typu, którego użyliśmy przy implementacji Callable.

Tym razem kod, który ma się wykonać w nowym wątku umieszczamy w metodzie call. Dodatkowo call wymuszą zwrócenie obiektu. Zwróćmy również uwagę, że Callable deklaruje możliwość rzucenia wyjątku kontrolowanego (checked exception).

Co wybrać?

Poznaliśmy 3 sposoby tworzenia wątków w Javie, ale który powinniśmy używać?

Sposobu pierwszego, czyli rozszerzania klasy Thread będziemy prawdopodobnie używać najrzadziej. Musimy pamiętać, że dziedziczenie powinno spełniać warunek IS-A, czyli klasa pochodna powinna być typem klasy nadrzędnej. Raczej rzadko będziemy spotykać się z sytuacją gdzie tworzona przez nas klasa będzie musiała rozszerzać Thread, aby rozszerzać jej funkcjonalność. Więcej o dziedziczeniu i kompozycji porozmawiamy w jednym z kolejnych wpisów.

Czyli pozostały nam dwie opcje Runnable i Callable. Tutaj powinniśmy dokonać wyboru mając na uwadze różnice pomiędzy tymi interfejsami:

  • metoda run z interfejsu Runnable jest typu void, natomiast metoda call z Callable zwraca wynik obliczeń
  • metoda call pozwala zadeklarować wyjątki kontrolowane (checked exceptions), czego nie pozwala metoda run.

Podsumowanie

Dzisiaj omówiliśmy sposoby tworzenia wątków w Javie. Powinniśmy zapamiętać, że wątek możemy stworzyć na 3 sposoby:

  • rozszerzając klasę Thread,
  • implementując interfejs Runnable,
  • implementując interfejs Callable.

W następnym wpisie związanym z wątkami omówimy sposoby na uruchomienie i zarządzanie naszymi wątkami.

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 🙂

Budowniczy w akcji!

Dzisiaj porozmawiamy trochę o jednym z bardziej popularnych wzorców projektowych, a mianowicie o Budowniczym (Builder). Jest to jeden z kreacyjnych wzorców projektowych.

A na co to komu?

Dzięki użyciu budowniczego możemy z pewnością osiągnąć przynajmniej dwie rzeczy:

  • oddzielimy tworzenie obiektu od jego reprezentacji,
  • nasz kod powinien stać się trochę bardziej przyjazny dla oka 😉

The good old way…

Na początku zobaczmy jak będzie wyglądał zwykły obiekt POJO. Jako przykład stwórzmy klasę, która będzie zawierała wszystkie informacje o mailu, który będzie mógł być później wysłany.

Jak widzimy, nasza klasa ma za zadanie przechowanie informacji o tym do kogo mail będzie wysłany (to), dodatkowych odbiorów (cc), temat maila (subject) oraz jego treść (content).

Stwórzmy teraz instancje naszej klasy:

Co prawda ten kod nie wygląda jeszcze zbyt strasznie, ale wyobraźmy sobie teraz, że do naszej klasy dodajemy jeszcze kilka pól jak bcc, mime type, załączniki i jeszcze kilka innych. Wtedy nasza klasa trochę się rozrośnie i stworzenie instancji tej klasy nie będzie wyglądało zbyt przyjemnie, szczególnie mając na uwadze, że dużo pól naszej klasy ma ten sam typ.

A co jeśli…

Możemy się okazać, że część pól w naszej klasie nie jest obowiązkowa przy tworzeniu naszego obiektu. W naszym przykładzie pole cc nie musi być obowiązkowe. Co w takim przypadku powinniśmy zrobić?

Możemy stworzyć dodatkowy konstruktor bez pola cc 🙂 Tylko co jeśli pól opcjonalnych będziemy mieć kilka? Tworzenie wszystkich kombinacji konstruktorów zdecydowanie odpada.

W takim przypadku możemy przecież stworzyć POJO z setterami/getterami 🙂

I stwórzmy teraz instancje naszej klasy, tylko tym razem bez inicjowania pola cc:

Podejście to pozwala nam stworzyć instancje naszego obiektu tylko z wybranymi przez nas polami. Dzięki setterom jest również trudniej o pomyłkę związaną z kolejnością przekazywanych parametrów do konstruktora.

Czy można zrobić to ładniej?

Wydaję mi się, że można 😉 I właśnie budowniczy przyjdzie nam z pomocą 🙂

Budowniczy pomaga nam w tworzeniu skomplikowanych obiektów poprzez danie możliwości tworzenia (budowania) ich kawałek po kawałku. Stwórzmy zatem budowniczego do naszej klasy 🙂

Zmiany, których dokonaliśmy w naszej klasie to:

  • stworzyliśmy prywatny konstruktor do klasy Mail, aby nikt nie stworzył nam naszego obiektu na lewo ;),
  • dodaliśmy statyczną metodę builder(), która zwraca nową instancje budowniczego,
  • dodaliśmy samego budowniczego.

Klasa budowniczego zawiera w sobie pole z instancją budowanego obiektu, metody odpowiadające ustawianym polom oraz metodę build(), która wieńczy dzieło i zwraca nam naszą zbudowaną instancje klasy Mail. Zwróćmy uwagę, że metody budowniczego zwracają instancje budowniczego. Dzięki czemu możemy zbudować nasz obiekt w sposób ‚płynny’ (fluent interface) 😉

I w ten oto sposób udało nam się stworzyć prostego budowniczego 🙂

A co jeśli… (cz. 2)

Wcześniej zauważyliśmy, że część pól z naszej klasy może być opcjonalna. Warto, żebyśmy też popatrzyli w drugą stronę – część pól z może być konieczna do poprawnego zainicjowania naszego obiektu. W naszej klasie Mail możemy uznać, że pola to, subject i content są obowiązkowe. I co teraz?

The good old way jeszcze raz 😉

Wróćmy na sekundę do podejścia z POJO. Problem ten możemy tutaj rozwiązać poprzez stworzenie konstruktora, który będzie przyjmować obowiązkowe parametry oraz stworzeniem setterów dla parametrów opcjonalnych.

Tylko w tym podejściu znów powraca problem z wieloma parametrami w konstruktorze, które nie wyglądają zbyt ładnie oraz dodatkowo nie jest trudno o pomyłkę.

I wróćmy do budowniczego

A jak możemy ten problem rozwiązać w budowniczym?

Możemy obowiązkowe parametry przekazać do konstruktora budowniczego, ale oczywiście rezygnujemy z tej opcji 😉

Do rozwiązania tego problemu musimy trochę zmodyfikować naszego budowniczego, którego już stworzyliśmy.

Na początku stwórzmy sobie kilka prostych interfejsów.

Zauważmy, że dla każdego obowiązkowego pola stworzyliśmy interfejs, który zawiera dokładnie jedną metodę odpowiadającą za ustawienie tego pola. Zwróćmy uwagę też, że metoda ustawiające dane pole zwraca interfejs do ustawienia kolejnego obowiązkowego pola. Wyjątkiem jest interfejs ContentStep, który ustawia ostatnie obowiązkowe pole i zwraca interfejs OptionalSteps, który zawiera możliwość ustawienia wszystkich opcjonalnych pól oraz metodę build(), która zwraca nam gotowy obiekt.

Teraz musimy użyć tych interfejsów w naszym budowniczym.

Sama implementacja znacząco się nie zmieniła. Teraz nasz builder implementuje stworzone przez nas interfejsy. Musieliśmy też zmienić zwracane typy w metodach budowniczego.

I ostatnia zmiana, którą musieliśmy zrobić to zmiana typu zwracanego w metodzie tworzącej naszego budowniczego, żeby zwracała interfejs do pierwszego obowiązkowego pola.

 

Samo budowanie obiektu nie zmieniło się w porównaniu do tego, jak było w naszym pierwszym budowniczym, ale dzięki tym kilku interfejsom klient używający naszego budowniczego będzie musiał podać wszystkie obowiązkowe pola, żeby utworzyć obiekt.

I to jest właśnie to, co chcieliśmy osiągnąć 🙂