a)対訳句の抽出

単語に基づく対訳文パターンと対訳学習文を用いて，対訳句を抽出する． まず単語に基づく対訳文パターンを用いて対訳学習文の構文解析を行う．構文解析にはボトムアップアルゴリズムを用いる． 構文解析を行うために，単語に基づく対訳文パターンはチョムスキー標準形（式(2.21)）の文脈自由文法に変換する．式(2.21)において，$V_X$ は非終端記号の集合，$V_C$ は前終端記号の集合を表す．

$${\rm A \rightarrow BC} {\rm A} \in V_X, B,C \in (V_C \cup V_X)$$ (2.21)

パターンに基づく統計翻訳は対訳文パターンの変数に品詞よる制約を持たないため，チョムスキー標準形の規則は変数化していない部分（以下，字面）と変数および記号で構成される．日本語文パターン``$X1$ は $X2$ $X3$ が いる 。"のチョムスキー標準形を表2.9に示す．表2.9において，``S数"は前終端記号を，``S"は開始記号を表す．なお，チョムスキー標準形への変換の際に，対訳文パターンに対して終端記号``END1"と``END2"を付与する．

表: チョムスキー標準形の例

規則

S $\rightarrow$ $X1$ 　S1

S1 $\rightarrow$ は　　S2

S2 $\rightarrow$ $X2$ 　S3

S3 $\rightarrow$ $X3$ 　S4

S4 $\rightarrow$ が　　S5

S5 $\rightarrow$ いる　S6

S6 $\rightarrow$ 。　　S7

S7 $\rightarrow$ END1 END2

構文解析は三角行列$a_{ij}$ （1 $\leq i \leq j \leq n$ ，$n$ は単語数）を用いて解析を行う． 日本語入力文``あの 人 は たくさん の 友達 が いる 。"を表2.9の文法規則を用いて構文解析する場合の三角行列を図2.13に示す．

図: 構文解析の例

構文解析において，変数に複数単語が適合することを許す．また，変数は品詞情報や関数による制約を持たないため，全ての単語および複数単語が変数と適合する． 文法規則を用いて要素$a_{n-1,n}$ から$a_{1,n}$ へボトムアップアルゴリズムで文法規則の探索を行う．要素$a_{k,n}$ において，文法規則の探索を行う場合，$a_{k,k+i}$ と $a_{k+1+i,n}$ を参照し探索を行う．ここで，$i$ は0 から$k+1+i=n$ になるまで１ずつ加算していく．例えば，図2.13の要素$a_{7,11}$ のS4は表2.9の文法規則より$a_{7,7}$ の``が"と$a_{8,11}$ の``S5"の文法規則より作られる．また，要素$a_{6,11}$ の$S3$ は$a_{6,6}$ の``友達"を変数``$X3$ "とし，$a_{7,11}$ の``S4"との文法規則より作られる．なお，各記号が，どの記号，変数および字面から作られたかをポインタにより記録しておく． そして，要素$a_{1,n}$ まで，文法規則の探索を行い，$a_{1,n}$ に開始記号Sが与えられれば，入力文の構文解析に成功したといえる． 構文解析に成功した場合，開始記号Sからポインタをたどり，各変数に対応する入力文の単語列を句として抽出する． 図2.13の構文解析により抽出される日本語句を表2.10に示す．

表: 抽出される日本語句の例

日本語句

あの 人

たくさん

たくさん の

友達

の 友達

日本語文パターンの対となる英語文パターンを用いて日本語学習文の対となる英語学習文に対しても同様の構文解析を行い，変数に対応する英語学習文の単語列を句として抽出する． そして，得られた日本語句と英語句において，同一の変数におけるすべての組み合わせを取得し，対訳句とする．

対訳句抽出の流れを図2.14に示す． なお，対訳句の抽出は網羅的に行うため，不適切な対応をとる対訳句を抽出する問題がある．図2.14の例では``彼の顔に"と``He"のような不適切な対応をとる対訳句がある．

図: 対訳句抽出の流れ