Портирование pymorphy2 на JavaScript

[Denis Olshin]

Всем привет.

Заинтересовался библиотекой (и компактным хранением словаря), но я хочу решать похожие задачи на js. Может быть, кто-нибудь в курсе аналогичных наработок на этом языке? Я пока не обнаружил даже реализации структуры DAWG/DAFSA на js, видимо придется всё это портировать самостоятельно.

Кстати, очень благодарен за подробную документацию в отношении внутреннего устройства pymorphy2. Если займусь написанием порта, возможно, буду задавать здесь вопросы. Пока что такой возник: как я понимаю, основной словарь используется только для слов, которые в него гарантированно входят — для анализа слов, отсутствующих в словаре, он не используется совсем. Не удобнее ли было бы хранить в нем слова задом наперед (<перевернутое слово><разделитель><метаинформация>), и если точного вхождения слова нет — использовать парадигмы тех слов, которые имеют наибольшее совпадающее окончание с искомым? (Собственно, я примерно такой подход сейчас использую, только не на DAWG, а на обычном trie, поэтому размер словаря оказывается неприлично велик)

[Mikhail Korobov]

Привет!

воскресенье, 10 апреля 2016 г., 21:36:34 UTC+5 пользователь Denis Olshin написал:

Всем привет.

Заинтересовался библиотекой (и компактным хранением словаря), но я хочу решать похожие задачи на js. Может быть, кто-нибудь в курсе аналогичных наработок на этом языке? Я пока не обнаружил даже реализации структуры DAWG/DAFSA на js, видимо придется всё это портировать самостоятельно.

Дело хорошее.

Я ничего не видел пока. Но, думаю, портировать должно быть несложно, т.к. можно не портировать код для построения DAFSA, а код для обхода DAFSA достаточно простой (см. https://github.com/kmike/DAWG-Python).
 

Кстати, очень благодарен за подробную документацию в отношении внутреннего устройства pymorphy2. Если займусь написанием порта, возможно, буду задавать здесь вопросы. Пока что такой возник: как я понимаю, основной словарь используется только для слов, которые в него гарантированно входят — для анализа слов, отсутствующих в словаре, он не используется совсем. Не удобнее ли было бы хранить в нем слова задом наперед (<перевернутое слово><разделитель><метаинформация>), и если точного вхождения слова нет — использовать парадигмы тех слов, которые имеют наибольшее совпадающее окончание с искомым? (Собственно, я примерно такой подход сейчас использую, только не на DAWG, а на обычном trie, поэтому размер словаря оказывается неприлично велик)

Там кроме обычного словаря строится еще подобный словарь для концов слов, это один из методов для предсказания незнакомых слов (см. http://pymorphy2.readthedocs.org/en/master/internals/prediction.html#id4).
По обычному словарю обход сейчас чуть более хитрый, чем просто поиск слова - там учитывается то, что буква ё может быть заменена на е в исходном слове.

[Denis Olshin]

воскресенье, 10 апреля 2016 г., 20:26:01 UTC+3 пользователь Mikhail Korobov написал:

Кстати, очень благодарен за подробную документацию в отношении внутреннего устройства pymorphy2. Если займусь написанием порта, возможно, буду задавать здесь вопросы. Пока что такой возник: как я понимаю, основной словарь используется только для слов, которые в него гарантированно входят — для анализа слов, отсутствующих в словаре, он не используется совсем. Не удобнее ли было бы хранить в нем слова задом наперед (<перевернутое слово><разделитель><метаинформация>), и если точного вхождения слова нет — использовать парадигмы тех слов, которые имеют наибольшее совпадающее окончание с искомым? (Собственно, я примерно такой подход сейчас использую, только не на DAWG, а на обычном trie, поэтому размер словаря оказывается неприлично велик)

Там кроме обычного словаря строится еще подобный словарь для концов слов, это один из методов для предсказания незнакомых слов (см. http://pymorphy2.readthedocs.org/en/master/internals/prediction.html#id4).
По обычному словарю обход сейчас чуть более хитрый, чем просто поиск слова - там учитывается то, что буква ё может быть заменена на е в исходном слове.

Да, я почитал об этом, но мне интересно, не получится ли избавиться от необходимости в дополнительном словаре, если в основном словаре слова будут лежать перевернутыми (правда, тогда готовый словарь от pymorphy использовать не получится, придется перегенерить). Само собой, поиск слова с конца (всего или его части) можно точно вести точно так же, с заменами ё. Но, может быть, я упускаю какой-то неочевидный нюанс, который не позволит реализовать такую стратегию?

Кстати, а откуда сейчас можно скачать уже собранные dawg-словари?

[Mikhail Korobov]

Да, интересно. Может и сработать. В aot.ru так и хранили. Я сейчас не очень помню, почему от этого отказался.

Скачать собранные словари можно с pypi: https://pypi.python.org/pypi/pymorphy2-dicts-ru/

воскресенье, 10 апреля 2016 г., 23:58:58 UTC+5 пользователь Denis Olshin написал:

[Denis Olshin]

Проверка показала, что хранить слова в обратной записи всё-таки неэффективно. DAWG плохо работает в ситуации, когда окончание слова находится с одной стороны графа, а payload (с информацией о парадигме) с другой. Словарь раздувается с 7.2 до 35.1 Мб. Так что эту идею пришлось отбросить.

Но немного получилось ужать словарь другими способами, которые, как упомянуто в документации, не очень подходят для питона, но вполне приемлемы для JS:

- Кодировка CP-1251 вместо UTF-8. В два раза меньше вершин в графе на каждую букву.

- Хранение payload без кодирования в base64. Два 16-битных индекса (номер парадигмы и словоформы в парадигме) урезаны до 14 бит и упакованы так: xxxx xxx1 xxxx xxx1 yyyy yyy1 yyyy yyy1 (т.е. у каждого байта младший бит выставлен в 1, что предотвращает появление нулевых байт).

Первый пункт уменьшает словарь на 20% (с 7.2 до 5.8 Мб), второй ещё на 7% (с 5.8 до 5.4 Мб, к тому же битовые операции кажутся проще декодирования base64). Мелочи, но для браузерного JS это всё же довольно актуально.

[Mikhail Korobov]

👍

А код где-то доступен? Это как открытый проект планируется?

четверг, 14 апреля 2016 г., 14:06:45 UTC+5 пользователь Denis Olshin написал:

[Denis Olshin]

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

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

четверг, 14 апреля 2016 г., 20:19:05 UTC+3 пользователь Mikhail Korobov написал:

[Denis Olshin]

У моей библиотеки теперь есть название — Az — и репозиторий на ГитХабе:

https://github.com/deNULL/Az.js

Документации пока нет. Есть простая демка: http://denull.github.io/Az.js

За морфологию отвечает модуль Az.Morph. А в виде модуля Az.Tokens я сделал токенизатор. Он умеет (настраиваемо) парсить не только обычный plain-text, но и HTML-, вики- и Markdown-разметку (последние две пока не очень уверенно). А ещё, например, выделяет в отдельные токены ссылки, емэйлы, хэштеги и упоминания через @.

Предсказатели для несловарных слов пока не делал. Зато я немного развил идею замен (е на ё).

Во-первых, если в слове есть повторы букв, сплошняком или разделенные дефисами (гоооол или го-о-о-ол), то в словаре найдется нормальный, сжатый до одной буквы вариант слова. Это у меня называется "заикание", stutter. Предельное число повторов можно ограничить (хотя по умолчанию стоит Infinity, т.к. в самих словах число букв конечно). 

Во-вторых, можно искать даже слова с опечатками. Сейчас, правда, из четырех видов опечаток поддерживаются три (слово «пример» найдется по запросам «притмер», «пирмер», «пнимер», но не найдется, если буква пропущена — «пимер»). При этом чтобы дополнительно сузить число вариантов, считается, что напечатать одну букву вместо другой можно только если они расположены рядом на клавиатуре. Как и «заиканиями», можно задавать предельное число опечаток на слово (но тут Infinity явно не стоит указывать). Например, я придумал «автоматический» режим — сначала ищется слово «как есть», без опечаток совсем; затем, если ничего не нашлось, и в слове хотя бы 5 букв, то с одной опечаткой; наконец, если и с одной опечаткой не нашлось вариантов, и в слове хотя бы 10 букв, то ищется с двумя допустимыми опечатками. Статистики у меня нет, но по ощущениям кажется, что при анализе текстов в сети подобный механизм может сильно пригодиться (пусть и ценой некоторого замедления разбора). Пока не знаю, как я это совмещу с предсказателями, но понятно, что по числу опечаток имеет понижать score, по которому сортируются результаты.

воскресенье, 10 апреля 2016 г., 19:36:34 UTC+3 пользователь Denis Olshin написал:

[Denis Olshin]

После некоторой паузы закончил перенос почти всех фич pymorphy2 на js: реализовал анализаторы (у меня они называются парсерами), добавил score. Поддержка исправления опечаток относительно неплохо вписалась: если слово найдено с одной опечаткой, score берется с коэффициентом 0.3, если с двумя — с коэффициентом 0.3*0.3 и т.д. Результаты выглядят достаточно правдоподобно.

У библиотеки теперь есть зачатки документации, осталось немного покрыть тестами — и можно думать о выходе первой версии :)

В планах на будущее к морфологии и токенизатору взяться за синтаксис. 

четверг, 21 апреля 2016 г., 9:29:51 UTC+3 пользователь Denis Olshin написал:

[Mikhail Korobov]

Круто! Добавил в вики: https://github.com/kmike/pymorphy2/wiki, если что-то не так написал, можно поправить.

воскресенье, 12 июня 2016 г., 7:25:48 UTC+5 пользователь Denis Olshin написал:

[kolykha...@whisla.com]

Денис здравствуйте!

Подскажите пожалуйста как привести в вашей библиотеке слово к начальной форме?. В примере фигурирует variants[i].normalize, но в возвращаемом массиве этого нет, в документации этого нет, Az.Morph в массиве этого поля нет. Буду признателен за помощь, спасибо. 

воскресенье, 12 июня 2016 г., 17:15:15 UTC+3 пользователь Mikhail Korobov написал: