電子情報通信学会論文誌 2006/12 Vol. J89–D No. 12構造パターンを受け取る．システムは入力された文法を用いてコーパス中の文を構文解析し，与えられた句依存構造に基づくコーパス検索加藤芳秀† a)（正員）稲垣康善†††（名誉員：フェロー）

松原茂樹††（正員）

兵藤らの手法 [3] や，Resnik らの提案する Linguist’sSearch Engine（LSE）[6] では，ユーザはまず，検出

Corpus Search Based on Dependency Structure
Yoshihide KATO† a) , Shigeki MATSUBARA†† , Members,

した い 文 の 一 例 を 入 力 す る ．入 力さ れ た 例 文 は 構

and Yasuyoshi INAGAKI††† , Fellow†††

文解析され，結果が提示される．ユーザは提示され名古屋大学大学院国際開発研究科，名古屋市

Graduate School of International Development, Nagoya Uni-

た構文解析結果を編集し，構造的なパターンを作成

versity, Nagoya-shi, 464–8601 Japanする．最終的にシステムは，編集により得られたパ名古屋大学情報連携基盤センター，名古屋市

Information Technology Center, Nagoya University, Nagoya-

ターンにマッチする構造をもつ文をコーパスから検出する．

shi, 464–8601 Japan†††

構造パターンをもつ文を検出する．

愛知県立大学情報科学部，愛知県

Faculty of Information Science and Technology, Aichi Pre-

しかしながら，これらのシステムが，キーワードに基づく検索のような，簡単で直観的なインタフェース

fectural University, Aichi-ken, 480–1198 Japana) E-mail: yosihide@gsid.nagoya-u.ac.jpを実現しているとは言いがたい．文法の設計や句構造パターンの編集が可能なレベルの文法的知識をもたなあらましキーワード系列の入力に対して，系列中のキーワードがコーパス内の各文において形成する依いユーザは，これらのシステムを利用することはできない．

存構造パターンを同定し，パターンごとに検索結果をそこで本論文では，キーワード系列をクエリとして分類する用例文検索を提案する．文の構文的構造を活受け取り，それらが形成する構造的なパターンを自動用した用例文検索が実現できる．

的に同定する用例文検索を提案する．本手法では，言キーワード 用例文検索，依存構造，構文木付き語構造として依存構造を用いる．検索対象のコーパスには，依存構造解析器などによりあらかじめ依存構造コーパス，依存構造パターン

1. ま え が きが付与されていることを前提とする．クエリを受け取

近年，言語資源としての大規模コーパスの重要性はると，まずコーパス内を検索し，クエリ中のすべてのますます高まっており，言語現象の調査，外国語学習，キーワードをその順序どおりに含む文を検出する．次自然言語処理システムの開発など様々な場面で活用さに，検出された各文において，キーワード系列が形成れている．コーパスを効果的に活用するために，様々する依存構造パターンを，コーパスに付与された依存なコーパス検索システムが提案されている．

構造を参照して同定する．

従来システムの多くは，いくつかのキーワードをク文の依存構造に応じて，キーワード系列は異なったエリとして受け取り，それらを含む用例文を検出する．

依存構造パターンを形成することになる．本手法では，精度の高い検索を実現するために，クエリ中の隣接す依存構造パターンごとに文を分類し，依存構造パターるキーワード間の距離を定義し，ある距離以下でキーンとそれにマッチする依存構造をもつ文を併せて表示

ワードが出現する文のみを検出する手法なども提案さする．依存構造パターンを提示することにより，ユーれている [5]．キーワードに基づく検索は，直観的でザは表示された文においてキーワード同士がどのようユーザビリティが高い反面，構文構造などの言語的構な構文的関係にあるかを知ることができる．また，特造を活用した検索はできず，ユーザは検出された文に定のパターンをもった文を探す場合にも，ユーザはいおいてキーワード同士にどのような関係があるのかをくつかの依存構造パターンの中から必要とするパター知ることはできない．

ンを選択するだけでよく，文法の設計や構造的なパ一方で，構造的な条件をユーザが明示的に指定して検索するシステムがこれまでに提案されている [2], [3], [6]．
これらのシステムでは，句構造や依存構造のパターンをクエリとしてコーパスを検索する．

ターンの編集などは不要である．

2. 依存構造パターン同定アルゴリズム
本章では，提案するコーパス検索の中心をなす依存構造パターン同定アルゴリズムについて述べる．同定

Corley らの提案する Gsearch [2] では，入力として，された依存構造パターンに従って，コーパス中の文は句構造パターンを生成するための文法と検出したい句分類される．本アルゴリズムは，キーワード（単語，2766

電子情報通信学会論文誌 D Vol. J89–D

c （社）電子情報通信学会 2006
No. 12 pp. 2766–2770 レター

図 1 “It is important for us to have such technology”
に対する依存関係
Fig. 1 Dependency relations for a sentence “It isimportant for us to have such technology.”

Fig. 2図 2 依存構造パターンの例
An example of dependency structure pattern.
図3 結合操作
Fig. 3 Combining.

または品詞（注 1））の系列，文，及び文の依存構造が与えられると，キーワード系列が形成する依存構造パター存することを意味する．R の場合は，右から依存するンを同定する．依存構造パターンは，キーワードに対ことを意味する．

応する文中の単語の間に成り立つ依存関係を表現する．
例えば，キーワード系列

本アルゴリズムは，クエリ q1 · · · qm に対して以下の操作をボトムアップに適用することにより，クエリ

it is for to(1)中のキーワードから構成される依存構造パターンを生成する．クエリ全体に対して依存構造パターン d が生及び，図 1 の文と依存構造が与えられると，図 2 の依（注 2）存構造パターンを出力する．この依存構造パター

ンは，各キーワードに対応する単語 “It,” “is,” “for,”

成されるとき，s の依存構造が d とマッチすることを意味する．
初期化

各 qi (1 ≤ i ≤ m)，wj (1 ≤ j ≤ n) に対“to” の間の依存関係（例えば，“It” が “is” に依存すして，qi が単語 wj あるいはその品詞にマッチするなるという関係）を表現している．

らば，qi に対する依存構造パターンとして (j, ε, ε) を本アルゴリズムは，キーワード系列からボトムアップに依存構造パターンを生成することにより，キーワード系列全体が形成する依存構造パターンを同定する．生成される依存構造パターンは，文の依存構造にマッチするパターンのみである．

生成する．

d = (h, L, R)，及び d = (h , L , R )をそれぞれ，qi · · · qj ，及び qj+1 · · · qk に対する依存構造パターンとし，d 中の最も右に出現する単語位置が，d 中の最も左に出現する単語位置よりも小結合操作入力として，さいものとする．h → h ∈ D かつ R = ε なら

q1 · · · qm （qi (1 ≤ i ≤ m) はキーワード）
文 s = w1 · · · wn （wj (1 ≤ j ≤ n) は単語と品詞

ば，qi · · · qj qj+1 · · · qk に対して，依存構造パターンクエリの対）依存構造（= 依存関係の集合） D(h , dL , R ) を生成する（図 3 (a) 参照）．h → h ∈ D
ならば，依存構造パターン (h, L, Rd ) を生成する（図 3 (b) 参照）．

を受け取り，依存構造パターンの集合を出力する．こ

結合操作を繰り返し適用することにより，クエリ中こで，D は，文 s に出現する単語間の依存関係の集の各キーワードが，クエリ中の別のキーワードに直接合である．wj が wk に依存するとき，その単語位置依存するようなすべてのパターンを生成できる．すの対 (j, k) は D の要素である．以下では，(j, k) をなわち，パターンが生成された文のみが，クエリ中のj → k と書くことにする．

キーワードが依存関係にある文である．

依存構造パターンは 3 項組 d = (h, L, R) である．
h は単語位置であり，これを d の主辞と呼ぶ．L，及び R は，依存構造パターンのリストである．(h, L, R)
は，L 中の依存構造パターンの主辞が左から h に依

図 4 に依存構造パターン同定アルゴリズムを示す．
（注 1）：単語や品詞の文字列パターンを正規表現により記述することもできる．
（注 2）：英語文を例に考えるが，本手法は，依存構造が付与された文であれば言語によらず適用可能である．

2767

電子情報通信学会論文誌 2006/12 Vol. J89–D No. 12を生成する．同様にして，“for to” に対して，(4, ε, (6, ε, ε))(7)を生成する．更に，4 → 2 であるので，依存構造パターン (6) と (7) を結合し，“it is for to” に対する依存構造パターンとして，(2, (1, ε, ε), (4, ε, (6, ε, ε)))(8)を生成する．以上より，図 1 の文には，依存構造パター
ン (8) の形で，“it is for to” が出現していることが分かる．一方，クエリ中のキーワードが依存関係が成り立つ形で出現していない文（例えば，“It is clear whether

support for the proposal will be broad enough to aserious challenge”）に対しては，結合操作によって依存構造パターンは生成されない．
図 4 依存構造パターン同定アルゴリズム
Fig. 4 An algorithm of identifying dependency
structure patterns.

3. 実装と評価提案手法を，CMUCL（注 3）を用いて実装した．シス
テムでは，検出された文は，マッチする依存構造パターンごとに分類され，依存構造パターンはグラフィ

D[i, j] は，過程で生成される qi+1 · · · qj に対する依カルに表示される．検索画面を，図 5 に示す．画面上存構造パターンを記録する．

部は，キーワード系列の入力部である．検索結果は，rm(d) は，d 中の最も右に出現する単語位置，lm(d )は，d 中の最も左に出現する単語位置を表す．
2. 1 依存構造パターン生成例
本章の冒頭に挙げた例，すなわち，クエリ (1)，及び図 1 の文とその依存構造に対する依存構造パターンの生成を考える．の単語にマッチするので，これに対して依存構造パターン

以下では，いくつかのクエリに対するシステムの具体的な動作について考察する．検索対象として，英語新聞記事に句構造を付与したコーパスである Penn
構造は，文献 [1] の方法に従って依存構造に変換した．
クエリ中のキーワードをその順序どおりに含む文を，人手により正解・不正解に分類し，検索システムの分(2)類とどのような関係にあるかを調べた．
動作例 1：“it is for to” に対する検索を生成する．同様にして，“is,” “for,” 及び “to” に対してそれぞれ，(2, ε, ε)をもつ文を並べる形で表示される．

Treebank [4] の 49208 文を使用した．コーパス中の句

まず，クエリの 1 番目の単語 “it” は，文の 1 番目

(1, ε, ε)依存構造パターンの下に，それにマッチする依存構造

クエリ “it is for to” に対する検索結果を表 1 に示
す．クエリ中のキーワードをこの順序どおりに含む文(3)(4, ε, ε)(4)(6, ε, ε)(5)は，合計 77 文あり，そのうち 17 文について依存構造パターンが同定された．同定された依存構造パターンはすべて，2. 1 の例と同様の形のパターンであり，そのパターンをもつ文はすべて正解であった．依存構造パターンが同定されなかった正解データを調べたとこを生成する．
隣接する依存構造パターン (2) と (3) の主辞に注目

ろ，それらに対する依存構造では，“for” は be 動詞ですると，依存関係 1 → 2 が成り立つ．したがって，“itはなく，補語に依存していた．このように，キーワーis” に対して，依存構造パターンドが他のキーワードに直接依存しないような文に対し(2, (1, ε, ε), ε)
2768

(6)

（注 3）：http://www.cons.org/cmucl/

レター

Fig. 5

図5 検索画面A view of sentence retrieval.

表 1 クエリ “it is for to” に対する検索結果
Table 1 Result for a query “it is for to.”パターンが同定された文されなかった文合計

表 2 クエリ “have 前置詞 mind” に対する検索結果
Table 2 Result for a query “have preposition mind.”

正解 不正解 合計
1701745660
215677パターンが同定された文されなかった文
合計

正解10111不正解 合計
01011121122てはその依存構造パターンを同定することはできないを同定し，同定されたパターンに基づき用例文を分類が，全体としては，81.0% (= 17/21) の正解データをするコーパス検索システムを提案した．提案システム

誤りを含むことなく分類することに成功している．の有用性を，いくつかのクエリに対する具体的な動作

動作例 2：“have 前置詞 mind” に対する検索の観察を通して確認した．結合操作のみによる依存構

クエリ “have 前置詞 mind” に対する検索について

造パターン同定では，クエリ中のキーワードが，他の考える．結果を表 2 に示す．このクエリについても，キーワードと直接には依存関係をもたない文を検出で依存構造パターンが同定されたか否かで文を分類するきない．このような文を検出する方法については稿をことにより，正解と不正解を高い精度で分類できる．

改めて論じたい．

前置詞にマッチした 10 個の単語のうち，9 個は “in”

今後の課題として，テストセットの量を増やした評であり，1 個は，“on” であった．キーワードに品詞を価実験や，ユーザビリティの観点からの評価が挙げら利用することにより，それが具体的にはどのような単れる．

語として現れるかを調べることができる．

謝辞

本 研 究 の 一 部 は ，名 古 屋 大 学 学 術 振 興 基

4. む す び

金，並びに科学研究費基盤研究（A）（2）（ 課題番号：

本論文では，キーワード系列から依存構造パターン1620001），若手研究（B）（課題番号：17700145）の助2769

電子情報通信学会論文誌 2006/12 Vol. J89–D No. 12

成を受けています．

[4]

文
[1]

Pennsylvania, 1999.
[2]

no.2, pp.310–330, 1993.
[5]

pora: The Gsearch corpus query system,” Computers
and the Humanities, vol.35, no.2, pp.81–94, 2001.

兵藤安昭，河田実成，応江 黔，池田尚志，“構文付きコーパスの作成と類似用例検索システムへの応用，” 自然言語処理，vol.3, no.2, pp.73–88, 1996.

2770

難波英嗣，森下智史，相沢輝昭，“論文データベースからのイディオム用例検索，” 情処学研報，NL-170, pp.53–59,2005.

S. Corley, M. Corley, F. Keller, M. Crocker, and S.
Trewin, “Finding syntactic structure in unparsed cor-[3]Penn Treebank,” Computational Linguistics, vol.19,

M. Collins, Head-driven statistical models for natural language parsing, PhD Dissertation, University ofM.P. Marcus, B. Santorini, and M.A. Marcinkiewicz,“Building a large annotated corpus of English: The献[6]P. Resnik and A. Elkiss, “The linguist’s search engine: An overview,” Proc. ACL Interactive Poseterand Demonstration Sessions, pp.33–36, 2005.

（平成 18 年 5 月 13 日受付，7 月 31 日再受付）