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

Алгоритъмът на Ерли (анг. 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<N+1, то i=i+1 и преминаваме на (2).

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