4W poprzednich wpisach zrobiłem przegląd istniejących algorytmów/systemów służących do wykrywania plagiatów w kodach źródłowych. W tym wpisie przedstawię ogólny zarys algorytmu, który wybrałem.

PlagDetector – algorytm

Głównym podejściem, wokół którego będzie koncentrował się mój system został opisany przeze mnie w tym wpisie. Chodzi o wykrywanie plagiatów przy użyciu aproksymacji złożoności Kołmogorowa.

Aplikacja będzie składała się z trzech głównych etapów.

Tokenizacja

Pierwszym etapem algorytmu jest poddanie kodu źródłowego tokenizacji.

Bardzo ważną rzeczą, jest dobranie odpowiedniego zestawu tokenów. Ztokenizowany kod programu powinien dobrze oddawać strukturę i logikę programu. Zbyt dokładne tokenizowanie może doprowadzić do pominięcia wykrycia plagiatu z powodu sprawdzania i porównywania nieistotnych informacji. Z drugiej strony, niewystarczająco dokładna tokenizacja może doprowadzić to fałszywych wskazań. Zestaw tokenów oraz sama tokenizacja jest przeprowadzona pod kątem danego języka programowa. Dzięki temu uzyskany ciąg tokenów powinien dobrze oddać strukturę programu. W Listingu poniżej znajduje się fragment przykładowego kodu i odpowiadający mu przykładowy ciąg tokenów.

String var;           VARIABLE_DECLARATION
int i;                VARIABLE_DECLARATION
i = 3;                IDENTIFIER
                      ASSIGN
                      IDENTIFIER
if (i > 2) {          IF_SWITCH_STATEMENT_BEGIN
                      OPEN_PARENTHESIS
                      IDENTIFIER
                      CONDITION
                      IDENTIFIER
                      CLOSE_PARENTHESIS
 var = "more than 2"; IDENTIFIER
                      ASSIGN
                      STRING
}                     IF_SWITCH_STATEMENT_END
else {                IF_SWITCH_STATEMENT_BEGIN
 var = "less than 2"; IDENTIFIER
                      ASSIGN
                      STRING
}                     IF_SWITCH_STATEMENT_END

Kompresja tokenów

Główną rzeczą przy wyborze algorytmu kompresji była konieczność wyboru takiego algorytmu, który będzie bezstratny, lecz jego stopień kompresji będzie możliwie duży. Na podstawie testów i doświadczeń autorów systemu SID (opisanego w poprzednim wpisie) wybór padł na algorytm LZ77.

Najważniejszą modyfikacją, którą wprowadzę do implementowanego algorytmu kompresji w stosunku do oryginalnego algorytmu LZ77 jest nieograniczony bufor słownika oraz nieograniczony bufor wejściowy. Dzięki takiemu podejściu stopień kompresji danych będzie większy niż w przypadku, gdy bufory słownika i wejściowy są ograniczone. Podejście to w oczywisty sposób powoduje wydłużenie działania algorytmu, lecz taki zabieg jest konieczny, aby uzyskać jak najbardziej dokładnie wyniki. Poniżej przedstawiłem pseudokod zmodyfikowanego algorytmu kodowania LZ77.

Require: Input
while(Input nie jest pusty) do
  znajdz najdluzszy prefiks z Input znajdujacy sie w slowniku
  if (znaleziono dopasowanie) then
    dodaj do slownika trojke (left_shift, length, mismatch_token)
      // gdzie:
      // left_shift - przesuniece w lewo
      // length - dlugosc dopasowanego ciagu
      // mismatch_token - pierwszy niepasujacy token
    przesun wskaznik o length + 1
  else
    dodaj do slownika trojke (0, 0, mismatch_token)
      // gdzie:
      // mismatch_token - pierwszy token na wejsciu
    przesun wskaznik o 1
  end if
end while

 

Wielkością skompresowanego ciągu jest ilość wpisów w słowniku pomnożona przez (shift_size + length_size + token_size), gdzie:

  • shift_size – wielkość w bajtach potrzebna do zakodowania przesunięcia w lewo;
  • length_size – wielkość w bajtach potrzebna do zakodowania długości;
  • token_size – wielkość w bajtach potrzebna do zakodowania jednego tokena.

Aproksymacja złożoności Kołmogorowa

Wartość aproksymacji Kołmogorowa jest przybliżana przy pomocy wzoru:
{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}.

Przez {\emph{K(x)}} w przypadku konstruowanego algorytmu będzie rozumiana wielkość (w bajtach) skompresowanego programu i będzie oznaczana 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)}} zostanie przybliżona w następujący sposób:
{Comp(x|y) = Comp(xy) - Comp(y)}.

Zatem ostatecznie wartość aproksymacji Kołmogorowa zostanie obliczone ze 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 jest przeliczana na współczynnik R według wzoru:
{R = 1 - d(x,y)}.

Wskaźnik ten służy za wskaźnik prawdopodobieństwa zajścia plagiatu. Im wartość {\emph{R}} jest większa, tym prawdopodobieństwo plagiatu jest większe.

Dodatkowo dla każdej pary programów obliczane są wartości {\emph{px}} oraz {\emph{py}}. Wartości te przedstawiają procentową zawartość informacji z jednego ciągu zawartych w drugim. Wartości te obliczane są w sposób następujący:
{px=\frac{R(\alpha + 1)}{R+1}},
{py=\frac{R(\frac{1}{\alpha} + 1)}{R+1}}, gdzie:
{\alpha = \frac{Comp(y)}{Comp(x)}}.

Wskaźniki {\emph{px}} i {\emph{py}} służą jako dodatkowa informacja, wskazująca na zawartość jednego ciągu w drugim. Wartości te mogą wykazać 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 R może nie wskazać zajścia plagiatu.

Podsumowanie

W tym wpisie omówiłem algorytm, który planuję zaimplementować. Składa się  on z 3 głównych kroków – tokenizacji, kompresji i aproksymacji złożoności Kołmogorowa. W kolejnych wpisach postaram się bardziej przybliżyć każdy z tych etapów.