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

Один из перспективных подходов в машинном обучении базируется на запоминании уже разобранных примеров и поиске похожего образца. Например, у нас уже есть коллекция расшифрованных аудиозаписей, и если появляется новый звуковой файл, мы ищем похожий образец и на его основе строим распознавание. Рассмотрим, как базируясь на этом принципе, можно построить морфологию русского языка.




В большинстве случаев словоформа образуется за счет изменения суффикса слова. При этом в простейшем случае правило, согласно которому будет определяться нормальная форма, задается тройкой (n,newsuffix,morphinfo),
где

• n - длина суффикса, который нужно отбросить;
• newsuffix - новый суффикс, добавление которого даст нормальную форму;
• morphinfo - морфологическая информация (например, падеж, род и т.д.).

Например, для слова “люди” правило будет иметь следующий вид - (4,”человек”,”существительное, мужского рода, в именительном падеже, множественного числа”). В том случае, если у слова может быть несколько нормальных словоформ (вина -> вино, вина), правило будет состоять из нескольких троек. Примеры, когда словоформа образуется еще и с помощью префикса, мы рассматривать не будем. Во основном, это касается прилагательных в превосходной степени, которые, в принципе, могут трактоваться как отдельное слово (например, “наилучший”, “наибольший”). Установив такое правило для каждого слова, мы легко можем получить нормальную словоформу.



Словарь с проекта AOT содержит около 5 миллионов словоформ, по которым строится порядка 30 тысяч правил для определения нормальной формы слова. Собственно, это и есть те самые обработанные результаты, столь необходимые для построения нашего алгоритма. При этом на первый взгляд кажется, что для нахождения нужного правила необходимо хранить все 5 миллионов словоформ. В действительности это не так.



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



Поступим следующим образом: отсортируем все словоформы в лексографическом порядке перевернутых слов. Например, для слов а, оружие, сторона, море верным будет такой порядок: а, сторона, оружие, море. Мы получаем следующую закономерность: слова, находящиеся после сортировки рядом, будут с большей вероятностью иметь одинаковое правило. Теперь удалим из нашего списка все слова, правила которых совпадают с правилом предшествующего ему слова. В нашем распоряжении останется около 500 тысяч слов, то есть мы смогли сократить объем хранимой информации в 10 раз. Таким образом, чтобы получить нормальную словоформу для какого-либо слова, нам необходимо найти наибольшее слово из оставшегося списка, не превосходящее данное и применить правило от него. Данный алгоритм будет корректно работать для всех слов из словаря и даст хорошую эвристику для незнакомых примеров. Этот подход может быть использован и для добавления поддержки русского языка в lucene.



Также для уменьшения объема занимаемой информации мы можем произвести дополнительное кодирование, при котором шесть подряд идущих букв представляются как 32-хбитный int. Таким образом, список образцов, по которым производится поиск нужного правила, представляется как двухмерный массив чисел, в котором одна строка соответствует одному слову. Для нахождения нужного образца необходимо использовать бинарный поиск. Скорость данного алгоритма составляет порядка 200 тысяч слов в секунду. Кроме того, возможны дальнейшие улучшения: например, использование префиксного дерева для хранения и поиска информации. Но это уже тема для следующего разговора.