Разбор естественного языка: под капотом

[Mopper]

В качестве языка реализации я выбрал Go, поскольку хотел малой ценой получить параллельный (в смысле, использующий все доступные ядра CPU)

Ну и на сколько быстрее стало работать из того что вы используете «Параллельность» GO?

[ababo]

Примерно в 2.5 раза на 4-ядерном процессоре.

[Mopper]

Как мне кажется Вы немножко лукавите насчето прироста скорости.
Посмотрел ваш репозиторий там нигде нет вызова
https://github.com/ababo/idiot/search?utf8=%E2%9C%93&q=GOMAXPROCS
Без его вызова у вас по умолчанию только один поток используется, несмотря на то что goroutин много.

http://stackoverflow.com/questions/17853831/what-is-the-gomaxprocs-default-value.

Вообще я так понимаю go придумали не столько как инструмент параллельной обработки данных сколько как инструмент «одновременной работы».

http://blog.golang.org/concurrency-is-not-parallelism
Я просто сам с этим столкнулся. у меня без этого вызова все в одном потоке крутилось.

[ababo]

Ничего я не лукавлю. С установкой GOMAXPROCS=4 скорость анализа возрастает где-то в 2.5 раза.

[neolink]

по умолчанию используется значение из одноименной переменной окружения

[excoder]

Почему бы не использовать одну из разновидностей минимального автомата? Например, как здесь: habrahabr.ru/post/190694.

[ababo]

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

[kmike]

А какой алгоритм парсинга используется, какие грамматики поддерживаются — LL(?), LR(?), любые контекстно-свободные, ...? Есть ли какие-то «хорошие» ограничения на сложность разбора — например, O(N) для некоторых однозначных и не больше чем O(N^3) для любых (хотя из-за атрибутов это может быть сложно..)? Можно ли парсить «снизу вверх», а не «сверху вниз», не требуя обязательного сопоставления стартовому символу, извлекая все поддеревья за один проход?

Ну и интересно, какая скорость морф. анализа по словарю получилась :)

Насчет упаковки данных в автомат есть простой способ — автомат строить библиотекой code.google.com/p/dawgdic (для кого-то может быть проще использовать питонью обертку github.com/kmike/DAWG), а потом написать читалку для полученного формата на Go. Там алгоритм построения автомата сложный, а вот сама читалка — довольно простая, портировать на Go должно быть нетрудно.

[ababo]

А какой алгоритм парсинга используется

Об этом сказано в статье.

Разбор нисходящий, грамматика контекстно-свободная (BNF-подобная). На счёт сложности не готов ответить. Сложность морфологического поиска Log2(n), где n — число словоформ (где-то 5 миллионов), но в относительных величинах, думаю, отстаёт от решений, написанных на C/C++. Количественно, увы, не помню (можете скачать и замерить :)). Я морфологию почти не оптимизировал, писал почти «в лоб». Скорость синтаксического разбора для сложных предложений — где-то порядка 0.1-0.2 секунды, для простых — в несколько раз быстрее.

[ababo]

Ради интереса измерил скорость морфологического поиска. Получилось чуть больше 200.000/сек. (если, конечно, где-то не ошибся). Учитывая, что у меня морфологический поиск несколько более продвинутый — он ищет множество словоформ по заданному префиксу и разделителю, а также совершенно не оптимизированный, то результат, кажется, совсем не плохой.

[Aracon]

Тут жена-филолог подсказывает (к списку правил грамматики) почитать про «структурные схемы синтаксиса русского языка». В частности, посмотреть «Российская грамматика 70, 80» (1970 и 1980 года издания, они так и называются), работы Белошапковой, Богданова, Золотова, Шмелёва, где примерно в 15 типов структурных схем укладывается все многообразие предложений русского языка. Возможно, поможет обойти часть велосипедов.

[ababo]

Спасибо, обязательно гляну.

[ababo]

А не дадите ссылочку?

[Aracon]

Насколько я понял, конкретных ссылок под рукой нет, так что Гугл по фамилиям и словосочетаниям в кавычках. На всякий случай напомню, что для поиска научных работ эффективнее использовать scholar.google.com