Привет!
Заметил этот репозиторий случайно, почитал код. Мне кажется, в MAnalyzer можно использовать DAWG лучше.
Я правильно понимаю, что в MAnalyzer DAWG используется следующим образом:
- слова (ну или их части) помещаются в DAWG;
- каждому слову в качестве значения приписывается уникальный id;
- в массиве значений по id можно посмотреть для слова какие-то данные (набор правил)?
Этот подход плох тем, что для каждого слова нужно как минимум хранить id, ну и сами данные (даже если они повторяются). Чтоб все не съедало очень много памяти, можно не сами слова помещать в DAWG, а разбивать их на стем и окончание (как делается в pymorphy) - но из-за этого замедляются выборки, т.к. нужно потом все это дело сопоставлять как-то. Особенно с учетом вырожденной "пустой" основы, для которой тысячи возможных парадигм оказывается.
Я сейчас как раз пишу https://github.com/kmike/pymorphy2 потихоньку (перепробовав много чего, тоже остановившись на dawgdic, через cython-обертку). В pymorphy2 подход другой (похожий на то, что у aot было): все слова помещаются в DAWG следующим образом:
<СЛОВО в utf8> <разделитель = chr(255)> <НОМЕР ПАРАДИГМЫ> <ИНДЕКС В ПАРАДИГМЕ>
Такой словарь для 5млн слов (это с учетом повтряющихся, имеющих > 1 варианта разбора) занимает 5M памяти.
Если нужно найти слово в словаре, с помощью Completer из dawgdic ищуются все ключи, начинающиеся с
<СЛОВО в utf8> <разделитель = chr(255)>
При этом мы получаем все возможные пары (<НОМЕР ПАРАДИГМЫ> <ИНДЕКС В ПАРАДИГМЕ>) для данного слова, а имея эти данные уже можно все что угодно получить.
utf8 используется, т.к. в питоне этот кодек на порядки быстрее cp1251. Если использовать однобайтовую кодировку, можно еще где-то 1/3 памяти сэкономить.
chr(255) выбран разделителем, т.к. этот символ по стандарту не может встретиться в utf8-строке.
С хранением <НОМЕР ПАРАДИГМЫ> <ИНДЕКС В ПАРАДИГМЕ> в самом ключе есть небольшая хитрость - Completer из dawgdic работает только с 0-terminated строками. Я сейчас просто кодирую все в base64. См. https://code.google.com/p/dawgdic/issues/detail?id=4 .
Встроенная в dawgdic поддержка хранения целочисленных значений не используются совсем. Т.к. мы храним номера парадигм и индексы в самих ключах, то эти данные DAWG тоже сжимает.
По описанной выше схеме в pymorphy2 пока получается > 200тыс слов/сек на ноуте с i5 1.8GHz (предсказателя еще нет, теггер - на голом питоне без cython-ускорения), словари на данный момент занимают 13M (там неоптимальная схема хренения парадигм в памяти + еще нет предсказателя; думаю, с нормальной схемой хранения парадигм и предсказателем тоже около того что-то получится).
Если это интересно, в pymorphy2 уже рабочий скрипт (с готовым интерфейсом командной строки) кодирования словарей из OpenCorpora (которые основаны были изначально на словарях из aot, но пару лет улучшались, переделывались и вычитывались): создаются json-файлы с "gramtab" и парадигмами + dawg со словами в формате dawgdic по описанной выше схеме (его можно загрузить и из C++). Ничего python-специфичного в сгенеренных данных нет, и, в принципе, ничего не мешает эти же данные тут использовать, чтоб работу 2 раза не делать по конвертации словаря.
В документации чуть подробнее: http://pymorphy2.readthedocs.org/en/latest/internals/dict.html (+ там еще есть описание граблей, на которые я тоже наступил - менее удачная попытка сделать примерно как описано в бумаге по mystem).
Привет!
Заметил этот репозиторий случайно, почитал код. Мне кажется, в MAnalyzer можно использовать DAWG лучше.
Я правильно понимаю, что в MAnalyzer DAWG используется следующим образом:
Этот подход плох тем, что для каждого слова нужно как минимум хранить id, ну и сами данные (даже если они повторяются). Чтоб все не съедало очень много памяти, можно не сами слова помещать в DAWG, а разбивать их на стем и окончание (как делается в pymorphy) - но из-за этого замедляются выборки, т.к. нужно потом все это дело сопоставлять как-то. Особенно с учетом вырожденной "пустой" основы, для которой тысячи возможных парадигм оказывается.
Я сейчас как раз пишу https://github.com/kmike/pymorphy2 потихоньку (перепробовав много чего, тоже остановившись на dawgdic, через cython-обертку). В pymorphy2 подход другой (похожий на то, что у aot было): все слова помещаются в DAWG следующим образом:
<СЛОВО в utf8> <разделитель = chr(255)> <НОМЕР ПАРАДИГМЫ> <ИНДЕКС В ПАРАДИГМЕ>Такой словарь для 5млн слов (это с учетом повтряющихся, имеющих > 1 варианта разбора) занимает 5M памяти.
Если нужно найти слово в словаре, с помощью Completer из dawgdic ищуются все ключи, начинающиеся с
<СЛОВО в utf8> <разделитель = chr(255)>При этом мы получаем все возможные пары (
<НОМЕР ПАРАДИГМЫ> <ИНДЕКС В ПАРАДИГМЕ>) для данного слова, а имея эти данные уже можно все что угодно получить.utf8 используется, т.к. в питоне этот кодек на порядки быстрее cp1251. Если использовать однобайтовую кодировку, можно еще где-то 1/3 памяти сэкономить.
chr(255) выбран разделителем, т.к. этот символ по стандарту не может встретиться в utf8-строке.
С хранением
<НОМЕР ПАРАДИГМЫ> <ИНДЕКС В ПАРАДИГМЕ>в самом ключе есть небольшая хитрость - Completer из dawgdic работает только с 0-terminated строками. Я сейчас просто кодирую все в base64. См. https://code.google.com/p/dawgdic/issues/detail?id=4 .Встроенная в dawgdic поддержка хранения целочисленных значений не используются совсем. Т.к. мы храним номера парадигм и индексы в самих ключах, то эти данные DAWG тоже сжимает.
По описанной выше схеме в pymorphy2 пока получается > 200тыс слов/сек на ноуте с i5 1.8GHz (предсказателя еще нет, теггер - на голом питоне без cython-ускорения), словари на данный момент занимают 13M (там неоптимальная схема хренения парадигм в памяти + еще нет предсказателя; думаю, с нормальной схемой хранения парадигм и предсказателем тоже около того что-то получится).
Если это интересно, в pymorphy2 уже рабочий скрипт (с готовым интерфейсом командной строки) кодирования словарей из OpenCorpora (которые основаны были изначально на словарях из aot, но пару лет улучшались, переделывались и вычитывались): создаются json-файлы с "gramtab" и парадигмами + dawg со словами в формате dawgdic по описанной выше схеме (его можно загрузить и из C++). Ничего python-специфичного в сгенеренных данных нет, и, в принципе, ничего не мешает эти же данные тут использовать, чтоб работу 2 раза не делать по конвертации словаря.
В документации чуть подробнее: http://pymorphy2.readthedocs.org/en/latest/internals/dict.html (+ там еще есть описание граблей, на которые я тоже наступил - менее удачная попытка сделать примерно как описано в бумаге по mystem).