Comments 14
В качестве языка реализации я выбрал Go, поскольку хотел малой ценой получить параллельный (в смысле, использующий все доступные ядра CPU)
Ну и на сколько быстрее стало работать из того что вы используете «Параллельность» GO?
Примерно в 2.5 раза на 4-ядерном процессоре.
Как мне кажется Вы немножко лукавите насчето прироста скорости.
Посмотрел ваш репозиторий там нигде нет вызова
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
Я просто сам с этим столкнулся. у меня без этого вызова все в одном потоке крутилось.
Посмотрел ваш репозиторий там нигде нет вызова
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
Я просто сам с этим столкнулся. у меня без этого вызова все в одном потоке крутилось.
Почему бы не использовать одну из разновидностей минимального автомата? Например, как здесь: habrahabr.ru/post/190694.
А какой алгоритм парсинга используется, какие грамматики поддерживаются — LL(?), LR(?), любые контекстно-свободные, ...? Есть ли какие-то «хорошие» ограничения на сложность разбора — например, O(N) для некоторых однозначных и не больше чем O(N^3) для любых (хотя из-за атрибутов это может быть сложно..)? Можно ли парсить «снизу вверх», а не «сверху вниз», не требуя обязательного сопоставления стартовому символу, извлекая все поддеревья за один проход?
Ну и интересно, какая скорость морф. анализа по словарю получилась :)
Насчет упаковки данных в автомат есть простой способ — автомат строить библиотекой code.google.com/p/dawgdic (для кого-то может быть проще использовать питонью обертку github.com/kmike/DAWG), а потом написать читалку для полученного формата на Go. Там алгоритм построения автомата сложный, а вот сама читалка — довольно простая, портировать на Go должно быть нетрудно.
Ну и интересно, какая скорость морф. анализа по словарю получилась :)
Насчет упаковки данных в автомат есть простой способ — автомат строить библиотекой code.google.com/p/dawgdic (для кого-то может быть проще использовать питонью обертку github.com/kmike/DAWG), а потом написать читалку для полученного формата на Go. Там алгоритм построения автомата сложный, а вот сама читалка — довольно простая, портировать на Go должно быть нетрудно.
А какой алгоритм парсинга используется
Об этом сказано в статье.
Разбор нисходящий, грамматика контекстно-свободная (BNF-подобная). На счёт сложности не готов ответить. Сложность морфологического поиска Log2(n), где n — число словоформ (где-то 5 миллионов), но в относительных величинах, думаю, отстаёт от решений, написанных на C/C++. Количественно, увы, не помню (можете скачать и замерить :)). Я морфологию почти не оптимизировал, писал почти «в лоб». Скорость синтаксического разбора для сложных предложений — где-то порядка 0.1-0.2 секунды, для простых — в несколько раз быстрее.
Ради интереса измерил скорость морфологического поиска. Получилось чуть больше 200.000/сек. (если, конечно, где-то не ошибся). Учитывая, что у меня морфологический поиск несколько более продвинутый — он ищет множество словоформ по заданному префиксу и разделителю, а также совершенно не оптимизированный, то результат, кажется, совсем не плохой.
Тут жена-филолог подсказывает (к списку правил грамматики) почитать про «структурные схемы синтаксиса русского языка». В частности, посмотреть «Российская грамматика 70, 80» (1970 и 1980 года издания, они так и называются), работы Белошапковой, Богданова, Золотова, Шмелёва, где примерно в 15 типов структурных схем укладывается все многообразие предложений русского языка. Возможно, поможет обойти часть велосипедов.
Sign up to leave a comment.
Разбор естественного языка: под капотом