Міністерство освіти і науки україни

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”

іНСТИТУТ КОМП’ютерних НАУК та ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

Кафедра “Системи автоматизованого проектування”

ВИВЧЕННЯ БІБЛІОТЕКИ ПРИКЛАДНИХ ПРОГРАМ NLTK, ДЛЯ ОПРАЦЮВАННЯ ТЕКСТІВ ПРИРОДНОЮ МОВОЮ.

АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ (частина2).

Методичні вказівки до лабораторної роботи № 12

з дисципліни “Комп’ютерна лінгвістика”

для студентів спеціальності 7.030.505 “Прикладна лінгвістика”

та магістрів за фахом 8.030.505 “Прикладна лінгвістика”.

Затверджено

на засіданні кафедри

“Системи автоматизованого проектування”

Протокол № 8 від 21.XI.2005 р.

на засіданні методичної ради ІКНІ

Протокол № 4-05/06 від 1.XII.2005 р.

ВАК № 1769 від 12.XII.2005 р.

Львів-2010

ВИВЧЕННЯ БІБЛІОТЕКИ ПРИКЛАДНИХ ПРОГРАМ NLTK, ДЛЯ ОПРАЦЮ­ВАННЯ ТЕКСТІВ ПРИРОДНОЮ МОВОЮ. АВТОМАТИЧНИЙ СИНТАКСИЧНИЙ АНАЛІЗ (частина2).Методичні вказівки до лабораторної роботи № 12 з дисципліни “Комп’ютерна лінгвістика” для студентів спеціальності 7.030.505 “Прикладна лінгвістика” та магістрів за фахом 8.030.505 “Прикладна лінгвістика” для стаціонарної та заочної форм навчання/Укл. А.Б.Романюк. - Львів: Національний університет ”Львівська політехніка”, 2010. - 24с.

Укладачі: Романюк а. Б., канд. Техн. Наук, ст. Викладач

Відповідальний за випуск: Лобур М. В., доктор техн. наук, професор

Рецензенти: Каркульовський В. І., канд. техн. наук, доцент

МЕТА РОБОТА

• Вивчення основ програмування на мові Python.

• Ознайомлення з автоматичним синтаксичним аналізом в NLTK.

КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ

Well-Formed Substring Tables

Прості синтаксичні аналізатори, які розглядалися в попередній лабораторній роботі мають ряд недоліків, які накладають значні обмеження як на ефективність так і взагалі на можливість отримання результатів синтаксичного аналізу. Для вирішення цих проблем використовуються алгоритми що базуються на динамічному програмуванні. Динамічне програмування передбачає збереження проміжних результатів та їх використання при необхідності що дозволяє значно підвищити ефективність роботи різноманітних алгоритмів. Застосування динамічного програмування для синтаксичного аналізу дозволить зберегти часткові рішення при аналізі та використовувати ці рішення для одержання загальних (повних, завершених) результатів синтаксичного аналізу. Одним з алгоритмів що базується на динамічному програмуванні є алгоритм аналізу за допомогою схем (chart parser).

Динамічне програмування дозволяє при синтаксичному аналізі речення речення I shot an elephant in my pajamas, будувати PP in my pajamas тільки один раз. Як тільки цей складник побудовано він зберігається в таблиці і ним можна скористатися при потребі як безпосереднім складником при побудові NPабоVP. Таку таблицю називають таблицею закономірностей підстрічок (well-formed substring table WFST). Підстрічкою вважається послідовність слів в межах одного речення. Розглянемо побудову такої таблиці на основі стратегії знизу-вверх в якій будуть послідовно збережені всі можливі безпосередні складники.

Розглянемо речення I shot an elephant in my pajamas як вхідні дані. Дане речення можна представити у вигляді, який показано на рис.1 і така структура називається ChartDataStructure.

Рис. 1. Структура речення: словами речення промарковані дуги графа.

В таблицюWFST,записуються позиції слів шляхом заповнення комірок трикутної матриці в якій по вертикалі записуються початкові позиції підстрічок а по горизонталі кінцеві позиції (таким чином слову shotбуде відповідати комірка з координатами(1, 2)).Для спрощення такого представлення, припускається що кожному слову відповідає тільки одна унікальна лексична категорія (тег морфологічних характеристик) і саме вона зберігається в комірці матриці(в комірці (1, 2) міститься V). Більш загально, якщо вхідної стрічкою є стрічка a₁a₂ ... a_n, і граматика містить правило вигляду A → a_i, тоді A додається до коміркиl (i-1, i).

Який тег відповідає слову shot з спискуtext,на основі граматики:

>>> groucho_grammar = nltk.parse_cfg("""

... S -> NP VP

... PP -> P NP

... NP -> Det N | Det N PP | 'I'

... VP -> V NP | VP PP

... Det -> 'an' | 'my'

... N -> 'elephant' | 'pajamas'

... V -> 'shot'

... P -> 'in'

... """)

можна знайти наступним чином:.

>>> text = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas'] >>> groucho_grammar.productions(rhs=text[1]) [V -> 'shot']

Для побудовиWFST,створюється матриця розміром(n-1)на(n-1). В Python така матриця за допомогою функції init_wfst()будується як список списків. Спочатку в цій матриці заповнена тільки центральна діагональ, куди записані теги всіх слів речення.В наступному прикладі показано реалізацію цієї функції та функції display()яка допоможе відображати на екрані результати побудови WFST.

 

def init_wfst(tokens, grammar): numtokens = len(tokens) wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)] for i in range(numtokens): productions = grammar.productions(rhs=tokens[i]) wfst[i][i+1] = productions[0].lhs() return wfst def complete_wfst(wfst, tokens, grammar, trace=False): index = dict((p.rhs(), p.lhs()) for p in grammar.productions()) numtokens = len(tokens) for span in range(2, numtokens+1): for start in range(numtokens+1-span): end = start + span for mid in range(start+1, end): nt1, nt2 = wfst[start][mid], wfst[mid][end] if nt1 and nt2 and (nt1,nt2) in index: wfst[start][end] = index[(nt1,nt2)] if trace: print "[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]" % \ (start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end) return wfst def display(wfst, tokens): print '\nWFST ' + ' '.join([("%-4d" % i) for i in range(1, len(wfst))]) for i in range(len(wfst)-1): print "%d " % i, for j in range(1, len(wfst)): print "%-4s" % (wfst[i][j] or '.'), print

>>> tokens = "I shot an elephant in my pajamas".split() >>> wfst0 = init_wfst(tokens, groucho_grammar) >>> display(wfst0, tokens) WFST 1 2 3 4 5 6 7 0 NP . . . . . . 1 . V . . . . . 2 . . Det . . . . 3 . . . N . . . 4 . . . . P . . 5 . . . . . Det . 6 . . . . . . N >>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar) >>> display(wfst1, tokens) WFST 1 2 3 4 5 6 7 0 NP . . S . . S 1 . V . VP . . VP 2 . . Det NP . . . 3 . . . N . . . 4 . . . . P . PP 5 . . . . . Det NP 6 . . . . . . N

В таблиці wfst0 записано Detв комірціcell(2, 3)що відповідає слову an,таNв комірці(3, 4)що відповідає словуelephant . На основі цих даних в комірку (2, 4)для послідовності слівan elephant таблиці wfst1 буде записано NP . В граматиці шукаємо правило виду A→Det N та записуємо A(NP) в комірку(2,4).

Більш загально,в комірку (i, j) записуєтьсяAякщо існує правилоA→BC,і знайдено нетерміналBв комірці(i, k)таCв комірці(k, j).Програма з попереднього прикладу використовує даний принцип при побудові WFST.Встановивши параметрtraceвTrueпри виклику функціїcomplete_wfst(),можна прослідкувати за всіма кроками побудови WFST:

>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar, trace=True) [2] Det [3] N [4] ==> [2] NP [4] [5] Det [6] N [7] ==> [5] NP [7] [1] V [2] NP [4] ==> [1] VP [4] [4] P [5] NP [7] ==> [4] PP [7] [0] NP [1] VP [4] ==> [0] S [4] [1] VP [4] PP [7] ==> [1] VP [7] [0] NP [1] VP [7] ==> [0] S [7]

Рис 2. Кінцевий стан WFST (Chart Data Structure: нетермінали маркують дуги графа).

Потрібно звернути увагу на спосіб пошуку правила (продукції) за його правою частиною. У функції complete_wfst проіндексовано всю граматику (змінна index) що дозволяє здійснювати пошуку за правою частиною без перебору всіх правил граматики.

Процес роботи алгоритму завершується якщо для вхідної стрічки в комірці з координатами (0, 7) отримано S , що вказує на те що, знайдено синтаксичну структуру ,яка відповідає вхідній послідовності. Кінцевий стан WFST відповідає зображенню на рис.2.

Програма побудови WFST це практично простий chart parser, який має декілька недоліків. Перший, таблиця яку ми отримали це не є окреме дерево розбору, а скоріше метод розпізнавання чи речення породжується (допускається) граматикою, а не програма його синтаксичного аналізу. Другий, програма потребує щоб правила граматики, де в правій частині знаходяться не термінали були бінарними.Звичайно, будь-яку контекстно-вільну граматику можна перетворити у таку форму (нормальну форму Хомського), але зручніше працювати без таких додаткових обмежень. Третій, підхід знизу вверх, відзначається великою надлишковістю, коли будує складники (пропонує розмістити не термінальні символи в комірках), які не передбачені граматикою .

На завершення,побудована таблиця WFSTне представляє структурну неоднозначність в цьому реченні (два різні дієслівні вирази).VPв комірку(2,8)записується двічі, перший раз на основіV NP, а другий раз на основі VP PP.Це дві різні гілки дерева (різні гіпотези) і другий VP записаний на місці першого. Справжні аналізатори сhart parsers використовують дещо більш складнішу структуру даних та цікавіші алгоритми для вирішення цих проблем. Для детальнішого ознайомлення з сhart parser можна скористатися демонстраційною програмою nltk.app.chartparser()та переглянути Додаток А.