Граф зависимости
Дата добавления: 2014-01-11; просмотров: 5; лекция была полезна: 0 студентам(у); не полезна: 0 студентам(у).
Опубликованный материал нарушает авторские права? сообщите нам...
Описание структур в форме классического графа зависимостей хорошо соответствует русской грамматической традиции: оно основывается на понятии бинарного словосочетания в предложении с выделенными главными и зависимыми элементами. Обычно ровно один узел графа в подавляющем большинстве моделей, соответствующий сказуемому, не имеет подчиняющего узла и называется вершиной. Иногда двумя вершинами представляют подлежащее и сказуемое.
Отношение подчинения задает частичный порядок на множестве узлов. Если одному узлу подчиняется сразу несколько узлов, то среди последних порядок не определен: граф зависимостей не передает информацию об относительной степени близости подчиненного слова к главному. Например, граф зависимостей для фразы «программное обеспечение вычислительной техники и автоматизированных систем » (рис.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
Привлекательными свойствами графа зависимостей является их экономичность, удобство использования в преобразованиях, возможность представления частичных результатов анализа в виде множества подграфов.