Az.js: JavaScript-библиотека для обработки текстов на русском языке

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

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

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

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

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

Az

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

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

Az.Tokens

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

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

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

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

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

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

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

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

Az.Morph

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор: deNULL

Источник ^[18]