Paper Reading:“Efﬁcient Divide-and-Conquer Parsingof Practical Context-Free Languages”

Paper from ICFP’13
発表者： kinaba

前提知識１：行列の掛け算

N×N 行列の掛け算
B11 B12 B13

Cij = Σ Aik・Bkj

B21 B22 B23

B31 B32 B33

3O(N )
回の加算乗算A11 A12 A13
A21 A22 A23
A31 A32 A33

再帰的に掛け算
N/2 × N/2 の
行列 4 つに分解して行列掛け算、と考えてもよい

B

βbᙙ

αAB+
αbAβ+αᙙa ∀aB+αbaβ+∀ᙙA再帰的に掛け算

N/2 の掛け算を8回(N/2)3 × 8 = N3BβbᙙαAB+
αbAβ+αᙙa ∀aB+αbaβ+∀ᙙ

このままでは変化なしA

[Strassen 69]

式変形すると7回でできる!!!
⇒ wikipedia⇒ O(N log2(7)) 乗算

Bβbᙙ

αAB+αbAβ+αᙙa ∀aB+αbaβ+∀ᙙA[Williams 11] 等々

もっと頑張って式変形と解析すると、もっと減る!!!!!!!

ω
行列乗算は

ωO(N )
でできる

現時点の人類の知識:ω≦2.372658
漸近計算量は速いがあまりに複雑なので実際に動かすとO(N3) の普通の乗算をきちんと書いた方が速い。
使えるのはせいぜい Strassen まで。
ωを減らすのは理論的興味。
…と考えられている模様

前提知識２：文脈自由文法

0 と 1 からなる奇数長の回文の文法

S→0S0S→1S1
S→0S→1

C言語風の何かの文法

文 → if (式 )ブロック
文 → if (式 )ブロック elseブロック
文→式;ブロック → 文
ブロック → { 文列
文列 → 文 文列文列 → }文脈自由文法

非終端記号 を、文法にしたがって書き換えっていって作れるのがその”言語”の”文”という”文法”の定義

S→0S0
S→1S1
S→0S→1

Chomsky 標準形 (CNF)
書き換え先の右辺が記号２つか１つな文法のことを “Chomsky標準形”であるという。# やや不正確な定義# この発表ではCNFだけ# 考えますS→0S0
S→1S1
S→0S→1

S→0T
T→S0S→1U
U→S1
S→0
S→1

CYK法

[Cocke et al. 70][Younger 67][Kasami 65]

文脈自由な文法に対して

S→0T
T→S0S→1U
U→S1S→0S→1“10101”
長さ N の文字列の構文解析は O(N3)
時間でできるCYK法

[Cocke et al. 70][Younger 67][Kasami 65]“10101”
S→0T
T→S0
S→1U
U→S1
S→0
S→11-0--1---0----

1

CYK法

[Cocke et al. 70][Younger 67][Kasami 65]“10101”
S→0T
T→S0
S→1U
U→S1
S→0
S→1

1,S
-

0,S-

-

1,S-

--

0,S-

---

1,S

CYK法

[Cocke et al. 70][Younger 67][Kasami 65]“10101”
S→0T
T→S0
S→1U
U→S1
S→0
S→1

1,S

M12 = M11 ☆ M22

T-

0,S-

-

“1文字目から2文字目まで”を生成するには“1文字目から1文字目” を作り“2文字目から2文字目”を作る
1,S---

0,S----

1,S

CYK法

[Cocke et al. 70][Younger 67][Kasami 65]

M13 = M11 ☆ M23† M12 ☆ M33

S→0T
T→S0
S→1U
U→S1
S→0
S→1

“10101”
1,S

T

S

-

0,S

U

-

-

1,S

T---

0,S

U----

1,S

CYK法

[Cocke et al. 70][Younger 67][Kasami 65]“10101”
S→0T
T→S0
S→1U
U→S1
S→0
S→1

1,S

T

S

TS-

0,S

U

S

U-

-

1,S

T

S---

0,S

U----1,S本題

[Valiant 75]

定理:
CFG構文解析は O(Nω) 時間で可能行列の掛け算と同じくらいのおさらい

行列の掛け算と同じくらいのCFG構文解析は O(Nω) 時間で可能
O(N3) 未満の行列乗算法は、複雑で実用には適さないおさらい

行列の掛け算と同じくらいのCFG構文解析は O(Nω) 時間で可能
O(N3) 未満の行列乗算法は、複雑で実用には適さない⇒
行列乗算を使うValiantの構文解析法も実用するならO(N3)でCYKと同じ。
この定理は理論的な興味にすぎない…？

読んだ論文読んだ論文 “Efﬁcient Divide-and-Conquer Parsing of Practical ContextFree Languages”
 To appear in ICFP’13
 Bernardy & Claessen
 Haskell で書かれ Haskell でスクリプトが書けるエディタ“Yi” を作っている人 Valiant 法を新しい視点から見直す Valiant 法が “速く” 動く文法について考える
 実際のプログラミング言語の文法はそうであると主張する

 あと普通に Valiant 法の説明が Valiant の原論文より100倍読みやすいValiant 法を新しい視点から見直す“文脈自由文法の構文解析は行列乗算を使って実装できる”△ 理論上 O(Nω) 時間でできる○ 乗算が高速にできるような特殊な行列しか使わないなら実用上もっと速くできる

疎行列！

Valiant 法の説明 (Why行列)
CYK 法を思い出そう

Mij = ∪ (Mik ☆ Mkj)“i 文字目から j文字目まで”が生成可能か調べる“i 文字目から k 文字目” を調べ“k 文字目から j 文字目”を調べそれを作れる文法規則があるか調べる

行列の掛け算の形

1,ST

S-0,SU--

1,ST---0,SU----

1,S

Valiant 法の説明(Why行列)
CYK 法のナナメ一列を埋める操作は
要素 ⇒非終端記号の集合

要素の足し算 ( ∪ )⇒集合の合併要素の掛け算 ( ☆ ) ⇒X☆Y = {N | N→ML, M∈X, L∈Y }の行列乗算！！！！！！

1,ST

S-

0,SU--

1,ST---

0,SU----

1,S

Valiant 法の説明
 CYK 法のナナメ一列を埋める操作は行列乗算⇒ ナナメ N 列を埋める操作は O(Nω+1) !!?!?!!!?!?!?!
 CYK 法の表全部を埋める操作は、乗算結果が変わらなくなるまで掛け算を繰り返す操作⇒ “Transitive Closure”⇒ 定理： 上三角行列のTCはO(Nω)時間で計算できる
1,ST

S-

0,SU--

1,ST---0,SU----1,S

Valiant 法の説明 (TC計算)“C=C・C+W”⇒
掛け算しても変わらない
不動点Valiant 法の説明
Strassen乗算を思いだそう

B

βb

ᙙ

αAB+αbAβ+αᙙa ∀aB+αbaβ+∀ᙙ

N/2 × N/2 行列に分解して再帰的に計算A

Valiant 法の説明

TCも N/2 × N/2 行列に分解して再帰計算

Valiant 法の説明

A’ と B’ は
A と B の TC。
再帰計算で求まる。

X’ は？

Valiant 法の説明

A,B,Xが与えられた時を満たすYを求める関数をとする。X’=V(A’,X,B’)A’ と B’ は
A と B の TC。
再帰計算で求まる。

X’ は？

Valiant 法の説明

さらに４つに分解

を満たす Y =この式変形の読み方

Valiant 法の計算時間

T(N) = N×N行列のTC計算
V(N) = N×N行列の V の計算
M(N) = N×N行列の乗算

T(N) = 2 T(N/2) + V(N)V(N) = 4 V(N/2) + 4 M(N/4)
よって T(N)≦O(Nω) (???)

Haskell での実装

どのような文法で、疎行列になるか？

スライドはここで終わっている（スライド作っている時間がありませんでした…）