{"id":268,"date":"2017-04-04T00:34:40","date_gmt":"2017-04-03T22:34:40","guid":{"rendered":"http:\/\/antek.atthost24.pl\/?p=268"},"modified":"2017-04-04T00:24:06","modified_gmt":"2017-04-03T22:24:06","slug":"wykrywanie-plagiatow-wybor-algorytmu","status":"publish","type":"post","link":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/","title":{"rendered":"Wykrywanie plagiat\u00f3w – wyb\u00f3r algorytmu"},"content":{"rendered":"

4W poprzednich wpisach zrobi\u0142em przegl\u0105d istniej\u0105cych algorytm\u00f3w\/system\u00f3w s\u0142u\u017c\u0105cych do wykrywania plagiat\u00f3w w kodach \u017ar\u00f3d\u0142owych. W tym wpisie przedstawi\u0119 og\u00f3lny zarys algorytmu, kt\u00f3ry wybra\u0142em.<\/p>\n

PlagDetector – algorytm<\/h3>\n

G\u0142\u00f3wnym podej\u015bciem, wok\u00f3\u0142 kt\u00f3rego b\u0119dzie koncentrowa\u0142 si\u0119 m\u00f3j system zosta\u0142 opisany przeze mnie w tym wpisie<\/a>. Chodzi o wykrywanie plagiat\u00f3w przy u\u017cyciu aproksymacji z\u0142o\u017cono\u015bci Ko\u0142mogorowa.<\/p>\n

Aplikacja b\u0119dzie sk\u0142ada\u0142a si\u0119 z trzech g\u0142\u00f3wnych etap\u00f3w.<\/p>\n

Tokenizacja<\/h4>\n

Pierwszym etapem algorytmu jest poddanie kodu \u017ar\u00f3d\u0142owego tokenizacji.<\/p>\n

Bardzo wa\u017cn\u0105 rzecz\u0105, jest dobranie odpowiedniego zestawu token\u00f3w. Ztokenizowany kod programu powinien dobrze oddawa\u0107 struktur\u0119 i logik\u0119 programu. Zbyt dok\u0142adne tokenizowanie mo\u017ce doprowadzi\u0107 do pomini\u0119cia wykrycia plagiatu z powodu sprawdzania i por\u00f3wnywania nieistotnych informacji. Z drugiej strony, niewystarczaj\u0105co dok\u0142adna tokenizacja mo\u017ce doprowadzi\u0107 to fa\u0142szywych wskaza\u0144. Zestaw token\u00f3w oraz sama tokenizacja jest przeprowadzona pod k\u0105tem danego j\u0119zyka programowa. Dzi\u0119ki temu uzyskany ci\u0105g token\u00f3w powinien dobrze odda\u0107 struktur\u0119 programu. W Listingu poni\u017cej znajduje si\u0119 fragment przyk\u0142adowego kodu i odpowiadaj\u0105cy mu przyk\u0142adowy ci\u0105g token\u00f3w.<\/p>\n

String var;           VARIABLE_DECLARATION\r\nint i;                VARIABLE_DECLARATION\r\ni = 3;                IDENTIFIER\r\n                      ASSIGN\r\n                      IDENTIFIER\r\nif (i > 2) {          IF_SWITCH_STATEMENT_BEGIN\r\n                      OPEN_PARENTHESIS\r\n                      IDENTIFIER\r\n                      CONDITION\r\n                      IDENTIFIER\r\n                      CLOSE_PARENTHESIS\r\n var = \"more than 2\"; IDENTIFIER\r\n                      ASSIGN\r\n                      STRING\r\n}                     IF_SWITCH_STATEMENT_END\r\nelse {                IF_SWITCH_STATEMENT_BEGIN\r\n var = \"less than 2\"; IDENTIFIER\r\n                      ASSIGN\r\n                      STRING\r\n}                     IF_SWITCH_STATEMENT_END<\/pre>\n
Kompresja token\u00f3w<\/h3>\n
G\u0142\u00f3wn\u0105 rzecz\u0105 przy wyborze algorytmu kompresji by\u0142a konieczno\u015b\u0107 wyboru takiego algorytmu, kt\u00f3ry b\u0119dzie bezstratny, lecz jego stopie\u0144 kompresji b\u0119dzie mo\u017cliwie du\u017cy. Na podstawie test\u00f3w i do\u015bwiadcze\u0144 autor\u00f3w systemu SID (opisanego w poprzednim wpisie) wyb\u00f3r pad\u0142 na algorytm LZ77.<\/p>\n
Najwa\u017cniejsz\u0105 modyfikacj\u0105, kt\u00f3r\u0105 wprowadz\u0119 do implementowanego\u00a0algorytmu kompresji w stosunku do oryginalnego algorytmu LZ77 jest nieograniczony bufor s\u0142ownika oraz nieograniczony bufor wej\u015bciowy. Dzi\u0119ki takiemu podej\u015bciu stopie\u0144 kompresji danych b\u0119dzie wi\u0119kszy ni\u017c w przypadku, gdy bufory s\u0142ownika i wej\u015bciowy s\u0105 ograniczone. Podej\u015bcie to w oczywisty spos\u00f3b powoduje wyd\u0142u\u017cenie dzia\u0142ania algorytmu, lecz taki zabieg jest konieczny, aby uzyska\u0107 jak najbardziej dok\u0142adnie wyniki. Poni\u017cej przedstawi\u0142em pseudokod zmodyfikowanego algorytmu kodowania LZ77.<\/p>\n
Require: Input\r\nwhile(Input nie jest pusty) do\r\n  znajdz najdluzszy prefiks z Input znajdujacy sie w slowniku\r\n  if (znaleziono dopasowanie) then\r\n    dodaj do slownika trojke (left_shift, length, mismatch_token)\r\n      \/\/ gdzie:\r\n      \/\/ left_shift - przesuniece w lewo\r\n      \/\/ length - dlugosc dopasowanego ciagu\r\n      \/\/ mismatch_token - pierwszy niepasujacy token\r\n    przesun wskaznik o length + 1\r\n  else\r\n    dodaj do slownika trojke (0, 0, mismatch_token)\r\n      \/\/ gdzie:\r\n      \/\/ mismatch_token - pierwszy token na wejsciu\r\n    przesun wskaznik o 1\r\n  end if\r\nend while\r\n<\/pre>\n
 <\/p>\n
Wielko\u015bci\u0105 skompresowanego ci\u0105gu jest ilo\u015b\u0107 wpis\u00f3w w s\u0142owniku pomno\u017cona przez (shift_size + length_size + token_size), gdzie:<\/p>\n
    \n
  • shift_size – wielko\u015b\u0107 w bajtach potrzebna do zakodowania przesuni\u0119cia w lewo;<\/li>\n
  • length_size – wielko\u015b\u0107 w bajtach potrzebna do zakodowania d\u0142ugo\u015bci;<\/li>\n
  • token_size – wielko\u015b\u0107 w bajtach potrzebna do zakodowania jednego tokena.<\/li>\n<\/ul>\n
    Aproksymacja z\u0142o\u017cono\u015bci Ko\u0142mogorowa<\/h4>\n
    Warto\u015b\u0107 aproksymacji Ko\u0142mogorowa jest przybli\u017cana przy pomocy wzoru:
    \n\"{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}\".<\/p>\n
    Przez \"{\emph{K(x)}}\" w przypadku konstruowanego algorytmu b\u0119dzie rozumiana wielko\u015b\u0107 (w\u00a0bajtach) skompresowanego programu i b\u0119dzie oznaczana jako \"{\emph{Comp(x)}}\". W zwi\u0105zku z tym wz\u00f3r na przybli\u017cenie aproksymacji Ko\u0142mogorowa przyjmie posta\u0107:<\/p>\n
    \"{d(x,y) = 1 - \frac{Comp(x)-Comp(x|y)}{Comp(xy)}}\".<\/p>\n
    Warto\u015b\u0107 \"{\emph{Comp(x|y)}}\" zostanie przybli\u017cona w nast\u0119puj\u0105cy spos\u00f3b:
    \n\"{Comp(x|y) = Comp(xy) - Comp(y)}\".<\/p>\n
    Zatem ostatecznie warto\u015b\u0107 aproksymacji Ko\u0142mogorowa zostanie obliczone ze wzoru:
    \n\"{d(x,y) = 1 - \frac{Comp(x)+Comp(y)-Comp(x|y)}{Comp(xy)}}\".<\/p>\n
    Tak obliczona warto\u015b\u0107 aproksymacji z\u0142o\u017cono\u015bci Ko\u0142mogorowa jest przeliczana na wsp\u00f3\u0142czynnik R wed\u0142ug wzoru:
    \n\"{R = 1 - d(x,y)}\".<\/p>\n
    Wska\u017anik ten s\u0142u\u017cy za wska\u017anik prawdopodobie\u0144stwa zaj\u015bcia plagiatu. Im warto\u015b\u0107 \"{\emph{R}}\" jest wi\u0119ksza, tym prawdopodobie\u0144stwo plagiatu jest wi\u0119ksze.<\/p>\n
    Dodatkowo dla ka\u017cdej pary program\u00f3w obliczane s\u0105 warto\u015bci \"{\emph{px}}\" oraz \"{\emph{py}}\". Warto\u015bci te przedstawiaj\u0105 procentow\u0105 zawarto\u015b\u0107 informacji z jednego ci\u0105gu zawartych w drugim. Warto\u015bci te obliczane s\u0105 w spos\u00f3b nast\u0119puj\u0105cy:
    \n\"{px=\frac{R(\alpha + 1)}{R+1}}\",
    \n\"{py=\frac{R(\frac{1}{\alpha} + 1)}{R+1}}\", gdzie:
    \n\"{\alpha = \frac{Comp(y)}{Comp(x)}}\".<\/p>\n
    Wska\u017aniki \"{\emph{px}}\" i \"{\emph{py}}\" s\u0142u\u017c\u0105 jako dodatkowa informacja, wskazuj\u0105ca na zawarto\u015b\u0107 jednego ci\u0105gu w drugim. Warto\u015bci te mog\u0105 wykaza\u0107 zaj\u015bcie plagiatu, w przypadku gdy jeden z program\u00f3w zawiera w sobie kod drugiego, lecz sam program jest o wiele bardziej rozbudowany i warto\u015b\u0107 wsp\u00f3\u0142czynnika R mo\u017ce nie wskaza\u0107 zaj\u015bcia plagiatu.<\/p>\n
    Podsumowanie<\/h3>\n
    W tym wpisie om\u00f3wi\u0142em algorytm, kt\u00f3ry planuj\u0119 zaimplementowa\u0107. Sk\u0142ada si\u0119 \u00a0on z 3 g\u0142\u00f3wnych krok\u00f3w – tokenizacji, kompresji i aproksymacji z\u0142o\u017cono\u015bci Ko\u0142mogorowa. W kolejnych wpisach postaram si\u0119 bardziej przybli\u017cy\u0107 ka\u017cdy z tych etap\u00f3w.<\/p>\n","protected":false},"excerpt":{"rendered":"
    4W poprzednich wpisach zrobi\u0142em przegl\u0105d istniej\u0105cych algorytm\u00f3w\/system\u00f3w s\u0142u\u017c\u0105cych do wykrywania plagiat\u00f3w w kodach \u017ar\u00f3d\u0142owych. W tym wpisie przedstawi\u0119 og\u00f3lny zarys algorytmu, kt\u00f3ry wybra\u0142em. PlagDetector – algorytm G\u0142\u00f3wnym podej\u015bciem,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,19],"tags":[],"class_list":["post-268","post","type-post","status-publish","format-standard","hentry","category-dsp2017","category-plagdetector"],"yoast_head":"\nWykrywanie plagiat\u00f3w - wyb\u00f3r algorytmu - Lukasz Antkowiak's blog<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/\" \/>\n<meta property=\"og:locale\" content=\"pl_PL\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Wykrywanie plagiat\u00f3w - wyb\u00f3r algorytmu - Lukasz Antkowiak's blog\" \/>\n<meta property=\"og:description\" content=\"4W poprzednich wpisach zrobi\u0142em przegl\u0105d istniej\u0105cych algorytm\u00f3w\/system\u00f3w s\u0142u\u017c\u0105cych do wykrywania plagiat\u00f3w w kodach \u017ar\u00f3d\u0142owych. W tym wpisie przedstawi\u0119 og\u00f3lny zarys algorytmu, kt\u00f3ry wybra\u0142em. PlagDetector – algorytm G\u0142\u00f3wnym podej\u015bciem,...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/\" \/>\n<meta property=\"og:site_name\" content=\"Lukasz Antkowiak's blog\" \/>\n<meta property=\"article:published_time\" content=\"2017-04-03T22:34:40+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2017-04-03T22:24:06+00:00\" \/>\n<meta name=\"author\" content=\"\u0141ukasz Antkowiak\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Napisane przez\" \/>\n\t<meta name=\"twitter:data1\" content=\"\u0141ukasz Antkowiak\" \/>\n\t<meta name=\"twitter:label2\" content=\"Szacowany czas czytania\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minuty\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/\",\"url\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/\",\"name\":\"Wykrywanie plagiat\u00f3w - wyb\u00f3r algorytmu - Lukasz Antkowiak's blog\",\"isPartOf\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/#website\"},\"datePublished\":\"2017-04-03T22:34:40+00:00\",\"dateModified\":\"2017-04-03T22:24:06+00:00\",\"author\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6\"},\"breadcrumb\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/#breadcrumb\"},\"inLanguage\":\"pl-PL\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Strona g\u0142\u00f3wna\",\"item\":\"https:\/\/blog.lantkowiak.pl\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Wykrywanie plagiat\u00f3w – wyb\u00f3r algorytmu\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/#website\",\"url\":\"https:\/\/blog.lantkowiak.pl\/\",\"name\":\"Lukasz Antkowiak's blog\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/blog.lantkowiak.pl\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"pl-PL\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6\",\"name\":\"\u0141ukasz Antkowiak\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"pl-PL\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/e18e2bfe319da9b5757cf7f7ae1bfecf?s=96&d=monsterid&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/e18e2bfe319da9b5757cf7f7ae1bfecf?s=96&d=monsterid&r=g\",\"caption\":\"\u0141ukasz Antkowiak\"},\"description\":\"dd\",\"url\":\"https:\/\/blog.lantkowiak.pl\/index.php\/author\/antek\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Wykrywanie plagiat\u00f3w - wyb\u00f3r algorytmu - Lukasz Antkowiak's blog","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/","og_locale":"pl_PL","og_type":"article","og_title":"Wykrywanie plagiat\u00f3w - wyb\u00f3r algorytmu - Lukasz Antkowiak's blog","og_description":"4W poprzednich wpisach zrobi\u0142em przegl\u0105d istniej\u0105cych algorytm\u00f3w\/system\u00f3w s\u0142u\u017c\u0105cych do wykrywania plagiat\u00f3w w kodach \u017ar\u00f3d\u0142owych. W tym wpisie przedstawi\u0119 og\u00f3lny zarys algorytmu, kt\u00f3ry wybra\u0142em. PlagDetector – algorytm G\u0142\u00f3wnym podej\u015bciem,...","og_url":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/","og_site_name":"Lukasz Antkowiak's blog","article_published_time":"2017-04-03T22:34:40+00:00","article_modified_time":"2017-04-03T22:24:06+00:00","author":"\u0141ukasz Antkowiak","twitter_card":"summary_large_image","twitter_misc":{"Napisane przez":"\u0141ukasz Antkowiak","Szacowany czas czytania":"4 minuty"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/","url":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/","name":"Wykrywanie plagiat\u00f3w - wyb\u00f3r algorytmu - Lukasz Antkowiak's blog","isPartOf":{"@id":"https:\/\/blog.lantkowiak.pl\/#website"},"datePublished":"2017-04-03T22:34:40+00:00","dateModified":"2017-04-03T22:24:06+00:00","author":{"@id":"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6"},"breadcrumb":{"@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/#breadcrumb"},"inLanguage":"pl-PL","potentialAction":[{"@type":"ReadAction","target":["https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/04\/04\/wykrywanie-plagiatow-wybor-algorytmu\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Strona g\u0142\u00f3wna","item":"https:\/\/blog.lantkowiak.pl\/"},{"@type":"ListItem","position":2,"name":"Wykrywanie plagiat\u00f3w – wyb\u00f3r algorytmu"}]},{"@type":"WebSite","@id":"https:\/\/blog.lantkowiak.pl\/#website","url":"https:\/\/blog.lantkowiak.pl\/","name":"Lukasz Antkowiak's blog","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/blog.lantkowiak.pl\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"pl-PL"},{"@type":"Person","@id":"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6","name":"\u0141ukasz Antkowiak","image":{"@type":"ImageObject","inLanguage":"pl-PL","@id":"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/e18e2bfe319da9b5757cf7f7ae1bfecf?s=96&d=monsterid&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/e18e2bfe319da9b5757cf7f7ae1bfecf?s=96&d=monsterid&r=g","caption":"\u0141ukasz Antkowiak"},"description":"dd","url":"https:\/\/blog.lantkowiak.pl\/index.php\/author\/antek\/"}]}},"_links":{"self":[{"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/268","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/comments?post=268"}],"version-history":[{"count":20,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/268\/revisions"}],"predecessor-version":[{"id":288,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/268\/revisions\/288"}],"wp:attachment":[{"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/media?parent=268"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/categories?post=268"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/tags?post=268"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}