Алгоритъм на Ерли

Алгоритъмът на Ерли (анг. Earley Parser) намира приложение в изчислителната лингвистика като средство за синтактичен анализ на текст. За разлика от CKY, алгоритъмът на Ерли извършва синтактичния анализ от горе надолу, започвайки от корена на синтактичното дърво.

Изчислителната сложност на алгоритъма зависи от използваната граматиката:

O(n³) в общия случай, където n e дължината на изречението
O(n²) за граматики, в които всички продукции са еднозначни
O(n) за LR(k) граматики

Таблица със състояния (частични дървета)

Алгоритъмът на Ерли съхранява таблица със състояния, които отразяват части от синтактичното дърво. Всяко от тези състояние съдържа една продукция от граматиката, начална позиция и крайна позиция. Състоянията могат да бъдат представени като „продукция с точка“, например:

S → NP • VP [0,1]

VP → • Verb [1,1]

Първото състояние представя изречение (S), за което е намерена фраза със съществително име (NP, Noun Phrase), но все още липсва глаголна фраза (VP). Индексите [0,1] показват, че само думите между позиции 0 и 1 са обработени. Второто състояние представя глаголна фраза, която се очаква след позиция 1 в изречението. Самият глагол все още не е намерен (точката е преди глагола.)

Алгоритъм

Алгоритъмът работи от ляво надясно, като за изречение от N думи се създават последователно N+1 списъка със състояния. Всеки списък съдържа състоянията, които са възможни за дадена позиция от изречението. Нулевото състояние няма съответна дума, но се инициализира с всички възможни развития на началния символ S. Анализът се извършва по следния начин:

(1) Извлича се първото състояние s[j=0, i]. В случай, че i=0, това е P → S (начално състояние.)
(2) Ако състоянието не е завършено (точката не е в края) и символа след точката не е терминал (например NP или VP), добавяме след s[j,i] всички възможни развития на s[j,i].
(3) Ако състоянието не е завършено (точката не е в края) и символа след точката е терминал (например Verb), добавяме към s[, i+1] съответното ново състояние (например VP → Love•)
(4) Ако състоянието е завършено (точката е в края), копираме го към s[,i+1].
(5) Ако текущия списък не се е изчерпил, то j+1 и преминаваме на стъпка (2).
(6) Ако това не е последната дума, то преминаваме на следващата дума i+1 и се връщаме на стъпка (2).

След изпълнението на алгоритъма последният списък съдържа всички възможни синтактични анализи на изречението. Ако този списък съдържа поне едно състояние от вида S → β•, то анализът е приключил успешно.

Външни препратки

Parse::Earley Perl модул, реализиращ алгоритъма на Ерли.
'early' Програмна реализация на C.
NLTK Архив на оригинала от 2007-08-22 в Wayback Machine. Python библиотека.
Pep Архив на оригинала от 2008-10-31 в Wayback Machine. Java библиотека.