Problem by D. Mikurube Slides by Y. Izumi

Presentation on theme: "Problem by D. Mikurube Slides by Y. Izumi"— Presentation transcript:

1 Problem by D. Mikurube Slides by Y. Izumi
Reading Brackets Problem by D. Mikurube Slides by Y. Izumi

2 a list of A, a list of P and Q, B, a list of X, Y and Z and C
Problem Outline 与えられた英文を S 式に変換せよ． 一応は機械翻訳の問題であるが，実質的には文法解析の問題． a list of A, a list of P and Q, B, a list of X, Y and Z and C (A (P Q) B (X Y Z) C)

3 Submission Summary 提出数 : 18 正答数 : 2 難しすぎた
240min  ((lambda x.xx)(lambda x.xx)) 267min  kitsune- 難しすぎた 難易度を気にせずに作ったら，こんな難しい問題になってしまったらしい． 曖昧性判定が曲者だった． 解釈が 1 通りであることが保証されていれば易しい．

4 How to Solve 想定解法 発展解法 CYK アルゴリズム，計算量は O(N3)
"a list of" と "and" の対応を求める問題だとみなすと線形時間の解析も可能．

5 Simplification もとの文法は解析が少し面倒． 入力文を次のように前処理する．
"a list of" は実質一単語として扱いたい． カンマは解析する上で不要． 入力文を次のように前処理する． 文字列中の "a list of" を "list" に置換する． カンマを全部削除する． 空白で分割して配列に格納する． e.g. list A B C and D e.g. list A list P and Q B list X Y and Z and C

6 Grammar Syntax S  "list" E S  "list" L L  E L L  E "and" E E  T
T  "A" | "B" | ...

7 LL Parsing ICPC における構文解析はこれがほとんど． （通常は）再帰降下法を適用する．
ただし今回は解釈が一意ではない可能性があるため，バックトラックを行わなければならない． 今回の問題では時間切れになる． 途中経過を上手に残せば間に合うかもしれないが． いわゆる形式言語理論（オートマトン，文脈自由文法）の科目の教科書などを参照して下さい．

8 LR Parsing 念のため触れておきます．
あらかじめ LR table を作成して，それに基づいてプッシュダウン・オートマトンで解析する． 表の作成が面倒なので ICPC で活用される例は少ない． 今回はオートマトンが非決定的になる． 今回の問題では時間切れになる． いわゆる形式言語理論（ry

9 Chomsky Normal Form 非終端記号 終端記号 チョムスキー標準形 規則の左辺にあらわれる記号． 文中に現れる記号．
全ての規則の右辺が非終端記号 2 個あるいは終端記号 1 個のいずれか．

10 Grammar Syntax (CNF) S  W1 S S  W1 T S  W1 L L  S L L  T L
L'  W2 S L'  W2 T T  "A" | "B" | ... W1  "list" W2  "and"

11 CYK Algorithm (1 of 2) 表を斜め方向（左上から右下）に埋める．
1 2 3 4 5 6 表を斜め方向（左上から右下）に埋める． 動的計画法 表中の S:1 は右辺の非終端記号が位置が 1 で分離されるという意味． e.g. S:1（左上） 規則は S  W1 L 本来はどの規則を適用したかも記録する． 0～1  W1 1～6  L W1 S:1 S:1 list T L:2 A W1 S:3 S:3 L:4 list T L:4 B W2 L':5 and T C

12 CYK Algorithm (2 of 2) (* w[0..n-1] = sentence *) for i = 0 to n-1
for each rule X -> w[i] t[i,i+1] = t[i,i+1] + {(X,i,w[i])} for k = 2 to n for i = 0 to n-k for j = 1 to k-1 for each rule X -> YZ if (Y,?,?) in t[i+0,i+j] and (Z,?,?) in t[i+j,i+k] then t[i,i+k] = t[i,i+k] + {(X,j,YZ)}

13 （参考）Advanced Algorithms
Earley 法 一般の文脈自由文法に適用可能な解析法． CYK 法と比べると複雑だが O(N3) 時間で解析可能． Bottom-up Chart 法 Earley 法に近いがボトムアップに解析する． GLR 法 オートマトンが非決定的であっても効率のよい解析が行えるように LR 法を改良したもの． 決定的ならば線形時間，最悪時は O(N3) 時間．

14 From Another Viewpoint
問題を "a list of" と "and" の対応付けを求める問題だと考える． 対応付けが与えられれば，S 式は一意に構築できる（具体的手順は省略）． e.g. list A list P and Q B list X Y and Z and C (A (P Q) B (X Y Z) C)

15 Linear-time Algorithm (1 of 2)
曖昧フラグを偽に初期化する． 最後の and の直前まで前から順番に走査． list が現れたら，現在位置をスタックに積む．このとき直前が and で，さらにもとのスタックが空でなければ，曖昧フラグをセットする（それ以外ではそのまま）． and が現れたら，スタックからポップした位置と現在位置の対応関係を適当な方法で記録する．ポップした後，スタックの要素数が 2 以上ならば曖昧フラグを立てる．そうでないときは逆に曖昧フラグをクリアする． それ以外はとりあえず無視．

16 Linear-time Algorithm (2 of 2)
最後の and は次のように扱う． スタックに単一の要素しかなければ一意． 曖昧フラグはクリアする． 曖昧フラグが立っていて，スタックに複数の要素があるときは与えられた文が曖昧だと判断する． そうでないときは，最後の and は対応関係が未解決の list のうち最も左側にあるものに対応させる． 残りは単一要素のリストの開始とみなす． ただし，最も左側において list が連続しているときは曖昧だと判断する．

17 Examples (1 of 2) スタックの内容だけ表記，* は曖昧なことをあらわす．
list A list P and Q B list X Y and Z and C []  [0]  [0,2]  [0]  [0,7]  [0]  [] list A list B C D E and F []  [0]  [0,2]  [2] 最後の and は特別扱いされることに注意 list list A A and A []  [0]  [0,1]  [1]* 先頭が list の連続なので曖昧になる list list A and A and A []  [0]  [0,1]  [0]  []

18 Examples (2 of 2) list A list B list C and D and E
[]  [0]  [0,2]  [0,2,4]  [0,2]*  [2]* D の直前の対応関係が曖昧 list A list list B and C and D list E F and G []  [0]  [0,2]  [0,2,3]  [0,2]*  [0]  [0,9]  [9] list A list B C and list D and E []  [0]  [0,2]  [0]  [0,6]*  [6]* and の直後に list があることが曖昧性を生んでいる list A and list B and list C []  [0]  []  [3]  [] C の直前の list は最後の and の後ろにあるため無視される

19 Validity 後日，別の場所に説明のためのページを用意したいと思います．