Распознавание речи. Обработка текстов на естественном языке.
Пониманием и синтезом текста на естественном языке занимается дисциплина, именуемая обработкой естественного языка (Natural Language Processing, NLP).
Она является частью таких направления научных исследований как искусственный интеллект и компьютерная лингвистика.
Понимание применительно к человеку характеризуется как некое субъективное состояние: если человек чувствует, что он понял нечто, то считается, что это так и есть. Применительно к компьютеру такая характеристика понимания не может быть признана приемлемой: нам нужны четкие и точно фиксируемые признаки того, что система поняла что-либо. В общем случае, впрочем, достаточно, чтобы воспринятая информация влияла не просто на объем накопленных знаний, но и изменяла алгоритм принятия решений или вносила изменение в структуру ранее полученных знаний – именно в этом случае мы имеем право сказать, что система нас поняла ( в том числе, может быть, и неправильно). То есть близким по смыслу к пониманию словом применительно к компьютеру будет «усвоение».
Естественный язык в отличие, например, от компьютерных (алгоритмических) языков формировался во многом стихийно, не формализовано. Это обуславливает целый ряд сложностей в понимании текста, вызванных, например неоднозначным толкованием одних и тех же слов в зависимости от контекста, который может быть и неизвлекаем в принципе из самого текста. Следовательно, этот контекст или знание о предметной области в систему должны быть заранее внесены. К тому же зачастую практические задачи требуют точного определения времени, места того, что описано в тексте, точной идентификации людей и т.д., в то время как подобная информация находится за пределами данного текста. В этом случае система может как не обрабатывать эту информацию, так и оставить ее до выяснения контекста и даже попытаться проявить инициативу в выяснении контекста, например, в диалоге с оператором, задающим ввод текста. То, как ведет себя система в подобной ситуации, определяется стилем и схемой работы системы.
Основные проблемы понимания текста таковы:
Здесь и далее ЕЯ- естественный язык, БЗ – база знаний. Кроме указанного на схеме в состав лингвистического процессора должна быть включена подсистема первоначального или постоянного обучения (например, ввод словаря лексем и их морфологических признаков, ввод первоначальных данных о проблемной области – «априорных» знаний).
Этап работы системы, включающий формирование знаний и, возможно, формирование запросов к базе знаний, называется проблемным анализом.
В случае, если лингвистический процессор ориентирован только на машинный перевод с одного ЕЯ на другой, его схема может быть более простой:
Или даже такой
Впрочем, второй вариант значительно хуже.
На каждом из этапов работы процессора(морфологический, синтаксический, семантический, проблемный анализ) вырабатываются определенные структуры: морфологическая, синтаксическая, семантическая и структура базы знаний.
Кроме того, на каждом из этапов используются различные дополнительные структуры данных и элементы баз данных. Так на этапе морфологического анализа необходим морфологический словарь конкретного ЕЯ, в машинном переводе используются комбинаторные словари (например, англо-русский, русско-английский). Чтобы сделать систему универсальной по отношению к различным ЕЯ и различным предметным областям могут использоваться структуры специального вида, описывающие конкретную синтаксическую систему, семантическую систему и проблемную область. Эти структуры могут представлять из себя текст программ на специальном языке, описывающем с одной стороны структуру синтаксиса, семантики или проблемной области, а с другой стороны -
Введем некоторые основные понятия.
Дискурс – связный текст.
Предложение - единица речи, состоящая из некоторого числа связанных слов и содержащая сообщение о чем-либо.
Словосочетание - единица речи, состоящая из двух или нескольких слов, связанных подчинительной связью (согласованием, управлением или примыканием) и не являющаяся сообщением.
Слово – основная единица речи, служащая для обозначения предметов ( в т.ч. одушевленных), действий, свойств предметов и т.д.
Лексема – слово в совокупности всех его возможных сочетаний (например, «корова», «коровы», «корове» и т.д. – все это одна лексема).
Словоформа – слово как конкретное сочетание звуков (то есть, «корова», «коровы», «корове» и т.д. – все это разные словоформы).
Морфема (часть слова) - наименьшая языковая единица, обладающая значением. Деление морфем на части приводит только к выделению незначимых элементов — фонем (звуков). Морфемы делятся на корни и аффиксы, аффиксы – в свою очередь подразделяются на префиксы(приставки), суффиксы и постфиксы (окончания).
В большинстве концепций морфема рассматривается как абстрактная языковая единица.
Конкретная реализация морфемы в тексте называется морфой или (чаще) морфом.
При этом морфы, представляющие одну и ту же морфему, могут иметь различный фонетический облик в зависимости от своего окружения внутри словоформы. Совокупность морфов одной морфемы, имеющих одинаковый фонемный состав, носит название алломорф (например корни «бег-» и «беж-» являются алломорфами).
Представляется, что морфему-корень можно представлять как совокупность всех вариантов данного корня, а о морфах говорить как о конкретных корнях.
Корень – основная значимая часть слова. Является обязательной частью любого слова - без корней слов не существует.
Аффикс – вспомогательная часть слова, присоединяемая к корню и служащая для словообразования и выражения грамматического значения. Аффиксы не могут самостоятельно, без корня, образовывать слово. Одинаковые аффиксы встрчаются в разных словах.
Синонимы – разные по написанию, но одинаковые по значению, слова (например,
«железо» и «булат»).
Омонимы – слова, имеющие одинаковое написание, но разное значение (например, «пол» в значении части помещения и в значении принадлежности к тому или иному способу продолжения рода).
Рассмотрим в общих чертах содержание каждого из этапов работы лингвистического транслятора.
На этапе морфологического анализа определяются
1) принадлежность каждой словоформы к определенной морфеме, находящейся в словаре,
2) грамматические признаки для каждой словоформы. Так для существительных этими признаками будут: род, число, падеж и склонение, для прилагательных: род, число и падеж, для глаголов – время, лицо, число, спряжение, вид, для местоимений – число и лицо.
Таким образом, для морфологического анализа необходим словарь основ слов и словоформ с их грамматическими признаками в зависимости от различных изменяемых частей слова (аффиксов) (для русского языка это окончания и, возможно, суффиксы).
На этапе синтаксического анализа формируется синтаксическая структура входного предложения: определяется синтаксическая роль слов в предложении (подлежащее, сказуемое, определения, дополнения, обстоятельства) и определяется характер синтаксической связи между словами.
Подлежащим в русском предложении может быть существительное ( в том числе имя собственное) или местоимение в именительном падеже. В английском языке, где существительные и местоимения не склоняются, подлежащее определяется как первое существительное или личное(?) местоимение с начала простого предложения.
Сказуемое в русском языке – это глагол, связанный с подлежащим и согласованный с ним в лице и числе, в английском языке подлежащее – первый глагол с начала простого предложения.
Подлежащее и сказуемое называются главными членами предложения.
Дополнение – существительное или местоимение, связанное со сказуемым в падеже.
Например, «я слышу музыку»: «слышу» - сказуемое, «музыку» - дополнение.
Обстоятельство – существительное или наречие, связанное со сказуемым только семантически (по смыслу). Например, «я сильно расстроился»: «сильно» - обстоятельство.
«Я был в городе»: «в городе» - тоже обстоятельство.
Определение – это прилагательное или порядковое числительное, связанное в русском языке с подлежащим или дополнением в числе и падеже, а в английском – относящееся к подлежащему или дополнению, идущему первым после него ( первым среди подлежащих и дополнений).
На этапе семантического анализа формируется семантическая структура входного предложения. Это может быть, например, дерево, построенное на основе семантических падежей Филмора или другая структура, описывающая смысловую взаимосвязь между словами предложения. Для построения этих структур может использоваться синтаксическая структура, полученная на предыдущем этапе и специальные семантические словари и (или) описание на определенном языке семантики языка.
Основными методами формальной семантики являются метод компонентного анализа и метод семантических падежей.
Метод компонентного анализа исходит из предположения, что посредством комбинаций конечного числа семантических компонентов можно описать неограниченное множество лексических единиц. На верхнем уровне иерархии все слова разбиваются на несколько категорий (например, физические объекты, действия и т.д.), далее эти категории разбиваются на подкатегории. Подкатегории внутри одной категории имеют общие друг с другом признаки (интегральные) и признаки, позволяющие отличить их друг от друга (дифференциальные). Членение продолжается до тех пор, пока все необходимые слова не окажутся охваченными.
Пример. Диван — вид мягкой мебели, предназначенной для сидения, лежания. В это понятие включаются следующие подкатегории: Тахта — широкий и невысокий диван без спинки. Софа — мягкий широкий диван с подлокотниками и низкой спинкой. Канапе — небольшой диван с приподнятым изголовьем. Оттоманка — широкий и мягкий диван с подушками, заменяющими спинку. Диван-кровать — раскладной диван с откидной спинкой. Для всех этих видов дивана интегральными признаками являются принадлежность к мягкой мебели и предназначенность для сидения и лежания. Дифференциальными признаками являются ширина, высота, наличие и высота спинки, ее способность откидываться, наличие подлокотников и подушек.
Филмор разделял значение слова на собственно значение и пресуббопозицию.
Применительно к нашему разговору значением является принадлежность к родительской категории, пресубпозицией – принадлежность к конкретной категории. Так выражение «Тахта – это не канапе» не означает, что тахта – это не диван, а «Вася – не мальчишка» не означает, что Вася не относится к людям мужского пола.
Смысл предложения понимается в компонентном анализе как сумма смыслов входящих в него слов.
Метод семантических падежей является логическим продолжением метода компонентного анализа. Чарльз Филмор принял идею компонентного анализа и развил ее вплоть до выделения семантически неделимых смысловых единиц (атомов смыла).
Согласно общепринятым взглядам центральной единицей смысла является предикат, под которым, как правило, подразумевается действие, выражаемое глаголом. Предикат имеет ряд атрибутов. По Филмору эти атрибуты имеют определенную семантическую роль. Он выделяет следующие роли:
Собственно эти роли и называются семантическими падежами Филмора.
На этапе проблемного анализа формируется утверждение для базы знаний или запрос к этой базе. Также, возможно, происходит поиск и разрешение логических противоречий в базе знаний. Проблемный анализ использует семантические структуры, полученные на предыдущем этапе и описание проблемной области, на которую настроена система.
На основе запроса к базе знаний, полученного на предыдущем этапе, и самой базы знаний формируется семантическая структура, которая затем переводится в синтаксическую и, далее, морфологическую структуру, после чего подбираются конкретные морфы из морфологического словаря и формируется готовый текст на ЕЯ.
Модель концептуальной зависимости была теоретически разработана в 1968-75 годах в Йельском университете группой, руководимой Робертом Шенком, и представляла новую теорию описания семантики языка. Отрицалось влияние синтаксиса и морфологии на семантику. Семантическая модель представлялась в виде так называемой сети концептуализаций. Основная единица семантики в этом подходе – т.н. концептуализация, - представляет из себя совокупность действия, его атрибутов (концептуальные или, они же, семантические падежи), участников действия и их характеристики.
Понятие концептуализации примерно соответствует в русском языке понятию «событие». Сеть концептуализаций – это граф, вершины которого могут относиться к одному из семи классов (типы вершин):
1) PP - имена физических объектов (существительные),
2) ACT - имена действий (глаголы),
3) PA - характеристики объекта (прилагательные),
4) AA - характеристики действий (наречия).
5) State – состояние.
6) LOCK – место
7) T – время.
Дуги могут быть помечены более чем одним символом. Существует следующие типы дуг:
1. Дуги первого типа - определяют роли участников действия (АСТ). Подразделяются на :
Дуга, соединяющая действие (оно же - предикат) с актором (агентом), выполняющим действие. Эта дуга на графе соответствует самому понятию концептуализации (события). Если есть действие, но нет актора, эта дуга все же должна присутствовать и соединяться одним концом с действием (ACT), другой конец не должен быть присоединен ни к чему.
Дуга, соединяющая действие (предикат) с объектом действия.
Дуга R, соединяющая действие (предикат) с лицом-адресатом (новым владельцем) и лицом-источником (первоначальным владельцем) объекта
Дуга D, соединяющая действие (предикат) с первоначальным и последующим местом объекта.
Дуга I, связывающее действие (предикат) с инструментом, выражаемым как другая концептуализация ( то есть не как предмет, а как событие).
2. Дуги второго типа могут присоединяться как к действию, так и к самой концептуализации . Включают в себя:
Дуга, связывающая действие (концептуализацию) ACT с характеристикой действия AA (то есть с обстоятельством в форме наречия).
Дуга, связывающая действие (концептуализацию) с местом (LOCK).
Дуга, связывающая действие (концептуализацию) с временем (T).
3. Дуги третьего типа – это дуги, выражающие причинные взаимосвязи между двумя действиями или между действием и состоянием.
Дуга R связывает одно событие (действие) A с другим событием (действием) B, если A является причиной B. Отношение такого типа называется причинной каузацией (reason causation).
Дуга E связывает событие (действие) A с событием (действием) B, если A делает возможным B. Такое отношение называется каузацией возможности.
Дуга r связывает событие (действие) A c B, если B является следствием завершения A. Это так называемая результирующая каузация.
Все действия в модели концептуальных зависимостей рассматриваются как комбинации 11 примитивных действий:
1). PROPEL – «применить силу к»
2). MOVE – «двигать часть тела»
3). INGEST – «ввести что-либо внутрь кого-либо (актора)»
4). EXPREL – «вывести что-либо наружу из кого-либо (актора)»
5). GRASP – «схватить физический объект»
6). PTRANS – «переместить что-либо»
7). ATRANS – «изменить какое-либо отношение»
8). SPEAK –«произвести звук»
9). ATTEND – «направить внимание или другие чувства на некоторый стимул»
10). MBUILD – «создать или объединить мысли»
11). MTRANS – «передать информацию».
Модель семантики предпочтения разрабатывалась в 1964-1972 в Стэнфордском университете под руководством Уилкса. Элементами семантики здесь являются:
Семантические формулы представляют из себя последовательности заключенных в скобки семантических элементов-атомов смысла, называемых в этой модели классификаторами.
В разных работах этого направления вводится различное число классификаторов (80-100), объединяемых в 15-20 классов, обозначаемых звездочкой. Например, к числу классификаторов класса *ЖИВОЕ относятся классификаторы ЭТО, ЧЕЛОВЕК, НАРОД, ЗВЕРЬ, класс *ЧЕЛОВЕК; к классификаторам класса *МЕСТО относятся ЭТО, ТОЧКА, ПРОСТРАНСТВО, ЧАСТЬ;
Таким образом, классификаторы объединены в иерархию с множественным наследованием. Например, для слова СТРЕЛЯТЬ Уилксом строится формула:
((*ЧЕЛОВЕК СУБЪЕКТ) ((*ЖИВОЕ ОБЪЕКТ)
((ПОРАЗИТЬ ЦЕЛЬ) ((ОРУЖИЕ ИНСТРУМЕНТ)
((ПУЛЯ ПЕРЕМЕЩАТЬ) ПРИЧИНА)))))
означающая, что это действие совершается человеком, который для поражения живого существа использует инструмент, вызывающий движение пули. Стоит отметить, что в формулу входят не слова естественного языка, а именно атомы смысла (классификаторы).
Образцы (шаблоны), как уже было сказано, служат для представления сообщений. Они разделяются у Уилкса на простые и полные образцы. Простой образец представляет тройку определенных ранее семантическими формулами элементов. Такой обрзец несет обобщенную информацию о многих конкретных высказываниях. Например тройка ЖИВОТНОЕ+БЫТЬ+ВИД может означать и «Васька - (есть) кот» и «Шарик – (есть) пес».
Существуют определенные правила получения полных образцов. Два образца, выделенные в предложении, с помощью правил следования, отражающих их смысловую совместимость, объединяются в один образец.
Процесс анализа текста построен следующим образом. С помощью специальных маркеров выполняется фрагментация текста. Далее анализируются отдельные фрагменты текста. Для этого всем словам фрагмента сопоставляются их значения из словаря. Далее на фрагмент текста делается попытка наложения каждого из простых образцов, известных системе. Образец считается совпавшим, если каждый из его элементов совпадает по смыслу с элементами данного фрагмента текста. Далее из простых образцов строятся полные образцы после анализа и добавления тех слов предложения, которые не вошли в простой образец. Таким образом обрабатываются все предложения во фрагменте текста.
Далее определяется семантическая близость предложений внутри текста. Для этого в системе вводится понятие семантической близости двух полных образцов. С этой целью для каждых двух полных образцов подсчитывается число классификаторов, входящих в оба образца и входящих только в какой-то один из них.
Модель Смысл<->Текст.
Родоначальником этой модели принято считать советского ученого Жолковского. Для описания существа и степени семантического сходства разных слов вводится язык семантических множителей, особенностью которого являются «атомное» строение смысла, высокая структурированность значения вместо представления его в виде множества семантических множителей и наличие правил преобразования. Принимаются следующие уровни представления языковой информации: фонетическо-фонологический, морфологический, синтаксический, семантический.
Фонетическо-фонологический в модели подробно не описывается.
Морфологический уровень состоит из двух подуровней: поверхностной морфологии и глубинной морфологии.
Поверхностно-морфологическое представление (ПМП) фразы состоит из цепочки (т.е. линейно упорядоченной последовательности) морфем, супраморфем (семейств морфологически значимых просодический явлений) и аналогичных морфемам морфологических операций (чередований, конверсий и т.п.).
Глубинно-морфологическое представление (ГМП) фразы состоит из цепочки ГМП всех словоформ фразы и сведений о просодических характеристиках фразы (интонация, паузы, фразовые ударения и т.д.).
Синтаксический уровень также состоит из двух подуровней: глубинного синтаксиса и поверхностного синтаксиса.
Поверхностно-синтаксическое представление (ПСП) фразы состоит из пяти компонент:
Глубинно-синтаксическое представление (ГСП) состоит из тех же компонентов, что и ПСП, но узлами дерева глубинно-синтаксической структуры являются только словоформы знаменательных частей речи в виде абстрактных или обобщенных лексем с некоторой морфологической информацией ( время, вид, наклонение для глаголов, число для существительных).
Семантический уровень выражается семантическим представлением (СЕМП), понимаемого как запись смысла. и отображающего содержание связного фрагмента без деления на фразы и слова. СЕМП состоит из семантического графа (СГ) и сведений о коммуникативной организации смысла. СГ – связанный ориентированный граф, вершины которого помечены символами сем («атомов» смысла). Семы бывают двух типов: предикатные переменные (предикаты) и предметные переменные (объекты и классы объектов). К предикатам относятся и логические связки и кванторы. Дуги СГ отражают связь сем-предикатов с их аргументами (стрелки направлены от предиката к аргументам). Стрелки пронумерованы.
Сведения о коммуникативной организации состоят из:
Для целей понимания и синтеза речи можно принять следующую типологию естественных языков.
Все языки можно разделить на аналитические и синтетические. В аналитических языках грамматические значения выражаются главным образом отдельными словами, в то время как в синтетических грамматические значения выражаются как правило аффиксами в составе словоформы.
Примером аналитического языка могут служить китайский и английский языки.
Практически все аналитические языки относятся также к изолирующим, так что понятия изолирующий язык и аналитический язык можно считать в этом смысле синонимами. Само понятие изолирующего языка означает отсутствие словоизменения и высокую грамматическую значимость порядка слов.
Синтетические языки можно разбить на флективные (фузионные) и агглютинативные.
Для флективных языков характерна многофункциональность грамматических морфем: одни и те же аффиксы могут служить для образования различных грамматических форм. В то же время одни и те же грамматические формы могут достигаться за счет использования разных аффиксов. Примерами флективных языков могут служить все славянские и балтийские языки, латынь.
Для агглютинативных языков характерна грамматическая однозначность аффиксов: один аффикс служит для образования одной грамматической формы. Одни и те же грамматические формы достигаются одними и теми же аффиксами. Примерами агглютинативных языков могут служить тюркские и финно-угорские языки, иврит.
Очевидно, что для аналитических языков этап морфологического разбора должен включать:
Для синтетических языков морфологический разбор включает:
Этап синтаксического анализа простого предложения (в т.ч. в составе сложного) в системе MyLingvo начинается с поиска предиката – сказуемого. Если сказуемое является глаголом, то можно определить по словарю его валентность – то есть способность слова в данной грамматической форме сочетаться с другими элементами. У глагола значением валентности является количество типов актантов, которые он может присоединить. Например, у безличного глагола светает валентность нулевая, у непереходного глагола спать валентность 1 (на подлежащее), у глагола купить валентность 3 или 4 (кто, что, у кого; в ряде трактовок также — за сколько). Акта?нт в лингвистике — активный, значимый участник ситуации, речевая конструкция, заполняющая семантическую или синтаксическую валентность предиката. Актант, как правило, обязательно сопровождает предикат; его опущение возможно только в ограниченных случаях и подчиняется специальным правилам.
Заполнение актантов при анализе в аналитических и синтетических языках также имеет свои отличия.
В синтетических языках определяющим понятием является падеж (лат.casus). Основные падежи, встречающиеся в синтетических языках, и их семантическая трактовка отражена в таблице:
Наличие описания синтаксиса языка также необходимо на стадии синтеза. Это описание должно содержать информацию о типичном порядке слов в языке (см. ниже) и типичной грамматической форме, которой в данном языке передается некий элемент семантической структуры.
С точки зрения порядка слов в предложении языки могут быть разделены на основе базового порядка, в котором в предложении стоят подлежащее (Subject), сказуемое (англ. Verb) и прямое дополнение (Object) (в русском языке прямое дополнение выражается существительным или личным местоимением в винительном падеже без предлога) .
Всего существует 6 возможных типов языков:
Существуют четыре основных вида алгоритмов морфологического анализа:
Применение первых двух способов в большинстве практических случаев более оправдано.
Морфологический анализ со словарем основ является наиболее распространенным способом анализа. Для его проведения требуется словарь основ слов и ряд вспомогательных таблиц. Основа – это неизменяемая часть слова, которая выражает его лексическое значение, то есть соотнесённость звуковой оболочки слова с соответствующими предметами или явлениями объективной действительности. Применительно к русскому языку основа – это часть слова без окончания. В английском языке основа слова, как правило, полностью совпадает с самим словом.
Если слово имеет несколько вариантов основ, то словарь,
как правило, содержит все варианты. Обычно в этом случае один из вариантов основы помечается как основной, а другие варианты содержат ссылку на него. Это необходимо для дальнейшего семантического анализа, чтобы устранить различные смысловые трактовки для одного и того же слова. Дополнительные таблицы содержат, как правило, список возможные варианты изменяемых частей слов ( в русском языке – окончаний) с соответствующими им значением грамматических признаков.
В общем случае производится поиск всего слова в словаре словоформ, если слово не найдено, от него отделяется последняя буква и производится повторный поиск. Так продолжается до тех пор, пока основа не будет найдена либо пока не останется букв. В случае удачного поиска из словаря извлекаются варианты частей речи, соответствующих этой основе. Затем производится поиск в таблице изменяемых частей слова. При этом пропускаются варианты соответствующие частям речи, к которым данная основа не может относиться. Таким образом, определяются грамматические признаки разбираемой словоформы. Впрочем тут возможно появление неоднозначности, о методах преодоления которой мы пока говорить не будем.
В основу метода морфологического анализа методом логического умножения положены положения формальной морфологии. Вводится понятие словарной функции – функции, определенной на словоформах, и сопоставляющей им некоторую информацию (последовательность нулей и единиц).
На предварительном этапе строится таблица в которой каждой возможной букве изменяемой части (с учетом позиции в этой самой изменяемой части) ставится в
соответствие вектор нулей и единиц. Каждая из позиций такого вектора соответствует определенной комбинации грамматических признаков. Единица означает, что данная буква в данной позиции может соответствовать этой комбинации грамматических признаков, ноль – что не может.
На первом этапе этот метод также предполагает членение словоформы на основу и изменяемую часть. Далее по предварительно созданной таблице векторов каждой букве изменяемой части подбирается вектор. Далее над векторами производится операция логического умножения. Таким образом определяется возможная ( возможные) комбинация (-ии) грамматических признаков.
Морфологический анализ без словарей также называется независимым анализом. Он проводится без использования словарей лишь с использованием таблицы аффиксов, списка слов-исключений и списка служебных неизменяемых слов (например, союзов, междометий, предлогов). Этот способ используется достаточно редко.
Также малооправданным представляется морфологический анализ со словарем словоформ, подразумевающий наличие словаря, содержащего список все возможных словоформ (например, все варианты сочетаний падежа и числа для каждого существительного) с соответствующими им грамматическими признаками. Кроме значительного роста словаря возникает еще одна проблема: в случае отсутствия словоформы в словаре мы не будем иметь о ней никаких грамматических признаков, что не позволит системе в дальнейшем оперировать неизвестным словом как частично известным, попытаться установить его смысл и т. д.
Стандартные списки окончаний русских слов для морфологического анализа представлены в следующих таблицах:
Списки окончаний существительных
Списки окончаний полных прилагательных и причастий
Списки окончаний кратких прилагательных и причастий
Списки окончаний глаголов
Для русского языка, как и для большинства синтетических языков, задача лексико-грамматического разбора решается довольно просто и почти стопроцентной точностью, благодаря их развитой морфологии. В аналитических языках, например английском, где широко представлена лексическая многозначность, простой алгоритм, сопоставляющий каждому слову в тексте наиболее вероятный для данного слова морфологический класс, дает лишь около 90% точности.
Для увеличения точности разбора используются два типа алгоритмов: вероятностно-статистические и основанные на продукционных правилах.
Алгоритмы, основанные на продукционных правилах, используют правила , которые строятся автоматически на основе некоторого корпуса текстов или создаются лингвистами. О продукционных правилах более подробно будет рассказано в главе 5 (?----проверить--------!!!!).
Вероятностно-статистические алгоритмы используют, в основном, два источника информации.
- Словарь словоформ, в котором каждой словоформе соответствует множество лексико-грамматических классов, которые могут быть у данной словоформы. Для каждого лексико-грамматического класса указывается частота его встречаемости относительно других морфологических классов данной словоформы.
- Информация о встречаемости всех возможных последовательностей морфологических классов попарно, по тройкам, по четверкам и т.д. с относительной частотой такой пары (тройки, четверки,…).
Эта информация обрабатывается неким статистическим алгоритмом (например, на основе скрытых цепей Маркова) для нахождения наиболее вероятного лексико-грамматического класса для каждого слова в предложении.
Оба подхода дают примерно одинаковый результат на уровне 96-98 % точности.
Синтаксисом называется раздел грамматики, изучающий строй связной речи и функционирование в речи различных лексико-грамматических классов (частей речи).
Центральными понятиями синтаксиса являются словосочетание и предложение.
Словосочетание состоит из двух и более знаменательных слов, соединенных на основе подчинительной связи; в нем обязательно наличие главного и подчиненного членов. Существуют три типа подчинительной связи:
1). Согласование – вид связи, при котором лексическая форма подчиненного слова повторяет лексическую форму главного. Например: глубокий ум, про дальние страны.
2). Управление – вид связи, при котором лексическая форма подчиненного слова не повторяет форму главного, но зависит от его значения. Например: жажда славы, дорога к дому.
3). Примыкание – вид связи, при котором зависимость слова выражается лексически, порядком слов и интонацией, без применения служебных слов и морфологического изменения. Например: громко кричать, упасть оцепенев.
Предложение – минимальная единица человеческой речи, представляющая из себя грамматически организованное соединение слов или слово, обладающее смысловой и интонационной законченностью. На письме конец предложение оформляется точкой, восклицательным или вопросительным знаком - или многоточием.
Существенно важной составляющей синтаксического анализа является анализ по членам предложения.
Подлежащее ( от лат. «subjectum» («под-лежащее») – субъект) определяется один из двух главных членов (наряду со сказуемым) предложения . Традиционное определение подлежащего – «то, о чем говорится в предложении».
Сказуемое — это главный член предложения, который связан с подлежащим и отвечает на вопросы «что делает предмет (или лицо)?», «что с ним происходит?», «каков он?», «что он такое?», «кто он такой?» и др., т.е. сказуемое обозначает действие или состояние предметов и лиц, которые выражены подлежащим.
Сказуемое может быть простым и составным.
Простым глагольным сказуемым называется сказуемое, выраженное одним глаголом в каком-либо наклонении:
Цирк уехал.
Составное сказуемое бывает глагольным и именным. Оно состоит из двух частей: связки и глагольной или именной части.
Составное глагольное сказуемое состоит из вспомогательного глагола и неопределённой формы глагола
Я хочу поехать к морю. Он рано начал курить .
Иногда в роли вспомогательного глагола употребляются краткие прилагательные (готов, должен, рад, склонен, горазд, способен и др.), существительные (мастер, мастерица, охотник, охотница и т.п.) и цельные выражения (быть в состоянии, быть не в силах, не иметь или иметь возможность, иметь или не иметь права).
Я должен работать. Он был не в состоянии простить ее.
Составным именным сказуемым называется сказуемое, которое состоит из именной части и глагола-связки.
Наиболее употребительным является глагол-связка быть, менее употребительны, но возможны и другие глаголы-связки.
Глагол-связка в предложении может быть опущен.
Именная часть составного сказуемого выражается по-разному:
1) Именем прилагательным
Девушка была красивая .
2) Именем существительным
Книга — лучший подарок .
3) Сравнительной степенью прилагательного
Мое слово крепче стали.
4) Кратким страдательным причастием
Голова помыта.
5) Кратким прилагательным
Ребенок совсем мал.
6) Наречием
Факт налицо.
7) Именем числительным
Трижды шесть — восемнадцать.
8) Местоимением
Эта девушка моя.
9) Синтаксически цельным словосочетанием
Он был титулярный советник.
Определение – второстепенный член предложения, который обозначает признак предмета и отвечает на вопросы «какой?», «чей?» и другие. По способу выражения определения делятся на согласованные (выражаются прилагательными, местоимениями, причастиями, числительными, которые согласуются с определяемым словом в роде, числе и падеже) и несогласованные (выражаются существительными с предлогами и без предлогов, они богаче по своему значению, так как они могут совмещать значение определения со значением обстоятельств и дополнений). Определения иногда несут основную смысловую нагрузку члена предложения, с которым они согласуются, и могут быть включены в его состав. Определения могут конкретизировать предмет по качественному признаку, по действию, по месту, по времени, по отношению к другому предмету, по принадлежности.
Приложение – определение, выраженное существительным, которое дает другое название, характеризующее предмет. Может давать характеристику предмета, указывать на степень родства, национальность, звание, профессию.
Дополнение - второстепенный член предложения, который зависит от сказуемого или других членов предложения и отвечает на вопросы косвенных падежей:
Дополнения делятся на:
Обстоятельство - второстепенный член предложения, который зависит от сказуемого и отвечает на вопросы
-«Где?» «Куда?» «Откуда?» «Как?» «Зачем?» «Почему?»
- «С каких пор?» «Как долго?» «Отчего?» «Каким образом?» «С какой целью?» «В какой мере?» «В какой степени?» «По какой причине?» «Вопреки чему?»
В зависимости от этого различают обстоятельства времени, места, образа действия, причины, цели, условия, уступки.
Существует определенная зависимость между тем, какой частью речи является слово и какую синтаксическую роль в предложении оно может иметь. Причем такая зависимость представляется общей как минимум для всех индоевропейских языков. Эту зависимость можно показать в виде таблицы:
Для частей речи, которые могут выступать в качестве разных членов предложения, синтаксическая роль как правило может быть уточнена по морфологической форме слова (как это характерно для русского языка) и по месту в предложении относительно других слов (например, в английском языке).
Блок синтаксического анализа состоит, как правило, из трех частей:
1) сегментации предложения;
2) устранение морфологической омонимии
3) установления связей между словами.
На этапе сегментации собираются воедино простые предложения в составе сложного. Любое простое предложение может быть разорвано деепричастными или причастными оборотами или придаточными предложениями. Для дальнейшей обработки необходимо правильно состав сегментов, каждый из которых относится к конкретному простому предложению.
Под морфологической омонимией понимается следующее явление. На этапе морфологического анализа мы получаем для каждого слова все варианты их морфологического разбора, а таковых часто больше одного. Так слово «мыла» может быть разобрано и как родительный падеж существительного «мыло» и как прошедшее время женского рода глагола «мыть». Если и дальше рассматривать при анализе все возможные варианты разбора, процесс может значительно усложниться или замедлиться. Поэтому уже до собственно синтаксического анализа, каковым считается установление связей между словами, морфологическая омонимия должна быть устранена. Для этой цели служат комбинаторные словари, содержащие информацию о том в контексте каких слов
употребляется та или иная морфологическая форма. Так если слову «мыла» предшествует слово, однозначно определенное как существительное женского рода в именительном падеже, то мы определяем слово «мыла» как глагол прошедшего времени. Если же, например, этому слову предшествует слово «много» - это однозначно указывает на то, что оно является существительным в родительном падеже.
Этап установления связей между словами определяется во многом системой формального описания синтаксиса. Рассмотрим несколько формальных моделей синтаксиса, применявшихся для русского языка.
Link Grammar (LG) (грамматика ссылок) – это теория синтаксиса, разработанная Дэйвом Темперли и Дэниэлом Слитором, которая построена на отношениях между парами слов в отличии от деревоподобных структур в других моделях. В то время как большинство систем используют структуры уровня именных и глагольных групп при построении дерева фразы, грамматика ссылок использует информацию о типах связей, которое каждое слово может иметь со словами, находящимися справа и слева и несколько общих грамматических правил.
Например, в языках типа SVO (подлежащее+сказуемое+объект), таких как английский, сказуемое содержит левую ссылку на субъект и правую ссылку на объект. Существительное имеют ссылку вправо, если это субъект (подлежащее), и влево – если объект.
В языках SOV (субъект+объект+сказуемое)), таких как персидский, сказуемое содержит левую ссылку на объект и более длинную левую сслыку на субъект. Существительное имеет ссылку вправо как в случае подлежащего, так и объекта.
Ссылки вправо представляются как a+, а ссылки влево как a-. Необязательные ссылки заключаются в фигурные скобки. Неожиданные ссылки в любом количестве заключаются в квадратные скобки. Множественные ссылки соединяются посредством конъюнкции & или дизъюнкции or. Каждое правило заканчивается точкой с запятой.
Например, список базовых правил для языка SVO может иметь вид:
<артикль>: D+;
<существительное-субъект>: {D-}&S+;
<существительное-объект>: {D-}&O-
<сказуемое>: S-&{O+}
Тогда английское предложение «The man killed a shark.»(«Человек убил акулу») должно быть представлено так:
В качестве примера использования такой модели можно привести Link Parser, разработанный в Carnegie-Melon University. Пример разбора предложения этой системой может выглядеть так:
Здесь обозначения таковы: Xp – связь между началом и концом предложения, Sp – связь между существительным и глаголом, Wd – связь между началом предложения и предложением, Mp - связь между именной группой и модифицирующей ее предложно-именной группой, Jp - связь между предлогом и относящейся к нему именной группой, MVa – связь между глаголом (прилагательным) и модификатором..
В качестве примеров таковых систем можно привести Ergo Linguistic Technologies Parser Д. Биккертона и Ф.Бралика из университета Гонолулу и Functional Dependency Grammar, созданный исследователями Хельсинкского Университета, позднее основавшими фирмы Lingsoft и Conexor.
Пример синтаксического разбора в Ergo может быть таким:
Здесь: S – предложение, NP – именная группа, NP-SBJ – именная группа-субъект, VP – глагольная группа, NP-PRD - именная группа-объект, PP-LOC – предложно-именная группа, локатив.
Отличительной особенностью Functional Dependency Grammar является то, что в случаях, когда невозможно снять многозначность, синтаксический анализатор либо не достраивает дерево данной части предложения либо выдает несколько вариантов анализа. Пример разбора может выглядеть так:
Эта запись представляет дерево фразы. Колонка 1 – номер по порядку, 2-3 содержат само слово, 4 – идентификаторы, отражающие вид и направление связи ( символ > предшествует номеру того элемента, которому подчинен данный), 5 – функциональные идентификаторы вершин.
Идентификаторы связей дерева таковы: det: - определение, subj: - субъект (подлежащее), main: - основной элемент, man: - обстоятельство образа действия, cc: - сочинительный союз. Функциональные идентификаторы: @DN> - определение, @SUBJ - субъект (подлежащее), @FMAINV – личный предикат, @ADVL – обстоятельство, @CC – сочинительный союз, @AD-A – интенсификатор.
основан на модели языка «СМЫСЛ-ТЕКСТ». Процессор позиционируется как система пригодная для применения как минимум для всех индоевропейских языков.
Блок-схема синтаксического анализа в этом процессоре выглядит так:
Пример морфологической структуры, описывающей предложение «Укажите соединения натрия.» выглядит следующим образом:
Как видно, даже в таком простом предложении налицо морфологическая омонимия слова «соединения».
Синтаксической структура – результат работы блока синтаксического анализа, представляет собой дерево, вершинами которого являются слова с набором их морфологических признаков, а ветвями – типы синтаксических связей между ними.
Этап предсинтаксического анализа в этой модели подразумевает устранение морфологической омонимии и предварительную постройку синтаксических связей между словами. На этапе собственно синтаксического анализа строится окончательный вариант синтаксической структуры.
Комбинаторный словарь представляет из себя совокупность команд на специальном языке. Эта совокупность представляет из себя некий набор правил. Каждое правило начинается с заголовка вида
REG ИМЯ N
где ИМЯ – имя совокупности правил, N – номер правила.
Правила бывают двух видов: элементарные и обобщенные (альтернативные).
Элементарное правило состоит из двух частей: зоны CHEK (проверить), содержащей список действий (инструкций). Если условия выполняются, то выполняются действия описанные в третьей части правила – зоне DO.
Обобщенное правило состоит из зоны общих условий и нескольких элементарных подусловий. Если выполняются общие условия, то происходит проверка подусловий, являющихся альтернативными по отношению друг к другу. Если какое-то из условий выполняется, осуществляется выполнение действий из зоны DO этого подусловия.
Все условия в зоне CHECK представляют собой выражения логики предикатов. Действия из зоны DO записываются в виде операторов.
Предикаты делятся на элементарные и составные. Список элементарных предикатов можно разбить на 5 групп:
1) предикаты идентификации;
Пример:
=(Z,t1,…,tn) или EQU(Z,t1,…,tn)
означает «словоформа Z обладает всеми характеристиками t1,…,tn (например, мужской род, единственное число, родительный падеж, прошедшее время и т.п.)
2) предикаты линейного порядка;
Пример:
M(Z,Z1,n)
означает «слово Z отстоит от Z1 не более чем на n слов (влево или вправо)»
R(Z,Z1,n)
Означает «слово Z расположено правее Z1 и между ними находится не более чем n слов»
3) предикаты доминации;
Пример:
DOM(Z,Z1,r)
Означает «узел Z является непосредственным родителем узла Z1 по отношению r».
DEP(Z,Z1,r)
Означает «узел Z является непосредственным ребенком узла Z1 по отношению r».
4) предикаты согласования;
Пример:
COCAS(Z1,Z2)
Означает «обе словоформы Z1 и Z2» имеют характеристики падежа и эти характеристики совпадают
CONMB(Z1,Z2)
Означает «обе словоформы Z1 и Z2» имеют характеристики числа и эти характеристики совпадают
5) предикаты моделей управления;
Пример составного предиката:
R-DEP-EQU(X,Z,n,r,t1,t2,…,tn)
Означает «справа от X на расстоянии не более n слов находится словоформа Z, обладающая характеристиками t1,t2,…,tn, для которой X является синтаксическим ребенком (синтаксически подчинено) по отношению r.
Инструкции в зоне DO, в свою очередь, можно разбить на 7 групп по выполняемым ими фукциям:
1) работа с характеристиками слов (добавление, стирание, изменение , перенесение)
Пример:
DOBUZHAR:Z(t1,…,tn)
Означает «добавить узлу Z характеристики t1,…,tn»
STERUZHAR:Z(t1,…,tn)
Означает «стереть у узла Z характеристики t1,…,tn»
2) инструкции, изменяющие синтаксическую структуру фразы
Пример:
SVUZOT:(Z,Z1,r)
Означает «связать Z(родителя) и Z1(ребенка) отношением r»
3) инструкции, изменяющие линейный порядок слов и синтаксических групп во фразе
4) инструкции, изменяющие словарный состав фразы
5) инструкции, обрабатывающие знаки препинания
6) инструкции, работающие с кореферентностью
7) вспомогательная функция
NIHIL: - «ничего не делать».
Как было сказано выше, результатом работы блока синтаксического анализа является построение дерева, вершины которого соответствуют словам фразы, а ветви – синтаксическим отношениям между ними.
Все виды отношений в лингвистическом процессоре поделены на 4 группы (приводятся примеры только наиболее существенных видов отношений):
1. Актантные
Примеры:
Предикативное синтаксическое отношение (далее – СинтО) – связывает личную форму глагола или именную часть сказуемого при нулевой связке с именной группой, предложно-именной группой, наречием, инфинитивом, союзом или личной формой глагола придаточного предложения в качестве подлежащего:
Человек (подчиненное-Y) родился (главное). Дела(Y) плохи(X).
Агентивное СинтО – связывает предикатное слово с его первым аргументом – вершиной именной группы в творительном падеже:
Дело рассматривается(X) областным судом (Y).
Первое комплективное СинтО – связывает предикатное слово с его вторым синтаксическим актантом (кроме случаев, когда оно попадает под определение присвязочного СинтО, которе мы не рассматриваем):
Изыскания(Y) продолжает(X) небольшая группа ученых. Есть мнение(X), что эта группа заслуживает поддержки(X).
Второе комплективное СинтО – связывает предикатное слово с его третьим актантом:
Такие действия мы не считаем(X) зазорными(Y). («мы считаем» - предикативное СинтО, «считаем действия» – первое комплективное СинтО, «считаем зазорными» - второе комплективное СинтО).
2. Атрибутивные
(Собственно) атрибутивное СинтО – связывает существительное, порядковое числительное или прилагательное с его несогласованным определением:
вопрос(X) времени(Y), хороший(X) по качеству(Y), тринадцатое(X) апреля(Y)
Определительное СинтО – связывает существительное или прилагательное X с прилагательным Y, полностью или частично согласованным с X по роду, числу, падежу и одушевоенности:
Главная(Y) цель(X), самый(Y) сильный(X)
Релятивное СинтО – связывает вершину именной группы главной группы с вершиной группы сказуемого придаточного определительного предложения:
Перечислите фамилии сотрудников(X) организации, которые зарабатывают(Y) более 40 тысяч рублей. Лучшее(X), что у нас есть(Y), мы отдаем людям.
Обстоятельственное СинтО – связывает глагол в качестве вершинного элемента с обстоятельством, выраженным наречием, существительным в творительном, родительном или (изредка) винительном падеже, порядковым прилагательным(?), деепричастием, инфинитивом, предложно-именной группой, количественной беспредложной группой, придаточным, водимым союзом, или союзной группой:
Конденсаторы включены(X) последовательно(Y). Плавать(X) кролем (Y).
3. Сочинительные
Сочинительное СинтО – связывает первый (очередной) член сочиненной группы со вторым (последующими). В случае союзного сочинения в качестве зависимого члена выступает союз:
Мы шли сквозь дым(X) и(Y) пожарища.
4. Служебные
Целью синтаксического анализа здесь является построение синтаксических групп на одном морфологическом варианте одной клаузы. Группы строятся с помощью синтаксических правил.
Клаузой здесь называется простое предложение в составе сложного или просто простое предложение. Морфологический вариант – набор юнитов. Юнит – это либо слово либо подклауза данной клаузы.
Синтаксическая группа определяется следующими параметрами:
Тип групп – это строковая константа (НАР_ПРИЛ,ПРИЛ_СУЩ и т.д.). Главная подгруппа – подгруппа (или слово) которая определяется как главная в описании данного типа группы. Внешние граммемы группы – это морфологические характеристики группы по отношению к группам вне данной группы. Например внешние граммемы группы «кот и пес» содержат множественное число, в то время как оба слова внутри этой группы имеют единственное число.
Синтаксическое правило – это правила соединяющие существующие группы и отдельные слова в новые группы. Все правила упорядочены, поэтому синтаксическая омонимия (неоднозначность в построении групп) игнорируется, то есть строится всегда один вариант.
На вход алгоритма синтаксического анализа подается морфологический вариант клаузы. Сначала к словам клаузы применяется первое правило и строятся все группы первого типа (КОЛИЧ), потом второе правило применяется к словам, незадействованным в группах и уже созданным группам и строятся группы второго типа. И так далее, пока не будут применены все правила.
Упорядоченный список типов групп выглядит следующим образом:
Основой семантического анализатора в системе ДИАЛИНГ является Русский семантический словарь (РОСС), созданный коллективом под руководством Н.Н. Леонтьевой. Этот же словарь использовался в системе ПОЛИТЕКСТ и системе французско-русского перевода ФРАП.
Структура словаря содержит следующие поля.
- Лексема;
- Категория лексемы;
- Семантический класс лексемы;
- Грамматический класс лексемы;
- Валентная структура лексемы;
- Семантические и грамматические ограничения на выражение каждого актанта из валентной структуры;
- Английские эквиваленты лексемы;
Категории лексем, представленных в словаре, следующие:
Кроме того, при записи формул применяются три операторные характеристики:
В системе применяется следующая система семантических отношений, многие из которых аналогичны применяемым в других системах.
Семантический анализ в этой системе есть переходный этап между синтаксическим анализом (построением синтаксической структуры) и построением SQL-запроса к таблицам реляционной базы данных (к которому здесь фактически сводится прагматический анализ). На этом этапе строится семантическая структура в виде семантического дерева зависимостей, уже явно ориентированного на построение SQL-запроса.
SQL-запрос имеет вид:
SELECT <Список полей таблицы>FROM<Таблица или другой запрос>WHERE<Список условий>
Семантическая структура, получаемая на выходе семантического анализа, как уже было сказано имеет вид дерева зависимостей. В данном случае это особенно удобно, так как выход синтаксического анализа в процессоре также представляет из себя древесную структуру. Таким образом для работы семантического анализа может использоваться алгоритмический аппарат, используемый в синтаксическом анализе.
Узлы семантической структуры бывают четырех типов:
Семантическая структура определяется чрез семантические поддеревья. Поддеревья бывают объектные и предикатные. Объектные служат для описания объектов, а предикатные – для записи утверждений об объектах.
Объектные поддеревья.
Обозначаются До.
1 Элементарные объектные поддеревья:
1.1. Вырожденное поддерево, состоящее из одного узла, в котором стоит терм-константа (значение поля таблицы)
1.2. Если F – некоторый функциональный символ (имя поля таблицы), а X – соответствующая ему переменная (имя таблицы), то
- элементарное До.
Если F – некоторый функциональный символ (имя поля таблицы), X – соответствующая ему переменная (имя таблицы), OPER – оператор, действия которого над множеством значений F допустимы, то
- элементарное До.
2. Если До(X) – элементарное объектное поддерево, а Дп1(X), Дп2(X),…,ДпN(X) – предикатные поддеревья, зависящие от одной и той же переменной X, то
- объектное поддерево, зависящее от переменной X.
Предикатные поддеревья.
Обозначаются Дп.
1.Элементарные предикатные поддеревья.
Если До и До1 – элементарные объектные поддеревья (см. выше), то Дп =
где r = {=,!=,<,>,>=,<=,Є,!Є}, – элементарное предикатное поддерево.
2. Если До – элементарное объектное поддерево, а До1 – какое-либо объектное поддерево, то
где r = {=,!=,<,>,>=,<=,Є,!Є}, – предикатное поддерево.
3. Если Дп1 и Дп2 – предикатные поддеревья, то Дп =
где r = {&,V}, – тоже предикатное поддерево.
Пример семантического дерева запроса:
соответствует запросу: SELECT Номер FROM Отдел WHERE Наименование = «Отдел продаж».
В разрабатываемом автором этой книги лингвистическом процессоре MyLingvo за основу построения семантического словаря взят принцип дихотомии (деления группы пополам по какому-то признаку). Изначально все слова в словаре разделены на действия (глаголы), объекты (существительные) и признаки (прилагательные и связанные с ними наречия).
Все объекты делятся на одушевленные и неодушевленные, одушевленные, в свою очередь, делятся на животные и растения, животные делятся на людей и прочих животных и т.д.
При этом сама структура дихотомии задается гибко и представляет из себя файл, содержащий два поля – 1) признак, наличие или отсутствие которого у объекта позволяет отнести его к той или иной подкатегории в пределах родительской категории, 2) уровень вложения.
В результате для каждого объекта может быть задана последовательность нулей и единиц, определяющая его место в семантической классификации и позволяющая оперировать с объектами при помощи алгебры логики. Для нашего примера класс объектов «ЧЕЛОВЕК» может быть представлен двоичным числом «111», а класс объектов «ЖИВОТНОЕ» - числом «011», растения – «01». Нули в первой позиции также существенны и не могут быть опущены. Иначе нельзя было бы отличить класс «РАСТЕНИЯ» (01) от класса «ОДУШЕВЛЕННЫЕ ПРЕДМЕТЫ» (1). В последний входят, как было уже сказано и «ЖИВОТНЫЕ»(11).
В системе определены элементарные действия:
1) БЫТЬ;
2) ИМЕТЬ(=держать);
3) ПРЕДСТАВЛЯТЬ;
4) МОЧЬ;
5) ХОТЕТЬ(=намереваться что-либо сделать);
Автор исходит из предположения, что любое действие может быть выражено при помощи логической комбинации этих действий, представленных как предикаты, с определенными семантическим объектом, инструментом и субъектом.
Например, действие «сказать» может быть представлено как ПРЕДСТАВЛЯТЬ(ЧЕЛОВЕК,ТЕКСТ,ГОЛОС), где «ЧЕЛОВЕК» - класс объектов для обозначения семантического субъекта, «ТЕКСТ» - класс объектов для обозначения семантического объекта, «ГОЛОС» - класс объектов для обозначения семантического инструмента.
Одной из важнейших структур, с помощью которых представляются и хранятся в оперативной памяти компьютера анализируемые в лингвистическом процессоре данные, является дерево. Дерево – это структура данных, представляющая из себя граф, у которого одна из вершин определена как корневая.
На языке C дерево может быть представлено в виде следующих структур
struct Node // Структура для описания вершины
{
char* name; // Имя вершины (или др. информация)
……………….
Arc* parent; // Указатель на дугу, идущую от родительской вершины
Arc** children; // Указатель на массив исходящих дуг
int nNumOfChildren; // Число исходящих дуг
}
struct Arc // Структура для хранения дуги
{
char* name; // Имя дуги (или др.информация)
………………..
Node* Prev; // Указатель на вершину-родитель
Node* Next; // Указатель на дочернюю вершину
}
struct Tree // Структура для описания дерева
{
Node* root; // Указатель на корневую вершину дерева
}
Очень удобной для хранения и зачастую удобной для обработки формой хранения дерева является линейная скобочная запись или, что то же самое, запись дерева в виде фреймов ( от английского frame – рамка). Линейная скобочная запись строится на основе того или иного обхода вершин дерева. Рекурсивная процедура обхода нашего дерева может иметь вид:
void tree_order (Node* nd)
{
for (int i=0; i
Node* cur_node =nd->children[i];
tree_order(cur_node);
}
}
Рассмотрим скобочную линейную структуру для следующего дерева:
Линейная скобочная структура должна иметь вид:
R0(A)(R1(B)(R4(E)R5(F))R2(C)R3(D)(R6(G)))
Таким образом, алгоритм будет таким:
Формула в логике предикатов – это или предикат, аргументы которого являются термами( в этом случае формула называется атомной или элементарной), или последовательность, получаемая одним из следующих способов из некоторых формул А и Б и некоторой переменной x:
В формулах 5) и 6) А называется областью действия соответствующего квантора.
На практике для обработки знаний представленных в виде логики предикатов используется метод резолюции хорновских дизъюнктов .
Алгоритм таков.
Шаг 1. Приведение формулы к предваренной нормальной форме.
Для этого:
Шаг 2. Приведение формулы к сколемовской нормальной форме.
Чтобы привести формулу к сколемовской форме, нужно исключить кванторы существования из предваренной нормальной формы.
Шаг 3. Исключение кванторов всеобщности.
Просто удалим кванторы всеобщности из сколемовской нормальной формы.
Шаг 4. Приведение формулы к конъюнктивной нормальной форме.
Для этого воспользуемся эквивалентностью:
1. А ИЛИ (Б И В) <-> (А ИЛИ Б) И (А ИЛИ В)
Шаг 5. Исключение конъюнкций – получение множества дизъюнктов.
Подстановкой будем называть множество вида {x1/t1,…,xn/tn}, где для всех i=1..n
Простое выражение – это терм или атомная формула.
Например: Пусть
Опишем алгоритм поиска наиболее общего унификатора для конечного множества простых выражений S.
Шаг 1. Полагаем к=0, П0=<Пустая подстановка>
Шаг 2. Если SПк содержит один элемент, то Пк – наиболее общий унификатор, алгоритм прерывается. Иначе – переходим к шагу 3.
Шаг 3. Если d(SПк) содержит некоторую переменную x и терм t такие, что x не входит в t, то полагаем П к+1=Пк{x/t}. Иначе множество S не унифицируемо и прерываем алгоритм.
Шаг 4. к=к+1.
Шаг 5. Переходим к шагу 2.
Правило резолюций состоит в следующем. Если одна и та же атомная формула входит в один из дизъюнктов положительно, а в другой отрицательно, то эти формулы можно вычеркнуть, а дизъюнкты объединить. Исходные дизъюнкты называются родительскими , результирующий дизъюнкт – револьвентой, а вычеркнутые формулы – контрарными литералами. Правило резолюций можно выразить так:
(А или В) и (Б или НЕ(В)) <-> А или Б.
Пусть есть два дизъюнкта Д1 и Д2, у которых нет общих переменных, Л1 – литерал, входящий в Д1, а Л2 – литерал, входящий в Д2. Пусть литералы имеют наибольший общий унификатор П. Тогда дизъюнкт (Д1П-Л1П)или (Д2П-Л2П) называется револьвентой дизъюнктов Д1 и Д2.
(А или Л1) и (Б или НЕ(Л2)) <-> (А или Б)П.
Здесь П – наибольший общий унификатор,
// Строка для результирующей линейной скобочной структуры, размер 10000
// взят для примера.
char* out_str=(char*)malloc(10000*sizeof(char));
strcpy(out_str,””);
// вызов процедуры
// Tree tr1; - входящее дерево
tree_order(out_str, tr1.root);
// сама процедура:
void tree_order (char* str1, Node* nd)
{
strcat(nd->parent.name);
strcat(str1,”(“);
strcat(nd.name);
strcat(str1,”)“);
if(nNumOfChildren>0)
strcat(str1,”(“);
for (int i=0; i
Node* cur_node =nd->children[i];
tree_order(str1, cur_node);
}
if(nNumOfChildren>0)
strcat(str1,”)“);
}
Исчисление предикатов.
Общие понятия.
Формальная система F считается определенной, если:
Логика предикатов – частный случай формальной системы.
Алфавит логики предикатов (или как ее еще называют, логики первого порядка) составляют:
Все предикатные и функциональные символы имеют определенное число аргументов. Если их число равно N, говорят, что мы имеем дело с N-местный (или N-арным) предикатным (функциональным) символом.
Термом называется или переменная или константа или функциональный символ, аргументы которого являются термами. Терм, не содержащий переменных, называется константным или основным.
1) НЕ А
2) А И Б
3) А ИЛИ Б
4) А->Б (т.е.из А следует Б)
5) СУЩ x А (т.е. существует x такое, что справедливо А)
6) ВСЕ x А (т.е. при всех x справедливо А).
При этом если x из этих формул входит в область действия, то такая переменная называется связанной, а в противном случае – свободной.
Положительным литералом называется атомная формула, отрицательным литералом – отрицание атомной формулы.
Конъюнктивной нормальной формой формулы называется конъюнкция конечного числа дизъюнктов. Предваренной (префиксной) нормальной формой называется представление формулы в виде:
КВАНТОР1 x1, …, КВАНТОРN xN А
Здесь КВАНТОР1,…,КВАНТОРN – это один из кванторов СУЩ или ВСЕ, а все это выражение называется префиксом, формула А не содержит кванторов и называется матрицей.
Сколемовской нормальной формой называется предваренная нормальная форма, не содержащая кванторов существования.
Дизъюнкт – это дизъюнкция (соединение при помощи ИЛИ) конечного числа литералов. Хорновскими называют дизъюнкты, содержащие не более одного положительного литерала.
Приведение произвольной формулы к множеству дизъюнктов.
1. Пользуясь эквивалентностью А->Б <-> (НЕ А) ИЛИ Б исключим импликацию.
2. Перенесем все отрицания внутрь формулы, чтобы они стояли только перед атомными формулами, пользуясь следующими эквивалентностями:
1. НЕ (А ИЛИ Б) <-> НЕ(А) И НЕ(Б)
2. НЕ (А И Б) <-> НЕ(А) ИЛИ НЕ(Б)
3. НЕ (СУЩ x А) <-> ВСЕ x НЕ(А)
4. НЕ (ВСЕ x А) <-> СУЩ x НЕ(А)
5. НЕ (НЕ(А)) <-> А
3. Переименовываем связанные переменные так, чтобы ни одна переменная не входила в формулу одновременно и как связанная и как свободная.
4. Выносим кванторы в начало, используя эквивалентности:
Если устраняемый квантор существования – самый левый квантор в префиксе, заменим все вхождении в формулу переменной, связанной этим квантором, на новую константу и вычеркнем квантор из префикса формулы.
Если левее этого квантора существования есть кванторы всеобщности, заменим все вхождения в формулу переменной, связанной этим квантором, на новый функциональный символ от переменных, связанных стоящими слева кванторами всеобщности, и вычеркнем квантор из префикса формулы.
2. А И (Б ИЛИ В) <-> (А И Б) ИЛИ (А И В)
Унификация и ее алгоритм.
xi – переменная, а ti – терм, причем xi<>ti. То есть имеет место отображение переменных в термы. При этом все переменные, входящие в подстановку различны.
Символом ? будем обозначать пустую подстановку.
Подстановка, в которой все термы основные называется основной подстановкой.
Если А – простое выражение, а П – подстановка, то АП получается путем одновременной замены всех вхождений каждой переменной из А соответствующим термом. То есть каждое вхождение xi в формулу заменяется на ti. АП называется примером (частным случаем) выражения А.
Пусть П1 и П2 – подстановки, П1 = {x1/t1,…,xn/tn}, П2 = {y1/s1,…,yn/sn}. Композиция
П1П2 получается из множества {x1/t1 П2,…,xn/tn П2, y1/s1,…,yn/sn } после удаления пар
xi/ti П2, где xi = ti П2 и пар, где yi совпадает с одним из xi. Здесь выражение xi/ti П2 означает последовательную замену в формуле всех вхождений xi на ti и ti на некое sk, если ti=yk.
Говорят, что подстановка П1 более общая, чем подстановка П2, если , если существует подстановка П3 такая, что П2=П1П2. Подстановка П называется унификатором простых выражений А и Б, если АП=БП. Сами выражения А и Б в этом случае называют унифицируемыми.
Соответственно наиболее общим унификатором двух простых выражений будет наиболее общая из подстановок, являющихся унификаторами для данных выражений.
Пусть S – некое множество простых выражений. Множеством разногласий (рассогласований) для S называется множество d(S), состоящее из элементов S начиная с первой позиции слева, в которой не во всех выражениях из S стоит один и тот же символ, и следующих после него подвыражений из выражений S.
S={f(p(x),h(y),a}, f(p(x),z,b), f(p(x),h(y),a)}.
Тогда множество разногласий:
D(S)={h(y),z } ( ??????)
Правило резолюций и его применение.
Тогда правило резолюций можно представить в виде:
Метод резолюций является обобщением метода доказательства от противного: мы добавляем отрицание формулы-гипотезы в множество аксиом и пытаемся вывести из него противоречие.
8. Литература и ссылки.
