НЕПОЛНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ТЕКСТА В
ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМАХ
А. Е. Ермаков
ООО “Гарант-Парк-Интернет”
Ключевые слова: синтаксический разбор, разрешение омонимии, выделение именных групп, статистический анализ текста, информационный портрет текста.
Доклад посвящен опыту разработки неполного синтаксического анализатора русского языка и его внедрению в прикладные системы анализа полнотекстовых документов в компании “Гарант-Парк-Интернет”. Синтаксический разбор без учета глагольного управления на основе бесконтекстной грамматики позволяет выделять именные группы и разрешать морфологическую омонимию, не выходя за рамки допустимых ограничений на вычислительные ресурсы систем, работающих с большими массивами документов. Экспериментально показано, что использование такого анализатора на этапе предварительной обработки документа существенно повышает точность работы алгоритмов статистического анализа текста в прикладных системах.
1. Введение
Задаче компьютерного анализа текста на естественном языке посвящено множество теоретических и практических работ. Доступные сегодня вычислительные мощности позволили применить широкий класс математических методов анализа неструктурированных данных для обработки больших массивов документов, эффективно решая задачи поиска информации, классификации, кластерного анализа, выявления скрытых закономерностей и другие. Не последнее место в этом ряду занимают и наши собственные разработки в компании “Гарант-Парк-Интернет”, представленные на сайтеhttp://research.metric.ru.
К сожалению, внедрение математических методов в обработку текста проходит на фоне отсталости собственно лингвистической составляющей алгоритмов, что не позволяет достичь высокого качества работы прикладных систем. Ставший устойчивым уклон в область статистических методов анализа привел к тому, что компьютерная лингвистика на время оказалась оставлена в стороне. Господствующего мнения, что лингвистические алгоритмы являются ненадежными, слабо масштабируемыми и чересчур медленными для решения реальных задач, до недавнего времени придерживались и автор в более ранних публикациях на эту тему [1,2].
Исследования, проведенные нами в последний год, заставили изменить сложившуюся точку зрения на место алгоритмов синтаксического разбора в структуре статистических анализаторов текста. Не претендуя на конкуренцию с разработчиками систем машинного перевода и оставаясь в рамках решения собственных задач, относимых скорее к разряду аналитических, мы начали успешно развивать синтаксическую обработку для внедрения в собственные продукты.
2. Синтаксический разбор в задачах автоматического анализа текста
Сложность реализации высокоточного анализатора связана с наличием тесной связи между синтаксисом и семантикой, присутствием в текстах русского языка большого количества синтаксически омонимичных конструкций, не допускающих однозначной интерпретации без привлечения знаний о семантической сочетаемости слов. Такова, например, проблема управления глагола предложно-падежными конструкциями. В синтаксически эквивалентных фразах “человек стрелял из ружья” и “человек стрелял из окна”, объект “ружье” представляет аргумент предиката “стрелять” в роли косвенного дополнения, а объект “окно” – обстоятельство места, которое является дополнительной характеристикой всей ситуации в целом.
Модель языка, призванная объединить синтаксическую и семантическую составляющие, известна под названием толково-комбинаторного словаря и призвана описать ограничения на сочетаемость лексических единиц в определенных синтаксических ролях, например, в форме известного аппарата лексических функций [6].
Однако, помимо колоссального объема необходимого ручного труда, разработку подобного словаря усложняет отсутствие достаточно полной и устоявшейся системы классификации типов синтагматических отношений (например, базиса лексических функций), а также парадигматической классификации лексики (тезауруса). Так, если описание синтагматики обязано декларировать, что аргумент предиката “стрелять”, представляющий орудие действия, должен относиться к классу “оружие”, то описание парадигматики призвано установить все имена, относимые к этому классу – “ружье”, “рогатка” и др.
Указанные проблемы привели к установившемуся мнению о нецелесообразности введения модуля синтаксического разбора в системы автоматического анализа текста. Однако оказалось, что, несмотря на ограниченную точность синтаксических анализаторов, их использование способно заметно повысить качество таких систем в случае комбинирования с известными статистическими методами [1,2], не выходя за рамки стандартных ограничений на вычислительные ресурсы.
Дело в том, что отдельные ошибки синтаксического анализатора поглощаются в дальнейшем при фильтрации статистическим анализатором, поскольку общее число “нормальных” языковых конструкций в тексте существенно превышает число “нестандартных”. Некоторые ошибки могут оказаться заметными при анализе текстов небольшого объема, однако стоит учесть, что статистическому анализу такие тексты вообще не поддаются.
Экспериментально проверенным фактом является также то, что для решения многих задач с приемлемым качеством не требуется полный синтаксический разбор, к которому призваны стремиться автоматические переводчики. Полный анализ всех возможных синтаксических связей, присутствующих во фразе, даже сейчас является непомерно долгим для нашего класса задач.
Основные задачи, решаемые сегодня системами анализа текста, следующие: формирование информационного портрета текста в терминах ключевых понятий, выявление смысловых связей между понятиями, автоматическое реферирование. Прикладные функции интеллектуальных систем, которые могут быть реализованы на основе этих результатов, были описаны в работах [3,4,5]. Важнейшей сопутствующей проблемой, решаемой исключительно средствами синтаксического анализа, является разрешение омонимии в тех случаях, когда грамматические формы различных слов совпадают (например, форма “стали” для существительного “сталь” и глагола “стать”).
3. Синтаксический разбор и разрешение омонимии
Целью синтаксического разбора является построение дерева синтаксических зависимостей между словами во фразе. В случае удачного разбора предложение сворачивается в полносвязное дерево с единственной корневой вершиной.
Поскольку одна словоформа может соответствовать нескольким грамматическим формам слова, в том числе формам различных слов, в ходе анализа необходимо производить свертку предложения для всех возможных вариантов грамматических форм. Те грамматические формы, которые обеспечивают максимальную свертку дерева (минимальное число висячих вершин), следует считать наиболее достоверными.
Как показала практика, для снятия большей части омонимии (около 90%) не требуется полный синтаксический анализ, обеспечивающий полную свертку дерева. Достаточным оказывается включение правил согласования слов в именных и глагольных группах, свертки однородных членов, согласования подлежащего и сказуемого, предложно-падежного управления и нескольких прочих – всего в пределах 20-ти правил, описываемых бесконтекстной грамматикой. Подробно ознакомиться со способами формального описания языка можно, например, в работе [7].
Порядок применения правил управляется алгоритмом разбора, который на каждом шаге проверяет возможность применения очередного правила к очередному фрагменту фразы (паре-тройке слов, знаков препинания и т.п.) и, если удается, сворачивает фрагмент. Свертка фрагмента обычно заключается в его замене одним главным словом – удалением подчиненных слов, после чего разбор продолжается. В случае невозможности дальнейшего применения правил на любом из шагов совершается откат – последний свернутый фрагмент восстанавливается и делается попытка применить другие правила. Окончательным вариантом разбора следует считать такую последовательность применения правил, которая порождает максимальную свертку фразы.
Так, в ходе разбора фразы “усталые гуси и утки стали снижаться”, возникают следующие варианты:
( усталые -> ( гуси + утки ) ) ~> ( стали <- снижаться ),
( усталые -> гуси ) и ( утки ~> ( стали <- снижаться ) ),
( ( усталые -> гуси ) + ( утки <- стали ) ) снижаться,
и ряд других.
Здесь каждая пара скобок включает ряд слов, обработанных некоторым правилом на очередном шаге анализа. Прямая стрелка указывает отношение подчинения при свертке именных и глагольных групп, знак плюса – свертку равноправных однородных членов, а волнистая стрелка – связь подлежащего со сказуемым. Такое представление соответствует дереву зависимостей во фразе.
Очевидно, что только первый вариант соответствует полному разбору – полносвязному дереву с одной вершиной, представленной глагольной группой “стали снижаться”. Второй вариант не полон, но все установленные синтаксические связи являются правильными и позволяют правильно разрешить омонимию у глагола “стать”. В третьем варианте присутствует ошибка, вызванная наличием у существительного “сталь” формы “стали” в родительном падеже множественного числа – выделена именная группа “утки стали” (аналогично “полосы стали”, “ковка стали”).
Как видно, процессу разбора соответствует целое дерево вариантов свертки фразы, вследствие чего производительность алгоритма падает экспоненциально с ростом числа используемых правил и количества слов в предложении. Так, очень сложные предложения могут порождать десятки тысяч вариантов разбора. Эта вычислительная проблема является общей для всех синтаксических анализаторов, ввиду чего на практике целесообразно ограничивать допустимое число рассматриваемых вариантов, и выбирать из них субоптимальный вариант свертки.
Как показал опыт, влияние подобного ограничения сказывается лишь на разборе небольшого количества особенно сложных предложений. Однако для разрешения омонимии даже неполного разбора практически всегда оказывается достаточно. Положительной стороной этого момента является то, что точность анализа и его скорость (обратно пропорциональная полноте) регулируются одним числовым параметром, определяющим соотношение между ними. Так, начиная с некоторого момента, повышение точности разбора на один процент требует двукратного снижения производительности. В нашей реализации этот предел соответствует скорости обработки около 50 Мбайт текста в час (P-II, 400Мгц), что приемлемо для прикладных систем.
4. Информационный портрет текста и именные группы
Основной проблемой, возникающей при формировании информационного портрета текста, является проблема выделения именных групп - устойчивых словосочетаний, в которые входят существительные и согласованные с ними прилагательные (например, “развитие сельского хозяйства”). Именно цельные именные группы, а не отдельные слова, характеризуют содержание текста и могут служить для тематического индексирования, авторубрицирования и т.п. Сопутствующей задачей является их ранжирование по значимости в тексте – вычисление так называемого “тематического веса”, отражающего вклад соответствующего понятия в содержание текста (его информативность).
Синтаксические отношения в пределах именных групп могут быть описаны десятком правил бесконтекстной грамматики, которые учитывают лишь согласование грамматических форм.
В общем случае полезно привлечение словаря моделей управления существительных, типа “борьба с [кем,чем?]”, “борьба против [кого,чего?]”. Однако, в отличие от глаголов, лишь немногие существительные может участвовать в управлении, вследствие чего доля образуемых ими словосочетаний относительно мала (см., к примеру, [8]).
В ходе полного синтаксического разбора фразы возможно установление синтаксических ролей именных групп в предложении, что позволяет ранжировать их с точки зрения важности для автора фразы. Так, наиболее важными являются слова из группы подлежащего, затем - сказуемого, прямого дополнения, косвенного дополнения, обстоятельства. В сочетании с алгоритмами статистического анализа эти факты способствуют более точному ранжированию понятий по значимости в информационном портрете документа.
Задача выявления дополнений и обстоятельств требует как минимум привлечения словаря моделей управления глаголов, который на данный момент отсутствует на рынке в объеме, достаточном для наших задач (в русском языке около 20 тысяч глаголов).
Задача выявления подлежащего в большинстве случаев решается достаточно просто и однозначно за счет введения соответствующих правил согласования существительного с глаголом.
Ниже приведен пример разбора нашим анализатором фразы:
(клинки,<- изготовленные) (великими->мастерами), становились
( (предметами <- (религиозного->поклонения) ), + (символами <- (гордости и+
( чести <- ( (живущих и+ будущих) -> (поколений<-японцев) ) ) ) ) )
После выбора наилучшего варианта разбора фразы включается обратный алгоритм синтеза, который проходит по дереву зависимостей и собирает все именные группы. Одновременно входящие в них слова ставятся в согласованные грамматические формы.
Полный список выделенных именных групп следующий:
100 КЛИНОК
50 СИМВОЛ ЧЕСТИ СЕГОДНЯШНЕГО ПОКОЛЕНИЯ ЯПОНЦА
50 СИМВОЛ ЧЕСТИ СЕГОДНЯШНЕГО ПОКОЛЕНИЯ
50 СИМВОЛ ЧЕСТИ ВЧЕРАШНЕГО ПОКОЛЕНИЯ ЯПОНЦА
50 СИМВОЛ ЧЕСТИ ВЧЕРАШНЕГО ПОКОЛЕНИЯ
50 СИМВОЛ ЧЕСТИ
50 СИМВОЛ ГОРДОСТИ
50 СИМВОЛ
50 ПРЕДМЕТ РЕЛИГИОЗНОГО ПОКЛОНЕНИЯ
50 ПРЕДМЕТ
50 КЛИНОК
50 ВЕЛИКИЙ МАСТЕР ДРЕВНОСТИ
50 ВЕЛИКИЙ МАСТЕР
40 ЧЕСТЬ СЕГОДНЯШНЕГО ПОКОЛЕНИЯ ЯПОНЦА
40 ЧЕСТЬ ВЧЕРАШНЕГО ПОКОЛЕНИЯ ЯПОНЦА
37 ЧЕСТЬ СЕГОДНЯШНЕГО ПОКОЛЕНИЯ
37 ЧЕСТЬ ВЧЕРАШНЕГО ПОКОЛЕНИЯ
33 РЕЛИГИОЗНОЕ ПОКЛОНЕНИЕ
33 МАСТЕР ДРЕВНОСТИ
30 СЕГОДНЯШНЕЕ ПОКОЛЕНИЕ ЯПОНЦА
30 ВЧЕРАШНЕЕ ПОКОЛЕНИЕ ЯПОНЦА
25 ЧЕСТЬ
25 СЕГОДНЯШНЕЕ ПОКОЛЕНИЕ
25 МАСТЕР
25 ГОРДОСТЬ
25 ВЧЕРАШНЕЕ ПОКОЛЕНИЕ
20 ПОКОЛЕНИЕ ЯПОНЦА
16 ПОКЛОНЕНИЕ
16 ДРЕВНОСТЬ
12 ПОКОЛЕНИЕ
10 ЯПОНЕЦ
Слева от каждой именной группы – понятия текста – указан его тематический вес, вычисляемый на основе синтаксической роли в предложении, а также места понятия в составе более сложной именной группы.
Так, если вес именной группы "предмет религиозного поклонения" равен 50 (не подлежащее), то веса входящих в нее понятий будут соответственно: 50 – для “предмет” (главного слова в группе), 50 * 2/3 = 33 для "религизное поклонение" (подчиненной группы длины 2 в группе длины 3) и 50 * 1/3 = 16 для "поклонение" (подчиненной группы длины 1 в группе длины 3).
Максимальный вес, равный 100, в данном примере имеет единственное понятие “клинок”, которое представляет подлежащее – главную тему фразы.
Заметим, что последняя часть разобранной фразы допускает второй, столь же полный вариант разбора:
(символами <-( (гордости и+ чести) <-
( (живущих и+ будущих) -> (поколений<-японцев) ) ) )
который порождает дополнительные именные группы:
гордость будущего поколения японца, гордость живущего поколения японца, символ гордости будущего поколения японца, символ гордости живущего поколения японца.
Наличие нескольких равноправных вариантов разбора есть явление синтаксической омонимии, разрешение которой невозможно без привлечения семантики, а иногда и прагматики, как в данном случае.
5. Заключение
Как показала практика, статистические методы анализа текста, на которых до настоящего времени были сконцентрированы усилия разработчиков интеллектуальных систем, достигли своего естественного предела. Дальнейшее усложнение математики без привлечения серьезной лингвистики не позволит заметно повысить качество подобных систем.
Несмотря на ограниченность синтаксических анализаторов текста, работающих без привлечения семантики, есть все основания утверждать, что их включение повышает точность работы статистических анализаторов, а также открывает качественно новые возможности, оставаясь в рамках разумных ограничений на вычислительные ресурсы.
Разработанный нами синтаксический анализатор русского языка, реализующий выделение именных групп и снятие омонимии, уже внедряется в очередную версию системы Russian Context Optimizer для СУБД Oracle [4]. С демонстрацией анализатора можно познакомиться на сайте http://research.metric.ru.
Литература
- Ермаков А.Е. Тематический анализ текста с выявлением сверхфразовой структуры // Информационные технологии. - 2000. - N 11.
- Ермаков А.Е., Плешко В.В. Ассоциативная модель порождения текста в задаче классификации // Информационные технологии. - 2000. - N 12.
- Плешко В.В., Ермаков А.Е., Липинский Г.В. TopSOM: визуализация информационных массивов с применением самоорганизующихся тематических карт // Информационные технологии. - 2001. - N 8.
- Ермаков А.Е. Проблемы полнотекстового поиска и их решение // Мир ПК. – 2001. – N 5.
- Ермаков А.Е., Плешко В.В. Тематическая навигация в полнотекстовых базах данных // Мир ПК. – 2001. – N 8.
- Мельчук И.А Опыт теории лингвистических моделей “Смысл-Текст”. Семантика, синтаксис. - М.: Школа "Языки русской культуры", 1999.
- Гладкий А.В. Формальные грамматики и языки. - М.: Наука, 1973.
- Розенталь Д.Э. Управление в русском языке. Словарь-справочник. – М.: Книга, 1986.
Restricted syntactic analysis of text document in information retrieval systems
A. E. Ermakov
Key words: syntactic parsing, ambiguity resolution, noun-groups extracting, statistical text analysis, information text structure.
The report is devoted to development of restricted syntactic parser for Russian language and embedding it into full-text document analysis systems produced by "Garant-Park-Internet" Ltd. The simplified syntactic parsing that omits verb control is still capable to extract noun-groups and resolve morphological ambiguity. We designed such parser on the base of context-free grammar. Simplification of the parsing algorithm allows us to process large arrays of text documents in times suitable for use in information retrieval and text analyzing systems. Our experiments demonstrate that this parser could be used on document preprocessing stage in statistical text analysis algorithms to increase the precision of these systems.