gazya.ru страница 1
скачать файл




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

Дерево непосредственных составляющих (ДНС) обеспечиваает структорноеописание предложений. Граматика непосредственных составляющих (ГНС)характеризует ДНС. И то и другое поэтому играют важную роль в обработкеестественного языка для создания структурных описаний предложения, которыемогут быть использованы в обработке систем понимания или порожления речи. Дерево непосредственных составляющих:ДНС кодирует иерархическую структуру предложения. Эта информация двухвидов: иерархическая структура группирования и синтаксические категорииэтих группирований.Предложение John wanted to publish the paper. (1)имеет следующую структуру: (2) John wanted to publish the paperЭта структура может быть представлена и в скобочной конструкции:[[John][[wanted][[to][publish][[the][paper]]]]] (3)(2) и (3) описывают группирование без идентификации составляющих. Такиеконструкции называются “скелетом”. Скелеты характеризуют фразу безобозначения вершин дерева. Скелет с обозначением категорий является ДНС,для фразы (1) это будет выглядеть так SNP VP VP NP (4)NPR V P V DET NJohn wanted to publish the paper“John” является здесь именем собственным, которое является также группойподлежащего, “wanted” и “publish” - глаголы, “to”- предлог (точнее говоря“to” должно быть названо частицей или временем), “the” - детерминатор,“paper” - существительное, “the paper” - группа существительного, “topublish 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. Часто эта формула пишется в виде а--> X (Z — W (8)Деревация в КНГ начинается с начального символа S и далее идет до тех пор,пока не будет применено последнее правило. Порядок применения правил неважен. S —> NP VP NP —> NPR NP —> DET N VP —> V VP VP —> P V NPNPR —> John, Mary, Bill N —> paper, man, cow V —> wanted, meet, want P —> toDET —> 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= а t0 t1 .... tnтогда Pt=A v P(t0)P(t1)....P(tn) где t0, t1 ....tn - деревья, А “ . “обозначает соединение; например: S а B C d E c ePt = 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 -->e2. S --> aT3. T --> aS4. 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, достигается гомоморфизм, позволяющий анализировать любоедерево G1 при помощи G и обратно - любое дерево G имеет гомоморфныйпрообраз в G1. Рассмотрим еще раз контекстно зависимое правило (10). V --> wanted( -VP когда (10) интерпретируется как ложное правило, как описано выше, лексема“wanted” появляется над узлом V, только если узел VP находится справа отнее (в дереве, где появляется V). Справа от V существует строка, имеющая VP“анализ”. Контекстно-зависимые правила в КГЗ используются для анализаобычных грамматик, а не есть правила простого переписывания строк.Терминальные символы в ГНС. До этого момента терминальные символы былипредставлены как нереализуемые элементы. Это было сделано для простотыизложения. Терминальные символы представляют собой наборы топологических,синтаксических и семантических признаков (4, 8). [В принципе возможноликвидировать все эти признаки посредством введения новых нетерминальныхсимволов. Однако их количество будет слишком велико (в соответсвии сбольшим количеством всех возможных комбинаций этих признаков). Это такжеповлечет значительное усложнение грамматики]. Например, терминальныесимволы в (4) заменяются на составные (комплексные) символы и получаем (4’). SNP VPNPR V VP NPJohn wanted P V+N +V DET N-DET- + - NP [to] publish+Animate . +V the paper + - NP + DET +N +Definite + DET - + SingilarЗдесь не обсуждается возможность связи комплексных символов и промежуточныхузлов.Форма (4’) является структурным описанием (СО) предложения (1): John wanted to publish the paperГНС в трансформационной грамматике (ТГ).ТГ также не обсуждаются в этой статье. Однако важно заметить, что ГНС (идеревья НС) играют важную роль в ТГ. Основная идея заключается в том, чтонекоторые структурные описания (СО)описываются в базовом компоненте ТГ, авсе остальные выводятся из них при помощи специальных правил, называемыхтрансформациями. Базовым компонентом является ГНС, которая определяет набордеревьев НС. Деревья, полученные при помощи трансфомаций также являютсядеревьями НС. Такой взгляд на ТГ является классическим и, конечно,упрощенным, хотя и достаточен для данного описания. Так, например, деревоНС для предложения (11), показанное на диаграмме (12) - является базовым.Дерево НС (14) для предложения (13), получается при применениитрансформационного правила.John saw Mary SNP AUX VPNPR V NPJohn past see NPK MaryMary was seen by John. SNP AUX VPNPR
скачать файл



Смотрите также:
Дерево непосредственных составляющих
51.48kb.
«Вот они какие, наши ручки!» 2 ч
58.4kb.
Какое дерево кормит зимой белку, клеста и лесных мышей
12.54kb.
«Отечественная история» одна из составляющих общего цикла гуманитарных и социально-экономических дисциплин, изучаемых в любом российском вузе
531.13kb.
Fips (Федеральный стандарт по обработке информации), в частности, стандартов шифрования и электронной подписи для данных, не составляющих государственной тайны. Aes
17.08kb.
Школьный этап Всероссийской олимпиады школьников по искусству
48.63kb.
1. Корни Аникиных и Курбатовых из д. Суханова и Поповых из д
303.25kb.
Закон движения материальной точки, движущейся по прямой, имеет вид
70.42kb.
Обобщить и систематизировать знания, активизировать познавательную деятельность учащихся, показать межпредметную связь химии и географии
100.51kb.
1. Российский экспорт вооружений и военной техники
101.18kb.
Сравнение методов реконструкции деревьев Исходное дерево: 3 5 2 1
25.88kb.
Селективный металлодетектор инструкция по эксплуатации
406.86kb.