Дерево непосредственных составляющих

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Дерево непосредственных составляющих

Дерево непосредственных составляющих

Дерево непосредственных составляющих (ДНС) обеспечиваает структорное

описание предложений. Граматика непосредственных составляющих (ГНС)

характеризует ДНС. И то и другое поэтому играют важную роль в обработке

естественного языка для создания структурных описаний предложения, которые

могут быть использованы в обработке систем понимания или порожления речи.

Дерево непосредственных составляющих:

ДНС кодирует иерархическую структуру предложения. Эта информация двух

видов: иерархическая структура группирования и синтаксические категории

этих группирований.

Предложение

John wanted to publish the paper. (1)

имеет следующую структуру:

(2)

John wanted to publish

the paper

Эта структура может быть представлена и в скобочной конструкции:

[[John][[wanted][[to][publish][[the][paper]]]]] (3)

(2) и (3) описывают группирование без идентификации составляющих. Такие

конструкции называются “скелетом”. Скелеты характеризуют фразу без

обозначения вершин дерева. Скелет с обозначением категорий является ДНС,

для фразы (1) это будет выглядеть так

S

NP VP

VP

NP (4)

NPR V P V

DET N

John wanted to publish

the paper

“John” является здесь именем собственным, которое является также группой

подлежащего, “wanted” и “publish” - глаголы, “to”- предлог (точнее говоря

“to” должно быть названо частицей или временем), “the” - детерминатор,

“paper” - существительное, “the paper” - группа существительного, “to

publish the paper” - группа сказуемого, “wanted to publish the paper” -

тоже группа сказуемого, и наконец, “John wanted to publish the paper” -

предложение.

Соответственно скобочная конструкция (3) будет выглядеть так:

[S[NR[NPR John]][VP[V to][V publish][NP[DET the][N paper]]]]]

(5)

Конструкции (4) и (5) обычно (но не всегда) используются в системах

обработки естественного языка.

Грамматика непосредственных составляющих (ГНС)

ГНС состоит из набора нетерминальных символов (таких как N, V, NP, VP, S и

т.д.) и из набора терминальных символов (таки лексические единицы как John

“wanted”, “to”, “publish”, “the”, “paper” и т. д. и из набора правил,

которые позволяют переписывать нетерминальные символы в цепочку

терминальных и нетерминальных симвлов. Если это переписывание не зависит от

контекста, то это контексто-независимая грамматика (КНГ), в противном

случае - это контекстозависимая грамматика (КЗГ). Правило перезаписи имеет

следующую форму:

А --> Х (6)

где Х - последовательсть терминальных и нетерминальных символов, а А -

нетерминальные.

КЗГ имеет иследующее правило перезаписи:

ZAW --> ZXW (7)

где X, Z, W - цепочки терминальных и нетерминальных символов, а А -

нетерминальные.

В (7) А и Х находятся в окружении Z и W. Часто эта формула пишется в виде

A --> X (Z — W (8)

Деревация в КНГ начинается с начального символа S и далее идет до тех пор,

пока не будет применено последнее правило. Порядок применения правил не

важен.

S —> NP VP

NP —> NPR

NP —> DET N

VP —> V VP

VP —> P V NP

NPR —> John, Mary, Bill

N —> paper, man, cow

V —> wanted, meet, want

P —> to

DET —> the

Несколько формальных свойств ГНС:

Если все правила некоторой ГНС G являются контекстно сводными, то G

называется контекстно свободной грамматикой (КСГ). Если некоторые правила

ГНС являются контекстно зависимыми, то G разывается КЗГ.

Строчный язык некоторой ГНС G определяется как набор всех конечных строк,

полученных из G и этот набор обозначается L(G). Строка w считается

полученной из G, если w можно получить при последовательном переписывании

начального символа S, используя правила грамматики G. Строчный язык L (т.е.

набор конечнных строк) называется контексто свободным языком (КСЯ), если

существует такая КСГ, что L(G)=L. L называется “строго контекстно зависимым

языком”, если не существует такой КСГ, что КСГ, что L(G)=L, и существунт

такая КЗГ, что L(G)=L. Заметьте, что грамматика G может быть

контекстнозависимой, но ее строчный язык L(G) не обязательно должен быть

КЗЯ. Класс КЗЯ включает класс КСЯ. В этом смысле, КЗЯ являются более

мощным чем КСЯ.

Однако есть и другой случай, когда КЗЯ не являются более мощными чем КСЯ.

Если некоторая КЗГ, G, используется для “анализа”, в этом случае язык

анализируемый при поиощи G - контекстносвободный (6, 7). Для того чтобы

объяснить использование КЗГ G для анализа данного дерева t, определим

анализ t следующим образом. Груба говоря анализ t представляет собой некий

срез дерева. Дадим более точное определение: Набор (Pt) для анализа дерева

t определяется следующим образом

1. Если t=( (пустое дерево), тогда Pt = (

2. Если t=

A

t0 t1 .... tn

тогда Pt={A} v P(t0)P(t1)....P(tn) где t0, t1 ....tn - деревья, А “ . “

обозначает соединение; например:

S

A B

C d E

c e

Pt = {S, AB, AE, Ae, CdB, CdE, Cde,cdB, cdE, cde}

Пусть G - контекстно зависимая грамматика, т.е. ее правила имеют форму

А-->(/( - (

где А ( V - ( (V - алфавит, и ( набор терминальных символов), ( ( V+

(набор ненулевых строк на множестве V) и (, ( ( V* (набор всех строк на V).

Если ( и ( - равны нулю, то такое правило называется контекскносвободным.

Дерево t называется “анализируемым ” в терминах грамматики G, если для

каждого узла дерева t выполняются правила G. Контекстно зависимое правило А-

-> (/( - (

выполняется для узла А, если строка соответствующая ответвлению от узла А,

является ( и существует анализ t вида (1(А((2 , где (1, (2 ( V*.

Контекстное условие ( - ( называется анализом предиката.

Наряду с контекстозависимымми правилами правилами, позволяющими

специфицировать “правый” и “левый” контекст, часто необходимо иметь правила

специфицирующие “верхний” и “нижний” контекст. Имеем узел А дерева t,

область (( - (), (, ( ( V*, содержит узел А, если существует путь от корня

до края дерева, и этот путь имеет форму

(1(А((2 ((1, (2 ( V*).

Контекстное условие, связанное с таким “вертикальным” анализом называется

“господствующим предикатом”.

В общем виде правило имеет форму

А -->(/СА

где СА - булева комбинация анализа и господствующих предикатов.

Пусть G - конечный набор правил и ((G) - набор деревьев, анализируемый G.

Предполагается, что деревья ((G) - предложения; т.е. корневой узел дерева

((G) обозначен начальным символом S, а конечные узлы - терминальными

символами. Покажем, что строчный язык L(((G)) = {x(x, где х терминальная

строка дерева t, и t ( ((G)} контекстно свободен (7).

Пример: Пусть V = {S, T, a, b, c, e} и ( = {a, b, c, e}, и G - конечный

набор строгих правил.

1. S -->e

2. S --> aT

3. T --> aS

4. S --> bTc / (a_()) ( DOM (T_)

5. T --> bSc / (a_()) ( DOM (S_)

Для правил 1, 2, 3 имеет место нулевой контекст и эти правила -

контекстносвободные. В четвертом и пятом правиле по условию требуется а

слева и узел подчиняется Т (в пятом правиле S).

Язык, порожденный G, может быть порожден G1:

S --> e S --> aT1

S --> aT T--> aS1

T --> aS T1--> bSc

S1-->bTc

Грамматика G1 содержит дополнительные нетерминальные символы S1 и Т1 для

проверки локального контекста при порождении. Легко заметить, что при

помощи S1 и Т1, достигается гом