Работа с русским языком на Perl
Сергей Протасов 2004
Регулярные выражения являются одним из популярным методов в обработке текстов на Perl. Хотя частенько они отпугивают начинающих программистов, позднее они становятся незаменимым и мощнейшим инструментом для работы с разнообразными данными.
Однако регулярные выражения не всесильны. Слишком сложные данные очень тяжело обрабатывать без дополнительных вспомогательных инструментов. А естественный язык вообще крайне сложно поддается какому-либо поиску семантической информации: если Вы хотите найти в тексте предложения, выражающие определенное мнение, отношение, действие или чувство по отношению к чему-либо - сделать это без знания грамматики предложений и только с помощью регулярных выражений не так-то просто.
Однако давайте рассмотрим, как это можно сделать:
# Cоздадим массив предложений
# в которых что-то росло, растeт или собирается расти.
while ($sentence =~ /\G($chto_to_rastet/g) ) {
push (@vse_chto_rastet, $1);
}
Наше строка поиска "$chto_to_rastet" может зависеть также от других слов в предложении, связи с которыми определяют время, число и род нашего ключевого слова: "растет", "выросли", "будет расти".
Грамматика связей
Существует несколько подходов в обработке естественного языка, но только некоторые из них стали действительно популярными в последнее десятилетие. Один из подходов - это разбор предложений с помощью Грамматики Связей (Link Grammar). Кроме определения основной функции каждого слова в предложении, парсер грамматики связей строит граф, где все слова связаны ссылками (связями или линками).
Данные связи-линки используются не только для определения части речи (существительные, прилагательные, глаголы и так далее) и отсечения омонимии ("мама мыла раму" - "мыла" здесь глагол, а не существительное), но и описывают более детально функцию данного слова в предложении. Например, если фраза состоит из двух прилагательных и двух существительных и нам очень нужно знать к какому все-же существительному относится каждое прилагательное. Грамматика связей решает эту проблему.
Грамматика связей основана на одном из высокочастотных свойств языка, которое называется планарность (или слабая проективность). Планарность означает, что если вы на плоскости соедините дугами все связи между словами в предложении (над предложением), то непересечение дуг означает грамматически правильное предложение, а если дуги пересекаются, то предложение скорее всего грамматически неправильное и звучит как-то не так. Например непланарное предложение "Я дом вижу высокий" имеет связи (я-вижу, вижу-дом, высокий-дом), которые пересекаются.
В терминологии грамматики связей связка означает один из успешных разборов предложения, в котором никакие две дуги не пересекаются. Пример простого разбора предложения:
+----------Wd----------+
| +----Sf3----+----MVv----+
| | | |
LEFT-WALL мама.nlfsi мыла.vnpdpfs раму.ndfsv
Главные части речи помечаются суффиксами. Суффиксы, начинающиеся на .n и .v означают существительное (noun) и глагол (verb). Дальнейшее символы в суффиксе несут информацию о роде, числе, падеже, времени и других морфологических признаках, в зависимости от части речи. Метки на дугах между словами обозначают тип связи. Например, коннектор S обозначает связь между главным существительным и глаголом. Коннектор MV - между глаголами и зависимыми от них существительными. Дальнейшие подтипы коннекторов (маленькие буквы) обозначают некоторую дополнительную информацию о двух связываемых словах, чаще всего это падеж, число и род.
Хотя эффективность грамматики связей довольно велика, она все же пока настроена на газетный стиль изложения и не будет справляться с более свободной разговорной лексикой.
Внутренняя работа парсера довольно сложна, однако алгоритм разбора использует несколько простых принципов. Вот три главных условия для того что бы предложение считалось разобранным:
Парсер использует словарь, где расписаны требования по связям для каждого слова. Например, слова "мама", "мыла", "раму" имеют следущие основные требования по связям:
"мама.nlfsi": {Afi-} & Sf3+;
"мыла.vnpdpfs": Sf3- & Wd-;
"мыла.ndnsg": {Ang-} & Mg-;
"раму.ndfsv": {Afv-} & MVv-;
Существительные "Мама.n", "мыла.n", "раму.n" могут (а скобочки { } обозначают, что могут и не иметь) иметь связи к прилагательным (коннекторы A-), а глагол "мыла.v" такой связи А- иметь не может, зато имеет обязательный коннектор S-, означающий связь с существительным. Таким образом существительное "мыла.n" в родительном падеже от "мыло" не существует ни в одной из связок и отбрасывается алгоритмом разбора.
Все требования связей для слов хранятся в специальных словарях парсера. Требования написаны на специальном логическом "языке грамматики связей", который представляет собой отдельный интерес. Вкратце можно сказать, что это логическое выражение с операциями ИЛИ, И над коннекторами различного направления A+, A-. Один из алгоритмов парсера с целью обработки на высокой скорости переводит данные выражения из словарей в дизьюктивную форму вида (A1 или A2 или .. или An), где Ai в свою очередь это список коннекторов (K1 и K2 и .. Kn). Данные списки в русской версии парсера могут (после преобразования из файлов в память) по размерам превышать сотни мегабайт для предложения. Это эффект от высокой морфологичности русского языка и от очень большого разнообразия грамматических конструкций. Далее над этими списками уже работает другой эффективный алгоритм, который за полиномиальное время (если быть точным O(n^3) от числа слов в предложении) находит грамматически правильную связку. Можно добавить, что задача поиска правильной связки сводится к задаче триангуляции выпуклого многоугольника. Скорость парсера напрямую зависит от числа доступной памяти. Если все слова русского языка со всеми их требованиями влезали бы в оперативную память, то скорость алгоритма на современном P4-2Ггц составила бы около 100 предложений в секунду. Однако из-за большой прожорливости русских словарей, приходится генерировать словарь из ограниченного числа слов при разборе каждого нового предложения, что ощутимо сказывается на скорости - в среднем около 1 предложение в секунду. Но этого уже достаточно для некоторых практических задач.
Модуль Lingua::RU::LinkParser
Перловый модуль грамматики связей представляет собой объектно-ориентированный интерфейс, который можно использовать из программ на Perl. После подключения модуля можно работать с объектами соответствующим предложениям, связкам, связям, словам и коннекторам. К примеру рассмотрим следующую программу:
use Lingua::RU::LinkParser my $parser = new Lingua::RU::LinkParser; # Создаем парсер my $text = "Бита была бита" my $sentence = $parser->create_sentence($text); # разбираем предложение my $linkage = $sentence->linkage(1); # использовать первую связку print $parser->get_diagram($linkage); # выводим диаграмму на экранЭта программа выводит:
+---------Wd--------+
| +---Sf3--+--AIfi--+
| | | |
LEFT-WALL бита.ndfsi была.vp бита.afss
Первая "бита" успешно распознана как существительное, а вторая - как краткое прилагательное.
Диаграмма помогает нам понять грамматику связей, но для практических задач нам потребуется работать с самим связями. Продолжая писать выше начатую программу, мы извлечем из объекта $linkage (связка) массив объектов слов $word:
my @words = $linkage->words;
foreach my $word (@words) {
print "\"", $word->text, "\"\n";
foreach my $link ($word->links) {
print " тип связи `", $link->linklabel,
"' со словом `", $link->linkword, "'\n";
}
}
Выдержка из вывода программы:
"бита.ndfsi" тип связи `Sf3' со словом `2: была.vp' "была.vp" тип связи `Sf3' со словом `1: бита.ndfsi' тип связи `Wd' со словом `0: LEFT-WALL' тип связи `AIfi' со словом `3: бита.afss' "бита.afss" тип связи `AIfi' со словом `2: была.vp'