Описано деякі проблеми побудови та зберігання пошукового індексу для систем автоматизованої перевірки документів на наявність запозичень, наведено ряд ефективних рішень.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Чиркин Євген Сергійович


SEARCH INDEX FOR SYSTEMS OF ANTI-PLAGIARISM

Some of the problems of building and storing the search index for the systems of automated document checks for the presence of borrowing and some effective solutions are considered.


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2014
    Журнал: Вісник російських університетів. Математика
    Наукова стаття на тему 'Проблеми реалізації пошукового індексу для системи антиплагіату '

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

    ?УДК 004.62

    ПРОБЛЕМИ РЕАЛІЗАЦІЇ пошукового індексу ДЛЯ СИСТЕМИ Антиплагіат

    © Е.С. Чиркин

    Ключові слова: антиплагіат; пошук; пошуковий індекс.

    Описано деякі проблеми побудови та зберігання пошукового індексу для систем автоматизованої перевірки документів на наявність запозичень, наведено ряд ефективних рішень.

    ВСТУП

    Будь-яка автоматизована система з пошуку запозичень (система антиплагіату) являє собою спеціалізовану пошукову систему повнотекстового пошуку.

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

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

    Розглянемо значущі складові етапів підготовки документа до індексування, їх проблеми та можливі рішення, а також рішення в модулі антиплагіату інформаційно-пошукової системи «ІТ-спеціаліст».

    ФОРМАТ ДОКУМЕНТА

    Документи, в яких повинен здійснюватися пошук, зазвичай представлені в найбільш поширених форматах програмних пакетів Microsoft Office, Open Office.Org/Libre Office - т. Зв. «Формати файлів» .doc, .docx, .rtf, .odt, рідше - .pdf і .djvu. Крім цього база всіх текстів поповнюється сторінками з мережі Інтернет, що означає необхідність підтримки HTML-формату. Не виключено, що документи будуть знаходитися в архівах форматів 7-Zip, ZIP або RAR, можливо багаторазове вкладення. Не виключено існування впроваджених в документ документів (причому, буває, вони не ізвлекаемості звичайними способами через програмні інтерфейси). Дане різноманіття документів представляє складність по організації логічного каталогу для зберігання метаінформації про них.

    Рішення: зручно вважати, що будь-який документ є таким собі контейнером, що містить інші контейнери. З будь-якого контейнера або може бути витягнутий текст, або ні. При формуванні результатів пошуку посилання виставляється на текст і всі документи, що містять даний текст.

    ОСНОВНА ЧАСТИНА

    Витяг тексту. Витяг тексту тісно пов'язане з форматом файлу документа - наприклад, «формат» .docx є ZIP-архів декількох файлів, головний з яких - XML-файл спеціальної структури, яка містить основний текст документа. Файли в форматах PDF і DjVu можуть містити текстовий шар, а можуть не містити. Існує відома особливість редагування .docx-файлів -наприклад, у файлі, створеному в старішої версії програмного пакету Microsoft Word, відредагованого в новішій і знову відкритого в колишньої, можуть зникати окремі порушені редагуванням в новій версії прогалини між словами. Дана особливість проявляється нерегулярно і спонтанно, однак побудова індексу для такого файлу буде безглуздим через пошкодження його оригінального вмісту при подібних маніпуляціях.

    Певну складність представляє витяг тексту з HTML-документів. Пов'язано це з тим, що з точки зору споживання ресурсів вигідно видобувати текст з викачаних сторінок в краулер (в самому пошуковому роботові, скачували за певним планом сторінки з мережі Інтернет), в той же час: а) розбір сторінки займає надто великий проміжок часу, щоб вважати цю операцію швидкої; б) нерідкі випадки, що вимагають саме детального аналізу сторінки (помилка вказівки кодування, помилковий синтаксис HTML-коду, розбір форматування і інші випадки). При цьому буває, що HTML-сторінки не містять помилок у форматуванні і не уявляють складності з аналізу та вилучення з них будь-якої інформації. Спільно ці дві проблеми породжують проблему вилучення тексту - цілком можливо, що один або кілька методів витягнуть помилковий або неповний текст, витяг закінчиться невдачею, текст буде витягнутий не в очікуваній формі (наприклад, часто документи - файли формату RTF, створені в Open

    Office.Org, відкриваються в неправильному кодуванні в Microsoft Word).

    Рішення: зважаючи на різноманіття і складності форматів документів, а також неповної сумісності файлів одного формату, створених різними програмами, слід вважати, що текст з контейнера може бути витягнутий різними способами. Наприклад, текст з файлу формату. doc можна витягти: Microsoft Word, Libre Office, Open Office.Org. З HTML - Microsoft Word, Libre Office, Open Office.Org, через COM-об'єкт Internet Explorer, бібліотеками движків браузерів Gecko і Web Kit, простим парсером.

    Маскування тексту. Видалений з повноцінного документа текст майже завжди містить нетекстові елементи. Наприклад, символи «м'якого» перенесення, що додаються текстовим редактором при кожному переносі слова в абзаці, у якого не заборонені автоматичні переноси. Можливе використання різних видів прогалин, розривів слів, рядків.

    Рішення: дані символи відносяться до категорії «невидимих», або символів форматування, і повинні бути або видалені, або замінені більш простими, еквівалентними їм за змістом. Наприклад: всілякі розриви рядків - на символи розриву рядків, всі види прогалин - на звичайний пробіл, «м'які» переноси - видаляються, буква «е» замінюється на «е» та інші перетворення.

    Помилки в написанні слів. Якщо якість тексту наукових робіт, публікації в періодичних і неперіодичних виданнях контролюються редакторами, коректорами, науковими керівниками, то сторінки в мережі Інтернет рясніють синтаксичними помилками. Причому помилки в т. Ч. Можуть міститися в публікаціях в довірених мережевих джерелах і представляють чималу практичну цінність.

    Рішення: при побудові індексу виявляється досить ефективним видаляти поспіль повторювані символи, а також м'який і твердий знаки.

    Перетворення слів для індексації. Кожне слово спочатку наводиться до його базової граматичній формі (етап лематизації). Потім отримане слово усікається (етап стемматізаціі) для підвищення інваріантності форм слів щодо його суфіксів і закінчення. Два цих етапу спільно необхідні для обробки слів, для яких неможливо відновити базову форму (наприклад, для невідомих слів). Наприклад, так робиться в Sphinx [1].

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

    Між етапом лематизації і стемматізаціі існує етап нормалізації слова щодо його синонімів, т. Е. Слово, якщо це можливо, замінює деякий його синонім, призначений «базовим». В системі міститься не дуже велика кількість синонімів, т. К. «Базових» слово (словосполучень) для ланцюжка синонімів в російській мові насправді не дуже багато.

    Якщо всі попередні етапи підготовки тексту до індексації - службові, то цей етап має на меті скорочення розміру пошукового індексу.

    Індексація. Етап полягає в зменшенні «довжини» слова, а також перетворення слова в якийсь код, придатний для його упорядкування (для подальшого прискорення пошуку). можливі кілька

    варіантів індексу. Кожну запис про слові можна представити у вигляді <docid, wordno, wordid>, де docid -код документа (точніше, тексту) в базі даних, wordno-номер слова в тексті, wordid - код слова. Запис існує для кожного слова документа. В ідеальному випадку docid - це хеш від тексту (т. Е. Порядковий номер запису в базі даних, а безпосереднє ідентифікує текст значення), wordno можна вважати беззнаковим 32-бітовим цілим (досить майже для будь-яких випадків), wordid - також MD5- хеш від слова або саме слово. Крім цього для прискорення додатково повинен бути відсортований стовпець wordid, т. Е. Даний стовпець повинен існувати в подвоєному вигляді - впорядкованим і в складі записи. На жаль, в такому випадку обсяг навіть однієї записи виявляється дуже великим, в базу даних на доступних носіях обсягом в 1 Тб поміститься менше 1 млн документів, індексованих документів, не рахуючи накладних витрат на організацію структур зберігання.

    Проблема вирішується таким чином:

    1) прямий індекс не є головним і не зберігається або взагалі не будується;

    2) замість прямого індексу використовується інвертований (при прямому індексі зберігається інформація -які слова є в документі, при інвертованому -які документи містять кожне конкретне слово);

    3) в якості wordid використовується не унікальний ідентифікатор слова, а, наприклад, контрольна сума від слова (наприклад, CRC32 або навіть CRC24) (це дає хибнопозитивні спрацьовування при пошуку, але усувається додатковим аналізом або через прямий індекс);

    4) індекс зберігається в стислому вигляді. Зазвичай використовуються не звичайні алгоритми побітового стиснення без втрат, а т. Зв. обчислення дельт (примітка: не плутати обчислення дельт з дельта-індексом) (було: 13, 5, 9, 21; стало: 5, 4, 4, 8, т. е. після сортування: 5, 9, 13, 21, після обчислення дельт: 5, 4 = (9 - 5), 4 = (13 - 5), 8 = (21 - 13)) або т. н. кодування змінної ширини (як в Lucene [2]), коли в двійковому поданні числа перші кілька бітів зберігають довжину в байтах двійкового представлення числа або старший біт кожного байта резервується для ознаки продовження двійкового представлення числа, пов'язаного з попереднім байтом, або будь-який інший алгоритм.

    Зберігання індексу. Суть проблеми зберігання індексу полягає в тому, що при звичайному зберіганні записів прямого індексу в будь-який реляційної СУБД значення, що зберігає docid, повторюється і фактично ніде і ніколи не використовується, служачи основою для індексу по колонці в СУБД. Інвертований індекс не вирішує дану проблему, проте робить можливим зберігання його в стислому вигляді. Оптимально зберігати інвертований індекс в сторінково організованою пам'яті або в структурах типу B + дерев. У нашій роботі було використано компромісне рішення, не заснований на реляційних СУБД: зберігання впорядкованих блоків записів, а також метаінформації. Розмір блоку в кожному випадку, якщо це можливо, максимальний (т. К. Чим більше блок - тим швидше працює двійковий пошук, тому що відбувається менша кількість проміжних читань з носія), в ідеальному випадку пошук по блоку вироджується, т. К. По метаінформації визначається, що шуканого значення в діапазоні значень, збережених в блоці, немає. Додатковим перевагою даного типу пошуку являє-

    ся найвища швидкість його побудови, що дорівнює сумі часів упорядкування блоку і записи його на носій.

    ВИСНОВОК

    У статті розглянуті основні етапи побудови пошукового індексу для систем автоматизованої перевірки на запозичення, обліку індексованих документів, приведено оригінальне рішення по організації системи зберігання пошукового індексу.

    ЛІТЕРАТУРА

    1. Sphinx 2.1.2-release reference manual. Part 3. Indexing. URL: http://sphinxsearch.com/docs/current.html#indexing (accessed:

    01.11.2013).

    2. Apache Lucene - Index File Formats. URL: http://lucene.apa-che.org/core/4_5_1/core/org/apache/lucene/codecs/lucene45/package-summary.html#package_description (accessed: 01.11.2013).

    ПОДЯКИ: Робота виконана за фінансової підтримки РФФД, проект № 12-07-00512.

    Надійшла до редакції 20 листопада 2013 р.

    Chirkin E.S. SEARCH INDEX FOR SYSTEMS OF ANTIPLAGIARISM

    Some of the problems of building and storing the search index for the systems of automated document checks for the presence of borrowing and some effective solutions are considered .. Kew words: anti-plagiarism; searching; search index.

    Чиркин Євген Сергійович, Тамбовський державний університет ім. Г.Р. Державіна, г. Тамбов, Російська Федерація, програміст, старший викладач кафедри інформатики та інформаційних технологій, e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Chirkin Evgeniy Sergeyevich, Tambov State University named after G.R. Derzhavin, Tambov, Russian Federation, Programmer, Senior Lecturer of Informatics and Information Technologies Department, e-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.


    Ключові слова: Антиплагіат /ПОШУК /ПОШУКОВИЙ ІНДЕКС /ANTI-PLAGIARISM /SEARCHING /SEARCH INDEX

    Завантажити оригінал статті:

    Завантажити