Мы уже рассказывали вам об интересном текстовая статистика , делал обзор статей по использованию автоэнкодеров в анализе текста , удивлен нашими свежими алгоритмами поиск переводных займов И парафраз .
Я решил продолжить нашу корпоративную традицию и, во-первых, начать статью с буквы «Т», а во-вторых, рассказать:
- как быстро найти абзац текста среди сотен миллионов статей;
- во что превращается документ после загрузки в систему Антиплагиат и что с ним делать дальше;
- как формируется отчет, который почти никто не смотрит, а надо бы;
- как индексировать не всё, но достаточно.
Как это все началось
В 2005 году к нам в компанию пришел ректор одного из крупных московских вузов.Форексис решить очень серьезную проблему - в учебных заведениях студенты сдавали полностью списанные дипломы и курсовые работы.
Мы взяли несколько сотен работ отличников и поискали их в Интернете по простым запросам.
Более половины «отличников» оказались мошенниками, которые скачали диплом из Интернета и подменили только титульный лист. Больше половины отличников, Карл! Трудно даже представить, что происходило с обычными студентами.
Проще всего было искать работу по запросу, содержащему слова с ошибками.
Нам стал ясен масштаб катастрофы.
Нужно было срочно что-то решать.
К тому времени зарубежные англоязычные вузы уже использовали решения для поиска заимствований, но работы на русском языке почему-то никто не проверял.
Иностранные игроки тогда не захотели адаптировать свои решения под русский язык.
В результате 17 марта 2005 года началась разработка первой отечественной системы поиска заимствований.
Само слово «Антиплагиат» появилось чуть позже, а домен антиплагиат.ру был зарегистрирован 28 апреля 2005 года.
Мы планировали выпустить сайт к 1 сентября 2005 года, но, как это часто бывает с программистами, немного опоздали.
поздно.
Официальным днем рождения нашей компании считается день, когда antiplagiat.ru принял своих первых пользователей, а именно 4 сентября.
Знаете, я этому даже рад, ведь во время корпоратива по случаю дня рождения компании каждый может спокойно отпраздновать и не переживать за первый день своего ребенка в школе.
Но как-то я отвлекся.
В 2005 году мы создали своеобразную поисковую систему, в которой, в отличие от Яндекса и Google, запрос представляет собой не два-три слова, а целый текст, состоящий из нескольких предложений.
Поэтому разумно использовать «Антиплагиат», если у вас текст объемом 1000 символов и более (это примерно полстраницы).
В ходе разработки сервиса был сделан прототип на PHP (веб-часть) и 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 внутри, его довольно легко обрабатывать, и многое можно сделать на низком уровне.
Самое сложное для нас – это док.
Этот формат долгое время был закрыт, а сейчас существует куча его реализаций.
Последний Microsoft Word, который не поддерживал .
docx (хотя и через пакет совместимости Microsoft Office), был выпущен 20 лет назад и входил в состав Microsoft Office 97. Формат внутри использует OLE, который позже перерос в COM и ActiveX, все двоичный, местами несовместимый между версиями.
В общем, это кошмар современного программиста.
Хорошо, что формат .
doc постепенно уходит со сцены.
Я думаю, пришло время помочь ему уйти на пенсию.
Скоро мы начнем специально предупреждать пользователей о том, что этот формат устарел.
Итак, вернемся к отчету.
Мы получили файл и начали извлекать текст. Вместе с текстом система также извлекает позиции слов на страницах, чтобы в дальнейшем иметь возможность показать нашим пользователям разметку отчета о заимствованиях на самом документе.
Кроме того, на этом же этапе мы ищем технические решения Антиплагиата.
Как только появился «Антиплагиат», показывающий процент оригинальности, появились люди, желающие пройти проверку на заимствование с минимальными усилиями, а также люди, предлагающие такую услугу за деньги.
Проблема в том, что числовой параметр начинает превращаться в оценку.
Все очень просто – вместо того, чтобы читать произведение, используя систему как инструмент, не читайте его, а оценивайте по проценту оригинальности! Именно эта беда породила такое направление, как тюнинговые работы (изменения текста с целью повышения процента оригинальности работы).
Подробнее о проблемах в университетских процессах читайте в статье.
«О практике выявления заимствований в российских вузах» .
В зарубежных поисковых системах практически нет проблемы обнаружения технических обходов и противодействия им.
Дело в том, что за обнаруженную «обманку ушами» последует весьма суровое наказание – отчисление, и несмываемое пятно на научной репутации, несовместимое с будущей карьерой.
Наша ситуация до смешного проста: «Ой, это система что-то напортачила!», «Ой, это не я, это сама!» Студента, скорее всего, отправят переделывать.
Дело в том, что списание, увы, не является чем-то зазорным.
Но я снова отвлекся.
Другой метод извлечения текста — OCR. Распечатываем документ на виртуальном принтере и затем распознаём его.
Подробнее об этом написано в статье «Распознавание изображений на службе Антиплагиата» .
Теперь немного нашей истории об извлечении текста.
Сначала мы извлекли тексты с помощью IFilters. Они медленные, только для Windows, и не возвращают информацию о форматировании (непонятно, где белый текст на белом фоне, нельзя потом разметить заимствованные блоки прямо в документе пользователя).
Мы думали, что эти проблемы будут решены, если мы начнем использовать платные библиотеки, но и здесь мы обнаружили ограничения: до сих пор в Windows они не видят формулы, иногда вылетают на специально подготовленных документах (разные библиотеки для разных!).
Следующей идеей было распознавать все входящие документы, но такой подход очень ресурсоёмкий (обработка всего 10 страниц в минуту на одном ядре), а в некоторых местах текст не извлекается точно.
Серебряной пули мы не нашли, хотя пару раз думали, что вот оно, Счастье.
Однако позже, пожив с этим некоторое время, мы поняли, что это снова Опыт. Извлечение текста находится на тонкой грани между производительностью (вам приходится извлекать текст из сотен документов в минуту), надежностью (вам приходится извлекать текст из всего), функциональностью (форматирование, сканирование и все).
Теперь у нас работает все вышеперечисленное и еще кое-что.
Мы постоянно экспериментируем в этой области и продолжаем поиск своего Счастья.
Текст извлечен, обходные пути найдены и частично устранены, пошли искать заимствования!
Поиск заимствований
Идею, реализованную в процедуре поиска, предложили Илья Сегалович и Юрий Зеленков (читать можно, например, в статье: Сравнительный анализ методов определения нечетких дубликатов веб-документов ).Я расскажу вам, как это работает у нас.
Возьмем, к примеру, предложение: «Указ Президента Российской Федерации от 7 мая 2012 г.
N 596 «О долгосрочной государственной экономической политике».
- Разбиваем предложения на слова, выкидываем цифры, знаки препинания, стоп-слова.
Лемматизируем (приводим к нормальной форме) все слова.
- Преобразуем слова в целые числа путем хеширования, получаем массив чисел.
- Берем первые три хеша, затем 2, 3, 4-й хэш, затем 3, 4, 5-й и так до конца хеш-массива.
Это черепица – черепица.
Свое название этот метод получил из-за мозаичного перекрытия множеств.
Мы объединяем каждый тайл в один объект и снова хэшируем его.
- Сортируем полученные числа и получаем упорядоченный массив целых чисел.
Это основа поиска.
Теперь для поиска нам понадобится волшебная функция, которая с помощью такого списка хешей превращает документы, отсортированные по убыванию количества совпадающих хэшей, в исходный документ. Эта функция должна работать быстро, потому что.
мы хотим искать в миллиардах документов.
Для того, чтобы быстро найти такое множество, нам нужен обратный индекс, который на основе хеша возвращает список документов, содержащих этот хеш.
Мы реализовали такую гигантскую хеш-таблицу.
В отличие от наших старших собратьев-поисковиков, мы храним эту таблицу на ssd, а не в памяти.
Нам этого спектакля вполне достаточно.
Поиск по индексу занимает небольшую часть времени всего цикла обработки документа.
Посмотрите, как работает поиск: ЭШаг 1. Поиск по индексу Для каждого хеша текста запроса мы получаем список идентификаторов исходных документов, в которых он встречается.
Далее мы ранжируем список идентификаторов исходных документов в соответствии с количеством хешей, встречающихся в тексте запроса.
Получаем ранжированный список документов-кандидатов на источник заимствования.
ЭШаг 2. Построение ревизии Для большого текста запроса кандидатов может быть около 10 тысяч.
Это все равно много для сравнения каждого документа с текстом запроса.
Мы действуем жадно, но решительно.
Берем первый исходный документ, проводим сравнение с текстом запроса и исключаем из всех остальных кандидатов те хеши, которые уже были в этом первом документе.
Удаляем из списка кандидатов тех, у кого осталось ноль хешей, и пересортируем кандидатов по новому количеству хэшей.
Берем первый документ из нового списка, сравниваем его с исходным текстом, удаляем хеши, удаляем нулевые кандидаты и пересортируем кандидатов.
Делаем это 10-20 раз, обычно этого хватает, чтобы список исчерпался или в нем остались только те документы, у которых есть совпадение по нескольким хешам.
Использование хэшей слов позволяет быстрее выполнять операции сравнения, экономить память и хранить не тексты исходных документов, а их цифровые копии (TextSpirit, как мы их ласково называем), полученные при индексировании, тем самым не нарушая авторских прав.
Выявление конкретных фрагментов заимствований осуществляется с помощью суффиксного дерева.
В результате проверки одним модулем поиска мы получаем ревизию, содержащую список источников, их метаданные и координаты заимствованных блоков относительно текста запроса.
Сборка отчета
Кстати, что делать, если один из 10-15 модулей не ответил вовремя? Ищем по коллекциям РГБ, eLibrary и Гаранта.Данные поисковые модули расположены на территории сторонних организаций и не могут быть перенесены на наш сайт по соображениям авторского права.
Точкой сбоя здесь всегда может стать канал связи и различные форс-мажорные обстоятельства в неконтролируемых нами дата-центрах.
С одной стороны, заимствования можно найти в любом поисковом модуле; с другой стороны, если один из компонентов системы недоступен, то можно ухудшить качество поиска, но отдать большую часть результата, предупредив при этом пользователя, что результат по некоторым модулям поиска еще не готов.
Какой вариант вы бы использовали? Мы используем оба этих варианта в зависимости от обстоятельств.
Наконец, все правки получены, приступаем к составлению отчета.
Здесь мы используем подход, аналогичный подготовке одной ревизии.
Вроде бы ничего сложного, но и здесь есть интересные проблемы.
У нас есть два типа заимствований.
Зелёным обозначены «Цитаты» — правильно оформленные (по ГОСТу) цитаты из модуля «Цитирование», выражения типа «что требовалось доказать» из модуля «Общеупотребительные выражения», нормативные документы из баз данных «Гарант» и «Лекспро».
Все остальные заимствования отмечены оранжевым цветом.
Зеленые имеют приоритет над оранжевыми, если только они не являются полностью частью оранжевого блока.
В результате отчет можно сравнить с текстом, напечатанным на бумаге, лежащим на столе, поверх которого начерчены разноцветные полосы (блоки заимствований и цитат), причудливо накладывающиеся друг на друга.
То, что мы видим сверху – это отчет. У нас есть две метрики для каждого источника: Поделиться в отчете — отношение объема заимствований, учитываемых из данного источника, к общему объему документа.
Если один и тот же текст обнаружен в нескольких источниках, то он учитывается только в одном из них.
При изменении конфигурации отчета (включение или отключение источников) этот индикатор источника может измениться.
Сумма дает процент заимствований и цитирований (в зависимости от цвета источника).
Поделиться в тексте - отношение объема, заимствованного из данного текстового источника, к общему объему документа.
Нет смысла суммировать доли в тексте по источникам; оно легко окажется 146% или даже больше.
Этот индикатор не меняется при изменении отчета.
Естественно, отчет можно редактировать.
Это специальная функция, чтобы эксперт, проверяющий произведение, отключал заимствование собственных произведений автора (в этом случае может обнаружиться, что данный фрагмент находится не только в собственном произведении автора, но и где-то еще) и отдельные блоки заимствований, меняет тип источника с заимствования на цитирование.
В результате редактирования отчета эксперт получает реальную стоимость заимствований.
Любую работу необходимо читать для проверки.
Это удобно сделать, просмотрев исходный вид документа, в котором отмечены блоки заимствования, и сразу редактировать отчет по мере его прочтения.
К сожалению, это вполне логичное действие совершают не все; многие довольствуются процентом оригинальности, даже не заглядывая в отчет. Однако давайте сделаем шаг назад и выясним, что входит в индекс модуля поиска в Интернете, созданного «Антиплагиатом».
Интернет-индексирование
Антиплагиат в основном ориентирован на студенческие работы, научные публикации, выпускные квалификационные работы, диссертации и т.д. Мы индексируем Интернет целенаправленно - ищем большие скопления научных текстов, рефератов, статей, диссертаций, научных журналов и т.д. Индексация происходит так:- Наш робот приходит, представляется и, руководствуясь robots.txt (робот у нас хороший), загружает документы с разумной нагрузкой на каждый хост (одновременно работают сотни сайтов, поэтому мы можем подождать некоторое время между загрузками страниц);
- Робот передает документ и его метаданные в очередь на обработку, а из документа извлекается текст;
- Текст анализируется на «качество» — как вы помните из статьи про дамп, мы умеем определять жанр документа, добавлять сюда простую эвристику по объёму и понимать, годится ли полученный нами текст или какая-то ерунда;
- Качественный текст проходит дальше и превращается в хеши.
Хэши и метаданные отправляются в основной индекс Интернета;
- Сравниваем полученный текст с ранее проиндексированными нами текстами.
Новичок добавляется только если он действительно новичок , т.е.
90% его хэшей не содержатся целиком в каком-то другом уже проиндексированном тексте.
Если у нас уже есть документ, мы добавляем URL этого документа в атрибуты нашего архива.
Рост объёма, индексируемого в Интернете, показан на рисунке ниже.
Сейчас в среднем мы добавляем в индекс 15-20 миллионов документов в месяц.
Вы заметили, что процедура удаления из индекса нигде не описана? А ее нет! Мы принципиально не удаляем документы из индекса.
Мы считаем, что если бы мы смогли что-то увидеть в Интернете, то и другие люди могли бы увидеть этот текст и так или иначе использовать его.
В связи с этим появляется интересная статистика о том, что когда-то было в Интернете, но его больше нет. Да, представьте себе, выражение «То, что попадает в Интернет, останется там навсегда» не соответствует действительности! Что-то исчезает из Интернета навсегда.
Вам интересно узнать нашу статистику по этому вопросу?
Заключение
Удивительно, как технические решения, принятые более 10 лет назад, до сих пор остаются актуальными.Мы сейчас готовимся к выпуску 4-й версии индекса, она быстрее, технологичнее, лучше, но основана на тех же решениях.
Появились новые направления поиска – переводные заимствования, перефразирование, но и там используется наш индекс, выполняющий небольшую, но важную часть работы.
Уважаемые читатели, что еще вам было бы интересно узнать о нашем сервисе? Теги: #математика #Алгоритмы #анализ данных #Поисковые технологии #Семантика #алгоритмы поиска #обработка текста #обработка текста #антиплагиат #черепица
-
Подкаст Unclesoky - Эпизод №28
19 Oct, 24 -
Что Это Вам Напоминает?
19 Oct, 24 -
Opera 9 Станет Лучшим Браузером Для Ajax
19 Oct, 24 -
#Mblt13: Мобильные Тенденции Из Японии
19 Oct, 24
