Синтаксический анализ английского языка с грамматикой связи

Каждый из замысловатых боксов-шаблонов с надписью является соединителем. Соединитель подбирается путем сопоставления соответствующих соединений (соответствующая форма обращается в противоположное направление). Именно один из соединителей, привязанных к определенной черной точке, должен быть удовлетворительным (остальные, если таковые имеются, не должны использоваться). Таким образом, cat требует D либо 0 соединитель слева или соединитель S справа от него. Собрав соответствующую пару соединителей вместе, становится возможным изобразить связь между этой парой слов.

Следующая диаграмма показывает, как требования связи удовлетворены в предложении The cat chased a snake.

Легко заметить, что Mary chased the cat,и the cat ran также предложения данной грамматики. Последовательность слов: the Mary chased cat не является этим языком. Любая попытка удовлетворить требования связи в ней приводит к нарушению одного из трех правил. К примеру:

По аналогии ran Mary, и cat ran chased не являются частью этого языка.

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

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

«+» или «суффикс» в названии соединителя указывает направление (относительное слово, если оно определено), в котором должен лежать соответствующий соединитель (если таковые имеются). & при двух формулах является удовлетворительным для обеих формулы. Или при двух формулах требует, чтобы ровно одна из формул должна быть удовлетворена. Порядок аргументов и операторов является важным и существенным. В дальнейшем, слева от соединителя выражается ближнее слово, к которому он подключается. Таким образом, при использовании catобъект, определяющий его (с которым он связан D-соединителем) должен быть ближе, чем глагол (который связан с 0 - соединителем).

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

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

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

Другая особенность лексической системы - то, что она позволяет конструировать полезные вероятностные модели языка. Это позволило исследователям создавать лексические версии других грамматических систем, примыкающие к дереву грамматики [13]. Лафферти и современные авторы также создали подобную вероятностную модель для грамматики связей [11].

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

3. В английском языке существительное может быть либо определенным, либо нет, независимо от того, используется оно в качестве предмета, объекта, или даже если это - часть фразы предложения. Алгебраическая форма записи, которую мы разработали для выражения грамматики связи, использует в своих интересах эту ортогональность. В любой лексической грамматической системе, если она используется человеком, должна быть такая возможность. В нашем современном он-лайн словаре слово cat может обозначаться 369 различными способами, а для time это число - 1689. Компактная формула грамматики связи объединяет это большое количество возможностей, и может быть легко записанной и понятной для человека.

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

Нашим вторым результатом является построение словаря грамматики связи для английского языка. Цель, которую мы поставили перед собой, состояла в том, чтобы создать грамматику связи, которая может отличить, максимально точно, синтаксически корректные английские предложения от неправильных. В качестве нашей модели мы выбрали формальный английский или английский язык газетного стиля. Результат – грамматика связи, включающая примерно 800 определений (формул) и 25000 слов, которые включают многие явления английской грамматики. Он охватывает: согласуемые существительные-глаголы, вопросы, императивы, комплексные и неправильные глаголы, многие типы существительных, причастия совершенного и несовершенного вида в субстантивных словосочетаниях, запятые, различные типы прилагательных, предлоги, наречия, притяжательные местоимения, координационные союзы, неограниченные зависимостей и многое другое.

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

Обе наши программы (написанные в ANSI-C) и наш словарь через анонимный доступ к ftp можно найти в Интернете. Имея в наличии программы для экспериментирования, вам будет легче понять данную работу.

Организация данной работы

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

Пространственные ограничения препятствуют тому, чтобы мы детально представили многие другие аспекты нашей работы. Следующие параграфы затрагивают некоторые из них. Более детально обо всех этих вопросах говорится в нашем техническом отчете[14].

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

Координирование союзов создает проблемы для грамматики связи. Это происходит потому, что в таком предложении, как The dog chased and bit Mary логически должны быть связи между парами dog и bit и chased и Mary. Такие связи пересеклись бы. Мы разработали схему, которая обрабатывает подавляющее большинство способов использования таких союзов, и включили их в нашу программу. Существование такого соединения в предложении изменяет грамматику слов в нем. Тот же алгоритм анализа затем используется на полученных модификациях грамматики.

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

2. Обозначения и терминология.

2.1. Мета – правила.

Словарь грамматики связи состоит из набора записей, каждая из которых определяет требования связей одного или более слов. Эти требования определены посредством формулы соединителей, объединенных двоичными ассоциативными операторами & и or. Место определено посредством круглых скобок. Без потери общности мы можем предположить, что соединитель - просто символьная строка, заканчивающаяся как + or-.

Когда связь соединяется со словом, она связана с одним из соединителей формулы этого слова, и она, как говорят, удовлетворяет этот соединитель. Никакие две связи не могут удовлетворить один и тот же соединитель. У соединителей на противоположных концах связи должны быть имена, которые совпадают, слева она должна заканчиваться на +, справа ­– на -. Два соединителя совпадают только в том случае, если их строки одинаковы (но, не включая окончание + or-). Более общая форма соответствия будет представлена позже.

Соединители, удовлетворяющие связи, должны работать для удовлетворения целой формулы. Мы определяем понятие удовлетворения формулы рекурсивно. Чтобы удовлетворить & двух формул, обе формулы должны быть удовлетворены. Чтобы удовлетворить or двух формул, одна из формул должна быть удовлетворена. Иногда удобно использовать пустую формулу (" ()"), которая удовлетворена, без связей.

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

Планарность: связи над предложением и не пересекаются.

Связь: связи достаточны, чтобы соединить все слова последовательности вместе.

Упорядочивание: Когда соединители формулы пересекаются слева направо, слова, с которыми они соединяются, рассматриваются от ближнего к дальнему.

Исключение: Никакие две связи не могут соединить одну и ту же пару слов.

2.2. Дизъюнктивная форма

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

В дизъюнктивной форме у каждого слова грамматики есть отдельный ряд, связанный с ним. Каждый дизъюнктив соответствует одному определенному способу удовлетворить требования слова. Дизъюнктив состоит из двух упорядоченных списков имен соединителя: левый список и правый список. Левый список содержит соединители, которые соединяются слева от текущего слова (те, что заканчиваются на -), и правый список, содержащий соединители, которые соединяются справа от текущего слова. Дизъюнктив будет обозначен:

((L₁, L₂, . . . , L_m) (R_n, R_{n – 1}, . . . , R₁))

Где L₁, L₂, . . . , L_m – соединители, которые должны соединиться слева, и R₁, R₂, . . . , R_n– соединители, которые должны соединиться справа. Число соединителей в любом списке может быть нулевым. Запаздывание + or - может быть опущено с имен соединителя при использовании дизъюнктивной формы, так как в форме дизъюнктива направление неявно.

Для удовлетворения требования соединения слова, один из его дизъюнктивов должен быть удовлетворен (и никакие связи не могут присоединить егони к какому другому дизъюнктиву). Чтобы удовлетворить дизъюнктив, все его соединители должны быть удовлетворены надлежащими связями. Слова, с которыми связаны L₁, L₂... слева от текущего слова, монотонно увеличиваются при удалении от текущего слова. Слова, с которыми связаны R₁, R₂, … справа от текущего слова, монотонно увеличиваются при удалении от текущего слова.

Легко продемонстрировать, как перевести грамматику связи в дизъюнктивной форме в одну из стандартных форм Это может быть сделано путем простого переписывания каждого дизъюнктива как

( L₁ & L₂ & . . . & L_m & R₁ & R₂ & . . . & R_n )

и объединив все дизъюнктивы вместе с or оператором, получим соответствующую формулу.

Также просто перевести формулу в ряд дизъюнктивов. Это можно сделать, перечисляя все способы, которыми может быть удовлетворена формула. Например, формула:

(A– or ( )) & D – & (B+ or ( )) & (0 – or S+)

соответствует следующим восьми дизъюнктивам:

2.3. Наш словарный язык

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

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

Самое общее правило соответствия - просто таблица – часть грамматики связи, которая определяет все пары соединителей, которые соответствуют. Полученная грамматика связи все еще контекстно-свободна.

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

Имя соединителя начинается с одной или более прописных букв, сопровождаемых последовательностью строчных букв или *s. Каждая строчная буква (or *) является нижним индексом. Чтобы определить, соответствуют ли два соединителя, удалите замыкающий + or - и добавьте бесконечную последовательность *s к обоим соединителям. Соединители соответствуют, если, и только если, эти две строки соответствуют условию, которое * соответствует строчной букве (or*).

Например, S соответствует и Sp и Ss, но Sр не соответствует Ss. Точно так же D*u, Dmu соответствует и Dm, но не Dmc. Все четыре из этих соединителей соответствуют Dm.

Формула "((A–& B +) or ())" и для A-, и для B +, или ни для одного из них. Концептуально, тогда выражение "(+ & B +)" дополнительное. Так как оно часто встречается, мы обозначим его с изогнутыми фигурными скобками, следующим образом: {+ & B +}.

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

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

3. Пример

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

3.1. Некоторые простые соединители

Мы разработали объяснение того, как это работает шаг за шагом. Давайте, для начала, обратим наше внимание на следующие соединители: S, 0, A, D. (Представьте словарь, где все другие соединители удалены.)

S используется, чтобы соединить существительное с его глаголом. 0 используются, чтобы соединить глагол с его объектом. А соединитель используется, чтобы соединить прилагательное с его существительным. D для соединения детерминатива к его существительному. Заметьте, что этот соединитель опущен для имен собственных, дополнений, существительных во множественном числе и обязательный для исключительных существительных. Также обратите внимание, что значения индексов позволяют использовать его в качестве определителя для множественного и единственного числа существительных, но эффективно он может работать только с существительными в единственном числе. Точно так же соединитель S преобразован в нижний индекс, чтобы гарантировать согласование существительного и глагола.

Упорядочивание условий в этих выражениях важно. Например, тот факт, что для существительных A- выполняется слева, D-, что прилагательное должно быть ближе к существительному, чем детерминатив.

Вот некоторые решения, которые могут продемонстрировать то, что мы до сих пор описывали:

*a dog chase a cat

*black the dog died

*a / *the Mary chased the cat

*a dogs died

*dog died

3.2. Предлоги

J, M и соединители EV выдают предложные фразы. Соединитель J соединяет предлог со своим объектом. Заметьте, что в существительных, J-альтернатива 0-. Это означает, что существительное не может быть объектом и глагола, и предлога. Соединитель M используется, когда предложная фраза изменяет существительное, и соединитель EV используется, когда предложная фраза изменяет глагол. Следующие два примера демонстрируют это:

Заметьте, что аналогично соединителю A - для существительных, ® используется для соединителей M - для существительных и соединителей EV - на глаголах

3.3. Причастия

Соединитель M - для chased позволяет ему действовать как фраза причастия, изменяющая существительное, как показано в этих примерах.

I соединитель используется для инфинитивов в качестве:

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

Похожим способом соединитель T используется для причастий прошедшего времени. У причастий прошедшего времени есть T- ; формы глагола have имеют T +. Соединитель GI используется для причастий настоящего времени. У причастий настоящего времени есть соединитель GI-; у форм глагола be есть GI +. Соединитель AI используется для предикативных прилагательных. У прилагательных есть AI - соединитель; у форм be есть AI + соединитель

3.4. Вопросы

Соединитель SI используется для вопросов, где есть инверсия подчиненного глагола. На SI существительных - альтернатива S +, и на обратимых глаголах (is, has, did, must, etc.) SI + является альтернативой S–. Это позволяет

Wh – вопросы работают всевозможными способами; здесь будут обсуждаться только вопросы, включающие, who. Для вопросов подчиненного типа, где, who заменяет предмет, who имеет S + соединитель. Это позволяет

Для вопросов о типе объекта, где, who заменяет объект, используется соединитель B. У переходных глаголов есть соединители B-, как их альтернатива – 0 + соединители. Who has B + соединитель. Это позволяет

Исключениями являются следующие неправильные предложения:

*Did John chase

*Who did John chase Mary

*John did Mary chase

*Chased John Mary

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

*Who John chased

3.5. Придаточные предложения

Для придаточных предложений относительно их субъект-типа, где антецедент действует как предмет, соединитель B служит, чтобы соединить существительное с глаголом. У существительных есть B + соединитель. Заметьте, что это не обязательно; также & редактор с S +, SI - 0 +, и J + соединители, означая, что один из этих соединителей должен использоваться. У глаголов есть соединитель B-; если глагол в придаточном предложении субъективного типа, он не может образовать S-связи.

Для субъекта придаточного типа, местоимение who является обязательным. С этой целью у глаголов есть соединитель Z-Anded с их соединителем B-. У who есть Z + соединитель; поэтому может выполняться данное условие. Однако также есть соединитель C- anded с его Z + соединителем; что должно соединиться в обратном порядке с C + соединителем для существительных. Это позволяет следующее:

Для придаточных предложений относительно их объект-типа используется B + соединитель для существительных. Однако на сей раз other соединяется с другим соединителем B- для глаголов, который является 0 + соединителем и который также используется для объекта wh- вопросы.

В этом случае, относительное местоимение, who является дополнительным. Заметьте, что у существительных есть дополнительный C + и CL - соединители, которые являются конечными с S + соединителями. Они используются, когда существительное – предмет относительно объект-типа придаточных предложений.

Когда who не присутствует в предложении, соединитель C+ на предшествующем существительном соединяется непосредственно с C- по контексту относительного предложения:

Когда who присутствует, C+ на предшествовании соединяется с C- на who это вынуждает CL+ соединиться с CL- по контексту предложения:

Эта система отклоняет следующие неправильные предложения:

*The dog chased cats died

*The dog who chase cats died

*The dog who John chased cats died

*The dog John chased cats died

*The dog who chased died

Следующие неправильные конструкции приняты, но могут быть удалены в последующей обработке:

*The dog did John chase died

*The dog who John died Mary chased died

4. Алгоритм

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

Алгоритм наиболее легко объяснить, определяя структуру данных для представления 2.2. дизъюнктов. У дизъюнкта d есть указатели на два связанных списка соединителей. Эти указатели обозначены left[d] и right[d], если c будет соединителем, то next[c] обозначит следующий соединитель после c в списке. У следующего поля последнего указателя списка будут NIL значения.

Например, предположим дизъюнкт d = ((D, Q) ()) (использование формы записи из раздела 2). Тогда left[d] указал бы на соединитель 0, nerf[left[d]] укажет на соединитель D, и next[next left[d]]] был бы NIL. Точно так же right[d] = >NIL.

Чтобы дать некоторую информацию о том, как алгоритм работает, рассмотрим ситуацию после того, как возникнет связь между соединителем I' в слове L, и соединителем r' в слове R. (Слова последовательности, которая будет проанализирована, пронумерованы от 0 до N — 1.) Для удобства мы определяем I и r будут next[l'] и next[r'] соответственно. Ситуация отражена в следующей схеме:

Здесь квадраты над словами L и R представляют узел структуры данных, соответствующий слову. Прямоугольник выше каждого из них представляет один из (возможно многих) дизъюнктов для слова. Небольшие квадраты, на которые указывают дизъюнкты, представляют соединители.

Как мы придем к расширению частичного решения в области строго между L и R? (Эта область будет обозначена (L..., R).), В первую очередь, при отсутствии слов в этой области (L = R + 1) тогда для частичного решения, мы допустим, что или l?NIL или r?NIL. Если l = r = NIL тогда эта область в порядке, и мы можем продолжать строить оставшуюся часть решения.

Теперь предположите, что область между L и R содержит, по крайней мере, одно слово. Чтобы присоединить слова этой области к остальной части предложения должна быть, по крайней мере, одна связь или от L до некоторого слова в этой области, или от R до некоторого слова в этой области (так как никакое слово в этой области не может соединиться со словом за пределами диапазона [L..., R], и что-то должно соединить эти слова с остальной частью предложения).

Так как соединитель l’ уже использовался в создаваемом решении, это решение должно использовать остальную часть соединителей дизъюнкта, в котором находится l’. То же самое касается г’. Единственные соединители этих дизъюнктов, которые могут быть вовлечены в (L, ..., R) область являются те из списка, которые начинаются с l и r. (Использование любого другого соединителя на этих дизъюнктах в этой области нарушило бы требование упорядочивания.) Фактически, все соединители этих списков должны использоваться в этой области, чтобы иметь удовлетворительное решение.

Предположим теперь, что l не NIL. Мы знаем, что этот соединитель должен соединиться с некоторыми дизъюнктами на некотором слове в области (L .... R) (его нельзя связать с R из-за правила исключения.) Алгоритм подбирает все возможные подобные слова и дизъюнкты. Предположим, что он находит слово W и d, слово W и дизъюнкт d на W таким образом, что соединитель l соответствует left[d].Теперь мы можем добавить эту связь к нашему частичному решению.

Ситуация показана в следующей схеме.

Как мы определим, может ли это частичное решение быть расширено на полное решение? Мы сделаем это, разрешив две проблемы, подобные проблеме, с которой мы начали. В частности мы спрашиваем, может ли решение быть расширено на диапазон слова (L ,..., W) с использованием списков соединителя, начинающихся next[l] и next [left[d]]. Мы также спрашиваем, может ли решение быть расширено на диапазон слова (W ,..., R) с помощью использования списков соединителя, начинающихся с right[d] и r. Заметьте, что в последнем случае, проблема, которую мы решаем, кажется поверхностно отличающейся: граничные слова уже не соединены вместе связью. Это отличие фактически не имеет последствий, потому что пара связей (L к R и L к W) играет роль, которую играла бы прямая связь от W до R: (1) они отделяют область (W ,..., R) от всех других слов, и (2) они служат, чтобы соединить слова W и R вместе.

Мы должны рассмотреть один из других вариантов. Найдем решение со связью между словами L и W и связью между словами W и R, (что приведет к решению, где график слова/связи циклический.) Алгоритм обрабатывает это предположение, пытаясь сформировать связь между right[d] и r. Если они соответствуют друг другу, то происходит третий рекурсивный вызов, решающий третью проблему, аналогичную нашей исходной проблеме. В этой проблеме диапазон слова – (W ,..., R), а списки соединителя, которые будут удовлетворены, начинаются с next [right[d] и left[r].

Подобного анализа достаточно, чтобы обработать случай, когда l - NIL.

У описанного алгоритма есть экспоненциальное время выполнения частного случая. как функции N, – числа слов в последовательности, которая будет проанализирована. Это может быть легко преобразовано в эффективный динамический алгоритм программирования при помощи memoization.

Время выполнения теперь ограничено числом различных возможных рекурсивных вызовов, умноженных, на время, используемое при каждом вызове. Рекурсивный вызов полностью определяется путем определения указателей l и r, (они уникально определяют L и R.), затраты для данного вызова ограничены общим количеством дизъюнктов в последовательности слов.

Если мы предположим, что d - число дизъюнктов, и c - число соединителей, то время выполнения будет O (c²d). Для фиксированной грамматики связи, d = O (N) и c = O (N), таким образом, время выполнения O (N³).

Наши технические отчеты описывают этот алгоритм более подробно. Они содержат псевдокод для данного алгоритма [14], аргумент для корректности [14] и изящное повторение для числа связей предложения [11].

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

5. Ускорение

Как указано во введении, в словаре грамматики связи со значительным покрытием английской грамматики число дизъюнктов на многих словах становится довольно большим. Таким образом, постоянная d в анализе в конце последнего раздела довольно велика. Мы разработали и реализовали несколько экономящих время схем, которые работают в комплексе с алгоритмом предыдущего раздела.

5.1. Сокращение

Наш первый подход основывается на следующем наблюдении: в любой определенной последовательности слов, которые будут проанализированы, большинство дизъюнктов, не важно, содержат они соединитель или нет, которым не соответствует никакой другой соединитель для слов в последовательности. Чтобы быть более точными, предположите, что у слова W есть дизъюнкт d с соединителем C в списке. Если ни у какого слова справа от W нет соединителя (указывающего налево), который соответствует C, то дизъюнкт не может быть ни в какой связи. Этот дизъюнкт может быть удален, не изменяя набор связей. Удаление такого дизъюнкта вызывают шагом сокращения. Сокращение состоит из повторения шага сокращения, до тех пор, пока это возможно.

Набор дизъюнктов образуется слева (после того, как сокращение завершено), независимо от порядка, в котором применены шаги, (сокращение имеет свойство Church–Rosser.) Поэтому мы выбираем упорядочивание, которое может быть эффективно реализовано. Было бы идеально, если бы мы могли достигнуть времени выполнения для сокращения, которое линейно в числе соединителей. Схема, которую мы предлагаем, априори привязана к времени выполнения, но на практике это, кажется, работает в линейном времени.

Серия последовательных передач через слова сделана поочередно слева направо и справа налево. Два типа передач аналогичны, таким образом, этого достаточно, чтобы описать передачу слева направо. Передача обрабатывает слова последовательно, начиная со слова 1. Рассмотрите ситуацию после того, как слова 1 ,..., W — 1 будут обработаны. Набор S соединителей вычислен. Это - набор соединителей, который существует в правильных списках дизъюнктов слов 1 ,..., W — 1, которые не были удалены. Чтобы обработать слово W, мы рассматриваем каждый дизъюнкт d в W поочередно. Для каждого соединителя c в левом списке d, мы ищем набор S, чтобы увидеть, содержит ли он соединитель, который соответствует c. Если один из соединителей d ничего не содержит в S, то мы применяем сокращение, продвигаемся в d (мы удаляем d). Каждый правильный соединитель каждого остающегося дизъюнкта из W теперь включен в набор S. Это завершает обработку слова W.

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

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

Несмотря на то, что мы знаем о нетривиальном привязывании числа передач, мы никогда не сталкивались с тем, чтобы требовалось больше, чем есть памяти. Таблица ?? показывает типичный пример сокращения числа дизъюнктов, достигнутого сокращением.

5.2. Структура данных быстрого соответствия

Внутренний цикл в алгоритме поиска слова W и дизъюнкта d этого слова, где левый соединитель соответствует l либо первый правильный соединитель соответствует r, описан в разделе 4. Если бы был быстрый способ найти все такие дизъюнкты, то могла бы быть достигнута значительная экономия. Быстрота - свойство структуры данных, которое основывается на хешировании. Ускорение, предоставленное этим методом, является примерным числом различных типов соединителя, которых около 30 в нашем текущем словаре.

5.3. Сокращение энергии

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

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

6. Зависимость и категориальные грамматики

6.1. Формализм зависимости

Есть большое собрание произведений, основанных на идеи, что лингвистический анализ может быть сделан, путем изменения связи между словами. Их называют по-разному: системами зависимости [5], синтаксисом зависимости [10], грамматикой зависимости [3, 4], или грамматикой слова [6, 7], В грамматике зависимости, грамматическое предложение обеспечено структурой зависимости, которая подобна связи. Эта структура, как определено Мелкуком [10], состоит из ряда планарных направленных дуг между словами, которые формируют дерево. У каждого слова (кроме корневого слова) есть дуга от одного к другому слову, и никакая дуга не может быть направлена к корневому слову. В связи (в противоположность структуре зависимости) связи маркированы, не ориентированы, могут формировать циклы, и не имеют корневого слова.

Гэйфмен [5]был первым, кто фактически сформулировал формальный метод выражения грамматики зависимости. Он показывает, что такая модель контекстно-свободна.

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

Необходимо взять грамматику зависимости в форме записи Гэйфмена и генерировать грамматику связи, которая принимает тот же язык. В связи с этим, связь, которая следует из разбора предложения, совпадает с соответствующей структурой зависимости. Это означает, что наш алгоритм для анализа связи может легко быть применен к грамматике зависимости. Число дизъюнктов в получающейся грамматике связи – самое большее квадратичное в числе правил грамматики зависимости. Ни один из алгоритмов, которые были описаны для анализа зависимости [3, 15, 7], кажется, не имеет никакого сходства с нашим. Поэтому вероятно предугадать, что наши алгоритмы и методы могли бы быть очень полезными для того, чтобы непосредственно проанализировать грамматику зависимости.

Результат Гэйфмена показывает, что возможно представлять грамматику связи как грамматику зависимости (они обе контекстно-свободны). Но это сопоставление мало полезно, если проанализированные структуры показывают, что результат полностью отличается.

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

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

Мы не имеем формы записи для систем зависимости, которая является лексической, или столь же краткой и хорошо подходящей для грамматики естественного языка, чем грамматика связи. Была проведена работа над созданием грамматики зависимости для английского языка [7, 3], но мы не имеем реализации грамматики зависимости ни для одного другого естественного языка, который почти так же сложен как наш.

6.2. Категориальные грамматики

Другая грамматическая система, известная как категориальная грамматика [1], имеет некоторое свойство, способное объединить грамматики. Ниже мы показываем, как выразить любую категориальную грамматику столь же кратко, как грамматику связи. Более сложно выразить грамматику связи, чем категориальную грамматику.

Так же, как в грамматике связи, каждое слово категориальной грамматики связано с одним или более символьными выражениями. Выражение - или атомарный символ или пара выражений, объединены одним из двух типов бинарных операторов: / и \.

Предложение выражено в языке, определенном категориальной грамматикой, если, после выбора одного выражения, связанного с каждым словом, есть деривация, которая преобразовывает выбранную последовательность выражений в S, единственное выражение, состоящее из специального атомарного символа. Деривация продолжается, комбинируя два соседних выражения в одно при использовании одного из следующих правил:

Здесь e и f являются произвольными выражениями, а f\e и f/e – другими выражениями, построенныеми с использованием e и f. В обоих случаях эти два объединяемых выражения должны быть смежными в текущей последовательности выражений. Каждая комбинационная работа производит одно выражение (которое находится под чертой) и сокращает количество выражений до одного. После n — 1 примененных операций, предложение, длиной n может быть уменьшенным до одного выражения.

Например, рассмотрим следующую категориальную грамматику [9]:

Вот деривация для предложения Harry likes peanuts passionately.

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

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

Допустим d - категориальное выражение грамматики. Мы покажем, как создать эквивалентное выражение E (d) для грамматики связи. Если у слова w есть набор {d₁, d_2, … d_k} категориальных выражений, тогда мы дадим этому слову выражение грамматики следующей связи:

E(d₁) or E(d₂) or … or E (d_k)

Функция E(.) определена рекурсивно следующим образом:

E(f/e) = f/e – or f/e+ or (e+ & E(f))

E(e\f) = e\f – or e\/+ or (e– & E(f))

Здесь А - позиция для любого атомарного символа категориальной грамматики: и A, f/e и e\f – имена соединителя в формулах грамматики связи.

Стена имеет формулу S +.

Вот грамматика связи, соответствующая категориальной грамматике выше:

WALL: S+;

Peanuts: NP+ or NP –

Harry:

(NP – or NP+)

or (S/<S\NP> –

or S/<S\NP>+

or (S\NP+ & (S+ or S – )));

likes:

<S\NP>/NP – or <S\NP>/NP+

or (NP = & (S+ or(S\NP – or S\NP+

or (S – & (NP – or NP+))));

passionately:

<S\NP>/<S\NP> – or <S\NP>/<S\NP>+

or (S\NP – & (S\NP – or S\NP+

or (S – & (NP – or NP+))));

(Здесь мы заменили круглые скобки в категориальных выражениях грамматики на скобки, при использовании их в выражении грамматики связи.)

Эта грамматика связи дает следующий анализ предложения, показанного выше:

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

7. Замечания

Грамматика связи стала основанием для некоторых других научно-исследовательских проектов. Джон Лафферти [11] предложил создать и автоматически настроить вероятностный язык, основанный на модели грамматики связи. Предложенная модель корректно охватывает триграммы и грамматические ограничения в одной платформе. Эндрю Хант разработал новую модель отношения просодии и синтаксиса на основе грамматики связи. Он реализовал модель, и ее предварительные испытания показали намного лучшие результаты, чем другими модели. Том Брехони изменил наш синтаксический анализатор, чтобы обнаружить ошибки, которые делают франкоязычные, когда пишут на английском языке.

Список использованной литературы

1. Y. Bar–Hillel, Language and information; selected essays on their theory and application. Addison–Wesley, 1964.
2. Gormen, T. II., C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw–Hill, 1990..
3. Fraser, N., "Parsing and dependency grammar," In: Carston, Robyn (ed.) UCL Working Papers in Linguistics 1, University College London, London, 1989 Pages 296–319.
4. Fraser, N., "Prolegomena to a formal theory of dependency grammar," In: UCL Working Papers in Linguistics 2, University College London, London, 1990 Pages 298–319.
5. Gaifman, II., "Dependency systems and phrase–structure systems," Information and Control 8, 1965, Pages 304–337.
6. Hudson, R., Word Grammar, Basil Black– well, 1984.
7. Hudson, R., "Towards a computer testable word grammar of English," In: Carston, Robyn (ed.) UCL Working Papers in Linguistics 1, University College London, London, 1989, Pages 321–339.
8. Hudson, R., English Word Grammar, Basil Blackwell, 1990.
9. Joshi, A. K., "Natural Language Processing," Science, Volume 253, No. 5025, (Sept. 13, 1991), Pages 1242–1249.
10. Melcuk, I. A. Dependency Syntax: Theory and Practice, State University of New York Press 1988.
11. Lafferty, J, D. Sleator, D. Temperley, "Grammatical Trigrams: A Probabilistic Model of Link Grammar," Proc. of the 1992 A A M Fall Symp. on Probabilistic Approaches to Natural Language, and Technical report CMU–CS–92–181, School of Computer Science, Carnegie Mellon University, Sept 1992.
12. Oehrle, B. T., E. Bach, and D. Wheeler, Editors Categorial Grammars and Natural Language Structures D. Reidel Publishing Company, 1988.
13. Y. Schabes. "Stochastic lexicalized tree– adjoining grammars." In Proceedings of COLING–92, Nantes, France, July 1992.
14. Sleator, D. D., D. Temperley, "Parsing English with a l ink Grammar," Technical report CMU–CS–91–196, Carnegie Mellon University, School of Computer Science, October 1991.
15. van Zuijlen, J., M., "Probabilistic methods in dependency grammar parsing," Proceedings of the International Workshop on Parsing Technologies, Carnegie Mellon University, 1989, Pages 142–250.