Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
АВТОМАТИЧНИЙ МОРФОЛОГІЧНИЙ АНАЛІЗ. СКІНЧЕННИЙ ПЕРЕТВОРЮВАЧ БЕЗ ЛЕКСИКОНУ
Содержание
- 1. АВТОМАТИЧНИЙ МОРФОЛОГІЧНИЙ АНАЛІЗ. СКІНЧЕННИЙ ПЕРЕТВОРЮВАЧ БЕЗ ЛЕКСИКОНУ
- 2. СКІНЧЕННИЙ ПЕРЕТВОРЮВАЧ БЕЗ ЛЕКСИКОНУЗАДАЧА ІНФОРМАЦІЙНОГО ПОШУКУ (IR)ПОШУКОВИЙ
- 3. АЛГОРИТМ СТЕМІНГУ PORTERСЕРІЇ ПРОСТИХ ПРАВИЛ ПЕРЕТВОРЕНЬПОМИЛКИ ВЛАСТИВІ АЛГОРИТМУКомп'ютерна лінгвістика (2009) Романюк А.Б.
- 4. ТОКЕНІЗАЦІЯ ТОКЕНІЗАЦІЯ – ПОЧАТКОВИЙ ЕТАП ОБРОБКИ ТЕКСТІВ,
- 5. ТОКЕНІЗАЦІЯ (ПРОДОВЖЕННЯ)РЕЗУЛЬТАТ ТОКЕНІЗАЦІЇ СЛІВ ЗА ПРОБІЛАМИ cents.
- 6. ТОКЕНІЗАЦІЯ (ПРОДОВЖЕННЯ)ПОСЛІДОВНІСТЬ КРОКІВ ПРИ ТОКЕНІЗАЦІЇ СЛІВ НА
- 7. ПРИКЛАД ТОКЕНІЗАЦІЇ РЕЧЕНЬ ПРИ ПОБУДОВІ ПАРАЛЕЛЬНОГО КОРПУСА
- 8. ПРИКЛАД ТОКЕНІЗАЦІЇ РЕЧЕНЬ ПРИ ПОБУДОВІ ПАРАЛЕЛЬНОГО КОРПУСА
- 9. ФРАГМЕНТ ПРОГРАМИ ТОКЕНІЗАЦІЇ (ПАЛІЙ З. 2008р.)import refrom
- 10. ВИЯВЛЕННЯ ТА ВИПРАВЛЕННЯ ПОМИЛОК В ТЕКСТАХЧАСТОТА ПОМИЛОК
- 11. ОСНОВНІ ЗАДАЧІ ВИЯВЛЕННЯ ТА ВИПРАВЛЕННЯ ПОМИЛОКВИЯВЛЕННЯ ПОМИЛОК,
- 12. ВИПРАВЛЕННЯ ПОМИЛОК НА ОСНОВІ ПОРІВНЯННЯ СТРІЧОКВСТАНОВЛЕННЯ ЯКЕ
- 13. АЛГОРИТМ MINIMUM EDIT DISTANCE ВІДСТАНЬ
- 14. ВІДСТАНЬ ЛЕВЕНШТЕЙНА (1964)ВАРТІСТЬ (ВАГА ОПЕРАЦІЙ)D – ВИДАЛЕННЯ=1І
- 15. АЛГОРИТМ MINIMUM EDIT DISTANCEКомп'ютерна лінгвістика (2009) Романюк А.Б.ПЕРЕЛІК НЕОБХІДНИХ ПЕРЕТВОРЕНЬ
- 16. АЛГОРИТМ MINIMUM EDIT DISTANCEнебо -> неба (замінюємо
- 17. ПОШУК МІНІМАЛЬНОЇ ВІДСТАНІ РЕДАГУВАННЯ – ПОШУКОВА ЗАДАЧА
- 18. МАТРИЦЯ ВІДСТАНЕЙ ДЛЯ ПОРІВНЯННЯ ПОСЛІДОВНОСТЕЙРОЗМІР МАТРИЦІ (N+1)X(M+1)N
- 19. ЕЛЕМЕНТИ МАТРИЦІ ВІДСТАНЕЙКомп'ютерна лінгвістика (2009) Романюк А.Б.ВИЗНАЧАЮТЬСЯ НА ОСНОВІ РЕКУРСИВНОГО РІВНЯННЯ
- 20. МАТРИЦЯ ВІДСТАНЕЙ ДЛЯ СТРІЧОК INTENTION ТА EXECUTIONКомп'ютерна лінгвістика (2009) Романюк А.Б.
- 21. АЛГОРИТМ MINIMUM EDIT DISTANCE Комп'ютерна лінгвістика (2009) Романюк А.Б.
- 22. АЛГОРИТМ MINIMUM EDIT DISTANCE ЩОБ ОТРИМАТИ СТРІЧКУ
- 23. АЛГОРИТМ MINIMUM EDIT DISTANCE http://rain.ifmo.ru/cat/view.php/vis/strings/levenshtein-2009ЗАПОВНЕННЯ ПЕРШОГО СТОВПЧИКА МАТРИЦІІ=1, J=1,2,3,4,5,6,7,8,9Комп'ютерна лінгвістика (2009) Романюк А.Б.
- 24. РЕАЛІЗАЦІЯ АЛГОРИТМУ НА МОВІ PYTHONdef distance(a, b):
- 25. МАТРИЦЯ ВІДСТАНЕЙ ДЛЯ СТРІЧОК INTENTION ТА EXECUTIONКомп'ютерна
- 26. ВИЗНАЧЕННЯ МІНІМАЛЬНОГО ШЛЯХУ ВИРІВНЮВАННЯ МІЖ СТРІЧКАМИ (ДИНАМІЧНЕ
- 27. ВИЗНАЧЕННЯ МІНІМАЛЬНОГО ШЛЯХУ ВИРІВНЮВАННЯ МІЖ СТРІЧКАМИКомп'ютерна лінгвістика (2009) Романюк А.Б.
- 28. ПЕРЕДБАЧЕННЯ СЛІВ. N-ГРАМИN-ГРАМ МОДЕЛЬ – ІМОВІРНІСНА МОДЕЛЬ,
- 29. ПЕРЕДБАЧЕННЯ СЛІВ. N-ГРАМИВИЗНАЧЕННЯ ЙМОВІРНОСТІ НАСТУПНОГО СЛОВА ТІСНО
- 30. ВИКОРИСТАННЯ N-ГРАМ МОДЕЛЕЙРОЗПІЗНАВАННЯ УСНОГО МОВЛЕННЯРОЗПІЗНАВАННЯ РУКОПИСНОГО ТЕКСТУМАШИННИЙ
- 31. ВИЗНАЧЕННЯ ІМОВІРНОСТЕЙНА ОСНОВІ ПІДРАХУНКІВ В КОРПУСАХ ТЕКСТІВЩО
- 32. N-ГРАМИ. ВИЗНАЧЕННЯ ІМОВІРНОСТІМЕТА: ОБЧИСЛИТИ ЙМОВІРНІСТЬ СЛОВА W
- 33. N-ГРАМИ. ВИЗНАЧЕННЯ ІМОВІРНОСТІЯ ХОЧУ ОТРИМАТИ – 62
- 34. ВИЗНАЧЕННЯ ЗАГАЛЬНОЇ ЙМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВP(w1,w2,w3,……..wn)CHAIN RULE (ПРАВИЛО
- 35. ВИЗНАЧЕННЯ ЗАГАЛЬНОЇ ЙМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВКомп'ютерна лінгвістика (2009)
- 36. ВИЗНАЧЕННЯ ЗАГАЛЬНОЇ ЙМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВПРОБЛЕМА ВИЗНАЧЕННЯ -
- 37. ЗАСТОСУВАННЯ ПРИПУЩЕННЯ МАРКОВАКомп'ютерна лінгвістика (2009) Романюк А.Б.
- 38. ВИЗНАЧЕННЯ ЙМОВІРНОСТІ N-ГРАМІВ НА ОСНОВІ МЕТОДУ МАКСИМАЛЬНОЇ ПРАВДОПОДІБНОСТІБІГРАМ Комп'ютерна лінгвістика (2009) Романюк А.Б.
- 39. ПРИКЛАДКомп'ютерна лінгвістика (2009) Романюк А.Б. I am
- 40. ПРИКЛАД (9332 РЕЧЕННЯ) Berkeley Restaurant Project
- 41. ЙМОВІРНОСТІ БІГРАМІВЙМОВІРНІСТЬ ВИЗНАЧАЄТЬСЯ ДІЛЕННЯМ ЧАСТОТИ БІГРАМІВ НА ЧАСТОТУ ПОПЕРЕДНЬОГО СЛОВА В КОРПУСІКомп'ютерна лінгвістика (2009) Романюк А.Б.
- 42. ЙМОВІРНІСТЬ РЕЧЕННЯКомп'ютерна лінгвістика (2009) Романюк А.Б.I WANT CHINESE FOOD – 0,0001
- 43. ЯКУ ІНФОРМАЦІЮ МОЖНА ОТРИМАТИ З АНАЛІЗУ ІМОВІРНОСТЕЙ
- 44. НЕОБХІДНО ПРОЧИТАТИDaniel Jurafsky, James H. Martin Speech
- 45. Скачать презентанцию
СКІНЧЕННИЙ ПЕРЕТВОРЮВАЧ БЕЗ ЛЕКСИКОНУЗАДАЧА ІНФОРМАЦІЙНОГО ПОШУКУ (IR)ПОШУКОВИЙ ЗАПИТ (студент OR викладач 6 960 000) (студентка OR викладач 2 080 000)ПОТРІБЕН СТЕМІНГ (ВСТАНОВЛЕННЯ ОСНОВИ СЛОВА) ЗАПИТІВ ТА СЛІВ В ДОКУМЕНТАХСТЕМІНГ ПРОВОДИЬСЯ НА ОСНОВІ МА БЕЗ
Слайды и текст этой презентации
Слайд 1АВТОМАТИЧНИЙ МОРФОЛОГІЧНИЙ АНАЛІЗ. СКІНЧЕННИЙ ПЕРЕТВОРЮВАЧ БЕЗ ЛЕКСИКОНУ (СТЕМІНГ). ТОКЕНІЗАЦІЯ. ВИЯВЛЕННЯ ТА ВИПРАВЛЕННЯ ПОМИЛОК. ПЕРЕДБАЧЕННЯ
НОВИХ СЛІВ. N-ГРАМИ
Слайд 2СКІНЧЕННИЙ ПЕРЕТВОРЮВАЧ БЕЗ ЛЕКСИКОНУ
ЗАДАЧА ІНФОРМАЦІЙНОГО ПОШУКУ (IR)
ПОШУКОВИЙ ЗАПИТ (студент OR
викладач 6 960 000)
(студентка OR викладач 2 080 000)
ПОТРІБЕН СТЕМІНГ (ВСТАНОВЛЕННЯ ОСНОВИ
СЛОВА) ЗАПИТІВ ТА СЛІВ В ДОКУМЕНТАХСТЕМІНГ ПРОВОДИЬСЯ НА ОСНОВІ МА БЕЗ ВИКОРИСТАННЯ ЛЕКСИКОНА
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 3АЛГОРИТМ СТЕМІНГУ PORTER
СЕРІЇ ПРОСТИХ ПРАВИЛ ПЕРЕТВОРЕНЬ
ПОМИЛКИ ВЛАСТИВІ АЛГОРИТМУ
Комп'ютерна лінгвістика (2009)
Романюк А.Б.
Слайд 4ТОКЕНІЗАЦІЯ
ТОКЕНІЗАЦІЯ – ПОЧАТКОВИЙ ЕТАП ОБРОБКИ ТЕКСТІВ, ЯКИЙ ПЕРЕДБАЧАЄ ПОДІЛ
(ВИДІЛЕННЯ ) ТЕКСТУ НА ОКРЕМІ СЛОВА ТА РЕЧЕННЯ
Mr. Sherwood
said reaction to Sea Containers' proposal has been "very positive." In New York Stock Exchange composite trading yesterday. Sea Containers closed at $62,625, up 62.5 cents.''I said, 'what're you? Crazy?' '' said Sadowsky. '‘ I can't afford to do that.''
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 5ТОКЕНІЗАЦІЯ (ПРОДОВЖЕННЯ)
РЕЗУЛЬТАТ ТОКЕНІЗАЦІЇ СЛІВ ЗА ПРОБІЛАМИ
cents. said, positive.“ Crazy?
ПРИКЛАДИ
СЛІВ ТОКЕНІЗАЦІЯ ЯКИХ Є СКЛАДНОЮ ЗАДАЧЕЮ
К.Т.Н. , ММ.РТ.СТ., 14/10/2009,
BOOK’S, WHAT’RE, complinguistics.blogspot.com,555,555.55 555 555,55
БІЛА ЦЕРКВА, П’ЯТНИЦЯ, П’ЯТНИЧАНИ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 6ТОКЕНІЗАЦІЯ (ПРОДОВЖЕННЯ)
ПОСЛІДОВНІСТЬ КРОКІВ ПРИ ТОКЕНІЗАЦІЇ СЛІВ НА ОСНОВІ РЕГУЛЯРНИХ ВИРАЗІВ
ВИДІЛЕННЯ
(ВІДДІЛЕННЯ ПРОБІЛАМИ) ОДНОЗНАЧНИХ РОЗДІЛОВИХ ЗНАКІВ (!,?,(,))
ВИДІЛЕННЯ КОМ, ЗА ВИКЛЮЧЕННЯМ КОМ
В ЧИСЛОВИХ ПОСЛІДОВНОСТЯХВІДДІЛЕННЯ ОДИНАРНИХ ЛАПОК ВІД АПОСТРОФІВ
ВИДІЛЕННЯ CLITICS
ВИДІЛЕННЯ КРАПОК (СЛОВНИК СКОРОЧЕНЬ ТА АБРЕВІАТУР)
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 7ПРИКЛАД ТОКЕНІЗАЦІЇ РЕЧЕНЬ ПРИ ПОБУДОВІ ПАРАЛЕЛЬНОГО КОРПУСА
ПОЧАТКОВИЙ ТЕКСТ
- Бери,
бери, Елберте. Що важливіше - дружба чи якась там п'ятірка?
Вважай, що я частую тебе обідом.Він вийшов з кабіни й попрямував коридором. Ідучи, стиха пробурмотів:
- Ох, і тюхтій же ти, Молверне...
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 8ПРИКЛАД ТОКЕНІЗАЦІЇ РЕЧЕНЬ ПРИ ПОБУДОВІ ПАРАЛЕЛЬНОГО КОРПУСА
РЕЗУЛЬТАТ ТОКЕНІЗАЦІЇ
18
"Skip it, Albert. What's a fin between pals? Eat some
extra meals on me."15 - Бери, бери, Елберте. Що важливіше - дружба чи якась там п'ятірка? Вважай, що я частую тебе обідом.
19 He got out of the car and started along the corridor.
16 Він вийшов з кабіни й попрямував коридором.
20 Softly, under his breath, he said:
17 Ідучи, стиха пробурмотів:
21 "Sucker .
18 - Ох, і тюхтій же ти, Молверне...
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 9ФРАГМЕНТ ПРОГРАМИ ТОКЕНІЗАЦІЇ (ПАЛІЙ З. 2008р.)
import re
from re import compile
patternSimplex
= compile("\-+ +[A-Z]+.+[.!?]")
patternComplex = compile("\-+ +[A-Z]+.+ +\.+\.+\.")
## Simple pattern
of direct speech (DS) like - Pryvit!## if patternSimplex.match(line):
#print 'Simplex--> ', (patternSimplex.match(line)).group()
NewList2.append((patternSimplex.match(line)).group()+'\n')
line = line.replace(patternSimplex.match(line).group(),'')
NewList2.append(line.strip()+'\n')
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 10ВИЯВЛЕННЯ ТА ВИПРАВЛЕННЯ ПОМИЛОК В ТЕКСТАХ
ЧАСТОТА ПОМИЛОК ВІД 0.05% ДО
38%.
ЗАДАЧА ВИЯВЛЕННЯ ТА ВИПРАВЛЕН Я ПОМИЛОК ВИРІШУЄТЬСЯ В ТЕКСТОВИХ ПРОЦЕСОРАХ,
ПОШУКОВИХ СИСТЕМАХ, СИСТЕМАХ РОЗПІЗНАВАННЯ ТЕКСТІВ ТА РУКОПИСНОГО ТЕКСТУОСНОВНИЙ ПІДХІД - ВИКОРИСТАННЯ ІМОВІРНІСНИХ МОДЕЛЕЙ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 11ОСНОВНІ ЗАДАЧІ ВИЯВЛЕННЯ ТА ВИПРАВЛЕННЯ ПОМИЛОК
ВИЯВЛЕННЯ ПОМИЛОК, ЩО ПРИВОДЯТЬ ДО
УТВОРЕННЯ НЕВІДОМИХ СЛІВ (GRAFFE - GIRAFFE, КНЬ-КІНЬ)
ВИПРАВЛЕННЯ ПОМИЛОК В ОКРЕМИХ
СЛОВАХВИЯВЛЕННЯ І ВИПРАВЛЕННЯ ПОМИЛОК З ВРАХУВАННЯМ КОНТЕКСТУ (THERE-THREE, АХМАТОВА-АХМЕТОВА, DESSERT-DESERT, PIECE-PEACE, РІКА-РУКА, КУТАТИ-КУСАТИ)
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 12ВИПРАВЛЕННЯ ПОМИЛОК НА ОСНОВІ ПОРІВНЯННЯ СТРІЧОК
ВСТАНОВЛЕННЯ ЯКЕ З ДВОХ СЛІВ
Є БЛИЖЧЕ ЗА ПРАВОПИСОМ ДО ТРЕТЬОГО – ОКРЕМИЙ ВИПАДОК ПОРІВНЯННЯ
СТРІЧОК (STRING DISTANCE)ПОРІВНЯТИ СТРІЧКИ - ВСТАНОВИТИ МІРУ ВІДМІННОСТІ МІЖ ДВОМА ПОСЛІДОВНОСТЯМИ СИМВОЛІВ
АЛГОРИТМ MINIMUM EDIT DISTANCE
ВІДСТАНЬ ЛЕВЕНШТЕЙНА
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 13АЛГОРИТМ MINIMUM EDIT DISTANCE
ВІДСТАНЬ ЛЕВЕНШТЕЙНА
Обчислюється як мінімальна кількість
операцій вставки, видалення і заміни, необхідних для перетворення одної послідовності
в іншу.ПЕРЕТВОРЕННЯ З ВИРІВНЮВАННЯМ ДВОХ СТРІЧОК
D - ВИДАЛЕННЯ
І – ВСТАВКА
S - ЗАМІНА
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 14ВІДСТАНЬ ЛЕВЕНШТЕЙНА (1964)
ВАРТІСТЬ (ВАГА ОПЕРАЦІЙ)
D – ВИДАЛЕННЯ=1
І – ВСТАВКА=1
S –
ЗАМІНА=1(2)
INTENTION -> EXECUTION =5(8)
НЕБО-> ТРЕБА = 3
Комп'ютерна лінгвістика (2009) Романюк
А.Б.
Слайд 15АЛГОРИТМ MINIMUM EDIT DISTANCE
Комп'ютерна лінгвістика (2009) Романюк А.Б.
ПЕРЕЛІК НЕОБХІДНИХ ПЕРЕТВОРЕНЬ
Слайд 16АЛГОРИТМ MINIMUM EDIT DISTANCE
небо -> неба (замінюємо о на а)-1(2)
неба
-> реба (замінюємо н на р)-1(2)
реба -> треба (вставляємо т)-1
Небо
-> Тебо (замінюємо н на Т)Тебо -> требо (вставляємо Р)
Требо -> треба (замінюємо о на А)
Комп'ютерна лінгвістика (2009) Романюк А.Б.
ПЕРЕЛІК НЕОБХІДНИХ ПЕРЕТВОРЕНЬ
Слайд 17ПОШУК МІНІМАЛЬНОЇ ВІДСТАНІ РЕДАГУВАННЯ – ПОШУКОВА ЗАДАЧА
ЗАДАЧУ ВИЗНАЧЕННЯ ВІДСТАНІ
РЕДАГУВАННЯ МОЖНА РОЗГЛЯДАТИ ЯК ЗАДАЧУ ПОШУКУ ШЛЯХУ (ПОСЛІДОВНОСТІ ОПЕРАЦІЙ РЕДАГУВАННЯ)
ДЛЯ ПЕРЕТВОРЕННЯ (ОТРИМАННЯ З) ПОЧАТКОВОЇ СТРІЧКИ – ЗАДАНУ СТРІЧКУПОЧАТКОВА ТА КІНЦЕВА СТРІЧКИ ВІДОМІ
ПОТРІБНО ЗНАЙТИ ПОСЛІДОВНІСТЬ ОПЕРАЦІЙ (ВСІ!!!)
ВИБРАТИ ПОСЛІДОВНІСТЬ З МІНІМАЛЬНОЇ МІРОЮ
Отримати послідовність кроків
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 18МАТРИЦЯ ВІДСТАНЕЙ ДЛЯ ПОРІВНЯННЯ ПОСЛІДОВНОСТЕЙ
РОЗМІР МАТРИЦІ (N+1)X(M+1)
N - КІЛЬКІСТЬ ЕЛЕМЕНТІВ
ПЕРШОЇ ПОСЛІДОВНОСТІ
M- КІЛЬКІСТЬ ЕЛЕМЕНТІВ ДРУГОЇ ПОСЛІДОВНОСТІ
КОМІРКИ МАТРИЦІ ЗНАЧЕННЯ
ВІДСТАНІ МІЖ ПЕРШИМИ I СИМВОЛАМИ ВХІДНОЇ ПОСЛІДОВНОСТІ ТА J СИМВОЛАМИ РЕЗУЛЬТУЮЧОЇ ПОСЛІДОВНОСТІКомп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 19ЕЛЕМЕНТИ МАТРИЦІ ВІДСТАНЕЙ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
ВИЗНАЧАЮТЬСЯ НА ОСНОВІ РЕКУРСИВНОГО
РІВНЯННЯ
Слайд 20МАТРИЦЯ ВІДСТАНЕЙ ДЛЯ СТРІЧОК INTENTION ТА EXECUTION
Комп'ютерна лінгвістика (2009) Романюк
А.Б.
Слайд 22АЛГОРИТМ MINIMUM EDIT DISTANCE
ЩОБ ОТРИМАТИ СТРІЧКУ ДОВЖИНОЮ К ПОТРІБНО
ЗРОБИТИ К ОПЕРАЦІЙ ВСТАВКИ
ЩОБ ОТРИМАТИ СТРІЧКУ ДОВЖИНОЮ 0 ПОТРІБНО ЗРОБИТИ
К ОПЕРАЦІЙ ВИДАЛЕННЯКРОК ПО ГОРИЗОНТАЛІ [j](ПО РЯДКУ) - ВСТАВКА
КРОК ПО ВЕРТИКАЛІ [i](ПО СТОВПЧИКУ) – ВИДАЛЕННЯ
КРОК ПО ОБОХ ІНДЕКСАХ [i,j] – ЗАМІНА, АБО ВІДСУТНІСТЬ ЗМІН КОЛИ СИМВОЛИ СПІВПАДАЮТЬ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 23АЛГОРИТМ MINIMUM EDIT DISTANCE
http://rain.ifmo.ru/cat/view.php/vis/strings/levenshtein-2009
ЗАПОВНЕННЯ ПЕРШОГО СТОВПЧИКА МАТРИЦІ
І=1, J=1,2,3,4,5,6,7,8,9
Комп'ютерна лінгвістика
(2009) Романюк А.Б.
Слайд 24РЕАЛІЗАЦІЯ АЛГОРИТМУ НА МОВІ PYTHON
def distance(a, b): "Calculates the
Levenshtein distance between a and b."
n, m =
len(a), len(b)if n > m: # Make sure n <= m, to use O(min(n,m)) space
a, b = b, a n, m = m, n
current_row = range(n+1) # Keep current and previous row, not entire matrix
for i in range(1, m+1):
previous_row, current_row = current_row, [i]+[0]*m
for j in range(1,n+1):
add, delete, change = previous_row[j]+1, current_row[j-1]+1, previous_row[j-1]
if a[j-1] != b[i-1]:
change += 1
current_row[j] = min(add, delete, change)
return current_row[n]
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 25МАТРИЦЯ ВІДСТАНЕЙ ДЛЯ СТРІЧОК INTENTION ТА EXECUTION
Комп'ютерна лінгвістика (2009) Романюк
А.Б.
ЯК З ЦІЄЇ МАТРИЦІ ОТРИМАТИ ПОТРІБНУ ПОСЛІДОВНІСТЬ ОПЕРАЦІЙ РЕДАГУВАННЯ?
Слайд 26ВИЗНАЧЕННЯ МІНІМАЛЬНОГО ШЛЯХУ ВИРІВНЮВАННЯ МІЖ СТРІЧКАМИ (ДИНАМІЧНЕ ПРОГРАМ.)
Комп'ютерна лінгвістика (2009)
Романюк А.Б.
ПРИ ЗАПОВНЮВАННІ КОЖНОЇ З КОМІРОК ПОТРІБНО ВКАЗАТИ НА ОСНОВІ
ЯКОЇ КОМІРКИ ВОНА ЗАПОВНЕНА ТА ЗА ДОПОМОГОЮ ЯКОЇ ОПЕРАЦІЇ ЦЕ ВІДБУЛОСЯ КРОК ПО ГОРИЗОНТАЛІ [j](ПО РЯДКУ) – ВСТАВКА (СТРІЛКА ВЛІВО)
КРОК ПО ВЕРТИКАЛІ [i](ПО СТОВПЧИКУ) – ВИДАЛЕННЯ (СТРІЛКА ВНИЗ)
КРОК ПО ОБОХ ІНДЕКСАХ [i,j] – ЗАМІНА, АБО ВІДСУТНІСТЬ ЗМІН КОЛИ СИМВОЛИ СПІВПАДАЮТЬ (СТРІЛКА ПО ДІАГОНАЛІ)
Слайд 27ВИЗНАЧЕННЯ МІНІМАЛЬНОГО ШЛЯХУ ВИРІВНЮВАННЯ МІЖ СТРІЧКАМИ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 28ПЕРЕДБАЧЕННЯ СЛІВ. N-ГРАМИ
N-ГРАМ МОДЕЛЬ – ІМОВІРНІСНА МОДЕЛЬ, ЯКА ПЕРЕДБАЧАЄ НАСТУПНЕ
СЛОВО НА ОСНОВІ N-1 ПОПЕРЕДНІХ СЛІВ
N-ГРАМ ПОСЛІДОВНІСТЬ N СЛІВ
2-ГРАМ –БІГРАМ
3-ГРАМ
- ТРИГРАМ N-ГРАМ МОДЕЛЬ – ЦЕ МОДЕЛЬ, ЯКА ВИЗНАЧАЄ (ОБРАХОВУЄ ) ОСТАННЄ СЛОВО N-ГРАМА НА ОСНОВІ N-1 ПОПЕРЕДНІХ СЛІВ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 29ПЕРЕДБАЧЕННЯ СЛІВ. N-ГРАМИ
ВИЗНАЧЕННЯ ЙМОВІРНОСТІ НАСТУПНОГО СЛОВА ТІСНО ПОВ’ЯЗАНЕ З ВИЗНАЧЕННЯМ
ІМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВ
IN(OVER)? THEКомп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 30ВИКОРИСТАННЯ N-ГРАМ МОДЕЛЕЙ
РОЗПІЗНАВАННЯ УСНОГО МОВЛЕННЯ
РОЗПІЗНАВАННЯ РУКОПИСНОГО ТЕКСТУ
МАШИННИЙ ПЕРЕКЛАД
ВИПРАВЛЕННЯ ПОМИЛОК
МОРФОЛОГІЧНИЙ АНАЛІЗ
ГЕНЕРАЦІЯ
ТЕКСТУ
ОЦІНКА ПОДІБНОСТІ СЛІВ
ІДЕНТИФІКАЦІЯ АВТОРСТВА
ПЕРЕДБАЧЕННЯ ТЕКСТУ ПРИ ВВЕДЕННІ
ВИЯВЛЕННЯ СЕНТИМЕНТІВ
Комп'ютерна лінгвістика (2009)
Романюк А.Б.
Слайд 31ВИЗНАЧЕННЯ ІМОВІРНОСТЕЙ
НА ОСНОВІ ПІДРАХУНКІВ В КОРПУСАХ ТЕКСТІВ
ЩО ВВАЖАТИ СЛОВОМ?
ЛЕМА, ГРАМАТИЧНА
ФОРМА, СЛОВОФОРМА
TOKENS? TYPES?
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 32N-ГРАМИ. ВИЗНАЧЕННЯ ІМОВІРНОСТІ
МЕТА: ОБЧИСЛИТИ ЙМОВІРНІСТЬ СЛОВА W , ЯКЕ СЛІДУЄ
ПІСЛЯ H P(W|H)
H=‘ITS WATER IS SO TRANSPARENT THAT’
P(THE| ITS WATER
IS SO TRANSPARENT THAT )=C( ITS WATER IS SO TRANSPARENT THAT )
C( ITS WATER IS SO TRANSPARENT THAT THE)
P=15|22 = 0,68
ДЕЯКІ ПОСЛІДОВНОСТІ СЛІВ МОЖУТЬ ЗУСТРІЧАТИСЯ РІДКО АБО І НЕ ЗУСТРІЧАТИСЯ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 33N-ГРАМИ. ВИЗНАЧЕННЯ ІМОВІРНОСТІ
Я ХОЧУ ОТРИМАТИ – 62 000
Я ХОЧУ ОТРИМАТИ
ВІДМІННО - 0
Я ЛЮБЛЮ - 111 000 000
Я ЛЮБЛЮ РОМАНЮКА
- 22/111000000=0,000000001802
Я ХОЧУ ОТРИМАТИ ВІДМІННО… (БУДЬ-ЯКЕ СЛОВО)… - 0
0/0 !!!
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 34ВИЗНАЧЕННЯ ЗАГАЛЬНОЇ ЙМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВ
P(w1,w2,w3,……..wn)
CHAIN RULE (ПРАВИЛО ЛАНЦЮГА)
УМОВНА ЙМОВІРНІСТЬ
ДЛЯ ПОСЛІДОВНОСТІ
P(A,B,C,D)
= P(A)P(B|A)P(C|A,B)P(D|A,B,C)
P(x1,x2,x3,…xn) = P(x1)P(x2|x1)P(x3|x1,x2)…P(xn|x1…xn-1)
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 35ВИЗНАЧЕННЯ ЗАГАЛЬНОЇ ЙМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
P(its water
was so transparent)=
P(its)*
P(water|its)*
P(was|its water)*
P(so|its water was)*P(transparent|its water was so)
Слайд 36ВИЗНАЧЕННЯ ЗАГАЛЬНОЇ ЙМОВІРНОСТІ ПОСЛІДОВНОСТІ СЛІВ
ПРОБЛЕМА ВИЗНАЧЕННЯ - P(wn|w1n-1) (Я ХОЧУ
ОТРИМАТИ ВІДМІННО У РОМАНЮКА)
ЯКЩО ВИКОРИСТАТИ N-ГРАМ (БІГРАМ) ТО ЗГІДНО ПРИПУЩЕННЯ
МАРКОВАP(wn|w1n-1) ~ P(wn|wn-1)
P(THE| ITS WATER IS SO TRANSPARENT THAT )=
P(THE| THAT )
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 38ВИЗНАЧЕННЯ ЙМОВІРНОСТІ N-ГРАМІВ НА ОСНОВІ МЕТОДУ МАКСИМАЛЬНОЇ ПРАВДОПОДІБНОСТІ
БІГРАМ
Комп'ютерна лінгвістика
(2009) Романюк А.Б.
Слайд 39ПРИКЛАД
Комп'ютерна лінгвістика (2009) Романюк А.Б.
I am Sam
Sam
I am
I do not like green eggs and
ham 
Слайд 40ПРИКЛАД (9332 РЕЧЕННЯ)
Berkeley Restaurant Project
ТАБЛИЦЯ ЧАСТОТ БІГРАМІВ
(I
WANT ЗУСТРІЧАЄТЬСЯ 827 РАЗ)
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 41ЙМОВІРНОСТІ БІГРАМІВ
ЙМОВІРНІСТЬ ВИЗНАЧАЄТЬСЯ ДІЛЕННЯМ ЧАСТОТИ БІГРАМІВ НА ЧАСТОТУ ПОПЕРЕДНЬОГО СЛОВА
В КОРПУСІ
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 43ЯКУ ІНФОРМАЦІЮ МОЖНА ОТРИМАТИ З АНАЛІЗУ ІМОВІРНОСТЕЙ N-ГРАМІВ
P(english|want) = .0011
P(chinese|want)
= .0065
P(to|want) = .66
P(eat | to) = .28
P(food | to)
= 0P(want | spend) = 0
P (i |
Комп'ютерна лінгвістика (2009) Романюк А.Б.
Слайд 44НЕОБХІДНО ПРОЧИТАТИ
Daniel 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. – Розділ,3 ст. 68-79. Розділ,4 ст. 83-95.Комп'ютерна лінгвістика (2009) Романюк А.Б.
