{"id":363,"date":"2017-05-20T15:00:49","date_gmt":"2017-05-20T13:00:49","guid":{"rendered":"http:\/\/antek.atthost24.pl\/?p=363"},"modified":"2017-05-17T23:43:31","modified_gmt":"2017-05-17T21:43:31","slug":"wyliczmy-podobienstwo","status":"publish","type":"post","link":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/","title":{"rendered":"Wyliczmy podobie\u0144stwo!"},"content":{"rendered":"

W poprzednim wpisie<\/a> dotycz\u0105cym PlagDetectora zajmowali\u015bmy si\u0119 kompresj\u0105 token\u00f3w. Dzisiaj zajmiemy si\u0119 trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobie\u0144stwa pomi\u0119dzy kodami \u017ar\u00f3d\u0142owymi.<\/p>\n

Ma\u0142a powt\u00f3rka<\/h3>\n

Na pocz\u0105tku wr\u00f3\u0107my do wpisu<\/a> gdzie omawiali\u015bmy ca\u0142y algorytm i przypomnijmy sobie kilka wzor\u00f3w.<\/p>\n

Warto\u015b\u0107 aproksymacji Ko\u0142mogorowa b\u0119dziemy przybli\u017ca\u0107 przy pomocy poni\u017cszego wzoru.
\n\"{d(x,y) = 1 - \frac{K(x)-K(x|y)}{K(xy)}}\".<\/p>\n

Przez \"{\emph{K(x)}}\" b\u0119dziemy rozumie\u0107 wielko\u015b\u0107 (w\u00a0bajtach) skompresowanego kodu \u017ar\u00f3d\u0142owego i b\u0119dziemy oznacza\u0107 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)}}\"\u00a0obliczymy w nast\u0119puj\u0105cy spos\u00f3b:
\n\"{Comp(x|y) = Comp(xy) - Comp(y)}\".<\/p>\n

Zatem ostatecznie warto\u015b\u0107 aproksymacji Ko\u0142mogorowa obliczymy z nast\u0119puj\u0105cego 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 przeliczymy na wsp\u00f3\u0142czynnik \"{\emph{D}}\" wed\u0142ug wzoru:
\n\"{D = 1 - d(x,y)}\".<\/p>\n

I ten w\u0142a\u015bnie wska\u017anik b\u0119dzie naszym g\u0142\u00f3wnym wyznacznikiem, kt\u00f3rego b\u0119dziemy u\u017cywa\u0107\u00a0do oceny prawdopodobie\u0144stwa zaj\u015bcia plagiatu.\u00a0 Im warto\u015b\u0107 \"{\emph{D}}\" jest wi\u0119ksza, tym prawdopodobie\u0144stwo plagiatu jest wi\u0119ksze.<\/p>\n

Dodatkowo dla ka\u017cdej pary program\u00f3w obliczymy warto\u015bci \"{\emph{px}}\" oraz \"{\emph{py}}\". Warto\u015bci te b\u0119d\u0105 przedstawia\u0107 procentow\u0105 zawarto\u015b\u0107 informacji z jednego kodu \u017ar\u00f3d\u0142owego zawartych w drugim. Warto\u015bci te obliczymy u\u017cywaj\u0105c nast\u0119puj\u0105cych wzor\u00f3w:
\n\"{px=\frac{D(\alpha + 1)}{D+1}}\",
\n\"{py=\frac{D(\frac{1}{\alpha} + 1)}{D+1}}\", gdzie:
\n\"{\alpha = \frac{Comp(y)}{Comp(x)}}\".<\/p>\n

Wska\u017aniki \"{\emph{px}}\" i \"{\emph{py}}\" pos\u0142u\u017c\u0105 nam jako dodatkowa informacja, wskazuj\u0105ca na zawarto\u015b\u0107 jednego ci\u0105gu w drugim. Warto\u015bci te pomog\u0105 nam wskaza\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 \"{\emph{D}}\" mo\u017ce nie wskaza\u0107 zaj\u015bcia plagiatu.<\/p>\n

I teraz kodowanie!<\/h3>\n

Zacznijmy od klasy, kt\u00f3ra przechowa nasze wyniki.<\/p>\n

package pl.lantkowiak.plagdetector.algorithm.kolmogorov\r\n\r\ndata class KolmogorovCalculationResult(val d: Double, val px: Double, val py: Double)<\/pre>\n
Podobnie jak przy tworzeniu klasy do przechowywania wynik\u00f3w kompresji – bana\u0142 \ud83d\ude09<\/p>\n
Teraz pora na obliczenia!<\/p>\n
class KolmogorovCalculator {\r\n    fun calculate(encodedData1Size: Int, encodedData2Size: Int, encodedData1_2Size: Int): KolmogorovCalculationResult {\r\n        val d = calculateD(encodedData1Size, encodedData2Size, encodedData1_2Size)\r\n\r\n        val px = calculateP(d, encodedData1Size, encodedData2Size)\r\n        val py = calculateP(d, encodedData2Size, encodedData1Size)\r\n\r\n        return KolmogorovCalculationResult(d, px, py)\r\n    }\r\n\r\n    private fun calculateD(encodedData1Size: Int, encodedData2Size: Int, encodedData1_2Size: Int): Double {\r\n        return (encodedData1Size + encodedData2Size - encodedData1_2Size) \/ (1.0 * encodedData1_2Size)\r\n    }\r\n\r\n    private fun calculateP(d: Double, size1: Int, size2: Int): Double {\r\n        val a = size2 \/ (1.0 * size1)\r\n\r\n        return d * (a + 1) \/ (d + 1.0)\r\n    }\r\n}<\/pre>\n
Tym razem nie zobaczymy \u017cadnej magii w kodzie. Mamy tylko zwyk\u0142e przepisanie wzoru na Kotlina \ud83d\ude09<\/p>\n
Podsumowanie<\/h3>\n
Dzisiaj zaj\u0119li\u015bmy si\u0119 ostatnim krokiem algorytmu, a mianowicie aproksymacj\u0105 z\u0142o\u017cono\u015bci Ko\u0142mogorowa. Przypomnieli\u015bmy sobie wzory potrzebne do oblicze\u0144, a nast\u0119pnie zaadoptowali\u015bmy te wzory do naszego kodu. W nast\u0119pnym wpisie wykonamy w ko\u0144cu nasze 3 kroki razem i przetestujemy dzia\u0142anie algorytmu \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"
W poprzednim wpisie dotycz\u0105cym PlagDetectora zajmowali\u015bmy si\u0119 kompresj\u0105 token\u00f3w. Dzisiaj zajmiemy si\u0119 trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobie\u0144stwa pomi\u0119dzy kodami \u017ar\u00f3d\u0142owymi. Ma\u0142a powt\u00f3rka…<\/p>\n","protected":false},"author":1,"featured_media":367,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,20,19],"tags":[],"class_list":["post-363","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-dsp2017","category-kotlin","category-plagdetector"],"yoast_head":"\nWyliczmy podobie\u0144stwo! - 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\/05\/20\/wyliczmy-podobienstwo\/\" \/>\n<meta property=\"og:locale\" content=\"pl_PL\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Wyliczmy podobie\u0144stwo! - Lukasz Antkowiak's blog\" \/>\n<meta property=\"og:description\" content=\"W poprzednim wpisie dotycz\u0105cym PlagDetectora zajmowali\u015bmy si\u0119 kompresj\u0105 token\u00f3w. Dzisiaj zajmiemy si\u0119 trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobie\u0144stwa pomi\u0119dzy kodami \u017ar\u00f3d\u0142owymi. Ma\u0142a powt\u00f3rka...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/\" \/>\n<meta property=\"og:site_name\" content=\"Lukasz Antkowiak's blog\" \/>\n<meta property=\"article:published_time\" content=\"2017-05-20T13:00:49+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2017-05-17T21:43:31+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/blog.lantkowiak.pl\/wp-content\/uploads\/2017\/05\/user756_1161918650.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"500\" \/>\n\t<meta property=\"og:image:height\" content=\"327\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\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=\"3 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\/05\/20\/wyliczmy-podobienstwo\/\",\"url\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/\",\"name\":\"Wyliczmy podobie\u0144stwo! - Lukasz Antkowiak's blog\",\"isPartOf\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/#website\"},\"datePublished\":\"2017-05-20T13:00:49+00:00\",\"dateModified\":\"2017-05-17T21:43:31+00:00\",\"author\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6\"},\"breadcrumb\":{\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/#breadcrumb\"},\"inLanguage\":\"pl-PL\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Strona g\u0142\u00f3wna\",\"item\":\"https:\/\/blog.lantkowiak.pl\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Wyliczmy podobie\u0144stwo!\"}]},{\"@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":"Wyliczmy podobie\u0144stwo! - 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\/05\/20\/wyliczmy-podobienstwo\/","og_locale":"pl_PL","og_type":"article","og_title":"Wyliczmy podobie\u0144stwo! - Lukasz Antkowiak's blog","og_description":"W poprzednim wpisie dotycz\u0105cym PlagDetectora zajmowali\u015bmy si\u0119 kompresj\u0105 token\u00f3w. Dzisiaj zajmiemy si\u0119 trzecim i zarazem ostatnim krokiem naszego algorytmu, a mianowicie wyliczaniem podobie\u0144stwa pomi\u0119dzy kodami \u017ar\u00f3d\u0142owymi. Ma\u0142a powt\u00f3rka...","og_url":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/","og_site_name":"Lukasz Antkowiak's blog","article_published_time":"2017-05-20T13:00:49+00:00","article_modified_time":"2017-05-17T21:43:31+00:00","og_image":[{"width":500,"height":327,"url":"https:\/\/blog.lantkowiak.pl\/wp-content\/uploads\/2017\/05\/user756_1161918650.jpg","type":"image\/jpeg"}],"author":"\u0141ukasz Antkowiak","twitter_card":"summary_large_image","twitter_misc":{"Napisane przez":"\u0141ukasz Antkowiak","Szacowany czas czytania":"3 minuty"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/","url":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/","name":"Wyliczmy podobie\u0144stwo! - Lukasz Antkowiak's blog","isPartOf":{"@id":"https:\/\/blog.lantkowiak.pl\/#website"},"datePublished":"2017-05-20T13:00:49+00:00","dateModified":"2017-05-17T21:43:31+00:00","author":{"@id":"https:\/\/blog.lantkowiak.pl\/#\/schema\/person\/009bfc4db220c225786c59b1748ba1e6"},"breadcrumb":{"@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/#breadcrumb"},"inLanguage":"pl-PL","potentialAction":[{"@type":"ReadAction","target":["https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/blog.lantkowiak.pl\/index.php\/2017\/05\/20\/wyliczmy-podobienstwo\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Strona g\u0142\u00f3wna","item":"https:\/\/blog.lantkowiak.pl\/"},{"@type":"ListItem","position":2,"name":"Wyliczmy podobie\u0144stwo!"}]},{"@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\/363","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=363"}],"version-history":[{"count":2,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/363\/revisions"}],"predecessor-version":[{"id":366,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/posts\/363\/revisions\/366"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/media\/367"}],"wp:attachment":[{"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/media?parent=363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/categories?post=363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.lantkowiak.pl\/index.php\/wp-json\/wp\/v2\/tags?post=363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}