Предисловие
Одно время мне везло на всякие странные работы. Например, я чуть было не устроился админом в синагогу. Остановила меня только предчувствие, что меня там как последнего гоя будут заставлять работать по субботам.
Другой вариант тоже был любопытным. Фирма сочиняла эссе и курсовые для американских студентов, которым в лом было писать самим. Уже потом я узнал, что это довольно распространенный и прибыльный бизнес, которому даже придумали собственное название — «paper mill», но сразу такой способ зарабатывания на жизнь показался мне полным сюром. Однако же надо заметить, что интересных задач на этой работе оказалось немало и среди них — самая сложная и хитрая из тех, что я делал за свою карьеру, и которой можно потом с гордостью рассказывать детям.
Формулировка ее была очень проста. Сочинители курсовых — удаленные работники, очень часто — арабы и негры, для которых английский язык был неродным, и ленивы они были ничуть не меньше самих студентов. Нередко они шли по пути наименьшего сопротивления и вместо написания оригинальной работы тупо передирали ее из Интернета, целиком или частями. Соответственно, надо было найти источник (или источники), сравнить, как-то определить процент сплагиаченности и передать собранные сведения для уличения нерадивых.
Дело несколько облегчалось языком курсовых — он был исключительно английским, без падежей и сложных флективных форм; и сильно усложнялось тем, что непонятно было, с какой стороны вообще за это дело браться.
В качестве языка реализации был выбран Перл, что оказалось очень удачным. Ни на каком статическом компилируемом языке с их ригидностью и тормознутостью запуска решить эту задачу вообще было невозможно. Переписать готовое решение можно, а придти к нему путем многочисленных проб — никак нельзя. Ну и плюс куча отличных обкатанных библиотек.
Тупики
Первоначально ковыряться в задаче поручили какому-то патлатому студенту. Тот долго не мудрствовал. Раз надо искать в Интернете, значит, понадобится поисковик. Запихаем туда весь текст, а Гугл сам найдет, откуда что взято. Потом прочитаем найденные источники и сравним их с кусками исходного текста.Разумеется, с этим ничего не получилось.
Во-первых, если отправить в Гугл весь текст целиком, то искать он будет очень плохо. В конце концов, у них там хранятся индексы, в которых количество рядом стоящих слов неизбежно ограничено.
Во-вторых, очень быстро выяснилось, что Гугл совсем не любит, когда в нем много ищут с одного и того же адреса. До этого я думал, что фраза «Тебя что, в Гугле забанили?» — это просто шутка. Оказалось, ничего подобного. Гугл после определенного количества запросов действительно банит, выводя достаточно сложную каптчу.
Ну и сама идея разбора HTML не сильно удачна — поскольку программа может упасть в любой момент, когда в Гугле решат чуть поправить верстку страницы с результатами поиска.
Студент решил зашифроваться и лазить в поисковую машину через открытые прокси: находить в интернете список и ходить через них. На деле половина этих прокси вообще не работала, а остальная половина безбожно тормозила, так что ничем хорошим процесс не заканчивался.
Ну и в-третьих, поиск кусков текста с помощью посимвольного сравнения оказался нереально медленным и совершенно непрактичным. А вдобавок еще и бесполезным — поскольку у кенийцев вполне хватало хитрости не переписывать тексты дословно, а слегка менять формулировки там и сям.
Пришлось начать с чтения специализированной литературы. Поскольку задача оказалась маргинальной, ни в одном учебнике и ни в одной солидной книге она описана не была. Все, что я нашел, была куча научных статей по частным вопросам и одна обзорная диссертация какого-то чеха. Увы, она попалась мне слишком поздно — к тому времени я и так уже знал все описанные там методы.
Отвлекаясь от темы, не могу не заметить, что почти все научные статьи, печатаемые в компетентных журналах, а) труднодоступны и б) довольно бесполезны. Те сайты, где они хранятся, и на которые выдает первые ссылки поисковик, всегда платные и весьма кусачи — обычно чуть ли не десять долларов за публикацию. Впрочем, пошарившись получше, можно, как правило, отыскать ту же самую статью и в открытом доступе. Если не удалось и это, можно попробовать написать автору, который, как правило, не отказывает в любезности выслать копию (из чего я делаю вывод, что от сложившейся системы сами авторы мало что получают, а доходы идут кому-то другому).
Впрочем, от каждой конкретной статьи практической пользы обычно немного. В них, за редким исключением, нет информации, по которой можно сесть и тут же набросать алгоритм. Там бывают или абстрактные идеи без всяких указаний, как же их реализовать; или куча математических формул, пробившись через которые понимаешь, что то же самое можно было написать в двух строчках и человеческим языком; или результаты экспериментов, проведенных авторами, с неизменным комментарием: «ясно далеко не все, нужно продолжать дальше». Не знаю, то ли эти статьи пишутся для галочки или, вернее, для каких-то внутринаучных ритуалов, то ли жаба давит делиться реальными наработками, которые вполне успешно можно использовать в собственном стартапе. В любом случае, эрозия науки налицо.
Кстати сказать, самый большой и известный сайт для поиска плагиата называется Turnitin. Это практический монополист в этой области. Внутренняя его работа засекречена не хуже, чем военная база, — я не нашел ни одной статьи, даже коротенькой заметки, повествующей хоть в самом общем виде о том, какие алгоритмы там применяются. Сплошная загадка.
Впрочем, от лирики вернемся снова к тупикам, на этот раз уже к моим собственным.
Не оправдала себя идея с отпечатками документов (document fingerprinting). В теории выглядело неплохо — по каждому документу, выкачанному из Интернета, считается его отпечаток — какое-то длинное число, как-то отражающее содержимое. Предполагалось, что будет заведена база, в которой вместо самих документов будут храниться url и отпечатки, и тогда будет достаточно сравнить исходный текст с базой отпечатков, чтобы сразу найти подозреваемых. Это не работает — чем отпечатки короче, тем сравнение хуже, а когда они достигают уже половины длины источника, то хранить их становится бессмысленным. Плюс изменения, которые устраивают авторы, чтобы обмануть распознавание. Ну и плюс огромный объем интернета — хранение даже самых коротких отпечатков очень быстро становится обременительным из-за гигантского размера данных.
Разбор и нормализация
Этот этап поначалу кажется банальным и неинтересным — ну понятно, что на входе явно будет текст в формат MS Word, а отнюдь не текстовый файл; его надо разобрать, разбить на предложения и на слова. На самом деле тут кроется огромный источник улучшения качества проверки, который далеко опережает любые хитрые алгоритмы. Это как с распознаванием книжек — если оригинал криво отсканирован и заляпан чернилами, то никакие последующие ухищрения это уже не исправят.Кстати сказать, и разбор, и нормализация требуются не только для исходного текста, но и для всех ссылок, найденных в Интернете, так что помимо качества тут требуется еще и скорость.
Итак, к нам попал документ в одном из распространенных форматов. Большинство из них разобрать легко — например, HTML отлично читается с помощью HTML::Parser, всякие PDF и PS можно обработать, вызвав внешнюю программу типа pstotext. Разбор документов OpenOffice — просто удовольствие, можно даже прикрутить XSLT, если вы наслаждаетесь извращениями. Общую картину портит только гадский Word — более ублюдочный формат текста найти невозможно: адски сложный в разборе и лишенный всякой структуры внутри. За подробностями отсылаю к своей предыдущей статье. Была бы моя воля, я бы его вообще никогда не разбирал, но он распространен гораздо больше всех остальных форматов, вместе взятых. То ли это закон Грешэма в действии, то ли происки мирового зла. Если Бог всеблаг, то почему все пишут в формате Ворда?
В процессе разбора, если попался нормальный формат, из текста можно узнать всякие полезные вещи: например, найти оглавление документа и исключить его из процесса сравнения (там все равно ничего полезного нет). То же самое можно проделать с таблицами (коротенькие строчечки в ячейках таблицы дают много ложных срабатываний). Можно вычислить заголовки глав, выкинуть картинки, пометить интернет-адреса. Для веб-страниц имеет смысл исключить боковые колонки и колонтитулы, если они отмечены в файле (html5 это позволяет).
Да, кстати, еще ведь могут быть архивы, которые надо распаковать и достать оттуда каждый файл. Главное, не спутать архив с каким-нибудь сложным запакованным форматом типа OOXML.
Получив просто текст, мы можем поработать над ним еще. Только на пользу пойдет выкидывание титульной страницы и служебной информации, которую университеты требуют в обязательном порядке («Работа студента такого-то», «проверил профессор Сякой Т.О.»). Заодно можно расправиться со списком литературы. Найти его не так-то просто, ибо названий у него не меньше дюжины («References»,«List of reference»,«Works Cited»,«Bibliography» и так далее). Впрочем, он может вообще быть никак не подписан. Его лучше всего из текста просто выкинуть, потому что список очень мешает распознаванию, создавая при этом немалую нагрузку.
Полученный текст надо нормализовать, то есть облагородить, придав ему унифицированную форму. Первым делом надо найти все кириллические и греческие буквы, по написанию похожие на соответствующие английские. Хитроумные авторы специально вставляют их в текст, чтобы обмануть проверку на плагиат. Но не тут-то было: подобный фокус — это стопроцентная улика и повод гнать такого автора в шею.
Потом все простонародные сокращенные формы типа can't заменяются на полные.
Теперь надо поменять все высокохудожественные уникодовские символы на простые — кавычки елочкой, кавычки в виде перевернутых запятых, длинные и полудлинные тире, апострофы, троеточия а также лигатуры ff, ffi,st и всякое такое. Заменить два апострофа подряд на нормальные кавычки (почему-то такое попадается очень часто), а два тире — на одно. Все последовательности пробельных символов (а их тоже куча) заменить на один обычный пробел. Вышвырнуть после этого из текста, все что не укладывается в диапазон символов ASCII. И напоследок убрать все управляющие символы, кроме обычного перевода строки.
Вот теперь текст готов к сравнению.
Дальше разбиваем его на предложения. Это не так-то просто, как кажется с первого взгляда. В сфере обработки естественного языка вообще всё кажется легким только поначалу и со стороны. Предложения могут заканчиваться точкой, троеточием, восклицательным и вопросительным знаком или вообще никак не заканчиваться (в конце абзаца).
Плюс точки могут стоять после всяких сокращений, который совсем не являются концом предложения. Полный список занимает полстраницы — Dr. Mr. Mrs. Ms. Inc. vol. et.al. pp. и так далее, и тому подобное. И плюс интернет-ссылки: хорошо, когда в их начале стоит протокол, но есть он там далеко не всегда. Например, статья может вообще рассказывать про разные сетевые магазины и постоянно упоминать Amazon.com. Так что еще нужно знать все домены — десяток основных и двести штук доменов по странам.
И заодно терять точность, поскольку весь процесс теперь становится вероятностным. Каждая конкретная точка может быть, а может и не быть концом предложения.
Первоначальная версия разбиения текста на предложения была написана в лоб — с помощью регулярных выражений находились все неправильные точки, заменялись на другие символы, текст бился на предложения по оставшимся, потом символы точек возвращались назад.
Затем мне стало стыдно, что я не использую передовые методы, разработанные современной наукой, так что я начал изучать другие варианты. Нашел фрагмент на Яве, разобрал за пару геологических эпох (ох и скучный же, монотонный и многословный язык). Нашел питоновский NLTK. Но больше всего мне понравилась работа некоего Дэна Гиллика (Dan Gillick, «Improved Sentence Boundary Detection»), в которой он хвастался, что его метод наголову превосходит все остальные. Метод строился на байесовских вероятностях и требовал предварительного обучения. На тех текстах, по которым я его натаскивал, он был превосходен, а на остальных… Ну не то, чтобы очень плох, но и не намного лучше той самой стыдной версии со списком аббревиатур. К ней я в конце концов и вернулся.
Поиск в Интернете
Итак, теперь мы имеем текст и надо заставить Гугл поработать за нас, поискать куски, разбросанные по всему Интернету. Разумеется, обычным поиском пользоваться нельзя, а как надо? Конечно, же с помощью Google API. Вcего-то делов. Условия там куда либеральнее, удобный и стабильный интерфейс для программ, никаких разборов HTML. Количество запросов в сутки хоть и ограничено, но на деле Гугл его не проверял. Если не наглеть, конечно, посылая запросы миллионами.Теперь другой вопрос — какими кусками слать текст. Гугл хранит некоторую информацию о расстоянии между словами. Опытным путем было выяснено, что оптимальные результаты дает серия из 8 слов. Конечный алгоритм был такой:
- Разбиваем текст на слова
- Выкидываем так называемые стоп-слова (служебные, попадающиеся чаще всего — a, on и так далее. Я пользовался списком, взятым из mysql)
- Формируем запросы из восьми слов с перекрытием (то есть, первый запрос — слова 1-8, второй 2-9 и так далее. Можно даже с перекрытием в два слова, это экономит запросы, но немного ухудшает качество)
- Если текст большой (>40kb), то можно выкинуть каждый третий запрос, а если очень большой (>200 kb), то даже каждый второй. Это вредит поиску, но не так уж сильно, очевидно, потому что плагиаторы обычно прут целыми абзацами, а не отдельными фразами
- Дальше посылаем все запросы на Гугл, даже одновременно.
- И, наконец, получаем ответы, разбираем, делаем общий список и выкидываем из него дубликаты. Еще можно отсортировать список полученных адресов по количеству пришедших дубликатов и отрезать последние, считая их не показательными и на что особо не влияющими. К сожалению, тут мы встречаемся с так называемым распределением Ципфа, которое при поиске плагиата глядит из каждого угла. Это такая экспонента вверх ногами с очень длинным и унылым хвостом, тянущимся в бесконечность. Полностью хвост обработать невозможно, а где резать — непонятно. Где бы ты ни отчекрыжил, качество ухудшится. Вот и со списком адресов так. Поэтому я резал его, исходя из эмпирической формулы, зависящей от длины текста. Это, во всяком случае, гарантировало какое-то стабильное время обработки как функцию числа букв
Алгоритм отлично работал, пока Гугл не спохватился и не прикрыл лафу. API остался, даже улучшился, но фирма стала хотеть за него деньги, и довольно немаленькие — 4 доллара за 1000 запросов. Пришлось смотреть альтернативы, коих было ровно две — Бинг и Яху. Бинг был бесплатным, но на этом его достоинства и заканчивались. Искал он заметно хуже Гугла. Может, последний — и новая корпорация Зла, но их поисковик по-прежнему лучший в мире. Впрочем, Бинг искал даже хуже самого себя — через API он находил в полтора раза меньше ссылок, чем из пользовательского интерфейса. Еще он имел отвратительную привычку часть запросов заканчивать с ошибкой и их приходилось повторять заново. Очевидно, таким образом в Майкрософте регулировали поток обращений. Кроме того, количество слов в строке поиска пришлось уменьшить до пяти, стоп-слова оставлять, перекрытие делать только в одно слово.
Яху находился где-то посередине между Гуглом и Бингом — и по цене, и по качеству поиска.
В процессе возникла еще одна идейка. Начальник отдела обнаружил проект, который каждые сутки собирал содержимое всего Интернета и складывал где-то на Амазоне. Нам оставалось только взять оттуда данные и проиндексировать в своей полнотекстовой базе, а потом в ней искать что надо. Ну фактически написать свой собственный Гугл, только без паука. Это было, как вы догадываетесь, совершенно нереально.
Поиск в локальной базе
Одной из сильных сторон Turnitin служит его популярность. Туда шлют множество работ: студенты — свои, преподаватели — студенческие, и их база поиска всё время увеличивается. В результате они могут находить краденое не только из интернета, но и из прошлогодней курсовой.
Мы пошли по тому же пути и сделали еще локальную базу — с готовыми заказами, а также с материалами, которые пользователи прикладывали к своим заявкам («Вот статья, по теме которой надо написать эссе»). Писатели, как выяснилось, очень любят переписывать свои же предыдущие работы.
Все это добро лежало в полнотекстовой базе KinoSearch (сейчас переименован в Люси). Индексатор работал на отдельной машине. Кинопоиск показал себя хорошо — хотя счет документам шел на сотни тысяч, искал быстро и тщательно. Единственный недостаток — при добавлении полей в индекс или смене версии библиотеки приходилось переиндексировать всё заново, что длилось несколько недель.
Сравнение
Ну теперь самое ядреное — без которого все остальное никому не нужно. Проверок нам нужно две — сначала сравнить два текста и определить, что в одном есть куски из другого. Если таких кусков нет, то дальше можно не продолжать и сэкономить вычислительные мощности. А если есть, тогда в дело вступает более сложный и тяжелый алгоритм, который ищет похожие предложения.Первоначально для сравнения документов использовался алгоритм шинглов — кусков нормализованного текста с перекрытиями. По каждому куску считается некая контрольная сумма, которая потом используется для сравнения. Алгоритм был реализован и даже работал в первой версии, но оказался хуже алгоритма поиска в векторных пространствах. Впрочем, сама идея шинглов неожиданно пригодилась при поиске, но об этом я уже писал.
Итак, считаем некий коэффициент совпадения между документами. Алгоритм будет тот же, что и в поисковых машинах. Я изложу его по-простому, по-колхозному, а научное описание можно найти в научной же книжке (Маннинг К., Рагхаван П., Шютце Х. Введение в информационный поиск. — Вильямс, 2011). Надеюсь ничего не перепутать, а это вполне возможно — тут самая сложная часть системы, да еще и постоянно менявшаяся.
Итак, берем все слова из обоих статей, выделяем основу слова, выкидываем дубли и строим гигантскую матрицу. В колонках у нее будут те самые основы, а строк всего две — первый текст и второй текст. На пересечении ставим цифру — сколько раз конкретное слово встретилось в данном тексте.
Модель достаточно простая, называется она «мешком слов», потому что никак не учитывает порядок слов в тексте. Но для нас она — самое то, потому что плагиаторы при переделке текста очень часто меняют слова местами, переформулируя списываемое.
Выделение основ слова на лингвистическом жаргоне называется стеммингом. Я проводил его с помощью библиотеки Snowball — быстро и никаких проблем. Стемминг нужен для улучшения распознания плагиата — потому что ушлые авторы не просто переписывают чужой текст, а косметически его меняют, нередко превращая одну часть речи в другую.
Итак, мы получили некоторую матрицу из основ, которая описывает огромное многовекторное пространство. Теперь мы считаем, что наши тексты — это два вектора в этом пространстве, и считаем косинус угла между ними (через скалярное произведение). Это и будет мера сходства между текстами.
Просто, изящно и в большинстве случаев верно. Плохо работает только, если один текст намного больше другого.
Опытным путем было найдено, что тексты с коэффициентом сходства <0.4 можно не рассматривать. Впрочем, потом, после жалоб службы поддержки о не найденных паре-тройки сплагиаченных предложений, порог пришлось понизить до 0.2, что сделало его достаточно бесполезным (и тут проклятый Ципф).
Ну и пару слов о реализации. Поскольку сравнивать все время приходится один и тот же текст, то есть смысл заранее получить список его основ и количество их вхождений. Таким образом, четверть матрицы уже будет готова.
Для перемножения векторов я сначала использовал PDL (а что еще?), но потом, в погоне за скоростью, заметил, что вектора получаются жутко разрежённые, и написал собственную реализацию на базе перловских хэшей.
Теперь нам нужно найти коэффициент сходства между предложениями. Тут есть два варианта и оба представляют собой вариации на все ту же тему векторного пространства.
Можно поступить совсем просто — взять слова из обоих предложений, составить векторное пространство из них и посчитать угол. Единственное — не нужно даже пытаться учитывать количество вхождений каждого слова — все равно слова в одном предложении повторяются очень редко.
Но можно сделать и хитрее — применить классический алгоритм tf/idf из книжки, только вместо коллекции документов у нас будет коллекция предложений из обоих текстов, а вместо документов — соответственно, предложения. Берем общее векторное пространство для обоих текстов, (уже полученное, когда мы вычисляли сходство между двумя текстами), строим векторы, в векторах заменяем количество вхождений на ln(вхождения/к-во предложений). Тогда результат будет получше — не радикально, но заметно.
Если порог сходства между двумя предложениями превышает определенную величину, то записываем найденные предложения в базу, чтобы потом тыкать сходством плагиаторов.
И еще — если в предложении всего одно слово, то мы его даже ни с чем не сравниваем — бесполезно, алгоритм на таких огрызках не работает.
Если коэффициент сходства больше 0.6 — тут к гадалке не ходи, это перефразированная копия. Если меньше 0.4 — сходство случайное или вообще его нет. А вот в промежутке образуется серая зона — это может быть и плагиат, и просто совпадение, когда на взгляд человека в текстах нет ничего общего.
Тогда в игру вступает еще один алгоритм, который я почерпнул из хорошей статьи (Yuhua Li, Zuhair Bandar, David McLean and James O’Shea. «A Method for Measuring Sentence Similarity and its Application to Conversational Agents»). Тут уже в дело идет тяжелая артиллерия — лингвистические признаки. Алгоритм требует учесть неправильные формы спряжения, отношения между словами вроде синонимии или гиперонимии, а также редкость слова. Для всего этого добра требуется соответствующая информация в машинно-читаемом виде. К счастью, добрые люди из Принстонского университета давно уже занимаются специальной лексической базой для английского языка, называющейся Wordnet. На CPAN есть и готовый модуль для чтения. Единственное, что я сделал, — переложил информацию из текстовых файлов, в которых она хранится в Принстоне, в таблицы MySQL, ну и соответственно переписал модуль. Чтение из кучи текстовых файлов ни удобством, ни скоростью не отличается, а хранение ссылок в виде смещений в файле не назовешь особенно элегантным.
Вторая версия
Хм… Вторая. А где же первая? Ну про первую рассказывать нечего. Она брала текст и последовательно выполняла все шаги алгоритма — нормализовала, искала, сравнивала и выдавала результат. Соответственно, ничего параллельно делать не могла и была медленной.
Так что вся остальная работа после первой версии была направлена на одно и то же — быстрее, быстрее, быстрее.
Поскольку основное время работы уходит на получение ссылок и стягивание информации из Интернета, то доступ к сети — первый кандидат на оптимизацию. Последовательный доступ был заменен на параллельное скачивание (LWP на асинхронный Curl). Скорость работы, разумеется, выросла фантастически. Радость не смогли испортить даже глюки в модуле, когда он получал 100 запросов, выполнял 99 и неопределенно долго висел на последнем.
Общая архитектура новой системы была сочинена по образцу ОС. Есть управляющий модуль, который запускает дочерние процессы, выделяя им по «кванту» времени (5 минут). За это время процесс должен прочитать из базы, на чем там остановились прошлый раз, выполнить следующее действие, записать в базу информацию по продолжению и завершиться. За 5 минут можно сделать любую операцию, кроме скачивания и сравнения ссылок, поэтому это действие разбивалось на части — 100 или 200 ссылок за раз. Через пять минут диспетчер прервет исполнение по-любому. Не успел? Попробуешь в следующий раз.
Впрочем, сам рабочий процесс тоже должен следить по таймеру за своим выполнением, потому что всегда есть риск нарваться на какой-нибудь сайт, который подвесит всё (например, на одном таком сайте перечислялись 100000 слов английского языка — и больше ничего там не было. Понятно, что описанные выше алгоритмы будут искать сходство трое суток и, может быть, даже когда-нибудь найдут).
Количество рабочих процессов можно было менять, в теории — даже динамически. На практике три процесса были оптимальны.
Ну, ясно, что еще была база данных MySQL, в которой хранятся тексты для обработки и промежуточные данные, а заодно и окончательные результаты. И веб-интерфейс, на котором пользователи могли посмотреть, что там в данный момент обрабатывается, и на какой оно стадии.
Задачам определялся приоритет, чтобы более важные выполнялись быстрее. Приоритет считался как некоторая функция от размера файла (чем больше, тем медленнее он обрабатывается) и срока сдачи работы (чем он ближе, тем быстрее нужны результаты). Диспетчер выбирал следующую задачу по самому большому приоритету, но с некоторой случайной поправкой — иначе низкоприоритетные задачи вообще не дождались бы своей очереди, пока есть более высокоприоритетные.
Третья версия
Третья версия была продуктом эволюционного развития с точки зрения алгоритмов обработки, и революцией в архитектуре. Помнится, торчал я как-то на холоде, перед неудачным свиданием, в ожидании Годо, и вспоминал читанный недавно рассказ о сервисах Амазона. И файлы они хранят, и машины виртуальные делают, и даже есть у них всякие непонятные службы из трех букв. Тут-то меня и осенило. Вспомнил я гигантскую креветку, виденную как-то в севастопольском аквариуме. Стоит она посреди камней, машет лапками и фильтрует воду. Несет течение к ней всякие вкусные кусочки, а она их отбирает, воду выплевывает дальше. А если поставить много таких креветок в ряд, так они же все там профильтруют за двадцать минут. А если еще эти ракообразные и разного вида будут, вылавливать каждое своё, так вообще — какие перспективы открываются.Переводя с образного языка на технический. У Амазона есть служба очередей SQS — такие непрерывные конвейеры, по которым идут данные. Делаем несколько программ, которые выполняют только одно действие — никаких переключений контекстов, порождений дочерних процессов и прочих накладных расходов. «Кран с утра до вечера наполняет водой одни и те же ведра. Газовая Плита подогревает одни и те же кастрюли, чайники и сковородки».
Реализация оказалась простой и красивой. Каждый описанный выше шаг алгоритма — отдельная программа. Под каждую есть собственная очередь. В очередях ходят сообщения XML, где написано, что и как надо сделать. Есть еще одна очередь управления и отдельная программа-диспетчер, которая следит за порядком, обновляет данные о ходе работ, уведомляет пользователя о случившихся проблемах. Отдельные программы могут слать ответ диспетчеру, а могут напрямую и в следующую очередь — как удобно. Если произошла ошибка — то отсылают сообщение об этому диспетчеру, а он уж разбирается.
Автоматически получается исправление ошибок. Если программа не справилась с заданием и, допустим, упала, то она будет перезапущена, а невыполненная задача остается в очереди и всплывет через какое-то время вновь. Ничего не потерялось.
Единственная сложность с Амазоном — служба очередей гарантирует, что каждое сообщение будет доставлено минимум один раз. То есть, доставлено оно по-любому будет, но не факт, что однажды. К этому надо быть готовым и писать процессы так, чтобы они подобающим образом реагировали на дубли — или не обрабатывали их (что не очень удобно, потому что надо вести какой-то учет), или же обрабатывали идемпотентно.
Скачанные из Интернета файлы, естественно, в сообщениях не пересылались — и неудобно, и в SQS есть ограничение на размер. Вместо этого они складывались на S3, а в сообщениях отсылалась только ссылка. Диспетчер после завершения задачи все эти временные хранилища вычищал.
Промежуточные данные (например, сколько ссылок нам надо прочитать и сколько уже сделано) хранились в Amazon Simple Data Storage — простой, но распределенной базе данных. У SDS тоже были ограничения, которые стоило учитывать. Например, она не гарантировала мгновенного обновления.
Ну и, наконец, готовые результаты — тексты с указанием плагиата, я стал складывать не в базу MySQL, а в CouchDB. Все равно в реляционной базе они хранились нереляционно — в текстовых полях в формате Data::Dumper (это перловский аналог JSONа). CouchDB был всем хорош, как царица Савская, но имел один недостаток, зато фатальный. К его базе невозможно обратиться с произвольным запросом — для любого запроса должны быть заранее построены индексы, то есть их надо предугадать заранее. Если хрустального шара нет, то надо начинать процесс индексирования — а для большой базы он длится несколько часов (!) и при этом все остальные запросы не выполняются. Сейчас бы я использовал MongoDB — там есть фоновое индексирование.
У получившейся схемы было огромное преимущество перед старой — она естественно масштабировалась. Действительно, никаких локальных данных у нее нет, все распределено (кроме базы результатов), все экземпляры рабочих процессов совершенно однотипны. Их можно сгруппировать по тяжести — на одной машине запускать все легкие, требующие мало ресурсов, а тормозным вроде процесса сравнения текстов выделить отдельный виртуальный сервер. Мало? Не тянет? Можно еще один. Не справляется еще какой-нибудь процесс? Вынесем и его на отдельную машину. В принципе, это даже можно делать автоматически — видим, что в одной из очередей скопилось слишком много необработанных сообщений, поднимаем еще один сервер EC2.
Впрочем, суровая тетка Жизнь, как водится, внесла в эту идиллию свои коррективы. С технической стороны архитектура была идеальна, а вот с экономической выяснилось, что использование SDS (да и S3) оказывается совсем невыгодным. Обходится очень уж дорого, особенно база.
Пришлось спешно выносить промежуточные данные в старый добрый MySQL, а скачанные документы складывать на жестком диске, расшаренном по NFS. Ну и заодно забыть о беспроблемном масштабировании.
Нереализованные планы
Изучая обработку естественного языка, в частности, по исчерпывающей книге Мэннинга, я никак не мог отделаться от мысли, что все описанные там методы — просто уловки ad hoc, фокусы под конкретную задачу, совершенно не обобщаемые. Лем еще в 2001 году уедал информатику, так и не придумавшую за сорок лет искусственный интеллект, хотя трещали на эту тему много. Тогда же он мрачно предсказывал, что положение в обозримом будущем не изменится. Машина как не понимала смысла, так понимать и не будет. Философ оказался прав.Точно такой же уловкой был и поиск плагиата. Ну породить ИИ и ждать человеческого осмысления текста я не надеялся, не так уж я наивен, но долго бродила в голове мысль приделать синтаксический анализ, чтобы хотя бы распознавать одинаковые по смыслу предложения, только стоящие в разных залогах (активном и страдательном). Однако все парсеры естественного языка, которые я находил, были крайне сложными, вероятностными, давали результаты в непонятной форме и требовали огромных вычислительных ресурсов. В общем, думаю, что на нынешней стадии развития наук это нереально.
Человеческий фактор
Система писалась так, чтобы работать в полностью автоматическом режиме, так что тут люди ничем подкузьмить не могли. Кроме того, со мной в паре трудился очень хороший сисадмин, благодаря которому все сервера настроены были отлично, а простои разного рода сводились к минимуму. Но оставались ведь еще и пользователи — служба поддержки. Ну и начальство, конечно же.И те, и другие долгое время были убеждены, что поиском плагиата занимается не компьютер, а маленький человечек (или даже целая толпа), который сидит внутри компьютера. Он почти как настоящий, в частности, отлично понимает все, о чем пишется в курсовых на любую тему, а плагиат находит потому, что держит в голове все содержимое Интернета. Впрочем, когда эти человечки лажали, спрашивали, вопреки всякой логике, почему-то не с них, а с меня. Одно слово — филологи.
Мне стоило больших трудов объяснить, что плагиат ищет все-таки компьютер, который совершенно не понимает того, что делает. Где-то через год до начальства это дошло, до остальных, кажется, не до конца.
Была у саппорта еще и другая мода — ввести несколько предложений в Гугл и радостно мне сообщать, что Гугл плагиат нашел, а моя система — нет. Ну что я мог на это сказать? Объяснять про распределение Ципфа, рассказать, что ради скорости и уменьшения объема памяти пришлось идти на компромиссы, а каждый такой компромисс означал ухудшение качества? Безнадежно. К счастью, в большинстве таких случаев оказывалось, что Гугл нашел материал на каком-нибудь платном сайте, к которому доступу у системы просто не было.
Еще была фишка — доложить, что Turnitin обнаружил плагиат, а наша система не обнаружила. И тут нереально было объяснить, что Turnitin, скорее всего, пишет целая команда квалифицированных специалистов с дипломами в соответствующей области, а сам сайт имеет интимные отношения с каким-то крутым поисковиком. Опять-таки, к счастью, большинство не обнаруженных случаев плагиата были с платных сайтов или из других студенческих работ, в общем, для нас никак недоступны.
Несколько месяцев я пытался удовлетворить требование директора о фиксированном времени обработки — каждая работа не должна проверяться более часа. У меня это никак не получалось, я не спал ночами, пока однажды мне не подсказали, что, в сущности, от меня хотят изобрести вечный двигатель — такой, мощность которого будет расти при увеличении нагрузки. В жизни таких не бывает, в мире программ — тоже. Когда требование было переформулировано — каждая работа не более определенного объема (50 страниц) должна искаться не более часа, если в это время в очереди нет огромных диссертаций — дело пошло на лад. Условия были жесткими, но хотя бы в принципе реализуемыми.
Временами радовала служба поддержки. Объяснить их логику я затрудняюсь, но периодически, при сильной загрузке очереди проверки они… запихивали в нее дополнительные копии работ. Ну то есть, если в пробке стоит сто автомобилей, то надо на дорогу пригнать еще сто, и тогда дело пойдет на лад. Объяснить им ошибку я так и не смог, и такие дела были запрещены чисто административно.
Напутствие комментаторам
Мой печальный опыт показывает, что на Хабре есть некоторое количество малолеток, по непонятным причинам считающим, что они сразу от рождения превосходно разбираются во всех отраслях знания, придуманных человечеством. Прямо по Чехову — «она у меня эмансипе, все у нее дураки, одна она умная». Если вы принадлежите к таким товарищам и решите написать мне, что я идиот, ничего не разумею, не понимаю простых вещей и т.п., то прошу помнить, что разработанная мной система эксплуатировалась в хвост и в гриву два года, 24 часа в сутки, почти без простоев, и сэкономила заказчику несколько мешков денег. Поэтому при сочинении комментариев описанного выше типа прошу сразу указывать аналогичные характеристики системы, разработанной вами. Ну чтобы ваша гениальность была заметна сразу, без наводящих вопросов.
