Система пошуку плагіату для заданої предметної області



В роботі надається на короткий огляд базового алгоритму «Шинглів» та його модифікації, що базується на конкретній області його застосування.

Plagiarism search engine for a given subject area

Mahdych Bohdan Valentinovich, Ukraine, Kiev, Faculty of Information and Computer Science, NTUU "KPI"

Work place: «IT-Enterprise», Ukraine, 02140, Kiev, pr. Bagana 14a, 4th floor

This work is a brief overview of the basic algorithm" Shingle"and its modifications based on the particular area of application.

Keywords: plagiarism, algorithm"Shingle", duplicate, copy, сopyright protection

Вступ

Стрімкий розвиток мережі Інтернет поряд з збільшення комп’ютерної грамотності широкої аудиторії користувачів стало причиною широкого використання плагіату в різних сферах людської діяльності, зокрема в галузі освіти та науки. В освіті проблема плагіату є доволі гострою та активно обговорюється. На жаль, більшість студентів не проводять багато часу в бібліотеках та архівах через те, що більшість інформації можна «скачати» з джерел мережі Інтернет, або запозичити роботи студентів минулих років навчання і при здачі матеріалу викладачеві банально замінити прізвище на своє. Таким чином, в теперішній час студенти досить часто порушують авторське право на інтелектуальну власність. Тому для викладачів досить актуальною є проблема виявлення плагіату в роботах студентів. В статті запропонована модифікація відомого алгоритму «шинглів» для поліпшення результативності пошуку плагіату.

Алгоритм «Шинглів»

Уди Манбер в 1994 році першим в світі висловив ідею пошуку дублікатів, а в 1997 році Андрій Бродер оптимізував і довів її до логічного завершення, давши ім'я даній системі - «алгоритм шинглів».

На сьогоднішній день він є найпопулярнішим алгоритмом для пошуку плагіату в довільних текстах. Він розроблений для пошуку копій (дублікатів) розглянутого тексту в документі та є потужним інструментом, що може боротися з проявами плагіату.

Метод заснований на представленні текстів у вигляді множини послідовностей фіксованої довжини, що складаються із сусідніх слів. При значному перетині таких множин документи будуть схожі один на одного.

Розберемо через які етапи проходить текст, що буде порівнюватись:

  1. Канонізація тексту і видалення «стоп-символів» і«стоп-слів»;

  2. Розбиття на шингли;

  3. Обчислення хешів шинглів;

  4. Порівняння та визначення результату.

Канонізаціятексту

Канонізація тексту приводить оригінальний текст до єдиної нормальної форми. Текст очищається від«стоп-символів» і «стоп-слів» (прийменників, сполучників, знаків пунктуації тощо), які не повиненні брати участь у порівнянні. У деяких випадках також пропонується видаляти з тексту прикметники, так як вони не несуть смислового навантаження. Також на етапі канонізації тексту можна приводити іменники до називного відмінку, єдиного числа або залишати від них тільки корінь. На виході цього етапу ми маємо текст, очищений від «сміття» і готовий до порівняння (рис. 1).

Рисунок 1. Послідовність робіт етапу канонізації в алгоритмі «шинглів»

Розбиття на шингли

Шингли - виділені підпослідовності слів. Необхідно з порівнюваних текстів виділити підпослідовності слів, що йдуть один за одним по N штук (довжина шингла). Таким чином, розбиваючи текст на підпослідовності, ми отримаємо набір шинглів. Дії по кожному із пунктів виконуються для кожного з порівнюваних текстів (рис. 2).

Рисунок 2. Послідовність робіт етапу розбиття на шингли

Обчислення хешів шинглів

Принцип алгоритму шинглів полягає в порівнянні випадкової вибірки контрольних сум шинглів (підпослідовностей) двох текстів між собою. Тепер у кожного з текстів є свої набори шинглів. Слід розрахувати контрольну суму кожного з шинглів. Для розрахунку можна використовувати відомий алгоритм CRC3 2 (рис. 3).

Рисунок 3. Послідовнсть робіт при знаходженні контрольних сум шинглів

Порівняння та визначення результату

На цьому етапі порівнюємо між собою всі елементи першого масиву з відповідними елементами другого масиву, зчитуємо відношення однакових значень та з цього отримуємо кінцевий результат (рис. 4).

Рисунок 4. Послідовнсть при порівнянні елементів масиву

Модифікація алгоритму для заданої предметної області

Заданий алгоритм є досить дієвим, протев кожній області є свої сталі вирази (фразеологізми) та свої найбільш частовживані слова, які необхідно також видаляти з тексту. Тому заданий алгоритм потрібно підлаштовувати під кожну предметну область. Для покращення роботи алгоритму булив ведені деякі модифікації.

Даний алгоритм не враховує слів синонімів. Досить часто здійснюється перефразовування речення для обходження системи анти-плагіату. Тому доцільним буде введення множини синонімів слів, що часто вживаються в заданій предметній області. Дане введення є досить великою модифікацією, що покращить заданий алгоритм.

Також необхідно ввести множину синонімів словосполучень, тому що досить часто автоматизовані системи надають новим словосполученням достатньо великий відсоток унікальності. Тому при знаходженні слів, що потрапляють в задані множини (множина синонімів часто вживаних слів, множина синонімів словосполучень), їх також потрібно враховувати в відсоток подібності текстів.

Задані модифікації будуть ще більш краще знаходити подібні тексти, та виявляти подібні тексти в заданій предметній області.

Перелік Посилань

  1. W-SHINGING–– URL : https://en.wikipedia.org/wiki/W\-shingling

  2. MOSS. A System for Detecting Software Plagiarism. ––URL: https://theory.stanford.edu/~aiken/moss/

  3. MillerC., ‘‘Detecting duplicates: a searcher’s dream come true’’ –– URL: https://www.questia.com/magazine/1G1\-9065495/detecting\-duplicates\-a\-searcher\-s\-dream\-come\-true
May 24, 2016