Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Асимптотика)
Строка 6: Строка 6:
 
== Алгоритм ==
 
== Алгоритм ==
 
'''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
 
'''Алгоритм Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i..j]</tex>.
+
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Заведем трехмерный массив d, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \dots j]</tex>.
  
 
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> - константа и <tex>m < n</tex>.
 
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> - константа и <tex>m < n</tex>.
Строка 24: Строка 24:
  
 
=== Завершение ===
 
=== Завершение ===
\После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике.
+
После окончания работы значение <tex>d[S][1][n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике.
  
 
== Модификации ==
 
== Модификации ==
Заметим, что если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B,i,k] \cdot d[C,k+1,j]</tex>, то <tex>d[A,i,j]</tex> - количество способов получить подстроку <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
 
  
Пусть <tex>P_{A \rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A,i,j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1}  ( d[B,i,k] + d[C,k+1,j] + P_{A \rightarrow BC} )</tex>, то <tex>d[A,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>.
+
=== Количество способ вывести слово ===
 +
Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j]</tex>, то <tex>d[A][i][j]</tex> - количество способов получить подстроку <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
 +
 
 +
=== Минимальная стоимость вывода слова ===
 +
Пусть <tex>P(A \rightarrow BC)</tex> - стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1}  ( d[B][i][k] + d[C][k + 1][j] + P(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> - минимальная стоимость вывода подстроки <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
  
 
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
 
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.
Строка 39: Строка 42:
 
     '''for''' i = 1 ... n
 
     '''for''' i = 1 ... n
 
       '''for''' (A <tex>\rightarrow</tex> w[i] <tex>\in</tex> <tex>\Gamma</tex>)
 
       '''for''' (A <tex>\rightarrow</tex> w[i] <tex>\in</tex> <tex>\Gamma</tex>)
           d[A][i][i] = true
+
           d[A][i][i] = ''true''
 
     '''for''' m = 1 .. n - 1
 
     '''for''' m = 1 .. n - 1
 
       '''for''' i = 1 .. n - m
 
       '''for''' i = 1 .. n - m
Строка 51: Строка 54:
 
Обработка правил вида <tex>A \rightarrow w[i]</tex> в шаге 1 выполняется за <tex>O(n \cdot |\Gamma|)</tex>.
 
Обработка правил вида <tex>A \rightarrow w[i]</tex> в шаге 1 выполняется за <tex>O(n \cdot |\Gamma|)</tex>.
  
Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
+
Проход по всем подстрокам в шаге 2 выполняется за <tex>O(n^2)</tex>. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(n \cdot |\Gamma|)</tex>. В итоге получаем конечную сложность <tex>O(n^3 \cdot |\Gamma|)</tex>.
  
 
Следовательно, общее время работы алгоритма - <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> -  количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.
 
Следовательно, общее время работы алгоритма - <tex>O(n^3 \cdot |\Gamma|)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 \cdot |N|)</tex>, где <tex>|N|</tex> -  количество [[Формальные_грамматики#Определения|нетерминалов]] грамматики.

Версия 23:32, 4 ноября 2014

Задача:
Пусть дана контекстно-свободная грамматика грамматика [math]\Gamma[/math] в нормальной форме Хомского и слово [math]w \in \Sigma^{*}[/math]. Требуется выяснить, выводится ли это слово в данной грамматике.


Алгоритм

Алгоритм Кока-Янгера-Касами (Cocke — Younger — Kasami algorithm, CYK - алгоритм) - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Будем решать задачу динамическим программированием. Заведем трехмерный массив d, состоящий из логических значений, и [math]d[A][i][j] = true[/math] тогда и только тогда, когда из нетерминала [math]A[/math] правилами грамматики можно вывести подстроку [math]w[i \dots j][/math].

Рассмотрим все пары [math]\lbrace \langle j, i \rangle | j-i=m \rbrace[/math], где [math]m[/math] - константа и [math]m \lt n[/math].

Шаг 1. База

[math]m = 0[/math]. В таком случае [math]i = j[/math].

Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки [math]w[/math]. В таком случае:

[math]d[A][i][i] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math]. Иначе [math]d[A][i][i] = false[/math].

Шаг 2. Переход

CYK rule 2.jpg

[math]m = j - i[/math].

Значения для всех нетерминалов и пар [math]\lbrace \langle j', i' \rangle | j' - i' \lt m \rbrace[/math] уже вычислены, поэтому [math]d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j][/math]. То есть, подстроку [math]w[i \dots j][/math] можно вывести из нетерминала [math]A[/math], если существует продукция вида [math]A \rightarrow BC[/math] и такое [math]k[/math], что подстрока [math]w[i \dots k][/math] выводима из [math]B[/math], а подстрока [math]w[k + 1 \dots j][/math] - из [math]C[/math].

Завершение

После окончания работы значение [math]d[S][1][n][/math] содержит ответ на вопрос, выводима ли данная строка в данной грамматике.

Модификации

Количество способ вывести слово

Если массив будет хранить целые числа, а формулу заменить на [math]d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j][/math], то [math]d[A][i][j][/math] - количество способов получить подстроку [math]w[i \dots j][/math] из нетерминала [math]A[/math].

Минимальная стоимость вывода слова

Пусть [math]P(A \rightarrow BC)[/math] - стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + P(A \rightarrow BC) )[/math], то [math]d[A][i][j][/math] - минимальная стоимость вывода подстроки [math]w[i \dots j][/math] из нетерминала [math]A[/math].

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.

Псевдокод

boolean CYK(char[] w, list [math]\Gamma[/math], int S)
   int n = length(w)
   boolean d[[math]|\Gamma|[/math]][n][n]
   for i = 1 ... n
      for (A [math]\rightarrow[/math] w[i] [math]\in[/math] [math]\Gamma[/math])
         d[A][i][i] = true
   for m = 1 .. n - 1
      for i = 1 .. n - m
         int j = i + m
         for (A [math]\rightarrow[/math] BC [math]\in[/math] [math]\Gamma[/math])
            for k = i .. j - 1
               d[A][i][j] = d[A][i][j] or d[B][i][k] and d[C][k + 1][j]
return d[S][1][n]

Асимптотика

Обработка правил вида [math]A \rightarrow w[i][/math] в шаге 1 выполняется за [math]O(n \cdot |\Gamma|)[/math].

Проход по всем подстрокам в шаге 2 выполняется за [math]O(n^2)[/math]. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за [math]O(n \cdot |\Gamma|)[/math]. В итоге получаем конечную сложность [math]O(n^3 \cdot |\Gamma|)[/math].

Следовательно, общее время работы алгоритма - [math]O(n^3 \cdot |\Gamma|)[/math]. Кроме того, алгоритму требуется память (на массив [math]d[/math]) объемом [math]O(n^2 \cdot |N|)[/math], где [math]|N|[/math] - количество нетерминалов грамматики.

См. также

Источники информации