Граф зависимости

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

Отношение подчинения задает частичный порядок на множестве узлов. Если одному узлу подчиняется сразу несколько узлов, то среди последних порядок не определен: граф зависимостей не передает информацию об относительной степени близости подчиненного слова к главному. Например, граф зависимостей для фразы «программное обеспечение вычислительной техники и автоматизированных систем» (рис.9.1).

Рисунок 9.1 - Граф зависимостей

Как правило, отношение подчинения подразделяется на ряд типов, и дуги графа помечаются индексами синтаксических отношений.

Иногда граф зависимостей одновременно с отношением подчинения задает и отношение линейного порядка следования узлов. Такой граф называется расположенным. Один из способов изображения такого графа представлен на рисунке 9.2.

Рисунок 9.2 - Расположенный граф зависимостей

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

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

Рисунок 9.3 - Представление однородности

Пусть х — произвольная непустая цепочка и Х — множество всех точек х. Произвольное бинарное отношение ® на X, при котором граф <Х, ®> является деревом, называют отношением зависимости (подчинения). Само дерево <Х, ®> называют деревом зависимостей для х. Будем изображать дерево зависимостей цепочки ω в виде последовательности обра­зующих ее точек, расставленных на прямой линии. Для всякой пары точек а,b цепочки ω, для которой а®b, на рисунке бу­дем проводить дугу из а в b, причем таким образом, чтобы все дуги были по одну сторону от прямой. Если a ® b, то будем называть точку а управляющей точкой («хозяином»), а b— под­чиненной точкой («слугой»). На рисунке 9.4 приведены два различ­ных дерева зависимостей для цепочки agbacdef.

При анализе предложений русского языка обычно использу­ют размеченные деревья зависимостей. Размеченное дерево за­висимостей для цепочки х — это четверка <Х, ®, Z, ψ>, где <Х, ®>—дерево зависи­мостей для х; Z — конечное множество, элементы которо­го называют метками, и ψ — отображение множества дуг дерева <Х, ®> в Z.

Рисунок 9.4 - Деревья зависимостей для цепочки agbacdef

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

Дата добавления: 2014-01-11