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 🙂

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *