-
CYK算法
鎖定
- 中文名
- CYK算法
- 外文名
- Cocke–Younger–Kasami algorithm
CYK算法簡介
普通的回溯法（backtracking）在最壞的情況下需要指數時間才能解決這樣的問題，而CYK算法只需要多項式時間就夠了（{\displaystyle ~O(n^{3})}， n 為字符串 w 的長度）。CYK算法採用了動態規劃的思想。
對於一個任意給定的上下文無關文法，都可以使用CYK算法來計算上述問題，但首先要將該文法轉換成喬姆斯基範式。
[1]
CYK算法相關參數定義
1.
是一個上下文無關文法
2.對於任意字符串
，定義
CYK算法算法描述
CYK算法簡介
通過由下而上的方法計算
這個集合，如果
，那麼就説明
是被上下文無關文法G接受的字符串。
因為
是一個喬姆斯基範式，當且僅當有下面描述的情況時
：
CYK算法偽代碼
FOR i:= 1 TO n DO {\displaystyle V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}}FOR l:= 1 TO n-1 FOR i:= 1 TO n-l DO {\displaystyle ~V_{i,i+l}:=\varnothing } FOR k:= i TO i+l-1 DO {\displaystyle ~V_{i,i+l}:=V_{i,i+l}\cup \{X~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}}IF {\displaystyle S\in V_{1,n}} THEN accept ELSE reject
CYK算法擴展CYK算法
CYK算法簡介
對於上述CYK算法作一個小改動，也就是説記住每次的k，就可以自動產生一個由該上下文無關語言的推導樹。
CYK算法偽代碼
FOR i:= 1 TO n DO {\displaystyle V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}}FOR l:= 1 TO n-1 FOR i:= 1 TO n-l DO {\displaystyle ~V_{i,i+l}:=\varnothing } FOR k:= i TO i+l-1 DO {\displaystyle ~V_{i,i+l}:=V_{i,i+l}\cup \{(X,k)~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}}IF {\displaystyle \exists k:(S,k)\in V_{1,n}} THEN accept ELSE reject
通過對下面的方法遞歸運行就可以生成推導樹。
Tree(X,i,j): IF i=j THEN RETURN {\displaystyle ~\sigma _{i}} 選擇一個 k 使 {\displaystyle (X,k)\in V_{i,j}} 選擇 Y 和 Z 使 {\displaystyle X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,j}} RETURN Tree(X,Tree(Y,i,k),Tree(Z,k+1,j))
- 參考資料
-
- 1. Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3. Information and Control 10(2): 189–208.
- 2. T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：8次歷史版本
- 最近更新： 郝会918