Русская морфология, основанная на памяти

[@akuznetsov]

code.google.com/p/russianmorphology/

[@Mairon]

Русская морфология, основанная на памяти.

Запятую забыли.

[@putnik]

Даже как-то страшно читать топик про русскую морфологию, у которого ошибка прямо в заголовке.

[@Mairon]

Вот я про тоже. Я остановил своё чтение на третьей фразе, где деепричастный оборот неправильно обособили. Я-то сам с орфографией и пунктуацией не особо дружу, но читать и оценивать статью о русском языке с такими ошибками пока не возьмусь. Добавил в избранное, потом гляну.

[@n0nSmoker]

grammar nazi detected?
а вообще статья не совсем о русском языке ;-)

[@Mairon]

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

[@desecho]

Как всё сложно. Морфология в общем-то с пунктуацией не особо связана, так что ничего криминального.
А как вам такая фраза с некого сайта: «Требуется граммотный специалист по продвижению сайта гостиницы.» :)

[@Nashev]

У меня одного впечатление, что с фразы «Словарь с проекта AOT содержит около 5 миллионов словоформ» начинается другая статья, про способ сокращения словаря морфем и ускорение поиска по нему? А до той фразы — что-то другое? И что память тут не при чём?

Впрочем, обе статьи небезынтересны. :)

[@akuznetsov]

В английской литературе есть понятие Memory-Based Algorithm. Они основанные запоминание уже разобранных образцов использование их в дальнейшем. Я понимаю, что по русски это немного режет, но у меня нет лучшего перевода. Если интересно можете посмотреть книгу Walter Daelemans, Antal van den Bosch Memory-Based Language Processing. Там довольно много подобных алгоритмов.

[@xRay]

Спасибо что напомнили про проект АОТ. Не знал что они исходники всех программ и словарей в open source выложили http://sourceforge.net/projects/seman/develop (доступно в SVN)

[@Rustam]

честно говоря, ничего не понял. по крайней мере, постановку задачи.
Нам нужно по введенному слову искать данное слово + заносить в базу(при этом анализируя слово(окончания, суффиксы и т.д) )?

мне казалось, что такая задача решается бором + экспертными системами(ну для самых извращенных нейронными сетями).

В общем, звучит интригующе. Прошу пополнить пост деталями.

[@akuznetsov]

Задача по слову определить его нормальную форму. Например для существительного нормальная форма это именительный падеж, единственное число. Для глагола это инфинитив. Для прилагательного именительный падеж, мужской род и т.д.

[@saterenko]

Я использовал в качестве словаря словари от aspell. На его основе строил все возможные словоформы, получилось, 1 361 765 словоформ. Всё это загнал в собственную хеш-таблицу, по которой поиск давал порядка 5 млн. слов в секунду. При этом слова были в UTF-8 без какого-либо преобразования к целым числам и без особых оптимизаций.

Потом по тексту, приведённому к основам слов, строится суффиксное дерево со ссылками на оригинальные слова в оригинальном тексте. По тестам получилось порядка 900 документов по 20Кб (~1300 слов) в секунду, т.е. ~ 1 170 000 слов в секунду.

Что-то ваш алгоритм медленный. Либо дерево медленное.

[@saterenko]

Сорри, не суффиксное дерево, а суффиксный массив.

[@akuznetsov]

В моем случая было критично объем оперативной памяти используемой программой. Кодирование к целым числам наоборот замедляют работу, но экономят используемую память.

Так же у меня используется упорядоченная структура, что бы угадывать правило для незнакомого слова, это тоже замедляет работу алгоритма.

Дерево пока не использовалось, возможно на такое представление будет сделан переход в следующей версии программы и оно должно даст значительный прирост производительности, но не уверен, что будет выгрыш по памяти, учитывая особенности языка java.

[@saterenko]

Ага, Java, тогда понятно :) Моя реализация на C, у меня больше свободы при работе с памятью, да и нет требований по экономии памяти, по крайней мере для словаря, всё ради скорости :)

Успехов.

[@yuriv]

Это не дерево медленное, а хэш быстрый. -)) К слову сказать, во всех алгоритмах точного поиска информации по текстовому ключу хэш даёт гораздо больший выигрыш по сравнению с деревьями (при больших объёмах данных, конечно). Именно поэтому не рекомендуют использовать стандартный std::map для хранения пар с текстовым ключом, хэш даёт выигрыш на порядок.

[@saterenko]

Для сравнения пробовал Judy Array (http://judy.sourceforge.net/) для словаря, давал порядка 3 млн. слов в секунду. Думаю, правильно написанное дерево может дать чуть больше. Но когда можно создать хеш-таблицу на весь словарь, хеш конечно рулит, не на порядок конечно, но раза в полтора-два выигрыша даст.

[@tyomitch]

Хороший набросок статьи, но самой статьи нет.

Тот, кто «не в теме», так ничего и не понял; а тот, кто разбирался и сам, не узнал ничего нового.

[@lightcaster]

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

[@akuznetsov]

В аот насамом деле используются два автомата. Один для слов из словаря. Второй для предсказания. Я писал такой автомат на Java, но увы он занимал слишком много памяти и был сложный в реализации.

[@lightcaster]

Да, вы правы. Там два автомата. Второй — реверснутый.

Алгоритм для создания и прохода по автомату довольно простой. А вот детерминизация и упаковка, действительно, нетривиальные в реализации.

[@saterenko]

А вы напишите статью про использование автоматов для русской морфологии.

[@lightcaster]

Вы меня провоцируете ). Хорошо, напишу.

[@saterenko]

Ждёмс :)

[@great_boba]

Что-то маленькая статья для понимания.
Где можно почитать поподробнее об этом?

[@akuznetsov]

Посмотрите ответ ниже.

[@akuznetsov]

Есть хорошая книжка по этой теме Walter Daelemans, Antal van den Bosch Memory-Based Language Processing. Так же еще можно прочитать статью на хабре про реализацию морфологии на python. И конечно сайт aot.ru.

[@FSA]

Как-то читал статью про анализ русского текста в играх. Были раньше такие на слабеньких по современным меркам компьютерах типа Spectrum — говоришь что делать, а компьютер тебе отвечает текстом. Надо будет поднять журнальчик.

[@yuk]

Здесь есть ссылка на Lucene библиотеки.
А где можно выкачать оригинал с aot.ru?
Почему нет немецкой библиотеки, если она указанна на АОТ.

[@akuznetsov]

Да есть. На всякий случай привожу ее ниже
code.google.com/p/russianmorphology/.

С сайта aot.ru я взял только словари. Да и языки реализации разные.

Для немецкого языка прежде, чем применять морфологический анализ для реальных текстов нужно, сначала научиться резать составные слова на части.

[@yuk]

Я ссылку нашел, мой вопрос был почему нет GermanLuceneMorphology — теперь понял, спасибо.
Но допустим я напишу код разбивки(spell chkerом) на слова. Сложно ли будет расширить эту библиотеку на поддержку немецкого для элементарных слов.

[@akuznetsov]

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

[@Aleksey]

А вы не пробовали выложить ваши Analyzer/Tokenizer/TokenFilter в саму библиотеку Lucene? В trunk-е проекта есть специальный модуль analysis, там этому самое место imho. Можно просто зафайлить Jira issue и приаттачить исходники. Вроде бы проблем с лицензией никаких нет и внимание ваша работа бы привлекла на порядок больше и квалифицированная помощь бы не заставила себя ждать.

[@akuznetsov]

Я хочу передать код в ASF, только руки ни как не доходят.