Как чуден и глубок русский курлык
— Генератор постов

Обработка естественного языка (natural language processing, NLP) — тема, на мой взгляд, очень интересная. Во-первых, задачи тут чисто алгоритмические: на вход принимаем совершенно примитивный объект, строчку, а извлечь пытаемся вложенный в него смысл (ну или хотя бы частичку смысла). Во-вторых, необязательно быть профессиональным лингвистом, чтобы решать эти задачи: достаточно знать родной язык на более-менее приличном уровне и любить его.

А ещё с небольшими затратами можно сделать какого-нибудь бестолкового чат-бота — или, как вот я, генератор постов на основе того, что вы писали на своей страничке в соцсети. Возможно, кто-то из вас уже видел это приложение — оно довольно глупое, чаще всего выдает бессмысленный и бессвязный текст, но изредка всё же дает повод улыбнуться.

Бессвязность текстов в нынешней версии «Генератора» вызвана тем, что на самом деле никакого анализа он производить не умеет. Просто в одних случаях «предсказывает» продолжение предложения по собранным биграммам, а в других — заменяет в готовом предложении некоторые слова на другие, которые заканчиваются похоже. Вот и вся начинка.

Конечно, хочется сделать что-нибудь поинтереснее. Беда в том, что модные сейчас нейросети не очень-то применимы здесь: им нужно много ресурсов, большую обучающую выборку, а в браузере у пользователя соцсети всего этого нет. Поэтому я решил изучить вопрос работы с текстами с помощью алгоритмов. К сожалению, готовых инструментов для работы с русским языком на JavaScript найти не удалось, и я решил сделать свой маленький велосипед.

Az

Свою библиотеку я назвал Az. С одной стороны — это первая буква кириллицы, «азъ», и в то же время первая и последняя буквы латиницы. Сразу дам все ссылки:
— GitHub;
— Документация: либо на гитхабе же, либо на Doclets.io;
— Демо.
Установить библиотеку вы можете как из npm, так и из bower (в обоих местах она имеет название az). На свой страх и риск — она ещё не покрыта полностью тестами и до выхода первой версии (который произойдет скоро, я надеюсь) у неё могут измениться публичные API. Лицензия: MIT.

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

Az.Tokens

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

Обычно для этой цели используется что-нибудь типа одного вызова split по простой регулярке, но мне этого показалось мало. Например, если разделить строку по пробелам, мы потеряем сами пробелы — иногда это удобно, но не всегда. Ещё хуже, если мы захотим предварительно разбить строку по точкам, вопросительным и восклицательным знакам (надеясь выделить так предложения): мало того, что теряются конкретные знаки препинания, так ещё и точки на самом деле не всегда завершают предложения. А потом мы понимаем, что в реальных текстах могут встретиться, скажем, ссылки (и точки в них точно никакого отношения к пунктуации не имеют) и регулярка становится совсем страшной.

Az предлагает свое, не-деструктивное, решение этой задачи. Гарантируется, что после токенизации каждый символ будет принадлежать некоторому токену и только одному. Пробелы, переводы строк и прочие невидимые символы объединяются в один тип токенов, слова — в другой, пунктуация — в третий. Если все токены склеить вместе — получится в точности исходная строка.

При этом токенизатор достаточно умен, чтобы понимать, что дефис, обрамленный пробелами — это знак препинания (вероятно, на его месте подразумевалось тире), а прижатый хотя бы с одной стороны к слову — часть самого слова. Или что «habrahabr.ru» — это ссылка, а «mail@example.com» — это, вероятно, емэйл (да, полная поддержка соответствующего RFC не гарантируется). #hashtag — это хэштег, user — упоминание.

И наконец — раз уж RegExp'ы для этой цели использовать не стоит — Az.Tokens умеет парсить HTML (а заодно — вики и Markdown). Точнее говоря, никакой древовидной структуры на выходе не будет, но все теги будут выделены в свои токены. Для тегов <script> и <style> сделано дополнительное исключение: их содержимое превратится в один большой токен (вы же не собирались разбивать на слова свои скрипты?).

А вот и пример обработки Markdown-разметки:



Обратите внимание, скобки в одних случаях превращаются в пунктуацию (светло-синие прямоугольники), а в других — в Markdown-разметку (показана зеленым цветом).

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

Az.Morph

После того, как текст разбит на слова (с помощью Az.Tokens или любым другим образом), из них можно попытаться извлечь морфологические атрибуты — граммемы. Граммемой может быть часть речи, род или падеж — у таких граммем есть значения, которые сами по себе являются граммемами, только «булевыми» (например, мужской род, творительный падеж). «Булевые» граммемы могут и не относиться к какой-то родительской граммеме, а присутствовать сами по себе, как флаги — скажем, помета устаревшее или возвратный (глагол).

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

Каждый конкретный набор граммем у слова называется тегом. Всевозможных тегов значительно меньше, чем слов — поэтому они пронумерованы и хранятся в отдельном файле. Чтобы уметь склонять слова (а Az.Morph это тоже умеет), нужно как-то уметь менять их теги. Для этого существуют парадигмы слов: они ставят в соответствие тегам определенные префиксы и суффиксы (то есть один и тот же тег в разных парадигмах имеет разные пары префикс+суффикс). Зная парадигму слова, достаточно «откусить» от него префикс и суффикс, соответствующие текущему тегу, и добавить префикс/суффикс того тега, в который мы его хотим перевести. Как и тегов, парадигм в русском языке относительно немного — это позволяет в словаре хранить для каждого слова только пару индексов: номер парадигмы и номер тега в ней.

Вот пример: слово «крепкая» имеет тег, по-русски кратко обозначаемый как «ПРИЛ, кач жр, ед, им» — то есть это качественное прилагательное женского рода единственного числа в именительном падеже. Этому тегу (в той парадигме, которой принадлежит слово «крепкая»), соответствует пустой префикс и суффикс «-кая». Предположим, мы хотим получить из этого слова его сравнительную степень, да ещё и не обычную, а особую, с префиксом «по-»: «КОМП, кач сравн2». У неё в этой парадигме, как нетрудно догадаться, префикс «по-» и суффикс «-че». Отрезаем «-кая», добавляем «по-» и «-че» — получаем искомую форму «покрепче».

NB. Как можно заметить, под префиксами и суффиксами тут понимаются не лингвистические термины, а просто подстроки, находящиеся в начале/конце слов.

Такое вот относительно сумбурное изложение внутреннего механизма склонений в Az.Morph. По сути эта часть библиотеки — порт замечательного морфологического анализатора pymorphy2 за авторством kmike (на Хабре была пара статей об этой библиотеке). Кроме самого анализатора, рекомендую ознакомиться с его документацией — там много полезной информации, которая полностью применима и к Az тоже. Кроме того, Az использует формат словарей, аналогичный словарям pymorphy2, за исключением небольших деталей (которые позволили сделать словарь на 25% компактнее). По этой причине, увы, самостоятельно собрать их не получится — но в будущем такая возможность, конечно, появится.

Как я уже упомянул, основные словари хранятся в хитром формате DAWG (в вики есть статья о directed acyclic word graph, как об абстрактной структуре данных, но о конкретной реализации информации мало). Реализуя его поддержку в JS, я оценил фичу pymorphy2, позволяющую при поиске слова сразу проверять вариант с «ё» вместо «е» — это не дает особых потерь в производительности из-за того, что при спуске по префиксному дереву легко обойти ветви, соответствующие обеим буквам. Но мне этого показалось мало и я аналогичным образом добавил возможность нечеткого поиска слов с опечатками (то есть можно задать максимальное расстояние Дамерау-Левенштейна, на котором должно находиться искомое слово от заданного). Кроме того, можно находить «растянутые» слова — по запросам «гоооол» или «го-о-о-ол» найдется словарное «гол». Разумеется, эти особенности тоже опциональны: если вы работаете в «тепличных условиях», с грамотными, вычитанными текстами — поиск опечаток стоит запретить. А вот для написанных пользователями записей это может быть весьма актуально. В планах — заодно ловить и наиболее распространенные ошибки, не являющиеся опечатками.

Как видите, по заданному слову библиотека может вернуть разные варианты разбора из словаря. И это связано не только с опечатками: классический пример грамматической омонимии — слово «стали», которое может оказаться формой как существительного «сталь», так и глагола «стать». Чтобы решить однозначно (снять омонимию) — нужно смотреть на контекст, на соседние слова. Az.Morph этого пока не умеет (да и задача эта уже не для морфологического модуля), поэтому вернет оба варианта.

Более того: даже если в словаре не нашлось ничего подходящего, библиотека применит эвристики (называемые предсказателями или парсерами), которые смогут предположить, как слово склоняется — например, по его окончанию. Тут бы вставить весёлую историю с башорга про анализатор, считающий слово «кровать» глаголом, да одна беда — оно, конечно же, есть в словаре, и только как существительное :)

Впрочем, у меня нашлись свои курьёзы. Например, у слова «философски» среди прочих вариантов нашлись некие «филососки» (с исправленной опечаткой). Но удивительнее всего оказалось, что слово «мемас» стабильно разбирается как глагол (!), инфинитив у которого — «мемасти» (!!!). Не сразу получается понять, как такое вообще возможно — но такую же парадигму имеет, например, слово «пасти». Ну и формы типы «мемасём», «мемасёмте», «мемасённый», «мемасено», «мемасши», по-моему, прекрасны.

Несмотря на эти странности, обычно результаты оказываются довольно адекватными. Этому способствует то, что (как и в pymorphy2) каждому варианту присваивается оценка «правдоподобия» и они сортируются по убыванию этой оценки. Так что если делаете алгоритм побыстрее — можно брать первый вариант разбора, а если хочется точности — стоит перебрать все.

Производительность

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

По моим грубым замерам, конкретные цифры (в браузере Chrome) примерно таковы:

• Токенизация: 0.7–1.0 млн символов в секунду
• Морфология без опечаток: 210 слов в секунду
• Морфология с опечатками: 180 слов в секунду

Впрочем, серьёзных бенчмарков пока не проводилось. Кроме того, библиотеке недостает тестов — поэтому приглашаю погонять её на упомянутой выше демке. Надеюсь, ваша помощь приблизит релиз первой версии :)

Дальнейшие планы

Главный пункт в roadmap библиотеки — эксперименты с синтаксическим анализом. Имея варианты разбора каждого слова в предложении, можно строить более сложные гипотезы об их взаимосвязях. Насколько мне известно, в опенсорсе таких инструментов совсем немного. Тем сложнее и интереснее будет думать над этой задачей.

Кроме того, не снимается вопрос оптимизации — JS вряд ли сможет угнаться за кодом на C, но что-то улучшить наверняка можно.

Другие планы, упомянутые в статье: инструмент для самостоятельной сборки словарей, поиск слов с ошибками (т.е., скажем, чтобы для слов на «т(ь)ся» возвращался вариант и с мягким знаком, и без, а синтаксический анализатор выбирал бы правильный).

И, разумеется, я открыт вашим идеям, предложениям, багрепортам, форкам и пулреквестам.