CYK算法详解与代码实现

概述

在计算机科学领域,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
#!usr/bin/env/python 3.6.5
#-*- coding: utf-8 -*-
'''
Python 3.6.5
installed module:
- tkinter
'''

import re
import itertools
import tkinter
from tkinter import ttk


class 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)
# MaxRow == MaxCol + 1
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 lowest level
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 upper level
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)))
# get answer
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)

# default
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)
# y&x scrollbar
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)
# insert information
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]))

# end
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底层技术之语言模型


   CYKpython


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×