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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

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

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

Таблица със състояния (частични дървета)[редактиране | edit source]

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

S → NP • VP [0,1]

VP → • Verb [1,1]

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

Алгоритъм[редактиране | edit source]

Алгоритъмът работи от ляво на дясно, като за изречение от 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 → β•, то анализът е приключил успешно.

Външни препратки[редактиране | edit source]

  • Parse::Earley Perl модул, реализиращ алгоритъма на Ерли.
  • 'early' Програмна реализация на C.
  • NLTK Python библиотека.
  • Pep Java библиотека.