Document

Reading Brackets
Problem by D. Mikurube
Slides by Y. Izumi
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)
Submission Summary
 提出数 : 18
 正答数 : 2
 240min  ((lambda x.xx)(lambda x.xx))
 267min  kitsune 難しすぎた
 難易度を気にせずに作ったら，こんな難しい問題に
なってしまったらしい．
 曖昧性判定が曲者だった．
 解釈が 1 通りであることが保証されていれば易しい．
How to Solve
 想定解法
 CYK アルゴリズム，計算量は O(N3)
 発展解法
 "a list of" と "and" の対応を求める問題だとみなすと
線形時間の解析も可能．
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
Grammar Syntax
 S  "list" E
 S  "list" L
L  E L
 L  E "and" E
E  T
E  S
 T  "A" | "B" | ...
LL Parsing
 ICPC における構文解析はこれがほとんど．
 （通常は）再帰降下法を適用する．
 ただし今回は解釈が一意ではない可能性があるため，
バックトラックを行わなければならない．
 今回の問題では時間切れになる．
 途中経過を上手に残せば間に合うかもしれないが．
 いわゆる形式言語理論（オートマトン，文脈自由文法）
の科目の教科書などを参照して下さい．
LR Parsing
 念のため触れておきます．
 あらかじめ LR table を作成して，それに基づいてプッ
シュダウン・オートマトンで解析する．
 表の作成が面倒なので ICPC で活用される例は少ない．
 今回はオートマトンが非決定的になる．
 今回の問題では時間切れになる．
 いわゆる形式言語理論（ry
Chomsky Normal Form
 非終端記号
 規則の左辺にあらわれる記号．
 終端記号
 文中に現れる記号．
 チョムスキー標準形
 全ての規則の右辺が非終端記号 2 個あるいは終端
記号 1 個のいずれか．
Grammar Syntax (CNF)
 S  W1 S
 S  W1 T
 S  W1 L
L  S L
L  T L
 L  S L'
 L  T L'
 L'

 L' 
T 
 W1 
 W2 
W2 S
W2 T
"A" | "B" | ...
"list"
"and"
CYK Algorithm (1 of 2)
0
1
W1
list
2
3
4
5
S:1
6
S:1
T
L:2
A
W1
list
S:3
S:3
L:4
T
L:4
B
W2
and
L':5
 表を斜め方向（左上か
ら右下）に埋める．
 動的計画法
 表中の S:1 は右辺の非
終端記号が位置が 1 で
分離されるという意味．
 e.g. S:1（左上）
 規則は S  W1 L
 本来はどの規則を適用
したかも記録する．
 0～1  W1
T
 1～6  L
C
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)}
（参考）Advanced Algorithms
 Earley 法
 一般の文脈自由文法に適用可能な解析法．
 CYK 法と比べると複雑だが O(N3) 時間で解析可能．
 Bottom-up Chart 法
 Earley 法に近いがボトムアップに解析する．
 GLR 法
 オートマトンが非決定的であっても効率のよい解析が
行えるように LR 法を改良したもの．
 決定的ならば線形時間，最悪時は O(N3) 時間．
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)
Linear-time Algorithm (1 of 2)
 曖昧フラグを偽に初期化する．
 最後の and の直前まで前から順番に走査．
 list が現れたら，現在位置をスタックに積む．このとき
直前が and で，さらにもとのスタックが空でなければ，
曖昧フラグをセットする（それ以外ではそのまま）．
 and が現れたら，スタックからポップした位置と現在位
置の対応関係を適当な方法で記録する．ポップした後，
スタックの要素数が 2 以上ならば曖昧フラグを立てる．
そうでないときは逆に曖昧フラグをクリアする．
 それ以外はとりあえず無視．
Linear-time Algorithm (2 of 2)
 最後の and は次のように扱う．
 スタックに単一の要素しかなければ一意．
 曖昧フラグはクリアする．
 曖昧フラグが立っていて，スタックに複数の要素があ
るときは与えられた文が曖昧だと判断する．
 そうでないときは，最後の and は対応関係が未解決
の list のうち最も左側にあるものに対応させる．
 残りは単一要素のリストの開始とみなす．
 ただし，最も左側において list が連続しているときは
曖昧だと判断する．
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]  []
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 の後ろにあるため無視される
Validity
 後日，別の場所に説明のためのページを用意し
たいと思います．

Download Report