Хабрахабр

Так устроен поиск заимствований в Антиплагиате

Мы уже рассказывали вам об интересных статистиках текстов, делали обзор статей применений автокодировщиков в анализе текстов, удивляли нашими свежими алгоритмами поиска переводных заимствований и парафраза. Я решил продолжить нашу корпоративную традицию и, во-первых, начать статью с «Т», а во-вторых, рассказать:

  • как быстро найти абзац текста среди сотен миллионов статей;
  • во что превращается документ после загрузки в систему Антиплагиат, и что с этим делать дальше;
  • как формируется отчет, который почти никто не смотрит, а стоило бы;
  • как проиндексировать не все, но достаточно.

Как все начиналось

В 2005 году ректор одного из крупных московских вузов пришел к нам в компанию Forecsys за решением очень серьезной проблемы — в учебных заведениях студенты сдавали тотально списанные дипломы и курсовые работы. Мы взяли несколько сотен работ отличников и поискали их в сети простыми запросами. Больше половины «отличников» оказались жуликами, которые скачали диплом из интернета и заменили только титульную страницу. Больше половины отличников, Карл! Что происходило с обычными студентами — сложно даже представить. Проще всего работа искалась по запросу, содержащему слова с «очепятками». Нам стали понятны масштабы бедствия. Надо было срочно что-то решать. Зарубежные англоязычные вузы к тому времени уже пользовались решениями по поиску заимствований, но работы на русском языке почему-то не проверял никто.

В результате 17 марта 2005 года стартовала разработка первой отечественной системы поиска заимствований. Зарубежные игроки не захотели тогда адаптировать свои решения под русский язык. Мы планировали выпустить сайт к 1 сентября 2005 года, но, как это часто бывает с программистами, немного не успели. Само слово «Антиплагиат» было придумано чуть позже, а домен antiplagiat.ru зарегистрирован 28 апреля 2005 года. Знаете, я даже этому рад, поскольку во время корпоратива по случаю дня рождения компании все могут спокойно праздновать, а не переживать за первый школьный день у своих детей. Официальный день рождения нашей компании — это день, когда antiplagiat.ru принял первых пользователей, а именно 4 сентября.

В 2005 году мы создали своеобразный поисковик, в котором, в отличии от Яндекса и Гугла, запросом выступает не два-три слова, а целый текст, состоящий из нескольких предложений. Но что-то я отвлекся. Поэтому разумно использовать «Антиплагиат», если у вас есть текст от 1000 знаков (это примерно полстраницы).

Сразу же стало понятно, что это не взлетит и будет медленно работать уже на нескольких миллионах документов. Во время разработки сервиса был сделан прототип на php (web-часть) и Microsoft SQL Server (поисковый движок). Сейчас система написана на C# и python, использует PostgreSQL и MongoDB (на самом деле много чего еще, но об этом в следующей статье). Поэтому пришлось пилить свой поисковый движок. Ставьте лайки Пишите в комментариях, если хотите узнать об истории развития системы, смене процессов работы компании и железе, на котором «Антиплагиат» работал в разные моменты своей жизни, и работает сейчас. Поисковый движок у нас по-прежнему полностью собственной разработки.

Часто в поисковике можно встретить такие выражения как «проверить на антиплагиат», «повысить антиплагиат». Слово, давшее название компании, сейчас стало уже нарицательным. Нас часто спрашивают про другие «антиплагиаты». Все, кто так или иначе связан с областью поиска заимствований в России и ближнем зарубежье, пытаются использовать слово «антиплагиат» для поднятия в поисковой выдаче. Так вот, «Антиплагиат» — один, это торговая марка и название нашей компании.

Сразу были отвергнуты различные семантические построения из текстов, поиск смыслов, разбор предложений и т.д. В самом начале реализации сервиса поиска заимствований мы решили, что будем работать с текстом как с последовательностью символов. Выбранное нами решение дает два огромных преимущества — высокую скорость поиска и относительно небольшой объем поисковых индексов.

Они отличаются функциональностью, но содержат в своей основе один и тот же принцип работы поиска заимствований. К настоящему моменту есть три продукта в нашей линейке. Схема поиска заимствований, как вы видите на изображении, проста и незамысловата, как рисование совы. В этой статье я расскажу о том, как устроен наш классический поиск заимствований — функционал, ставший основой сервиса с самого начала и концептуально не поменявшийся до сих пор. Дальше ищем заимствования в этом тексте, получаем «ревизии» (так мы называем отчет по одному модулю поиска) и, наконец, собираем ревизии в один большой отчет, который и показываем в итоге пользователю. Сначала мы получаем документ от пользователя, затем мы извлекаем из него текст.

Давайте посмотрим, как все это происходит в деталях.

Извлечение текста

Прежде всего, «Антиплагиат» является сервисом поиска только текстовых заимствований, а значит, из всех документов нам нужно извлечь текст, чтобы дальше с ним работать. Система поддерживает возможность загрузки документов в docx, doc, txt, pdf, rtf, odt, html, pptx и еще нескольких (никогда не использовавшихся) форматах. Также все эти документы вы можете загружать в архивах (7z, zip, rar). Такой способ был популярен, когда у нас не было возможности загружать сразу несколько документов через веб-интерфейс. Ниже приведен график популярности форматов загружаемых документов в корпоративной части нашей системы. На нем видно, как за несколько лет doc вытесняется docx, и постепенно растет доля pdf. Если не рассматривать txt (извлечение текста для него тривиально), то для нас наиболее приятным является pdf. За рубежом pdf является стандартом де-факто, в нем публикуются статьи, готовятся студенческие работы. Согласно нашей статистике, pdf постепенно набирает популярность в России и странах СНГ. Мы и сами продвигаем этот формат в массы, рекомендуя загружать документы именно в нем.

Вам ведь надо проверить текст, а не протестировать систему? Мы ограничили форматы загрузки документов для частных клиентов до pdf и txt, и именно поэтому сократили потребление ресурсов, уменьшили затраты на поддержку бесплатного сервиса. Так какая разница в каком формате его загружать?

Следующим по простоте извлечения текста идет docx, т.к., по сути, это zip-архив с xml внутри, его достаточно просто обрабатывать, и многое можно сделать на низком уровне.

Этот формат долгое время был закрытым, и сейчас существует куча его реализаций. Самым сложным для нас является doc. Формат использует внутри себя OLE, позже выросшее в COM и ActiveX, все бинарное, местами не совместимое между версиями. Последний Microsoft Word, который не поддерживал .docx (пусть и через Microsoft Office Compatibility Pack), выпускался аж 20 лет назад и входил в Microsoft Office 97. Хорошо, что .doc-формат постепенно сходит со сцены. В общем, ужасный сон современного программиста. Скоро мы станем целенаправленно предупреждать пользователей о том, что этот формат устарел. Думаю, настало время и нам помочь ему выйти на пенсию.

Мы получили файл и начали извлекать текст. Итак, вернемся к отчету. Кроме того, на этом же этапе мы ищем технические обходы «Антиплагиата». Вместе с текстом система извлекает и позиции слов на страницах, чтобы в дальнейшем иметь возможность показывать нашим пользователям разметку отчета о заимствовании на самом документе.

Проблема в том, что числовой параметр так и просится стать оценкой. Как только появился «Антиплагиат», показывающий процент оригинальности, появились и желающие пройти проверку на заимствование с минимальными усилиями, а также люди, предлагающие такую услугу за деньги. Именно эта беда и породила такое направление, как тюнинг работ (изменение в тексте с целью увеличить процент оригинальности работы). Ведь это так просто — вместо чтения работы с использованием системы в качестве инструмента, не читать ее, а оценить по проценту оригинальности! Подробнее о проблемах в вузовских процессах читайте в статье «О практике обнаружения заимствований в российских вузах».

Дело в том, что за обнаруженный «финт ушами» последует очень жесткое наказание — отчисление, и несмываемое пятно на научной репутации, несовместимое с дальнейшей карьерой. В зарубежных системах поиска проблемы обнаружения технических обходов и противодействия им, практически, не стоит. Студента скорее всего отправят переделывать. У нас же ситуация до комичного проста: «Ой, это система что-то напортачила!», «Ой, это не я, оно само!». Дело в том, что списать, увы, не является чем-то зазорным.

Еще одним способом извлечения текста является OCR. Но опять отвлекся. Подробнее об этом написано в статье «Распознавание изображений на службе у «Антиплагиата»». Мы печатаем документ на виртуальном принтере, а потом распознаем его.

Сначала мы извлекали тексты с помощью IFilter'ов. Теперь немного нашей истории об извлечении текстов. Мы думали, что эти проблемы решатся, если начать использовать платные библиотеки, но и тут обнаружили ограничения: по-прежнему под Windows, не видят формул, иногда падают на специально подготовленных документах (разные библиотеки на разных!). Они медленные, только под Windows, и не возвращают информацию о форматировании (непонятно, где белый текст на белом фоне, нельзя потом сделать разметку блоков заимствования прямо в документе пользователя). Следующая идея была в том, чтобы OCR'ить все входящие документы, но этот подход очень ресурсозатратен (обработка всего 10-и страниц в минуту на одном ядре), и местами текст извлекается не точно.

Однако потом, немного пожив с этим, понимали, что это снова Опыт. Серебряной пули мы не нашли, хотя пару раз думали, что вот оно, Счастье. Сейчас у нас работает все вышеперечисленное и еще немножко. Извлечение текста балансирует на тонкой грани между производительностью (надо извлекать текст из сотни документов в минуту), надежностью (надо извлекать текст из всего), функциональностью (форматирование, обходы, вот это вот все). Мы постоянно экспериментируем с этой областью и продолжаем искать свое Счастье.

Текст извлечен, обходы найдены и частично устранены, отправляемся искать заимствования!

Поиск заимствований

Идея, реализованная в процедуре поиска, была предложена Ильей Сегаловичем и Юрием Зеленковым (прочитать можно, например, в статье: Сравнительный анализ методов определения нечетких дубликатов для Web-документов). Расскажу, как это работает у нас. Возьмем, для примера, предложение: «Указ Президента РФ от 7 мая 2012 г. N 596 „О долгосрочной государственной экономической политике“».

  1. Разбиваем предложения на слова, выкидываем числа, знаки препинания, стоп-слова. Лемматизируем (приводим в нормальную форму) все слова.
  2. Превращаем слова в целые числа путем хеширования, получаем массив чисел.
  3. Берем первую тройку хешей, затем 2, 3, 4-ый хеш, затем 3, 4, 5-ый и так до конца массива хешей. Это и есть шинглы — черепички. Свое название такой способ получил из-за такого черепичного перекрытия наборов. Каждую черепичку сливаем в один объект и хешируем еще раз.
  4. Сортируем полученные числа, получаем упорядоченный массив целых чисел. Это и есть основа для поиска.

Эта функция должна работать быстро, т.к. Теперь для поиска нам нужна магическая функция, которая по такому списку хешей превращает документы, отранжированные по убыванию числа совпавших хешей, в документ-источник. Для того, чтобы быстро находить такой набор, нам нужен обратный индекс, который по хешу возвращает список документов, в которых этот хеш есть. мы хотим искать в миллиардах документов. В отличии от наших старших братьев-поисковиков, мы храним эту таблицу на ssd, а не в памяти. У нас реализована такая гигантская хеш-таблица. Поиск по индексу занимает малую часть времени от всего цикла обработки документа. Нам вполне хватает такой производительности. Смотрите как проходит поиск:

Поиск по индексу Этап 1.

Дальше ранжируем список идентификаторов документов-источников по числу встретившихся хешей из текста-запроса. Для каждого хеша текста-запроса мы получаем список идентификаторов документов-источников, в которых он встречается. Получаем ранжированный список документов-кандидатов на источник заимствования.

Построение ревизии Этап 2.

Это все равно много для сравнения каждого документа с текстом-запросом. Для большого текста-запроса кандидатов может быть порядка 10 тыс. Берем первый документ-источник, делаем сравнение с текстом-запросом и исключаем из всех остальных кандидатов те хеши, которые уже были в этом первом документе. Действуем жадно, но решительно. Берем первый документ из нового списка, сравниваем с текстом-источником, удаляем хеши, удаляем нулевых кандидатов, пересортируем кандидатов. Удаляем из списка кандидатов тех, у которых остался ноль хешей, пересортируем кандидатов по новому числу хешей. Делаем так раз 10-20, обычно этого хватает, чтобы список иссяк или в нем остались только те документы, у которых есть совпадение по нескольким хешам.

Выделение конкретных фрагментов заимствования делается с помощью суффиксного дерева. Использование хешей слов позволяет нам проводить операции сравнения быстрее, экономить на памяти и хранить не тексты документов-источников, а их цифровые слепки (TextSpirit, как мы их ласково называем), полученные при индексации, тем самым не нарушая авторских прав.

В результате проверки одним модулем поиска получаем ревизию, в которой находится список источников, их метаданные и координаты блоков заимствований относительно текста-запроса.

Сборка отчета

Кстати, а что делать, если один из 10-15 модулей не ответил вовремя? Мы ищем по коллекциям РГБ, eLibrary и Гаранта. Эти модули поиска расположены на территории сторонних организаций, и не могут быть перенесены на нашу площадку по соображениям авторского права. Точкой отказа тут всегда может быть канал связи и различные форс-мажоры в дата центрах, не управляемых нами. С одной стороны, заимствование может быть найдено в любом модуле поиска, с другой, если один из компонентов системы недоступен, то можно ухудшить качество поиска, но отдать большую часть результата, предупредив при этом пользователя, что результат по некоторым модулям поиска пока не готов. Какой вариант применили ли бы вы? Мы применяем оба этих варианта в зависимости от обстоятельств.

Здесь используется подход аналогичный подготовке одной ревизии. Наконец, все ревизии получены, начинаем сборку отчета. У нас есть заимствования двух типов. Вроде бы ничего сложного, но и тут есть интересные задачи. Оранжевым отмечаются все остальные заимствования. Зеленым обозначаются «Цитирования» — корректно оформленные (по ГОСТу) цитаты из модуля «Цитирование», выражения типа «что и требовалось доказать» из модуля «Общеупотребительных выражений», нормативно правовые документы из баз Гаранта и Лекспро. Зеленые имеют приоритет над оранжевыми, если только не входят целиком в оранжевый блок.

То, что мы видим сверху, и есть отчет. В результате отчет можно сравнить с лежащим на столе распечатанным на бумаге текстом, поверх которого набросаны разноцветные полоски (блоки заимствований и цитирований), причудливо перекрывающие друг друга. У нас есть два показателя для каждого источника:

Если один и тот же текст был найден в нескольких источниках, то учитывается он только в одном из них. Доля в отчете — отношение объема заимствований, которое учитывается из данного источника, к общему объему документа. В сумме дает процент заимствований и цитирований (в зависимости от цвета источника). При изменении конфигурации отчета (включении или отключении источников) данный показатель источника может меняться.

Доли в тексте по источникам суммировать нет смысла, легко получится 146% или даже больше. Доля в тексте — отношение объема, заимствованного из данного источника текста к общему объему документа. Данный показатель не изменяется при изменении отчета.

Это специальная функция для того, чтобы эксперт, проверяющий работу, отключил заимствования собственных работ автора (при этом может открыться, что данный фрагмент есть не только в собственной работе автора, но и где-то еще) и отдельные блоки заимствования, изменил тип источника с заимствования на цитирование. Естественно, отчет можно редактировать. Любую работу для проверки надо прочитать. В результате редактирования отчета эксперт получает реальное значение заимствований. К сожалению, это вполне логичное действие не всеми совершается, многие довольствуются процентом оригинальности, даже не заглядывая в отчет. Это удобно делать, просматривая исходный вид документа, в котором размечены блоки заимствования, и сразу же, по мере прочтения, редактировать отчет.

Однако вернемся на шаг назад и узнаем, что же попадает в индекс модуля поиска по интернету, созданный Антиплагиатом.

Индексация интернета

Антиплагиат в значительной степени ориентирован на студенческие работы, научные публикации, выпускные квалификационные работы, диссертации и т.п. Интернет мы индексируем направлено — ищем большие скопления научных текстов, рефератов, статей, диссертаций, научных журналов и т.п. Индексация происходит так:

  1. Наш робот приходит, представляется и, руководствуясь robots.txt (у нас хороший робот), загружает документы с разумной нагрузкой на каждый хост (в работе одновременно сотни сайтов, поэтому мы можем и подождать некоторое время между загрузками страниц);
  2. Робот передает документ и его метаданные в очередь на обработку, из документа извлекается текст;
  3. Текст анализируется на «качество» — как вы помните из статьи про свалку, мы умеем определять жанр документа, добавляем сюда простые эвристики на объем и понимаем, годный текст к нам пришел или какая-то белиберда;
  4. Качественный текст проходит дальше и превращается в хеши. Хеши и метаданные отправляются в основной индекс интернета;
  5. Мы сравниваем пришедший текст с ранее проиндексированными нами текстами. Новичок добавляется, только если он реально новый, т.е. 90% его хешей не содержится целиком в каком-то другом уже проиндексированном тексте. Если же документ уже есть у нас, мы добавляем url этого документа в атрибуты нашего архива.

Таким образом мы индексируем качественные тексты, и все проиндексированные тексты у нас существенно различны. Рост объема проиндексированного в интернете показан на рисунке ниже. Сейчас в среднем мы добавляем в индекс по 15-20 млн документов в месяц.

А ее и нет! Заметили, что нигде не описана процедура удаления из индекса? Мы считаем, что если нам удалось увидеть что-то в интернете, то и другие люди могли видеть этот текст и использовать его тем или иным способом. Мы принципиально не удаляем документы из индекса. Да, представьте себе, выражение «Попавшее в интернет останется там навсегда», — не верно! В связи с этим появляется интересная статистика того, что когда-то было в интернете, а теперь уже больше там нет. Интересно ли вам узнать о нашей статистике по этому вопросу? Что-то исчезает из интернета навсегда.

Заключение

Удивительно, как технические решения, принятые больше 10 лет назад, до сих пор остаются актуальными. Мы сейчас готовим к выпуску 4 версию индекса, она быстрее, технологичнее, лучше, однако в ее основе лежат всё те же решения. Появились новые направления поиска — переводные заимствования, перефразирование, но и там находит применение наш индекс, выполняя пусть и малую, но важную часть работы.

Уважаемые читатели, что вам было бы интересно узнать о нашем сервисе ещё?

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть