Jak wykrywać plagiaty? Część druga!

W jednej z poprzednich notek opisałem metody służące do wykrywania plagiatów, które bazują na zliczaniu atrybutów. Dzisiaj postaram się opisać i przedstawić systemy bazujące na metrykach strukturalnych.

Systemy bazujące na metrykach strukturalnych

Techniki wykrywania plagiatów opierające się na metrykach strukturalnych polegają na badaniu podobieństwa na podstawie podobnych lub identycznych fragmentów w badanych plikach. Poniżej opiszę kilka najpopularniejszych systemów służących do wykrywania plagiatów w kodach źródłowych programów, które bazują na metryce strukturalnej.

Dotplot

Metoda Dotplot jest wizualną metodą znajdującą pasujące do siebie fragmenty tekstu (w szczególnym przypadku kodu źródłowego). Decyzja o plagiacie jest podejmowana przez użytkownika analizującego otrzymane wizualne wyniki. Autor systemu uważa, iż właśnie dzięki powierzeniu decyzji o plagiacie człowiekowi można zdecydowanie podwyższyć próg skuteczności znajdowania plagiatów. System działa w następujący sposób:

• tokenizacja wejścia
• konkatenacja tokenów z programu A i programu B
• przedstawienie wyników w postaci graficznej

Aby lepiej pokazać działanie algorytmu, poniżej pokażę przykład działania algorytmu.

Ciągi wejściowe:

• Ala ma kota
• Kot ma na imie ala

Przebieg algorytmu:

• tokenizacja: alamakota, kotmanaimieala
• konkatenacja: alamakotakotmanaimieala
• wyniki w graficznej formie:
  

  	ala	ma	kota	kot	ma	na	imie	ala
  ala	XXX							XXX
  ma		XXX			XXX
  kota			XXX
  kot				XXX
  ma		XXX			XXX
  na						XXX
  imie							XXX
  ala	XXX							XXX

Na podstawie tak przedstawionych wyników, osoba analizująca dane z pomocą wskazówek, stworzonych przez autora systemu, może stwierdzić zajście plagiatu.

JPlag

System JPlag jest darmowym systemem do wykrywania plagiatów dostępnym online. System analizując kody źródłowe programów działa w dwóch etapach:

1. Parsowanie i tokenizacja kodu źródłowego.
   Przy pomocy parsera i tokenizera kod źródłowy programu jest zamieniany na ciąg tokenów.
2. Porównanie par ciągów tokenów ze sobą.
   Każda para ciągu tokenów jest porównywana ze sobą przy użyciu algorytmu Greedy String Tiling
   Przy porównywaniu tokenów przestrzegane są następujące zasady:
   1. Każdy token z programu A może zostać dopasowany tylko do jednego tokena z programu B.
   2. Podciągi tokenów są znajdowane niezależnie od ich pozycji.
   3. Dłuższe podciągi są bardziej preferowane od krótszych

Uwzględniając powyższe zasady powstał algorytm, który przebiega w dwóch fazach:

1. W pierwszej fazie algorytmu w dwóch ciągach tokenów znajdowany jest najdłuższy wspólny podciąg dla dwóch podanych ciągów wśród tokenów, które nie są oznaczone.
2. W drugiej fazie wszystkie tokeny zawierające się w znalezionym w fazie pierwszej podciągu zostają oznaczone jako użyte i algorytm wraca do punktu pierwszego.

Algorytm jest wykonywany dopóki są znajdowane dopasowania tokenów o długości nie mniejszej niż ustalony próg.\par
W listingu poniżej przedstawiono pseudo-kod algorytmu Greedy String Tiling.

Greedy-String-Tiling(String A, String B) { tiles = {}; do { maxmatch = MinimumMatchLength; matches = {}; Forall unmarked tokens A(a) in A { Forall unmarked tokens B(b) in B { j = 0; while (A(a)+j == B(b)+j && unmarked(A(a+j)) && unmarked(B(b+j))) { j++; } if (j == maxmatch) { append(matches,match(a,b,j)); } else if (j > maxmatch) { matches = {match(a,b,j)}; maxmatch = j; } } } } }

Na podstawie wyniku działania algorytmu jest wyliczane prawdopodobieństwo w następujący sposób:

, gdzie:

Obliczone podobieństwo jest wyrażone w procentach, zatem im wyższa wartość tym większe prawdopodobieństwo na to, iż mamy do czynienia z plagiatem.

MOSS

Ostatnim systemem opierającym się na metrykach strukturalnych, który opiszę jest MOSS. Głównym algorytmem systemu jest algorytm Winnowing. Jego zasada działania opiera się na k-gramach, czyli podciągach tokenów długości k. Algorytm przebiega następująco:

1. podanie na wejście ciągu znaków
2. usunięcie zbędnych znaków
3. podzielenie ciągu wejściowego na k-gramy
4. zamiana k-gramów na hashe
5. wybranie części hashów, według odpowiedniego algorytmu – wybrane hashe tworzą tzw. odcisk palca programu.

Tak przygotowane zestawy odcisków palca są ze sobą porównywane w celu znalezienia jak największych wspólnych części odcisków palców.

Krótkie podsumowanie

Dzisiaj pokazałem bardziej zaawansowane systemy wykrywania plagiatów. według mnie na szczególną uwagę zasługuje system JPlag, który ma całkiem niezłą skuteczność.

W jednym z kolejnych wpisów opiszę jeszcze 2-3 podejścia do tego problemu. Po tej dawce teorii będziemy mogli z czystym sumieniem przejść do praktyki i implementacji naszego algorytmu