Синтаксический разбор предложения и построение дерева зависимостей

C/C++:

HGREN_RESPACK sol_SyntaxAnalysis( HGREN hEngine, const wchar_t * Sentence, int MorphologicalFlags, int SyntacticFlags, int Constraints, int LanguageID )

HGREN_RESPACK sol_SyntaxAnalysis8( HGREN hEngine, const char * SentenceUtf8, int MorphologicalFlags, int SyntacticFlags, int Constraints, int LanguageID )

HGREN_RESPACK sol_SyntaxAnalysisA( HGREN hEngine, const char * Sentence, int MorphologicalFlags, int SyntacticFlags, int Constraints, int LanguageID )

C#:

IntPtr sol_SyntaxAnalysis( IntPtr hEngine, string Sentence, int MorphologicalFlags, int SyntacticFlags, int Constraints, int LanguageID )

Delphi:

function sol_SyntaxAnalysis( hEngine: PInteger; Sentence: PWideChar; MorphologicalFlags: Integer; SyntacticFlags: Integer; Constraints: Integer; LanguageID: Integer ): PInteger;

PHP:

sol_SyntaxAnalysis8( $hEngine, $Sentence, $MorphologicalFlags, $SyntacticFlags, $Constraints, $LanguageID )

Аргументы:

hEngine - дескриптор экземпляра грамматического словаря.

Sentence - указатель на строку из широких символов, из которой будет извлечен список лексем. Для функций с суффиксом 8 и A строка должна быть в кодировке utf-8 или текущей системной однобайтовой соответственно. Строка должна заканчиваться нулевым символом. Строка должна содержать одно предложение, в противном случае разбор может закончиться неудачно.

MorphologicalFlags - флаги, управляющие работой морфологического анализатора. Может иметь значение 0 для базового алгоритма анализа или быть побитовым объединением следующих значений:

SOL_GREN_MODEL

Использовать вероятностную модель морфологии, статистически обучаемую по размеченному корпусу. Для использования вероятностной морфологии необходимо, чтобы в составе двоичных файлов словаря были файлы данных модели, а также пути к этим файлам должны быть указаны в секции <models> в конфигурационном файле словаря. На практике вероятностная модель представляет из себя несколько двоичных файлов и входит в состав SDK.

SOL_GREN_ALLOW_FUZZY

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

SOL_GREN_COMPLETE_ONLY

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

SOL_GREN_PRETOKENIZED

Вместо использования внутреннего токенизатора использовать символ с кодом 0x1F как указатель границ слов. Это позволяет разбить предложение по своим правилам, если имеющиеся в словаре не устраивают, или нет возможности модифицировать словарь.

SOL_GREN_TOKENIZE_ONLY

Выполняется только токенизация; этот флаг предназначен для автоматизированного тестирования движка.

SOL_GREN_DISABLE_FILTERS

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

SOL_GREN_ENABLE_RECONSTRUCTION

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

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

SOL_GREN_REORDER_TREE

Переупорядочивать порядок ветвей так, чтобы они шли по возрастанию исходных позиций слов.

Constraints - параметры для управления потребляемыми при разборе текста ресурсами. Значение 0 отключает все ограничения. Старшие 10 битов этого 32-битового аргумента задают максимальное значение одновременно проверяемых альтернативных путей разбора в нисходящем анализаторе. Младшие 22 бита задают максимальное время в миллисекундах, отведенное на выполнение анализа.

LanguageID - id (первичный ключ) объявления языка, на котором записано разбираемое предложение. Можно задать -1 для автоматического определения языка.

Возвращает:

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

Примечания

Синтаксический разбор предложения (парсинг) включает в себя несколько этапов, каждый из которых можно выполнить отдельно с помощью специальной функции API. Сначала предложение разбивается на слова в токенизаторе. Затем выполняется морфологический анализ, в ходе которого для каждого слова определяется его часть речи и грамматические признаки, к примеру падеж, род, число, время, степень и так далее. Наконец, начинается собственно синтаксический разбор, в ходе которого определяются синтаксические свойства слов в предложении и создается синтаксический граф (дерево зависимостей). Эта структура в явном виде представляет синтаксические отношения слов, например подчиненные прилагательные прикрепляются к существительным, или существительные в роли подлежащего прикрепляются к прилагательному в роли именного сказуемого, и так далее. В некоторых случаях получающееся дерево отражает также некоторые смысловые признаки, например кто является инициатором действия (подлежащее), что он делает (сказуемое).

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

Анализ результатов синтаксического разбора

Для работы с результатами синтаксического разбора следует использовать функции sol_CountGrafs, sol_CountRoots, sol_GetRoot, sol_CountLeafs, sol_GetLeaf, sol_GetNodeIEntry, sol_GetNodeVerIEntry, sol_GetNodePosition, sol_GetNodeContents, sol_GetNodeCoordState, sol_GetNodeVersionCount, sol_GetNodeCoordPair, sol_GetNodeVerCoordPair, sol_GetNodePairsCount, sol_GetNodeVerPairsCount, sol_GetNodePairCoord, sol_GetNodeVerPairCoord, sol_GetNodePairState, sol_GetNodeVerPairState. Все они предназначены для обхода синтаксического дерева и получения значений о каждом узле.

Обычно порядок разбора результатов такой. Просматриваем альтернативные списки деревьев с помощью sol_CountGrafs и sol_CountRoots. В случае полностью завершенного морфологического и синтаксического анализа получается 1 набор корней, в котором ровно 3 корневых узла. Другими словами, функция sol_CountGrafs вернет 1, а sol_CountRoots(...,0) вернет 3. Первый и последний узлы являются специальными метками начала и конца анализируемого предложения. Они вставляются грамматическим движком и обычно не должны приниматься в расчет прикладным кодом. Средний узел этого набора корней является корневым узлом синтаксического дерева, например глаголом для простых предложений с глагольным сказуемым. Например, предложение Большой кот сладко спит на старом кожаном диване даст такие результаты:

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

Функция sol_CountGrafs может вернуть число больше 1, это значит, что некоторые части предложения допускают неоднозначную токенизацию. Например, если в предложении есть фрагмент да и, то он может быть распознан и как один союз, и как два отдельных союза. Из-за этого в результатах появляется два альтернативных набора синтаксических деревьев. В прикладном коде можно выбрать для дальнейшего анализа один из них, например - самый короткий. Другими словами, пройдя по набору альтернативных список и проверив длину каждого из них с помощью sol_CountRoots, выбираем список с минимальным числом корневых узлов. Таким способом мы получим в большинстве случаев результат с наиболее глубоко выполненным анализом. В качестве пояснения запустите отладочную консоль морфологического анализатора с помощью скрипта ...\scripts\syntax\console-morphology.cmd и введите словосочетание много, да и дешево. Результаты будут такими:

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

Задание языка

Параметр LanguageID определяет набор правил, которые будут загружены из словарной базы данных для токенизации, морфологического и синтаксического анализа. Если вместо константы языка указать -1, то движок сам определит язык предложения. На распознавание языка потребуется определенное время, поэтому следует явно указывать id языка в случаях, когда он известен априори. Кроме того, при выборе языка используются статистические критерии, поэтому большое количество слов, записанных латиницей (названия компаний и так далее), может привести к неправильному определению языка и выбору неподходящего набора правил синтаксического разбора.

Ограничения для глубину анализа

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

Ограничения задаются заданием значения для параметра Constraints. Взглянув в исходный код утилиты ParseLine, вы увидите там строку const int MAX_ALT = 20;, она как раз передается в функцию sol_SyntaxAnalysis в параметре Constraints.

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

Обычно ограничения по ресурсам имеет смысл комбинировать с использованием вероятностной модели морфологии, то есть включать соответствующий модуль флагом SOL_GREN_MODEL для параметра MorphologicalFlags. Вероятностная модель морфологии позволяет выбирать наиболее достоверные варианты распознавания грамматических признаков слова на основе его окружения, то есть используя алгоритм POS tagging. Что это дает на практике? Если парсер получил на очередном шаге слишком много альтернативных вариантов, то он должен отбросить некоторое количество малодостоверных. Достоверность варианта разбора включает в себя, кроме прочего, также достоверность варианта распознавания словоформы. Поэтому выбор модели сразу же выводит такие варианты в верхушку списка при ранжировании, что повышает вероятность правильного разбора даже при серьезном ограничении на число просматриваемых вариантов.

Примеры выполнения синтаксического анализа из прикладного кода

В составе SDK, в папке ...\ai\solarix\argon\ParseLine, есть исходный C++ код консольной программы для синтаксического разбора предложения, читаемого из текстового файла, и сохранения результата в XML файле. Для проверки можно воспользоваться скриптом ...\scripts\ParseLine\parse.cmd, который запустит скомпилированную утилиту, взяв 2 аргумента - имя входного файла и имя файла для сохранения результата:

parse input.txt out.xml

После выполнения скрипта файл out.xml будет содержать подробную информацию о построенном синтаксическом дереве в формате XML.

Ниже представлен пример выполнения разбора одного предложения.

C++:

int MAX_ALT = 20;
int TIMEOUT = 60000;
int Constraints = (MAX_ALT<<22) | TIMEOUT;
int MorphologicalFlags=0;
int SyntacticFlags=0;
HGREN_RESPACK hPack = sol_SyntaxAnalysis8( hEngine, Sentence, MorphologicalFlags, SyntacticFlags, Constraints, id_language );

const int ngrafs = sol_CountGrafs(hPack);

// Выберем среди результатов альтернативу с минимальным количеством корневых
// узлов. Два узла присутствуют в каждой альтернативе - это метки начала $BEGIN$
// и конца $END$. В случае полностью успешного анализа альтернатива имеет 3
// корневых узла - средний узел представляет из себя искомое синтаксическое дерево.
int imin_graf=-1, minv=1000000;
for( int i=0; i<ngrafs; i++ )
 {
  const int nroots = sol_CountRoots(hPack,i);
  if( nroots<minv ) 
   {
    minv = nroots;
    imin_graf = i; 
   }  
 }

// работаем с самой короткой альтернативой
const int nroot = sol_CountRoots(hPack, imin_graf);
for( int i=1; i<nroot-1; ++i )
 {
  HGREN_TREENODE hNode = sol_GetRoot( hPack, imin_graf, i );
  ...
 }

sol_DeleteResPack( hPack );

C#:

IntPtr hPack = GrammarEngine.sol_SyntaxAnalysis( hEngine, text, GrammarEngine.SOL_GREN_ALLOW_FUZZY, 2, 60000, GrammarEngineAPI.RUSSIAN_LANGUAGE );
int nroot = GrammarEngine.sol_CountRoots( hPack, 0 );
for( int iroot=1; iroot<nroot-1; ++iroot )
 {
  IntPtr hRoot = GrammarEngine.sol_GetRoot( hPack, 0, iroot );
  ...
 }
GrammarEngine.sol_DeleteResPack(hPack);

Delphi:

hPack := sol_SyntaxAnalysisA( hEngine, PAnsiChar('Толстый пушистый кот сладко спит на диване'), 0, 0, 100000, RUSSIAN_LANGUAGE );

nlinkage := sol_CountGrafs( hPack );
for ilinkage:=0 to nlinkage-1
 do begin

  nroot := sol_CountRoots( hPack, ilinkage );
  for iroot:=1 to nroot-2
   do begin

    hNode := sol_GetRoot( hPack, ilinkage, iroot );
    PrintNode( hEngine, hNode );

   end;

  WriteLn('');

 end;

sol_DeleteResPack(hPack);

Навигация по API грамматического словаря

Приобретение SDK грамматического словаря

API layer C++ source code: grammar_engine_api.cpp

Вернуться к списку функций API

  © Elijah Koziev 2010
прикладные проекты на основе грамматического словаря API грамматической машины компоненты для доступа к грамматическому словарю условия получения SDK токенизатор и сегментатор морфологический анализ и синтез лемматизатор база N-грамм синтаксический анализатор словоформы морфология и синтаксис русского языка падеж число род совершенный и несовершенный вид экспорт в SQL формат экспорт в XML формат скрипт SQL словаря структура SQL словаря структура XML словаря компоненты для доступа к грамматическому словарю ORM Persistent Dictionary Library лемматизация стемминг примеры использования грамматического словаря склонение существительных в русском языке склонение русских прилагательных спряжение глаголов в русском языке поиск текста с учетом морфологии OCR подсистема расширенные регулярные выражения генератор текста генератор случайного текста и имитатор рандомизатор синонимизатор перефразировщик Статистика буквенных паттернов

Грамматический словарь русского языка



Грамматический словарь
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
требования: 512 Mb свободной памяти, 300 Мб на диске
размер:         34 Мб

  скачать грамматический словарь купить грамматический словарь SDK грамматического словаря
грамматический словарь русского языка



SDK Грамматического словаря



SDK Грамматического Словаря
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
размер:         13 Мб

SQL словарь (демо):
sqlite mysql oracle firebird mssql

скачать демо-версию SDK купить SDK API грамматического словаря



Поисковая система



Integra
настольная и сетевая поисковая система 

платформа:  Windows XP ... Windows 7
требования: 512 Mb свободной памяти
размер:         21 Мб

Дополнительные компоненты:
MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать поисковую систему SDK поисковой системыописание поисковой системы



SDK Поисковой системы



SDK Поискового движка
API для настольной и сетевой поисковая система 

платформа:  Windows XP ... Windows 7
размер:         17 Мб

Дополнительные компоненты:

MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать SDK SDK поисковой системы



Экранный переводчик



Translator
экранный переводчик

платформа:  Windows XP ... Windows 7
требования: 256 Mb свободной памяти
размер:         4.4 Мб

Дополнительные компоненты:
расширенный англо-русский словарь 6.4 Мб


скачать экранный переводчикописание экранного переводчика



изменено 11-Sep-13