Разделы презентаций

АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ АЛГОРИТМИ АНАЛІЗУ

Содержание

КОНТЕКСТНО-ВІЛЬНА ГРАМАТИКА ОПИСУЄ ЧИ НАЛЕЖИТЬ СТРІЧКА (НАБІР СЛІВ) ДАНІЙ МОВІ, АЛЕ НЕ ВИЗНАЧАЄ ЯКИМ ЧИНОМ ЗДІЙСНИТИ ТАКИЙ АНАЛІЗ АБО ВСТАНОВИТИ ВІДПОВІДНІСТЬ ДО СИНТАКСИЧНОЇ СТРУКТУРИ (ДЕРЕВА)АЛГОРИТМ СИНТАКСИЧНОГО АНАЛІЗУ ВИКОРИСТОВУЄ ГРАМАТИКУ ДЛЯ ПОБУДОВИ

Слайды и текст этой презентации

Слайд 1АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ АЛГОРИТМИ АНАЛІЗУ
ЛЕКЦІЯ №10
Комп'ютерна лінгвістика (2009) Романюк А.Б.

АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ АЛГОРИТМИ АНАЛІЗУЛЕКЦІЯ №10Комп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 2
КОНТЕКСТНО-ВІЛЬНА ГРАМАТИКА ОПИСУЄ ЧИ НАЛЕЖИТЬ СТРІЧКА (НАБІР СЛІВ) ДАНІЙ МОВІ,

АЛЕ НЕ ВИЗНАЧАЄ ЯКИМ ЧИНОМ ЗДІЙСНИТИ ТАКИЙ АНАЛІЗ АБО ВСТАНОВИТИ

ВІДПОВІДНІСТЬ ДО СИНТАКСИЧНОЇ СТРУКТУРИ (ДЕРЕВА)
АЛГОРИТМ СИНТАКСИЧНОГО АНАЛІЗУ ВИКОРИСТОВУЄ ГРАМАТИКУ ДЛЯ ПОБУДОВИ ДЕРЕВА - СИНТАКСИЧНОЇ СТРУКТУРИ.

КОНТЕКСТНО-ВІЛЬНА ГРАМАТИКА

Комп'ютерна лінгвістика (2009) Романюк А.Б.

КОНТЕКСТНО-ВІЛЬНА ГРАМАТИКА ОПИСУЄ ЧИ НАЛЕЖИТЬ СТРІЧКА (НАБІР СЛІВ) ДАНІЙ МОВІ, АЛЕ НЕ ВИЗНАЧАЄ ЯКИМ ЧИНОМ ЗДІЙСНИТИ ТАКИЙ

Слайд 3КОНТЕКСТНО-ВІЛЬНА ГРАМАТИКА приклад
Комп'ютерна лінгвістика (2009) Романюк А.Б.

КОНТЕКСТНО-ВІЛЬНА ГРАМАТИКА прикладКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 4BOOK THAT FLIGHT
ДЕРЕВО РОЗБОРУ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

BOOK THAT FLIGHTДЕРЕВО РОЗБОРУ Комп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 5ЗНАЙТИ ВСІ ДЕРЕВА, В ЯКИХ КОРІНЬ S І ЯКІ МІСТЯТЬ

ВСІ СЛОВА З ВХІДНОЇ ПОСЛІДОВНОСТІ
АЛГОРИТМ ДЛЯ ЗДІЙСНЕННЯ ТАКОГО ПОШУКУ ПОВИНЕН

ВРАХОВУВАТИ ЦІ ОБМЕЖЕННЯ
ПИТАННЯ, ЯКЕ З ДЕРЕВ Є ПРАВИЛЬНИМ ДЛЯ ДАНОГО РЕЧЕННЯ І ЯКИМ ЧИНОМ ЦЕ ДЕРЕВО ВИБРАТИ З МНОЖИНИ ДЕРЕВ, ЗАЛИШАЄТЬСЯ ВІДКРИТЕ
ДВІ СТРАТЕГІЇ (ТИПИ АЛГОРИТМІВ) ЗДІЙСНЕННЯ СИНТАКСИЧНОГО АНАЛІЗУ : ЗВЕРХУ-ВНИЗ, ЗНИЗУ-ВВЕРХ

СИНТАКСИЧНИЙ АНАЛІЗ, ЯК ПОШУКОВА ЗАДАЧА

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ЗНАЙТИ ВСІ ДЕРЕВА, В ЯКИХ КОРІНЬ S І ЯКІ МІСТЯТЬ ВСІ СЛОВА З ВХІДНОЇ ПОСЛІДОВНОСТІАЛГОРИТМ ДЛЯ ЗДІЙСНЕННЯ

Слайд 6ШУКАЄМО ДЕРЕВО РОЗБОРУ “ВИВОДУ” ПОЧИНАЮЧИ ВІД S І ДОНИЗУ ДО

ЛИСТКІВ.
ПЕРЕХОДИ ДОНИЗУ ЗДІЙСНЮЮТЬСЯ НА ОСНОВІ ПРАВИЛ ГРАМАТИКИ

ЗВЕРХУ-ВНИЗ
Комп'ютерна лінгвістика (2009) Романюк

А.Б.
ШУКАЄМО ДЕРЕВО РОЗБОРУ “ВИВОДУ” ПОЧИНАЮЧИ ВІД S І ДОНИЗУ ДО ЛИСТКІВ.ПЕРЕХОДИ ДОНИЗУ ЗДІЙСНЮЮТЬСЯ НА ОСНОВІ ПРАВИЛ ГРАМАТИКИЗВЕРХУ-ВНИЗКомп'ютерна

Слайд 7Комп'ютерна лінгвістика (2009) Романюк А.Б.
ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ

ЗВЕРХУ-ВНИЗ

Комп'ютерна лінгвістика (2009) Романюк А.Б.ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗВЕРХУ-ВНИЗ

Слайд 8АНАЛІЗ ПОЧИНАЄТЬСЯ З РОЗГЛЯДУ СЛІВ, ЯКІ ПОСТУПИЛИ НА ВХІД АНАЛІЗАТОРУ
ПОСЛІДОВНІ

СПРОБИ ВИКОРИСТОВУЮЧИ ПРАВИЛА ГРАМАТИКИ ПОБУДУВАТИ ДЕРЕВО
ЗНИЗУ-ВВЕРХ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

АНАЛІЗ ПОЧИНАЄТЬСЯ З РОЗГЛЯДУ СЛІВ, ЯКІ ПОСТУПИЛИ НА ВХІД АНАЛІЗАТОРУПОСЛІДОВНІ СПРОБИ ВИКОРИСТОВУЮЧИ ПРАВИЛА ГРАМАТИКИ ПОБУДУВАТИ ДЕРЕВОЗНИЗУ-ВВЕРХКомп'ютерна лінгвістика

Слайд 9ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХ
Комп'ютерна лінгвістика (2009) Романюк

А.Б.

ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 10ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХ
Комп'ютерна лінгвістика (2009) Романюк

А.Б.

ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 11ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХ
Комп'ютерна лінгвістика (2009) Романюк

А.Б.

ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 12ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХ
Комп'ютерна лінгвістика (2009) Романюк

А.Б.

ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 13ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХ
Комп'ютерна лінгвістика (2009) Романюк

А.Б.

ПОБУДОВА ДЕРЕВА РОЗБОРУ НА ОСНОВІ СТРАТЕГІЇ ЗНИЗУ-ВВЕРХКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 14Комп'ютерна лінгвістика (2009) Романюк А.Б.
ПОРІВНЯННЯ СТРАТЕГІЙ
ЗВЕРХУ- ВНИЗ
ЗДІЙСНЮЄТЬСЯ ПОШУК ДЕРЕВ, ЯКІ

МАЮТЬ S В КОРЕНІ
БУДУЮТЬСЯ ДЕРЕВА, ЯКІ НЕ ВІДПОВІДАЮТЬ ВХІДНІЙ ПОСЛІДОВНОСТІ
ЗНИЗУ

- ВВЕРХ
БУДУЮТЬСЯ ДЕРЕВА, ЯКІ ВІДПОВІДАЮТЬ ВХІДНІЙ ПОСЛІДОВНОСТІ
РОЗГЛЯДАЮТЬСЯ ДЕРЕВА, ЯКІ НІКОЛИ НЕ БУДУТЬ МАТИ КОРЕНЯ S

S

Комп'ютерна лінгвістика (2009) Романюк А.Б.ПОРІВНЯННЯ СТРАТЕГІЙЗВЕРХУ- ВНИЗЗДІЙСНЮЄТЬСЯ ПОШУК ДЕРЕВ, ЯКІ МАЮТЬ S В КОРЕНІБУДУЮТЬСЯ ДЕРЕВА, ЯКІ НЕ

Слайд 15СТРУКТУРНА НЕОДНОЗНАЧНІСТЬ (МОЖНА ПОБУДУВАТИ БІЛЬШ НІЖ ОДНЕ ДЕРЕВО ДЛЯ ОДНОГО

РЕЧЕННЯ) ВКЛЮЧАЄ:
НЕОДНОЗНАЧНІСТЬ ПРИЄДНАННЯ
ONE MORNING I SHOT AN ELEPHANT IN MY

PAJAMAS
НЕОДНОЗНАЧНІСТЬ КООРДИНАЦІЇ
OLD MAN AND WOMEN

ЛОКАЛЬНА НЕОДНОЗНАЧНІСТЬ
BOOK THAT FLIGHT

КІЛЬКІСТЬ ДЕРЕВ = еN (N-кількість слів у реченні)



НЕОДНОЗНАЧНІСТЬ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРУКТУРНА НЕОДНОЗНАЧНІСТЬ (МОЖНА ПОБУДУВАТИ БІЛЬШ НІЖ ОДНЕ ДЕРЕВО ДЛЯ ОДНОГО РЕЧЕННЯ) ВКЛЮЧАЄ:НЕОДНОЗНАЧНІСТЬ ПРИЄДНАННЯONE MORNING I SHOT AN

Слайд 16НЕОДНОЗНАЧНІСТЬ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

НЕОДНОЗНАЧНІСТЬКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 17СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМ
ЗАДАЧУ ОДНОЧАСНОЇ ПОБУДУДОВИ ВСІХ ДЕРЕВ ВИРІШИТИ НЕМОЖЛИВО
ДЕРЕВА

БУДУЮТЬСЯ ПОСТУПОВО ОДНЕ ЗА ОДНИМ
ЯКЩО ДЕРЕВО ПОБУДУВАТИ НЕ ВДАЛОСЯ, ТО

ПОВЕРТАЄМОСЯ В ПОЧАТКОВИЙ СТАН
НЕОДНОЗНАЧНІСТЬ ГРАМАТИКИ, НАПРИКЛАД ВИБІР ОДНОГО З ПРАВИЛ
Nominal -> Noun
Nominal -> Nominal PP


Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМЗАДАЧУ ОДНОЧАСНОЇ ПОБУДУДОВИ ВСІХ ДЕРЕВ ВИРІШИТИ НЕМОЖЛИВОДЕРЕВА БУДУЮТЬСЯ ПОСТУПОВО ОДНЕ ЗА ОДНИМЯКЩО ДЕРЕВО ПОБУДУВАТИ

Слайд 18СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМ
A flight from Indianapolis to Houston on

TWA
Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМA flight from Indianapolis to Houston on TWAКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 19СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 20СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 21СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 22СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

СТРАТЕГІЯ ПЕРЕБОРУ З ПОВЕРНЕННЯМКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 23ЗБЕРІГАЮТЬСЯ ВСІ ПРОМІЖНІ РІШЕННЯ ДЛЯ ВИРІШЕННЯ ОСНОВНОЇ ЗАДАЧІ
ПІДДЕРЕВА ДЛЯ ОКРЕМИХ

СКЛАДНИКІВ БУДУЮТЬСЯ ОДИН РАЗ І ЗБЕРІГАЮТЬСЯ ДЛЯ ПОВТОРНОГО ВИКОРИСТАННЯ
ВИРІШУЄТЬСЯ ПРОБЛЕМА

ПОВТОРНОЇ ПОБУДОВИ ПІДДЕРЕВ
ЧАСТКОВО ВИРІШУЄТЬСЯ ПРОБЛЕМА НЕОДНОЗНАЧНОСТІ – Є ВСІ СКЛАДОВІ ТА ЇХ ЗВ’ЯЗКИ, ЩО ДОЗВОЛЯЄ ПЕРЕБУДОВУВАТИ ДЕРЕВО

ДИНАМІЧНЕ ПРОГРАМУВАННЯ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ЗБЕРІГАЮТЬСЯ ВСІ ПРОМІЖНІ РІШЕННЯ ДЛЯ ВИРІШЕННЯ ОСНОВНОЇ ЗАДАЧІПІДДЕРЕВА ДЛЯ ОКРЕМИХ СКЛАДНИКІВ БУДУЮТЬСЯ ОДИН РАЗ І ЗБЕРІГАЮТЬСЯ ДЛЯ

Слайд 24АЛГОРИТМ ВИКОРИСТОВУЄ ГРАМАТИКІ ТІЛЬКИ В НОРМАЛЬНІЙ ФОРМІ ХОМСЬКОГО
ПРАВИЛА В НОРМАЛЬНІЙ

ФОРМІ ХОМСЬКОГО МАЮТЬ ВИГЛЯД A —> Β C АБО A

—> α
БУДЬ-ЯКУ КВГ МОЖНА ПЕРЕТВОРИТИ ДО НОРМАЛЬНОЇ ФОРМИ ХОМСЬКОГО

АЛГОРИТМ СИНТАКСИЧНОГО АНАЛІЗУ СKY

Комп'ютерна лінгвістика (2009) Романюк А.Б.

АЛГОРИТМ ВИКОРИСТОВУЄ ГРАМАТИКІ ТІЛЬКИ В НОРМАЛЬНІЙ ФОРМІ ХОМСЬКОГОПРАВИЛА В НОРМАЛЬНІЙ ФОРМІ ХОМСЬКОГО МАЮТЬ ВИГЛЯД A —> Β

Слайд 25В ЗВИЧАЙНІЙ ГРАМАТИЦІ МОЖЛИВІ ТАКІ СИТУАЦІЇ:
В ПРАВИЛАХ СПРАВА Є ТЕРМІНАЛЬНІ

І НЕ ТЕРМІНАЛЬНІ СИМВОЛИ
В ПРАВИЛАХ СПРАВА Є ОДИН НЕ ТЕРМІНАЛЬНИЙ

СИМВОЛ
В ПРАВИЛАХ СПРАВА Є БІЛЬШ НІЖ ДВА НЕ ТЕРМІНАЛЬНІ СИМВОЛИ

ПЕРТВОРЕННЯ ГРАМАТИКИ ДО НОРМАЛЬНОЇ ФОРМИ ХОМСЬКОГО

Комп'ютерна лінгвістика (2009) Романюк А.Б.

В ЗВИЧАЙНІЙ ГРАМАТИЦІ МОЖЛИВІ ТАКІ СИТУАЦІЇ:В ПРАВИЛАХ СПРАВА Є ТЕРМІНАЛЬНІ І НЕ ТЕРМІНАЛЬНІ СИМВОЛИВ ПРАВИЛАХ СПРАВА Є

Слайд 26КОПІЮВАТИ ВСІ ПРАВИЛА, ЯКІ ВІДПОВІДАЮТЬ ВИМОГАМ В НОВУ ГРАМАТИКУ
ПЕРЕТВОРИТИ ТЕРМІНАЛИ

В ПРАВИЛАХ ВВІВШИ ФІКТИВНІ НЕ ТЕРМІНАЛИ
ПЕРЕТВОРИТИ ОДИНИЧНІ ПРАВИЛА
ПЕРЕТВОРИТИ ВСІ ПРАВИЛА

НА БІНАРНІ І ДОДАТИ ДО НОВОЇ ГРАМАТИКИ

ПЕРТВОРЕННЯ ГРАМАТИКИ ДО НОРМАЛЬНОЇ ФОРМИ ХОМСЬКОГО

Комп'ютерна лінгвістика (2009) Романюк А.Б.

КОПІЮВАТИ ВСІ ПРАВИЛА, ЯКІ ВІДПОВІДАЮТЬ ВИМОГАМ В НОВУ ГРАМАТИКУПЕРЕТВОРИТИ ТЕРМІНАЛИ В ПРАВИЛАХ ВВІВШИ ФІКТИВНІ НЕ ТЕРМІНАЛИПЕРЕТВОРИТИ ОДИНИЧНІ

Слайд 27ЗВИЧАЙНА ГРАМАТИКА
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ЗВИЧАЙНА ГРАМАТИКАКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 28ГРАМАТИКА ПЕРЕТВОРЕНА В НОРМАЛЬНУ ФОРМУ ХОМСЬКОГО
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ГРАМАТИКА ПЕРЕТВОРЕНА В НОРМАЛЬНУ ФОРМУ ХОМСЬКОГОКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 29ОСКІЛЬКИ, ГРАМАТИКА В НОРМАЛЬНІЙ ФОРМІ, ТО КОЖЕН НЕТЕРМІНАЛЬНИЙ СИМВОЛ (НЕТЕРМІНАЛЬНИЙ

ВУЗОЛ ДЕРЕВА ) МОЖЕ МАТИ ТІЛЬКИ ДВІ “ДОНЬКИ”
ПРОСТА ДВОВИМІРНА МАТРИЦЯ

ВИКОРИСТОВУЄТЬСЯ ДЛЯ ЗБЕРЕЖЕННЯ СТРУКТУРИ ВСЬОГО ДЕРЕВА

CKY АЛГОРИТМ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ОСКІЛЬКИ, ГРАМАТИКА В НОРМАЛЬНІЙ ФОРМІ, ТО КОЖЕН НЕТЕРМІНАЛЬНИЙ СИМВОЛ (НЕТЕРМІНАЛЬНИЙ ВУЗОЛ ДЕРЕВА ) МОЖЕ МАТИ ТІЛЬКИ ДВІ

Слайд 30ДЛЯ РЕЧЕННЯ ДОВЖИНОЮ N БУДУЄТЬСЯ МАТРИЦЯ РОЗМІРОМ (N+1)*(N+1)
КОЖЕН ЕЛЕМЕНТ (I,J)

МАТРИЦІ МІСТИТЬ НАБІР НЕТЕРМІНАЛЬНИХ СИМВОЛІВ, ЩО ПРЕДСТАВЛЯЮТЬ ВСІ СКЛАДОВІ, ЯКІ

ОХОПЛЮЮТЬ ПОЗИЦІЇ ВІД I ДО J ВХІДНИХ ЕЛЕМЕНТІВ
В КОМІРЦІ МАТРИЦІ (0,N) , ЯКА ПРЕДСТАВЛЯЄ ВСЕ РЕЧЕННЯ ОЧІКУЄТЬСЯ СИМВОЛ S

CKY АЛГОРИТМ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ДЛЯ РЕЧЕННЯ ДОВЖИНОЮ N БУДУЄТЬСЯ МАТРИЦЯ РОЗМІРОМ (N+1)*(N+1)КОЖЕН ЕЛЕМЕНТ (I,J) МАТРИЦІ МІСТИТЬ НАБІР НЕТЕРМІНАЛЬНИХ СИМВОЛІВ, ЩО ПРЕДСТАВЛЯЮТЬ

Слайд 31
ДЛЯ ПРАВИЛА ВИДУ A  B C ПОВИННО БУТИ ДЕЯКЕ

К ТАКЕ, ЩО B Є В ПРОМІЖКУ [І,К] ТА

C Є В ПРОМІЖКУ [К,J].
ЯКЩО A ВІДПОВІДАЄ ПРОМІЖКУ I,J З ВХІДНОЇ ПОСЛІДОВНОСТІ І A  B C - ПРАВИЛО З ГРАМАТИКИ, ТО ПОВИННО БУТИ B В ПРОМІЖКУ [І,К] ТА C В ПРОМІЖКУ [К,J] ДЛЯ iПОЧАТКОВА ЗАДАЧА - ПРАВИЛЬНО ЗАПОВНИТИ МАТРИЦЮ (ТАБЛИЦЮ)
МАТРИЦЯ ЗАПОВНЮЄТЬСЯ ЗНИЗУ-ВВЕРХ І ЗЛІВА - НАПРАВО

CKY АЛГОРИТМ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ДЛЯ ПРАВИЛА ВИДУ A  B C ПОВИННО БУТИ ДЕЯКЕ К ТАКЕ, ЩО B Є В

Слайд 32CKY ТАБЛИЦЯ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

CKY ТАБЛИЦЯКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 33Комп'ютерна лінгвістика (2009) Романюк А.Б.
CKY АЛГОРИТМ

Комп'ютерна лінгвістика (2009) Романюк А.Б.CKY АЛГОРИТМ

Слайд 34CKY АЛГОРИТМ
МАТРИЦЯ (ТАБЛИЦЯ) ЗАПОВНЕНА
ПОТРІБНО ОТРИМАТИ ДЕРЕВО
ПРИ ЗАПОВНЕНІ МАТРИЦІ ПОТРІБНО ЗБЕРІГАТИ

ІНФОРМАЦІЮ ПРО ТЕ, НА ОСНОВІ ЯКИХ КОМІРОК ОТРИМАНО ПОТОЧНИЙ НЕТЕРМІНАЛЬНИЙ

СИМВОЛ
ПРИ ЗАПОВНЕННІ МАТРИЦІ В КОМІРЦІ ПОТРІБНО ЗБЕРІГАТИ РІЗНІ ВЕРСІЇ ТОГО САМОГО НЕТЕРМІНАЛЬНОГО СИМВОЛУ
ЗАПОВНЕНА ТАКИМ СПОСОБОМ МАТРИЦЯ ДОЗВОЛИТЬ ПОБУДУВАТИ ВСІ ДЕРЕВА РУХАЮЧИСЬ ВІД S ПО ЙОГО СКЛАДНИКАХ.

Комп'ютерна лінгвістика (2009) Романюк А.Б.

CKY АЛГОРИТММАТРИЦЯ (ТАБЛИЦЯ) ЗАПОВНЕНАПОТРІБНО ОТРИМАТИ ДЕРЕВОПРИ ЗАПОВНЕНІ МАТРИЦІ ПОТРІБНО ЗБЕРІГАТИ ІНФОРМАЦІЮ ПРО ТЕ, НА ОСНОВІ ЯКИХ КОМІРОК

Слайд 35ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 36ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІ
ЗАПОВНЕННЯ КОЛОНКИ 5
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІЗАПОВНЕННЯ КОЛОНКИ 5Комп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 37ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 38ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 39ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІ
Комп'ютерна лінгвістика (2009) Романюк А.Б.

ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІКомп'ютерна лінгвістика (2009) Романюк А.Б.

Слайд 40ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІ
S1 – PP (FLIGHT)
S2 – PP (BOOK)
S3 –

VP->X2 PP
VP->Verb NP PP
Комп'ютерна лінгвістика (2009)

Романюк А.Б.
ПРИКЛАД ЗАПОВНЕННЯ ТАБЛИЦІS1 – PP (FLIGHT)S2 – PP (BOOK)S3 – VP->X2 PP VP->Verb NP

Слайд 41ПРОБЛЕМИ ВИКОРИСТАННЯ CKY АЛГОРИТМУ
ПОБУДОВА ВСІХ ДЕРЕВ ДУЖЕ ДОРОГА ОПЕРАЦІЯ
ВИМОГА ВИКОРИСТАННЯ

НОРМАЛЬНОЇ ФОРМИ ХОМСЬКОГО ПРИВОДИТЬ ДО:
НЕОБХІДНОСТІ РОЗРОБНИКАМ ГРАМАТИКИ ВРАХОВУВАТИ ЦЮ ВИМОГУ
СКЛАДНОЩІВ

ПРИ ВИКОРИСТАННІ ЧУЖИХ ГРАМАТИК
ВИНИКНЕННЯ ПРОБЛЕМ ПРИ ВИКОРИСТАННІ ТАКОЇ ГРАМАТИКИ ПРИ СЕМАНТИЧНОМУ АНАЛІЗІ
ОСНОВНА ПРОБЛЕМА: ВСІ АЛГОРИТМИ ЗНИЗУ-ВВЕРХ ПРИ СИНТАКСИЧНОМУ АНАЛІЗІ ПРИВОДЯТЬ ДО ПОБУДОВИ ВЕЛИКОЇ КІЛЬКОСТІ СКЛАДНИКІВ, ЯКІ НАСПРАВДІ НІКОЛИ НЕ БУДУТЬ ВИКОРИСТАНІ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

ПРОБЛЕМИ ВИКОРИСТАННЯ CKY АЛГОРИТМУПОБУДОВА ВСІХ ДЕРЕВ ДУЖЕ ДОРОГА ОПЕРАЦІЯВИМОГА ВИКОРИСТАННЯ НОРМАЛЬНОЇ ФОРМИ ХОМСЬКОГО ПРИВОДИТЬ ДО:НЕОБХІДНОСТІ РОЗРОБНИКАМ

Слайд 42Daniel Jurafsky, James H. Martin Speech and Language Processing: an

Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition

- Second Edition Prentice Hall, 2008 -988. – Розділ,13 ст. 427-458.

НЕОБХІДНО ПРОЧИТАТИ

Комп'ютерна лінгвістика (2009) Романюк А.Б.

Daniel Jurafsky, James H. Martin Speech and Language Processing: an Introduction to Natural Language Processing, Computational Linguistics,

Похожие презентации

Russia; People we are proud of; History of Russia; Moscow; Traditions; Famous Russia; People we are proud of; History of Russia; Moscow; Traditions; Famous 287
Иван Шкловец заместитель руководителя Федеральной службы по труду и Иван Шкловец заместитель руководителя Федеральной службы по труду и 164
КОММЕРЧЕСКОЕ ПРЕДЛОЖЕНИЕ КВС. Управление недвижимостью имеет успешный опыт по КОММЕРЧЕСКОЕ ПРЕДЛОЖЕНИЕ КВС. Управление недвижимостью имеет успешный опыт по 160
Характерные особенности класса Млекопитающих Отряд ластоногие (PINNIPEDIA) Характерные особенности класса Млекопитающих Отряд ластоногие (PINNIPEDIA) 164
Исследовательская деятельность Исследовательская деятельность 215
Род глаголов в прошедшем времени 148 Род глаголов в прошедшем времени 148 193
Правонарушение. Юридическая ответственность. Законность и правопорядок Правонарушение. Юридическая ответственность. Законность и правопорядок 250
3.ppt 3.ppt 224
ТАРАСОВА ЕЛИЗАВЕТА ЕВГЕНЬЕВНА первый проректор по научной работе Белгородского ТАРАСОВА ЕЛИЗАВЕТА ЕВГЕНЬЕВНА первый проректор по научной работе Белгородского 327
Ткани растений Ткани растений 259
Зарубежные ИСУП Зарубежные ИСУП 245
Мурманск – Город-герой Мурманск – Город-герой 157
Дисциплина Рекламная деятельность Дисциплина Рекламная деятельность 221
Литературные юбилеи 2019 ЦБС г. Арзамаса Центральная детская библиотека им Литературные юбилеи 2019 ЦБС г. Арзамаса Центральная детская библиотека им 178
PALLIATIVE MEDICAL CARE Chandankumar nittur bhaktaprakash (La2-co-161A) PALLIATIVE MEDICAL CARE Chandankumar nittur bhaktaprakash (La2-co-161A) 174
ДЗ 3. Прибыль фирмы. Вопросы к пар. 22, стр. 154 ДЗ 3. Прибыль фирмы. Вопросы к пар. 22, стр. 154 208
История стиля Electro Dance История стиля Electro Dance 242
Древняя Спарта Древняя Спарта 483
ФЗ № 52   ФЗ № 52  "О санитарно-эпидемиологическом благополучии населения" 520
ФГАОУ ВО ФГАОУ ВО "КРЫМСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ им. В.И.ВЕРНАДСКОГО" "МЕДИЦИНСКАЯ 199

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика