概述
在计算机科学领域,CYK算法(也称为Cocke–Younger–Kasami算法)是一种用来对上下文无关文法(CFG,Context Free Grammar)进行语法分析(parsing)的算法。该算法最早由John Cocke, Daniel Younger and Tadao Kasami分别独立提出,其中John Cocke还是1987年度的图灵奖得主。CYK算法是基于动态规划思想设计的一种自底向上语法分析算法。
乔姆斯基范式
我们首先来谈谈CNF的话题。通常把一门语言定义成一些由单词组成的词串(也就是句子)构成的集合。所以如果问两种语法(或文法)是否等价,其实就是要考察它们能否生成完全一样的词串集合。事实上,两个完全不同的CFG是不可能生成相同语言的。
而谈到两种语法“等价”,我们又可以定义弱等价和强等价两种类型的等价:
如果两种语法能够生成相同的词串集合,且为每个句子都赋与相同的短语结构(phrase structure),也就是说仅允许对non-terminal symbols进行重命名,那么它们就是强等价的。
如果两种语法能够生成相同的词串集合,但不会为每个句子都赋与相同的短语结构,那么它们就是弱等价的。
CNF(Chomsky Normal Form)是一种这样的语法标准: 如果一个\(CFG是 \varepsilon-free\) ,而且它的规则只有如下两种形式:
\(A\rightarrow BC\)
\(A\rightarrow a\)
那么这个CFG就是CNF形式的,可见CNF语法都是二分叉的。任何语法都可以转化成一个弱等价的CNF形式,具体方法如下:
Step 1: Convert \(A\rightarrow Bc\) to \(A\rightarrow BC\) ,\(C\rightarrow c\)
Step 2: Convert \(A\rightarrow BCD\) to \(A\rightarrow BX,X\rightarrow CD\)
CYK算法
CYK算法处理的语法必须是CNF形式的,所以如果输入的是任意文法,那么需要按照前面的步骤把CFG转换成CNF形式。
CYK算法是用来判断一个字符串是否属于某个CNF语法,故设输入的字符串w长度为n。
接下来我们需要用程序填一个动态规划的状态转移表,这里我们叫这个表parse table。
parse table的规模为\((n + 1) \times n\)
算法原理
注意,我们前面说过CYK是一种自底向上的算法,这里的自底向上意思是从单词开始,朝向 S(句子)工作。所以在上图我们填写的大方向是从左到右填写的。S 位于表的右上角,表示成功。算法描述如下: 其中,i 和 j 指示的内容如下图所示:
我们定义\(PT[n + 1][n]\) 表示parse table,且\(PT[n, :]\) 依次存储字符串w中的每一个符号\(a_1, a_2, \dots, a_n\) 。 \[
\begin{bmatrix}
& &\dots & \\
& \vdots & \ddots & \\
a_1 & a_2 & \dots &a_n
\end{bmatrix} %]]>
\] 我们设根据给定CNF,即G能推导出w中第i到第j个字符的串的集合为\(x_{i,j}\)
为了填写这个表,我们一行一行,自下而上地处理。每一行对应一种长度的子串。最下面一行对应长度为1的子串,倒数第二行对应长度为2的子串,以此类推。最上面一行就对应长度为n的子串,即w本身。计算该表的任何一个表项的方法如下:
对于最下面一行的元素,即\(x_{i,i}\) ,是使得\(A \rightarrow a_i\) 是G的产生式的变元A的集合。
对于不在最下面一行的元素,我们需要找到符合以下条件的变元A的集合:
1、整数k满足\(i \leq k < j\)
2、\(B \in X_{i,k}\)
3、\(C \in X_{k+1, j}\)
4、\(A \rightarrow BC\) 是G的产生式
根据这样的方法,我们可以填出一个下三角矩阵。
例如:
CNF文法G的产生式: \[
S \rightarrow AB|BC \\
A \rightarrow BA|a \\
B \rightarrow CC|b \\
C \rightarrow AB|a
\] 对L(G)测试字符串\(w = baaba\) 的成员性构造Parse Table如下: \[
\begin{bmatrix}
x_{1,5}=\{S, A,C\} & & & & \\
& x_{2,5}=\{S, A, C\} & & & \\
& x_{2,4}=\{B\} & x_{3,5}=\{B\} & & \\
x_{1,2} = \{S, A\} & x_{2,3}=\{B\} & x_{3,4}=\{S, C\} & x_{4,5}=\{S, A\} &\\
x_{1,1} = \{B\} & x_{2,2} = \{A, C\} & x_{3,3} =\{A, C\} & x_{4,4}=\{B \} & x_{5,5}=\{A,C\} \\
a_1 = b & a_2 = a & a_3 = a & a_4 = b & a_5 = a
\end{bmatrix} %]]>
\] 最终得到\(x_{1,5}\) 集合之后,判断起始变元\(S\) 是否属于\(x_{1,5}\) 。如果是,则w可被G接受,反之不接受。
代码实现
cyk.py 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 ''' Python 3.6.5 installed module: - tkinter ''' import reimport itertoolsimport tkinterfrom tkinter import ttkclass CNF (object ): def __init__ (self ): self.__rules = {} def read_file (self, filename ): with open (filename, 'r' ) as inFile: for line in inFile.readlines(): line = re.sub('[\n\t ]' , '' , line) rec_begin = line[:line.find('-' )] for element in line[line.find('>' ) + 1 :].split('|' ): if element in self._CNF__rules: self.__rules[element].append(rec_begin) else : self._CNF__rules[element] = [rec_begin] def get_inf (self, tar ): if isinstance (tar, list ) == False : exit() inf_set = [] for tarEle in tar: inf_set.extend(self.__rules.get(tarEle, [])) return list (set (inf_set)) class CYK (object ): def __init__ (self, filename ): if isinstance (filename, str ) == False : exit() self.__str = '' self.__srtlen = 0 self.__canvas = [] self.__myCNF = CNF() self.__myCNF.read_file(filename) def get_str (self ): self._CYK__str = input ('input string:\n' ).strip() if len (self._CYK__str) == 0 : exit() self._CYK__srtlen = len (self._CYK__str) self._CYK__canvas = list (list ([] for tmp in range (self._CYK__srtlen)) for tmp in range (self._CYK__srtlen + 1 )) for iter in range (self._CYK__srtlen): self._CYK__canvas[self._CYK__srtlen][iter ].append(self._CYK__str[iter ]) def CYK_process (self ): for col in range (self._CYK__srtlen): self._CYK__canvas[self._CYK__srtlen - 1 ][col].extend(self._CYK__myCNF.get_inf(self._CYK__canvas[self._CYK__srtlen][col])) for row in range (self._CYK__srtlen - 2 , -1 , -1 ): for col in range (row + 1 ): mid_set = set () idx_i, idx_j = col + 1 , col - row + self._CYK__srtlen for mid_k in range (idx_i, idx_j): fir_row, fir_col = idx_i - mid_k - 1 + self._CYK__srtlen, idx_i - 1 sec_row, sec_col = mid_k - idx_j + self._CYK__srtlen, mid_k mid_set |= set (obj[0 ] + obj[1 ] for obj in itertools.product(self._CYK__canvas[fir_row][fir_col], self._CYK__canvas[sec_row][sec_col])) self._CYK__canvas[row][col].extend(self._CYK__myCNF.get_inf(list (mid_set))) if 'S' in self._CYK__canvas[0 ][0 ]: print ('%s can be accepted.' % self._CYK__str) else : print ('%s can not be accepted.' % self._CYK__str) def GUI_show (self ): def exc (line, step, row ): if isinstance (line, list ) == False and isinstance (line[0 ], list ) == False : exit() for col in range (len (line)): line[col] = str ('{' + '%s, ' * (len (line[col]) - 1 ) + '%s' * (len (line[col]) > 0 ) + '}' ) % (tuple (line[col])) if col <= row: line[col] = 'X%d,%d = ' % (col + 1 , step + col + 1 ) + line[col] return (line) window = tkinter.Tk() window.geometry('800x400' ) window.title('CYK algorithm' ) table = ttk.Treeview(window, height = 10 , show = 'headings' ) table['columns' ] = (list (elem for elem in range (self._CYK__srtlen))) for col in range (self._CYK__srtlen): table.column(str (col), width = 100 ) yscrollbar = tkinter.Scrollbar(window, orient = tkinter.VERTICAL, command = table.yview) table.configure(yscrollcommand = yscrollbar.set ) yscrollbar.pack(side = tkinter.RIGHT, fill = tkinter.Y) xscrollbar = tkinter.Scrollbar(window, orient = tkinter.HORIZONTAL, command = table.xview) table.configure(xscrollcommand = xscrollbar.set ) xscrollbar.pack(side = tkinter.TOP, fill = tkinter.X) for row in range (self._CYK__srtlen): table.insert('' , row, values = exc(self._CYK__canvas[row], self._CYK__srtlen - row - 1 , row)) table.insert('' , self._CYK__srtlen, values = (self._CYK__canvas[self._CYK__srtlen])) table.pack(side = tkinter.TOP, expand = 1 , fill = tkinter.BOTH) window.mainloop() def main (): myCYK = CYK('./CNF.cfg' ) myCYK.get_str() myCYK.CYK_process() myCYK.GUI_show() if __name__ == '__main__' : main()
实验效果
参考文献
概率上下文无关文法PCFG
Tagging Problems, and Hidden Markov Models
NLP底层技术之语言模型