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 🙂

Tokenizacja kodu źródłowego

W tym wpisie opiszę pierwszy etap w wykrywaniu plagiatów w Plag-Detectorze.

O co właściwie chodzi?

Tokenizacja jest terminem występującym często w tematyce związanej z bezpieczeństwem czy też szyfrowaniem. W tym przypadku chodzi o coś trochę innego. Wspomniałem o tym w jednym z poprzednich wpisów.

Poniżej użyję tego samego przykładu, którego użyłem w tamtym wpisie.

Ideą tokenizacji jest zamiana kodu źródłowego na ciąg tokenów. W listingu powyżej można zobaczyć jak może wyglądać przykładowa tokenizacja kawałka kodu.

Jak to zrobić w praktyce?

Oczywiście można by samemu napisać tokenizer, ale byłaby to dość skomplikowana i długa robota. Oczywiście zakładając, że tokenizer powinien uwzględniać gramatykę danego języka. Z pomocą przychodzi nam ANTLR, czyli ANother Tool for Language Recognition.

Dla ANTLRa możemy zdefiniować gramatykę, według której będzie przeprowadzona tokenizacja. Zdefiniowanie gramatyki dla każdego języki również byłoby dosyć karkołomnym zadaniem. Na szczęście większość gramatyk dla popularnych języków programowania została już zdefiniowana i jest dostępna tutaj: https://github.com/antlr/grammars-v4.

Konfiguracja i użycie ANTLRa

Ponieważ jesteśmy leniwi, chcemy żeby wszystko nam się robiło automatycznie. I tak jest w tym przypadku 🙂

Zależności

Konfiguracje musimy standardowo zacząć od dodania zależności do naszego pliku pom.xml.

Gramatyka

Następnie musimy znaleźć interesującą nas gramatykę i wrzucić ja do folderu antlr4, który umieszczamy w katalogu serc/main. Dodatkowo, jeżeli chcemy, żeby kod wygenerowany na podstawie naszej gramatyki był w konkretnym pakiecie to musimy gramatykę wrzucić właśnie pod taką ścieżką. Czyli np. jeżeli chcę, żeby klasy związane z gramatyką były w pakiecie pl.lantkowiak.plagdetector.algorithm.grammar, to powinienem mieć taką strukturę katalogów jak przedstawiona poniżej.

Pluginy

Teraz potrzebujemy dodać do naszego poma kolejne dwa pluginy.

antlr4-maven-plugin

Plugin ten będzie odpowiedzialny za wygenerowanie klas związanych z naszą gramatyką.

build-helper-maven-plugin

Ten plugin sprawia, że nasze wygenerowane źródła będą widoczne w Eclipsie jako klasy, których możemy użyć.

Mały hack

Jeżeli będziemy wykorzystać wygenerowane klasy w naszym kodzie Kotlinowym to nasz projekt niestety się nie zbuduje. Maven nie będzie widział wygenerowanych źródeł. Aby to naprawić musimy w naszym pomie zamienić kolejnością pluginy odpowiedzialne za kompilacje Javy i Kotlina. W wpisie Hello Kotlin pisałem, że plugin do kompilacji kodu Kotlina powinien być przed pluginem Javovym, żeby kod kotlina mógł być użyty w Javie. Niestety póki co musiałem z tego zrezygnować, aby móc zautomatyzować proces generacji kodów źródłowych dla gramatyk ANTLRowych.

Użycie w kodzie

Dla np. gramatyki dla Java 8 ANTLR wygeneruje następujące pliki:

Klasa, która będzie nas interesowała do przeprowadzenia tokenizacji to Java8Lexer.

Ponieważ Plag-Detector będzie wspierał wiele języków programowania stworzyłem enuma, który będzie zawierał wszystkie wspierane języki.

Następnie stworzyłem prostą fabrykę, która na podstawie przekazanego enuma zwróci mi instancje oczekiwanego leexera.

Klasa Lexer jest klasą abstrakcyjną, po której dziedziczą wszystkie lexery wygenerowane przez ANTLRa.

Sama tokenizacja jest już bardzo prosta:

W pierwszej linii metody tworze instancje fabryki, a następnie pobieram lexer. Następnie wywołuję metodę getallTokens(), która zwraca mi listę wszystkich tokenów z przetworzonego kodu źródłowego. Ponieważ do dalszych potrzeb istotne są dla mnie tylko typy tokenów, a nie całe obiekty z nadmiarowymi danymi, mapuję tokeny na ich typ, czyli int. Taką listę intów jest zwracana przez metodę i będzie dalej użyta w procesie wykrywania plagiatów.

Podsumowanie

W tym wpisie przedstawiłem ANTLRa oraz pokazałem jak go skonfigurować. Dodatkowo pokazałem w jaki sposób można użyć ANTLRa, aby dokonać tokenizacji ciągu znaków na wejściu – w naszym przypadku kodu źródłowego.

 

Hello Kotlin!

W końcu pora na kodowanie!

Po kilku wpisach teoretycznych na temat mojej aplikacji przyszła pora, żeby napisać pierwsze linijki w Kotlinie! Postaram się od razu przygotować projekt tak, aby mógł być dalej rozwijany i ostatecznie stać się gotową aplikacją.

Struktura projektu

Aplikacja będzie się nazywać plag-detector. Będzie ona podzielona na kilka modułów. W tym wpisie zacznę od podstawowego modułu mojej aplikacji, czyli części programu, która będzie odpowiedzialna za wyliczanie prawdopodobieństwa plagiatu pomiędzy dwoma kodami źródłowymi.

Build tool

Przed napisaniem pierwszej linijki kodu warto wybrać narzędzie automatyzujące budowę aplikacji. Wybór padł na klasykę, czyli stary i lubiany Maven 😉

Konfiguracji parenta, czyli plag-detector, nie będę pokazywał. Nie ma tam nic odkrywczego 🙂

Poniżej przedstawię pom.xml modułu plag-algorithm.

W tej konfiguracje ważne są właściwie dwie rzeczy:

  1. Pluginy do kompilacji Kotlina i Javy. Wydaję mi się, że nie ma za bardzo co tutaj się rozpisywać 🙂
  2. Kolejność pluginów. Plugin Kotlina powinien być przed pluginem do kompilacji kodu Javy. Dzięki temu w kodzie Javowym będziemy mogli używać naszych klas Kotlinowych

Hello world!

I w końcu! Pierwszy kawałek kodu w Kotlinie!

Po uruchomieniu powyższego kodu, tak jak można się łatwo domyślić, otrzymujemy:

Kilka słów na koniec

Dzisiaj w wpisie pokazałem szkielet mojej aplikacji. Udało mi się skonfigurować mavena, tak aby kompilował kody napisane zarówno w języku Java, jak i w Kotlnie. Napisałem również pierwszy kod w Kotlinie, który się ładnie przywitał 😉

W następnych wpisach będę pokazywał swoje kolejne zmagania z Kotlinem, przy rozwijaniu plag-detectora 🙂