Aby lepiej pokaza\u0107 dzia\u0142anie algorytmu, poni\u017cej poka\u017c\u0119 przyk\u0142ad dzia\u0142ania algorytmu.<\/p>\n
Ci\u0105gi wej\u015bciowe:<\/p>\n
- \n
- Ala ma kota<\/li>\n
- Kot ma na imie ala<\/li>\n<\/ul>\n
Przebieg algorytmu:<\/p>\n
- \n
- tokenizacja: ala<\/em>
![\"{\diamond}\"](\"https:\/\/blog.lantkowiak.pl\/wp-content\/ql-cache\/quicklatex.com-2eb7138ffc8f1d6339fa1f5d74d6b1cc_l3.png\" "\\"Rendered")
ma<\/em>kota<\/em>, kot<\/em>ma<\/em>na<\/em>imie<\/em>ala<\/em><\/li>\n- konkatenacja: ala<\/em>
ma<\/em>kota<\/em>kot<\/em>ma<\/em>na<\/em>imie<\/em>ala<\/em><\/li>\n- wyniki w graficznej formie:
\n\n\n\n
\n\t <\/td> ala<\/td> ma<\/td> kota<\/td> kot<\/td> ma<\/td> na<\/td> imie<\/td> ala<\/td>\n<\/tr>\n \n\t ala<\/td> XXX<\/span><\/td> <\/td> <\/td> <\/td> <\/td> <\/td> <\/td> XXX<\/span><\/td>\n<\/tr>\n \n\t ma<\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td> <\/td>\n<\/tr>\n \n\t kota<\/td> <\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td> <\/td> <\/td> <\/td>\n<\/tr>\n \n\t kot<\/td> <\/td> <\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td> <\/td> <\/td>\n<\/tr>\n \n\t ma<\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td> <\/td>\n<\/tr>\n \n\t na<\/td> <\/td> <\/td> <\/td> <\/td> <\/td> XXX<\/span><\/td> <\/td> <\/td>\n<\/tr>\n \n\t imie<\/td> <\/td> <\/td> <\/td> <\/td> <\/td> <\/td> XXX<\/span><\/td> <\/td>\n<\/tr>\n \n\t ala<\/td> XXX<\/span><\/td> <\/td> <\/td> <\/td> <\/td> <\/td> <\/td> XXX<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/li>\n<\/ul>\n Na podstawie tak przedstawionych wynik\u00f3w, osoba analizuj\u0105ca dane z pomoc\u0105 wskaz\u00f3wek, stworzonych przez autora systemu, mo\u017ce stwierdzi\u0107 zaj\u015bcie plagiatu.<\/p>\n
JPlag<\/h4>\n
System JPlag jest darmowym systemem do wykrywania plagiat\u00f3w dost\u0119pnym online. System analizuj\u0105c kody \u017ar\u00f3d\u0142owe program\u00f3w dzia\u0142a w dw\u00f3ch etapach:<\/p>\n
- \n
- Parsowanie i tokenizacja kodu \u017ar\u00f3d\u0142owego.
\nPrzy pomocy parsera i tokenizera kod \u017ar\u00f3d\u0142owy programu jest zamieniany na ci\u0105g token\u00f3w.<\/li>\n - Por\u00f3wnanie par ci\u0105g\u00f3w token\u00f3w ze sob\u0105.
\nKa\u017cda para ci\u0105gu token\u00f3w jest por\u00f3wnywana ze sob\u0105 przy u\u017cyciu algorytmu Greedy String Tiling
\nPrzy por\u00f3wnywaniu token\u00f3w przestrzegane s\u0105 nast\u0119puj\u0105ce zasady:<\/p>\n- \n
- Ka\u017cdy token z programu A mo\u017ce zosta\u0107 dopasowany tylko do jednego tokena z programu B.<\/li>\n
- Podci\u0105gi token\u00f3w s\u0105 znajdowane niezale\u017cnie od ich pozycji.<\/li>\n
- D\u0142u\u017csze podci\u0105gi s\u0105 bardziej preferowane od kr\u00f3tszych<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
Uwzgl\u0119dniaj\u0105c powy\u017csze zasady powsta\u0142 algorytm, kt\u00f3ry przebiega w dw\u00f3ch fazach:<\/p>\n
- \n
- W pierwszej fazie algorytmu w dw\u00f3ch ci\u0105gach token\u00f3w znajdowany jest najd\u0142u\u017cszy wsp\u00f3lny podci\u0105g dla dw\u00f3ch podanych ci\u0105g\u00f3w w\u015br\u00f3d token\u00f3w, kt\u00f3re nie s\u0105 oznaczone.<\/li>\n
- W drugiej fazie wszystkie tokeny zawieraj\u0105ce si\u0119 w znalezionym w fazie pierwszej podci\u0105gu zostaj\u0105 oznaczone jako u\u017cyte i algorytm wraca do punktu pierwszego.<\/li>\n<\/ol>\n
Algorytm jest wykonywany dop\u00f3ki s\u0105 znajdowane dopasowania token\u00f3w o d\u0142ugo\u015bci nie mniejszej ni\u017c ustalony pr\u00f3g.\\par
\nW listingu poni\u017cej przedstawiono pseudo-kod algorytmu Greedy String Tiling.<\/p>\nGreedy-String-Tiling(String A, String B) {\r\n\ttiles = {};\r\n\tdo {\r\n\t\tmaxmatch = MinimumMatchLength;\r\n\t\tmatches = {};\r\n\t\tForall unmarked tokens A(a) in A {\r\n\t\t\tForall unmarked tokens B(b) in B {\r\n\t\t\t\tj = 0;\r\n\t\t\t\twhile (A(a)+j == B(b)+j && unmarked(A(a+j)) && unmarked(B(b+j))) {\r\n\t\t\t\t\tj++;\r\n\t\t\t\t}\r\n\t\t\t\tif (j == maxmatch) {\r\n\t\t\t\t\tappend(matches,match(a,b,j));\r\n\t\t\t\t}\r\n\t\t\t\telse if (j > maxmatch) {\r\n\t\t\t\t\tmatches = {match(a,b,j)};\r\n\t\t\t\t\tmaxmatch = j;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}<\/pre>\nNa podstawie wyniku dzia\u0142ania algorytmu jest wyliczane prawdopodobie\u0144stwo w nast\u0119puj\u0105cy spos\u00f3b:<\/p>\n
![\"{sim(A,B)=\frac{2\cdot coverage(tiles)}{|A|+|B|}}\"](\"https:\/\/blog.lantkowiak.pl\/wp-content\/ql-cache\/quicklatex.com-2acfc9987adf67f86d10f8d30bc9ce62_l3.png\" "\\"Rendered")
, gdzie:<\/p>\n![\"{coverage(tiles) = \sum_{match(a,b,length)\in tiles}length}\"](\"https:\/\/blog.lantkowiak.pl\/wp-content\/ql-cache\/quicklatex.com-0c7a51e19d1e3554d2e0330af045a8a6_l3.png\" "\\"Rendered")
<\/p>\nObliczone podobie\u0144stwo jest wyra\u017cone w procentach, zatem im wy\u017csza warto\u015b\u0107 tym wi\u0119ksze prawdopodobie\u0144stwo na to, \u017ce mamy do czynienia z plagiatem.<\/p>\n
MOSS<\/h4>\n
Ostatnim systemem opieraj\u0105cym si\u0119 na metrykach strukturalnych, kt\u00f3ry opisz\u0119 jest MOSS. G\u0142\u00f3wnym algorytmem systemu jest algorytm Winnowing<\/em>. Jego zasada dzia\u0142ania opiera si\u0119 na k-gramach<\/em>, czyli podci\u0105gach token\u00f3w d\u0142ugo\u015bci k. Algorytm przebiega nast\u0119puj\u0105co:<\/p>\n
- \n
- podanie na wej\u015bcie ci\u0105gu znak\u00f3w<\/li>\n
- usuni\u0119cie zb\u0119dnych znak\u00f3w<\/li>\n
- podzielenie ci\u0105gu wej\u015bciowego na k-gramy<\/li>\n
- zamiana k-gram\u00f3w na hashe<\/li>\n
- wybranie cz\u0119\u015bci hash\u00f3w, wed\u0142ug odpowiedniego algorytmu – wybrane hashe tworz\u0105 tzw. odcisk palca programu.<\/li>\n<\/ol>\n
Tak przygotowane zestawy odcisk\u00f3w palca s\u0105 ze sob\u0105 por\u00f3wnywane w celu znalezienia jak najwi\u0119kszych wsp\u00f3lnych cz\u0119\u015bci odcisk\u00f3w palc\u00f3w.<\/p>\n
Kr\u00f3tkie podsumowanie<\/h3>\n
Dzisiaj pokaza\u0142em bardziej zaawansowane systemy wykrywania plagiat\u00f3w. wed\u0142ug mnie na szczeg\u00f3ln\u0105 uwag\u0119 zas\u0142uguje system JPlag, kt\u00f3ry ma ca\u0142kiem niez\u0142\u0105 skuteczno\u015b\u0107.<\/p>\n
W jednym z kolejnych wpis\u00f3w opisz\u0119 jeszcze 2-3 podej\u015bcia do tego \u00a0problemu. Po tej dawce teorii b\u0119dziemy mogli z czystym sumieniem przej\u015b\u0107 do praktyki i implementacji naszego algorytmu \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"
W jednej z poprzednich notek opisa\u0142em metody s\u0142u\u017c\u0105ce do wykrywania plagiat\u00f3w, kt\u00f3re bazuj\u0105 na zliczaniu atrybut\u00f3w. Dzisiaj postaram si\u0119 opisa\u0107 i przedstawi\u0107 systemy bazuj\u0105ce na\u00a0metrykach strukturalnych. Systemy bazuj\u0105ce…<\/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-207","post","type-post","status-publish","format-standard","hentry","category-dsp2017","category-plagdetector"],"yoast_head":"\n
Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga! - 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\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/\" \/>\n<meta property=\"og:locale\" content=\"pl_PL\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga! - Lukasz Antkowiak's blog\" \/>\n<meta property=\"og:description\" content=\"W jednej z poprzednich notek opisa\u0142em metody s\u0142u\u017c\u0105ce do wykrywania plagiat\u00f3w, kt\u00f3re bazuj\u0105 na zliczaniu atrybut\u00f3w. Dzisiaj postaram si\u0119 opisa\u0107 i przedstawi\u0107 systemy bazuj\u0105ce na\u00a0metrykach strukturalnych. Systemy bazuj\u0105ce...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/\" \/>\n<meta property=\"og:site_name\" content=\"Lukasz Antkowiak's blog\" \/>\n<meta property=\"article:published_time\" content=\"2017-03-16T13:29:39+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2017-04-02T21:09:25+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\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/\",\"url\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/\",\"name\":\"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga! - Lukasz Antkowiak's blog\",\"isPartOf\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/#website\"},\"datePublished\":\"2017-03-16T13:29:39+00:00\",\"dateModified\":\"2017-04-02T21:09:25+00:00\",\"author\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6\"},\"breadcrumb\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/#breadcrumb\"},\"inLanguage\":\"pl-PL\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Strona g\u0142\u00f3wna\",\"item\":\"https:\/\/blog.lantkowiak.pl\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga!\"}]},{\"@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":"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga! - 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\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/","og_locale":"pl_PL","og_type":"article","og_title":"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga! - Lukasz Antkowiak's blog","og_description":"W jednej z poprzednich notek opisa\u0142em metody s\u0142u\u017c\u0105ce do wykrywania plagiat\u00f3w, kt\u00f3re bazuj\u0105 na zliczaniu atrybut\u00f3w. Dzisiaj postaram si\u0119 opisa\u0107 i przedstawi\u0107 systemy bazuj\u0105ce na\u00a0metrykach strukturalnych. Systemy bazuj\u0105ce...","og_url":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/","og_site_name":"Lukasz Antkowiak's blog","article_published_time":"2017-03-16T13:29:39+00:00","article_modified_time":"2017-04-02T21:09:25+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\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/","url":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/","name":"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga! - Lukasz Antkowiak's blog","isPartOf":{"@id":"https:\/\/blog.lantkowiak.pl\/#website"},"datePublished":"2017-03-16T13:29:39+00:00","dateModified":"2017-04-02T21:09:25+00:00","author":{"@id":"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6"},"breadcrumb":{"@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/#breadcrumb"},"inLanguage":"pl-PL","potentialAction":[{"@type":"ReadAction","target":["https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/03\/16\/jak-wykrywac-plagiaty-czesc-druga\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Strona g\u0142\u00f3wna","item":"https:\/\/blog.lantkowiak.pl\/"},{"@type":"ListItem","position":2,"name":"Jak wykrywa\u0107 plagiaty? Cz\u0119\u015b\u0107 druga!"}]},{"@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\/207","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=207"}],"version-history":[{"count":8,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/207\/revisions"}],"predecessor-version":[{"id":220,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/207\/revisions\/220"}],"wp:attachment":[{"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/media?parent=207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/categories?post=207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/tags?post=207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- konkatenacja: ala<\/em>
- tokenizacja: ala<\/em>