Компьютерный анализ естественно-языкового текста Кафедра информационных систем в искусстве и гуманитарных науках

Компьютерный анализ естественно-языкового текста СТРУКТУРА КУРСА 1.Введение в дисциплину 2.Автоматический анализ текста на морфологическом уровне 3.Автоматический анализ текста на синтаксическом уровне 4.Семантический компонент в системах автоматического анализа текста

Компьютерный анализ естественно-языкового текста СТРУКТУРА КУРСА 3. Автоматический анализ текста на синтаксическом уровне –Задачи анализа текста на синтаксическом уровне –Модели представления структуры высказывания –Примеры реализации синтаксического анализа

Компьютерный анализ естественно-языкового текста СТРУКТУРА КУРСА 3. Автоматический анализ текста на синтаксическом уровне –Задачи анализа текста на синтаксическом уровне –Модели представления структуры высказывания –Примеры реализации синтаксического анализа

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Каким метаязыком можно пользоваться?

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Каким метаязыком можно пользоваться? структуры составляющих структуры зависимостей гибридные модели

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Определились с метаязыком. А насколько этот метаязык способен отобразить наши знания о синтаксисе?

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Определились с метаязыком. А насколько этот метаязык способен отобразить наши знания о синтаксисе? Существуют описания (фрагментов) естественных языков, строящиеся на основе: -структур составляющих (ранние версии порождающей грамматики, …) -структур зависимостей (теория «Смысл Текст, …) -гибридные структуры (поздние версии порождающей грамматики, …)

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Определились с метаязыком. Можем опереться на существующие описания (фрагментов) естественных языков – «грамматики» А как пользоваться этими описаниями для автоматической реализации синтаксического анализа?

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Определились с метаязыком. Можем опереться на существующие описания (фрагментов) естественных языков – «грамматики» А как пользоваться этими описаниями для автоматической реализации синтаксического анализа? Стоит вопрос о переходе от описания «что бывает в языке» к описанию алгоритма «как отождествить то, что видим в данном предложении, с тем, что бывает в языке»

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Определились с метаязыком. Можем опереться на существующие описания (фрагментов) естественных языков – «грамматики» А как пользоваться этими описаниями для автоматической реализации синтаксического анализа? Стоит вопрос о парсинге Процедура, которая предложению на некотором языке приписывает описание его структуры на специально предназначенном для этого метаязыке. Синоним в информатике – «синтаксический анализ» (также: «синтаксический разбор»)

ФОРМАЛЬНЫЙ ПОДХОД К ОРГАНИЗАЦИИ СИНТАКСИЧЕСКОГО АНАЛИЗА Мы хотим наши знания о синтаксисе формализовать. Определились с метаязыком. Можем опереться на существующие описания (фрагментов) естественных языков – «грамматики» ПАРСИНГ 1) Для грамматик составляющих – проще (для некоторых классов – совсем просто) 2) Для грамматик зависимостей – сложнее 3) На практике – чаще гибридные структуры, используются алгоритмы с несколькими проходами по предложению, большое количество решений для частных случаев (АОТ)

ПАРСИНГ: ГРАММАТИКИ СОСТАВЛЯЮЩИХ неограниченные грамматики контекстно-зависимые грамматики (грамматики НС) контекстно-свободные грамматики Соответствуют обычному пониманию структур составляющих автоматные (регулярные) грамматики Соответствуют частному случаю в обычном понимании структур составляющих

ПАРСИНГ: ГРАММАТИКИ СОСТАВЛЯЮЩИХ неограниченные грамматики Их структурный коррелят значительно сложнее структур составляющих в обычном понимании контекстно-зависимые грамматики (грамматики НС) Их структурный коррелят сложнее структур составляющих в обычном понимании контекстно-свободные грамматики Соответствуют обычному пониманию структур составляющих автоматные (регулярные) грамматики Соответствуют частному случаю в обычном понимании структур составляющих

ПАРСИНГ:ГРАММАТИКИ СОСТАВЛЯЮЩИХ и АВТОМАТЫ неограниченные грамматики машины Тьюринга контекстно-зависимые грамматики (грамматики НС) линейно ограниченные автоматы / машины Тьюринга с конечной лентой контекстно-свободные грамматики автоматы с магазинной памятью (стековые автоматы) автоматные (регулярные) грамматики конечные автоматы

ПАРСИНГ:ГРАММАТИКИ СОСТАВЛЯЮЩИХ и СЕТИ ПЕРЕХОДОВ неограниченные грамматики усиленные (=расширенные) сети переходов контекстно-зависимые грамматики (грамматики НС) контекстно-свободные грамматики рекурсивные сети переходов автоматные (регулярные) грамматики базовые сети переходов (=диаграммы переходов конечных автоматов)

ПАРСИНГ:ГРАММАТИКИ СОСТАВЛЯЮЩИХ и АВТОМАТЫ …… контекстно-свободные грамматики автоматы с магазинной памятью (стековые автоматы) автоматные (регулярные) грамматики конечные автоматы

ПАРСИНГ для КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Для КС грамматик нет универсального алгоритма/процедуры перехода «Грамматика Автомат» Тем не менее, автомат – это не единственная форма задания алгоритма парсинга; для более общей задачи создать алгоритм перехода «Грамматика Парсинг» существуют универсальные решения и в классе КС грамматик Однако эти универсальные решения, т.е. способы по любой КС грамматике построить алгоритм парсинга, малоэффективны, т.к. -состоят из нескольких этапов -тот алгоритм парсинга, который получается в результате такой универсальной процедуры, слишком затратный в отношении вычислительных ресурсов Для некоторых классов КС-грамматик (но не для всех) существуют более эффективные способы организовать парсинг

ПАРСИНГ для КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Наиболее известные универсальные способы построения по любой КС грамматике алгоритма парсинга: -алгоритм Кока-Янгера-Касами -алгоритм Эрли Оба предусматривают в качестве промежуточного шага построение вспомогательной структуры данных (таблица для алгоритма К-Я-К, список для алгоритма Эрли) Оба включают в качестве входа не только грамматику, но и конкретное разбираемое предложение Оба требуют времени разбора n 3 и объема затрачиваемой памяти n 2, где n – длина разбираемого предложения (хотя для некоторых подтипов КС-грамматик алгоритм Эрли может работать затрачивать линейные время и объем памяти).

ПАРСИНГ для КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Алгоритм Кока-Янгера-Касами (пример) Дано: 1.грамматика S NP VP(1) NP Det N(2) VP V NP(3) N boy | ball(4) (5) Det the(6) V sees(7) 2.предложение the boy sees the ball

ПАРСИНГ для КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Алгоритм Кока-Янгера-Касами (пример) Этапы: 1.Построение таблицы 2.Разбор по таблице t 15 t 14 t 24 t 13 t 23 t 33 t 12 t 22 t 32 t 42 t 11 t 21 t 31 t 41 t 51

ПАРСИНГ для КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Алгоритм Кока-Янгера-Касами (пример) Принцип построения таблицы: В клетки t ij вносятся такие нетерминальные символы A (левые части правил грамматики), что из A можно вывести j слов разбираемого предложения, начиная с i-го слова. t 15 t 14 t 24 t 13 t 23 t 33 t 12 t 22 t 32 t 42 t 11 t 21 t 31 t 41 t 51

ПАРСИНГ для КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК Алгоритм Кока-Янгера-Касами (пример) Построение таблицы для данного примера: Далее – разбор по таблице… S VP NPNP DetNV N

ПАРСИНГ: ГРАММАТИКИ ЗАВИСИМОСТЕЙ … не входит в данный курс( не входит в данный курс ) … Более подробная информация об организации парсинга для структур зависимостей (на английском языке) dependency-parsing

ПАРСИНГ:ПРИМЕР ДЛЯ ГИБРИДНОЙ МОДЕЛИ СИНТАКСИСА (АОТ) Синтаксический процессор ДИАЛИНГ (Л.Гершензон, Д.Панкратов, А.Сокирко) разработан в г. на основе процессора ПОЛИТЕКСТ (система анализа политических текстов Центра информационных исследований). Используется понятие синтаксических групп На входе результаты работы графематического и морфологического модуля (каждая словоформа представлена множеством морфологических омонимов)

ПАРСИНГ:ПРИМЕР ДЛЯ ГИБРИДНОЙ МОДЕЛИ СИНТАКСИСА (АОТ) - 2 Особенность архитектуры: двунаправленное взаимодействие модуля сегментации (=фрагментации, разбиение на предикативные единицы типа простых предложений) и синтаксиса (построения синтаксических групп слов в предложении). Перед анализом не ставится цель построить полную синтаксическую структуру (только объединяет в группы то, что можно объединить). Демонстрация анализа в режиме он-лайн: (а также модуль SynAn пакета Dialing, загружаемого с сайта АОТ)

ПАРСИНГ:ПРИМЕР ДЛЯ ГИБРИДНОЙ МОДЕЛИ СИНТАКСИСА (АОТ) - 3 Этапы работы синтаксического анализатора 1.Первичная сегментация по пунктуации и сочинительным союзам с учетом простейших рядов однородных членов 2.Объединение элементов аналитических форм глагола 3.Выделение терминологических именных групп 4.Обработка существующих и восстановление пропущенных тире в функции связки 5.Построение множества МИ внутри сегментов 6.Объединение сочиненных сегментов …

ПАРСИНГ:ПРИМЕР ДЛЯ ГИБРИДНОЙ МОДЕЛИ СИНТАКСИСА (АОТ) - 4 Этапы работы синтаксического анализатора … 7.Построение сочиненных групп (именных, глагольных) внутри сегментов 8.Вложение сегментов (установление отношений подчинения) 9.Построение синт. групп, включающих вложенные сегменты 10.Объединение разрывных сегментов 11.Построение групп с использованием всех правил обработки МИ 12.Ранжирование МИ по синтаксическому покрытию

ПАРСИНГ:ПРИМЕР ДЛЯ ГИБРИДНОЙ МОДЕЛИ СИНТАКСИСА (АОТ) - 5 ТипНазваниеПример Количественная группа (последовательность числительных) КОЛИЧдвадцать восемь Последовательность чиселСЛОЖ-ЧИСЛ12,3, II-III Группа существительного, пре-модифицированная одним или несколькими прилагательными ПРИЛ-СУЩдлинная тяжелая дорога, двигающийся человек Группа существительного, пре-модифицированная наречным числительным НАР-ЧИСЛ-СУЩмного ребят, мало стульев Группа существительного, пре-модифицированная числительным СУЩ-ЧИСЛвосемь попугаев, два человека Предложная группаПГв дом, на холме … 39 типов синтаксических групп, в том числе:

ПАРСИНГ:ПРИМЕР ДЛЯ ГИБРИДНОЙ МОДЕЛИ СИНТАКСИСА (АОТ) - 6

РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА Тестелец Я. Г. Введение в общий синтаксис. М., (Главы I, II) АОТ: Синтаксический анализ. Ножов И.М. Морфологическая и синтаксическая обработка текста (модели и программы). Дисс. … канд. тех. наук. М., (Глава 3, I) или (диссертация полностью) ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА Мельчук И. А. Опыт теории лингвистических моделей «Смысл Текст». М., 1974 (1999) (Глава II, § 1, 2) Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. М.: Мир, 1978.