Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм для произвольной грамматики)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 2 участников)
Строка 8: Строка 8:
 
== Алгоритм для произвольной грамматики ==
 
== Алгоритм для произвольной грамматики ==
  
Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i..j-1]\right] \ </tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии]] алгоритма.   
+
Будем решать задачу динамическим программированием. Введём динамику <tex>a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i \ldots j-1]\right] \ </tex>, аналогично [[Алгоритм_Кока-Янгера-Касами_разбора_грамматики_в_НФХ|базовой версии]] алгоритма.   
  
Также введём вспомогательный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true \ </tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i..j-1\right]</tex>.  
+
Также введём вспомогательный четырехмерный массив <tex>h\left[A \rightarrow \alpha, i, j, k\right] = true \ </tex> тогда и только тогда, когда из префикса длины <tex>k</tex> правой части данного правила можно вывести <tex>w\left[i \ldots j-1\right]</tex>.  
  
 
Рассмотрим все тройки <tex>\lbrace \langle j, i \rangle \mid j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>, и <tex>k</tex> такое, что <tex>k < \left|\alpha\right|</tex>.
 
Рассмотрим все тройки <tex>\lbrace \langle j, i \rangle \mid j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>, и <tex>k</tex> такое, что <tex>k < \left|\alpha\right|</tex>.
Строка 24: Строка 24:
 
* '''Переход''':  
 
* '''Переход''':  
  
:Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle \mid j' - i' < m \rbrace \ </tex> и <tex>\lbrace k' \mid k' < k \rbrace \ </tex> уже вычислены, поэтому вспомогательная динамика: <tex> h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i..j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha\left[k\right],r,j+1\right]\right)</tex>. То есть, подстроку <tex>w[i..j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..r-1\right]</tex>, а подстрока <tex>w[r..j]</tex> выводится из <tex>k</tex>-го символа правой части правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\right]</tex>, но на результат это не повлияет, так как в данный момент <tex>a\left[A,i,j+1\right]=false</tex>.   
+
:Пусть значения для всех нетерминалов, пар <tex>\lbrace \langle j', i' \rangle \mid j' - i' < m \rbrace \ </tex> и <tex>\lbrace k' \mid k' < k \rbrace \ </tex> уже вычислены, поэтому вспомогательная динамика: <tex> h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i \ldots j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha\left[k\right],r,j+1\right]\right)</tex> То есть, подстроку <tex>w[i \ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i \ldots r-1\right]</tex>, а подстрока <tex>w[r \ldots j]</tex> выводится из <tex>k</tex>-го символа правой части правила. Это вычисление может обратится к <tex>a\left[A,i,j+1\right] </tex>, но на результат это не повлияет, так как в данный момент <tex>a\left[A,i,j+1\right]=false \ </tex>.   
  
:Но если <tex>\alpha\left[k\right]</tex>  {{---}}  терминал, то подстроку <tex>w[i..j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i..r-1\right] \ </tex>, а подстрока <tex>w[r..j]</tex> выводится, если <tex>w\left[r..j\right]=\alpha\left[k\right]</tex>.
+
:Но если <tex>\alpha\left[k\right]</tex>  {{---}}  терминал, то подстроку <tex>w[i \ldots j]</tex> можно вывести из префикса длины <tex>k</tex> правой части данного правила, если из префикса длины <tex>k-1</tex> правой части данного правила можно вывести <tex>w\left[i \ldots r-1\right] \ </tex>, а подстрока <tex>w[r \ldots j]</tex> выводится, если <tex>w\left[r \ldots j\right]=\alpha\left[k\right] \ </tex>.
  
:Базовая динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right] \ </tex>. То есть, подстроку <tex>w[i..j-1] \ </tex> можно вывести из нетерминала <tex>A</tex>, если из длины правой части данного правила можно вывести <tex>w\left[i..j-1\right] \ </tex>.  
+
:Базовая динамика выражается так: <tex>a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right] \ </tex>. То есть, подстроку <tex>w[i \ldots j-1] \ </tex> можно вывести из нетерминала <tex>A</tex>, если из длины правой части данного правила можно вывести <tex>w\left[i \ldots j-1\right] </tex>.  
  
 
* '''Завершение''':  
 
* '''Завершение''':  
Строка 61: Строка 61:
 
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.   
 
Обозначим <tex>M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|</tex> — максимальную длину правой части правила.   
  
Обработки правил вида <tex>A \rightarrow w[i]</tex>, <tex>A \rightarrow \varepsilon</tex> и нахождение <tex>h\left[A \rightarrow \alpha, i, i, 0\right]</tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>.  
+
Обработки правил вида <tex>A \rightarrow w[i]</tex>, <tex>A \rightarrow \varepsilon</tex> и нахождение <tex>h\left[A \rightarrow \alpha, i, i, 0\right] \ </tex> выполняются за <tex>O(n \cdot |\Gamma|)</tex>.  
  
Время одного перехода вспомогательной динамики <tex>O(n)</tex>, суммарное число состояний <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex>. Отсюда расчёт вспомогательной динамики занимает <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex> времени, базовая динамика находится, как <tex>O \left( n^2 \cdot |\Gamma| \right)</tex>. Итоговая временная сложность алгоритма равна <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex>. Алгоритму требуется <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex> памяти.
+
Время одного перехода вспомогательной динамики <tex>O(n)</tex>, суммарное число состояний <tex>O(n^2 \cdot |\Gamma| \cdot M)</tex>. Отсюда расчёт вспомогательной динамики занимает <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right) \ </tex> времени, базовая динамика находится, как <tex>O \left( n^2 \cdot |\Gamma| \right)</tex>. Итоговая временная сложность алгоритма равна <tex>O \left( n^3 \cdot |\Gamma| \cdot M \right)</tex>. Алгоритму требуется <tex>O(n^2 \cdot |\Gamma| \cdot M) \ </tex> памяти.
  
 
== См. также ==  
 
== См. также ==  

Текущая версия на 19:07, 4 сентября 2022

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


Базовая версия данного алгоритма работает только для грамматик в нормальной форме Хомского. Модифицируем алгоритм для работы на произвольных контекстно-свободных грамматиках. Модификация алгоритма сильно проще в написании, чем приведение к нормальной форме Хомского, поэтому часто используют её, не смотря на то, что время работы у нее больше.

Алгоритм для произвольной грамматики

Будем решать задачу динамическим программированием. Введём динамику [math]a\left[A,i,j\right] = \left[A \Rightarrow^{*} w[i \ldots j-1]\right] \ [/math], аналогично базовой версии алгоритма.

Также введём вспомогательный четырехмерный массив [math]h\left[A \rightarrow \alpha, i, j, k\right] = true \ [/math] тогда и только тогда, когда из префикса длины [math]k[/math] правой части данного правила можно вывести [math]w\left[i \ldots j-1\right][/math].

Рассмотрим все тройки [math]\lbrace \langle j, i \rangle \mid j-i=m \rbrace[/math], где [math]m[/math] — константа и [math]m \lt n[/math], и [math]k[/math] такое, что [math]k \lt \left|\alpha\right|[/math].

  • База динамики:
[math]a\left[A, i, i+1\right] = true \ [/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i] \ [/math], иначе [math]a\left[A, i, i+1\right] = false \ [/math];
[math]a\left[A, i, i\right] = true \ [/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow \varepsilon \ [/math], иначе [math]a\left[A, i, i\right] = false \ [/math];
[math]h\left[A \rightarrow \alpha, i, i, 0\right] = true \ [/math].
  • Переход:
Пусть значения для всех нетерминалов, пар [math]\lbrace \langle j', i' \rangle \mid j' - i' \lt m \rbrace \ [/math] и [math]\lbrace k' \mid k' \lt k \rbrace \ [/math] уже вычислены, поэтому вспомогательная динамика: [math] h\left[A \rightarrow \alpha, i, j+1, k\right] = \bigvee\limits_{r=i \ldots j+1}\left(h\left[A \rightarrow \alpha, i, r, k-1\right] \wedge a\left[\alpha\left[k\right],r,j+1\right]\right)[/math] То есть, подстроку [math]w[i \ldots j][/math] можно вывести из префикса длины [math]k[/math] правой части данного правила, если из префикса длины [math]k-1[/math] правой части данного правила можно вывести [math]w\left[i \ldots r-1\right][/math], а подстрока [math]w[r \ldots j][/math] выводится из [math]k[/math]-го символа правой части правила. Это вычисление может обратится к [math]a\left[A,i,j+1\right] [/math], но на результат это не повлияет, так как в данный момент [math]a\left[A,i,j+1\right]=false \ [/math].
Но если [math]\alpha\left[k\right][/math] — терминал, то подстроку [math]w[i \ldots j][/math] можно вывести из префикса длины [math]k[/math] правой части данного правила, если из префикса длины [math]k-1[/math] правой части данного правила можно вывести [math]w\left[i \ldots r-1\right] \ [/math], а подстрока [math]w[r \ldots j][/math] выводится, если [math]w\left[r \ldots j\right]=\alpha\left[k\right] \ [/math].
Базовая динамика выражается так: [math]a\left[A,i,j\right]=\bigvee\limits_{A \rightarrow \alpha}h\left[A \rightarrow \alpha, i, j, \left|\alpha\right|\right] \ [/math]. То есть, подстроку [math]w[i \ldots j-1] \ [/math] можно вывести из нетерминала [math]A[/math], если из длины правой части данного правила можно вывести [math]w\left[i \ldots j-1\right] [/math].
  • Завершение:
После окончания работы ответ содержится в ячейке [math]a\left[S, 1, n\right] [/math], где [math]n = |w|[/math].

Псевдокод

CYK_Modified(S, Г): // S — строка длины n, Г — КС-грамматика 
     for i = 1..n
      for Rj -> alpha // перебор состояний 
       if( A -> w[i] in Г) a[A, i, i+1] = true // если в грамматике Г присутствует правило A -> w[i] 
       else a[A, i, i+1] = false
       if( A -> eps in Г) a[A, i, i] = true // если в грамматике Г присутствует правило A -> eps 
       else a[A, i, i] = false
       h[A->alpha, i, i, 0] = true
     for m = 1..n
      for i = 1..n
          j = i+m
       for k = 1..M
        for Rj -> alpha // перебор состояний 
         h[A->alpha, i, j+1, k] = OR( for r = i..j+1) (h[A->alpha, i, r, k-1] & a[alpha[k],r,j+1])
     for i = 1..n
       for j = 1..n
         for Rj -> alpha
          a[A, i, j] = OR( for A->alpha) h[A->alpha, i, j, |alpha|] // где |alpha| — размер правой части правила
     return a[S, 1, n]     

Оценка сложности

Обозначим [math]M = \max\limits_{A \rightarrow \alpha}\left|\alpha\right|[/math] — максимальную длину правой части правила.

Обработки правил вида [math]A \rightarrow w[i][/math], [math]A \rightarrow \varepsilon[/math] и нахождение [math]h\left[A \rightarrow \alpha, i, i, 0\right] \ [/math] выполняются за [math]O(n \cdot |\Gamma|)[/math].

Время одного перехода вспомогательной динамики [math]O(n)[/math], суммарное число состояний [math]O(n^2 \cdot |\Gamma| \cdot M)[/math]. Отсюда расчёт вспомогательной динамики занимает [math]O \left( n^3 \cdot |\Gamma| \cdot M \right) \ [/math] времени, базовая динамика находится, как [math]O \left( n^2 \cdot |\Gamma| \right)[/math]. Итоговая временная сложность алгоритма равна [math]O \left( n^3 \cdot |\Gamma| \cdot M \right)[/math]. Алгоритму требуется [math]O(n^2 \cdot |\Gamma| \cdot M) \ [/math] памяти.

См. также