大規模コーパス作成支援システム Bonsai
吉田 恭祐 † 橋本 泰一 † 徳永 健伸 † 田中 穂積 ††東京工業大学大学院 情報理工学研究科 計算工学専攻{rincho, taiichi, take, tanaka}@cl.cs.titech.ac.jp

1 背景と目的S #1(0-1,4-3)

近年，自然言語処理の分野では，大規模な言語資源に基づく統計的手法が研究の中心となっている．そのNP-SBJ #2

ため，大規模な言語資源の作成が必要となるが，それ(0-2,1-1)

を全て人手により行うのは，困難である．この問題を解決するために，言語資源作成支援システムに関する

VP #4(1-2,4-2)

I #3
have #5
NP #6( 0 - 3 , 1 - 0 )( 1 - 3 , 2 - 0 ) ( 2 - 1 , 4 - 1 )研究が盛んに行われている [6, 1, 5]．
過去の事例を参考にしながら言語資源を作成することができれば，言語資源を一貫性を保ちながら作成

wsj.xmlapen #8#7(2-2,3-0) (3-1,4-0)

出現位置( l_pos_1 - l_pos_2 , r_pos_1 - r_pos_2)

することが可能になる．我々は，言語資源作成支援シ
図 1: 構文木の例

ステムとして，コーパスに構文構造を付与するためのツール Bonsai を構築している．このツールは，コーパス作成中に文法の一貫性を確認するための検索機能

行なう1 ．sentenceID,nameID,pathID は正数で与え，を提供しており，ユーザは検索したい構文構造をクエ

それらに対応する文字列はそれぞれ SentenceTable,リとして与えることで，その構造を含む文を構文構造

NameTable, PathTable に格納する．

付きコーパスから検索できる．
本論文では，この検索機能の仕組みについて述べる．まず，2 節で構文構造付きコーパスを関係データベースに変換する方法について述べ，3 節で構築したデータベースの検索手法について述べる．検索にはSQL を用いるが，検索条件の絞り込みの工夫，最適な SQL 文の作成により，検索時間を高速化する手法を提案する．

2 コーパスのデータベース化
我々は木構造をデータベース化する方法として，XMLに着目した．吉川らは XML 文書をオブジェクト関係データベースを用いて効率良く格納，検索する手法を提案している [3, 4]．この手法では「出現位置」というデータを用いて，ノードが木の構造のどの部分に位フィールド名sentenceID
nodeID
nameID
pathID
parentID
nextSibID
l pos 1,l pos 2
r pos 1,r pos 2

格納する値
その構文木の名前の id (wsj.xml に対する id)
ノード毎にユニークな数値．先行順で与える． (]5)
そのノードのタグ名の id (”have”に対する id)
ルートからのパスの id (”S/VP/have”に対する id)
そのノードの親の nodeID (]4)
そのノードの弟の nodeID (]6)
出現位置．4 つの正数で与える．
(順に 1,3,1,0)

表 1: 基本テーブルの概要「出現位置」は図 1 のように 4 つの正数で与える．
このような与え方により図 2 のようなノード間の位置関係が表現できる．包含関係は，X の子孫ノードが Xノードをルートとする木の中のノードであることを特定する．親戚関係は，i ノードと j ノードの左右に関する位置を特定する．

置するかをうまく表現している．我々は吉川らの手法

3 検索手法を参考に，コーパスのデータベース化を以下のように

3.1 検索の概要実現した．
本論文では，Penn Treebank コーパス [2]48,884 文をデータベース化した．各文は，図 1 のような構文木で表現される．データベース化は，各ノード毎に表1 のような情報を基本テーブルに格納することによりクエリは図 3 左のような木構造で与える．∗ はワイルドカードで，任意の label を許す．図 3 のクエリの場合，図 1 のようにクエリを部分木としてもつ構文木が検索結果となる (この場合，]4, ]5, ]6 の部分とマッ
1 各フィールドの説明の後に，図 1 のノード”have”に対する具体例を ( ) 内に示す．

＊ : ワイルドカード
Xi , j の先祖(l1 : l2 - r1 : r2)
＊＊

＊

＊

＊

＊

selectVP

frompenn_tbl n1, penn_tbl n2,penn_tbl n3

NP＊n0.sentence_id

wheren2.parentID = n1.ID
and n2.nextSibID = n3.ID

Xの子孫(L1 : L2 - R1 : R2)

包含関係
l1 <= L1
r1 >= R1i(l1 : l2 - r1 : r2)

and n1.nameID = 11j(L1 : L2 - R1 : R2)and n3.nameID = 3

図 3: クエリと SQL 文の例

親戚関係r1 <= L1

図 2: 包含関係と親戚関係
チする)．ただし，図 4 に示す Exact Match と Partial
Match のどちらを指定するかによって，検索結果は異なる．Exact Match はクエリの子供の数と該当する部分の子供の数が必ず等しくなければならないが，Partial Match は，部分的にクエリと構造が等しければ，答えとして出力する．本システムでは，ユーザの検索要求に合わせて，どちらか選択できるようになっている．
図 3 左のクエリは同図右の SQL 文で検索する．このように，SQL 文では，クエリのノード数に応じてfrom 節でそれぞれ宣言し，where 節で各ノードに対する条件を書く．従って，クエリのノード数が多くなれば，それに応じて SQL 文も長くなる．3.2 節で行った実験により，ノード数が 18 以上では，検索時間が大幅に遅くなることが分かった．したがって，クエリをそのまま SQL1 文で検索するという手法では，ノード数の大きいクエリに対応できない．この問題を解決するため，クエリを適当な部分木に分割して，それぞれを別の SQL 文で検索するという手法を提案する．

3.2 検索単位
どのくらいの大きさの部分木が SQL1 文に適しているのか調べるため，クエリのノード数に対する検索時間の比較実験を行った．実験に用いたクエリは，PennTreebank コーパス中の 4 文から抜き出した全ての部分木である．検索手法としては，図 4 の 2 つが考えられるが，実験では，どちらの検索手法でも安定する部分木を見つけるため，条件が緩く検索時間がより大きい Partial Match を用いた．その実験結果を表 2 に示す．
平均検索時間からすると，ノード数が 17 から 18 で検索時間が大幅に増えているのが分かる．これより，部分木のノード数は 17 以下にするべきだと考えられる．また，ノード数が 12 以内の場合は，最大検索時

VPVPVPVPNPVP

Exact Match ○Partial Match ○isNP

VPNPandExact Match ×
Partial Match ○図 4: 図 3 をクエリとした場合の例
間からも分かるように，部分木に分割せず，SQL1 文で検索したほうが早いことが分かった．
次に，同じ実験結果を深さ別に分類したものを表 3に示す．深さ 7 で検索時間が大きくなっているのは，ノード数の多さが原因だと思われる．また，深さ 1 の検索時間も大きくなっているが，これは深さ 1 では条件が少なすぎて，出力数が多くなっていることが原因だと考えられる．絞り込みをうまく行うには，個々の部分木の出力数はなるべく少ないほうが望ましいので，深さ 1 は適してないと言える．以上のことをふまえて，以下のような検索戦略を用いる．

1: ノード数が 12 以内のクエリは分割しない
2: 基本的に，深さ 2 で分割
3: ノード数が 18 以上の場合は，更に 2 分割
この戦略に基づき，クエリから逐次的に部分木へ分割を行う．ここで，分割される各部分木のことを検索単位と呼ぶことにする．深さを 2 としたのは，深さ 3 ではこの逐次処理において頻繁にノード数が 18 を越えてしまい，再分割のコストがかかってしまうからである．また，18 という閾値は最小検索時間から決定した．表 2 の最大検索時間を考慮すると，各検索単位のノード数を常に 12 以内としたほうが良いように思われる．しかし，これらの最大検索時間は SQL 文の書き方を工夫することで改善することが可能である．この SQL 文の最適化については，5 節で詳しく述べる．

3.3 検索単位の順序検索をするにあたり，どの検索単位を最初に検索するかは検索効率に大きく影響する．最初の検索単位とマッチする数が少なければ，候補の数を早く絞り込むノード数

平均検索時間 (sec)

最大検索時間最小
検索時間

平均出力数(部分木)

実験した
クエリ数

23456789101112131415161718192021〜

2.04
1.59
0.84
0.38
0.19
0.12
0.09
0.07
0.06
0.05
0.07
0.11
0.18
0.28
0.56
1.94
7.51
31.13
161.021108.17

10.63
11.33
11.51
10.05
6.42
1.64
1.64
1.35
1.31
1.31
1.32
3.84
9.36
45.45
2.25
6.12
18.09
47.52
185.453394.60

0.001
0.001
0.002
0.002
0.002
0.003
0.003
0.004
0.008
0.009
0.010
0.012
0.018
0.041
0.065
0.270
1.093
8.021
135.250298.3324330.30
9854.962189.00
337.26
65.11
17.00
7.16
3.32
1.91
1.36
1.13
1.04
1.011.00
1.00
1.00
1.00
1.00
1.00
1.00

65
99
168
281
437
611
762
860
902
901
869
801
678
498
300
140
47
10
323

nameIDnamechildrenparentfrequency

Indianmovie

121112501
1820

106901
94319
179161
3674

star

2971

58

S
NP-SBJ
VPS
NP-SBJNP

frequency

NP-SBJ:VP

41604

Indian:NP
movie:star1325(2) Children Table(1) Name Table

図 5: 頻度決定に用いるテーブル
S 41604
NP-SBJ
Indian

NP

36
movie
74

VP

13179161

25
star
58

表 2: ノード数別平均検索時間
深さ

平均検索時間 (sec)

最大検索時間最小
検索時間

平均出力数(部分木)

実験した
クエリ数

1234567

2.08
0.34
0.14
0.16
0.13
0.16
2.60

10.63
11.33
45.45
1.64
1.35
18.09
3394.60

0.001
0.001
0.002
0.007
0.007
0.007
0.020

19092.0
609.0
24.6
38.6
8.3
2.0
1.0

134
694
2544
458
760
1680
2185

表 3: 深さ別平均検索時間ことができ，検索時間は短くなる．つまり，最初に検索する検索単位の候補数が最も少なくなるように，クエリを分割することが重要となる．これを実現するた
め，次のように最初に検索する検索単位を決定する．
図 6 をクエリとした場合を例として説明する．2

図 6: 最初の検索単位の決定方法
分木がその対象となる．次に，3.2 節で述べたように，検索単位は深さ 2 を基本とするので，この部分木を深さ 1 だけ拡張する．最小頻度ノードの親ノードの頻度が，最小頻度ノードの全ての子ノードの頻度よりも小さい場合は上へ，その他の場合は下へと拡張する．図6 の例では，下へと拡張されており，深さ 2 の最初の検索単位が決定されている2 ．
最初に検索する検索単位決定後，3.2 節で述べた定義に基づき，クエリの残りの部分を逐次的に，検索単位に分割する．

節で述べたように，nameID の指し示す label(”NP”

最初の検索単位の次に検索する検索単位は，隣接すや”VP”など) は，図 5(1) のような NameTable に格る検索単位の中から選ぶ．その際，なるべく候補を絞納される．NameTable には，label ごとの頻度が fre-れる検索単位を選ぶのが望ましい．そこで，隣接するquency フィールドに格納してある．また，図 5(2) のような ChildrenTable には，子ノードの label のリス
トを値に持つ children フィールドがあり，それぞれの頻度が frequency フィールドに格納してある．図 5(2)の最上部の行の場合，親ノードの label が S で，1 番目の子ノードの label が NP-SBJ, 2 番目が VP であるノードの頻度が 41,604 であることを示す．この 2つのテーブルより，クエリの全てのノードに頻度を与える．
このように，全てのノードに頻度を与えた後，その中で最小の頻度を持つノードとその子ノードより構成される部分木が最初の検索単位に含まれるようにする．図 6 の例では，NP-SBJ が頻度最小のノードであるので，その子ノード Indian, NP より構成される部

検索単位の中で最小の頻度ノードを含む検索単位を次に検索する．それ以降も同様の基準で検索順を決める．

4 実験
検索時間についての実験を行った．実験に用いたクエリは，Penn Treebank コーパス中の 1,924 文から抜き出した全ての部分木 22,402 個からランダムに 463 個選んだものである．検索手法としては，Exact Matchを用いた．また，検索するデータベースには，PennTreebank コーパス 48,884 文が格納されてある．
まず始めに，クエリを常に SQL1 文で検索するものとの比較を行った．ここで，提案手法ではノード数が12 以下のものはクエリの分割を行わず同じ検索手法
2 便宜上，ノード数の少ないクエリで説明したが，このクエリはノード総数が 12 以下なので，厳密には検索単位には分割しない．

となるので，実験対象とはしない．表 4 にその結果をを SQL 文の順序に用いることで，検索時間を更に短示す．提案手法では，ノード数が増えても平均検索時縮できる可能性がある．また，検索時間の遅くなるよ

間の差は見られないが，SQL1 文で検索する手法では，うな順序を求めることにより，安定したシステムの構ノード数が 17 以上で特に検索時間が大きくなってい築が可能であろう．今回の実験では，どのような書きるのが分かる．

順で SQL 文を書けばよいか，はっきりとは分からな

次に，最初に検索する検索単位が検索時間をどれだけ短縮させているかを調べるため，提案手法と同様に検索単位を分割した後，トップダウンに検索単位を検かったが，これについては，十分改良の余地がある．

6 まとめと今後の課題索するものとの比較を行った．この実験でも，ノード

本論文では，吉川の手法を基に関係データベースに数が 12 以下のクエリは実験対象としていない．表 4

格納した構文構造付きコーパスから構文木を検索するにその結果を示す．

手法の改善方法を提案した．Penn Treebank における全体的に見て，トップダウン手法の約 6 分 1 の時間で検索していることが分かる．この結果より，最初の検索単位での検索候補の絞り込みがうまくいっていると言える．
ノード数

クエリ数

提案手法

13141516171819202122232425504949363136322919222539
46

0.039
0.045
0.047
0.024
0.280
0.033
0.042
0.043
0.036
0.092
0.041
0.048
0.046

SQL1 文
0.151
0.174
0.386
1.972
12.6719.797
41.44875.802298.331787.267
723.551
1369.466
3394.602

トップダウン

0.383
0.318
0.226
0.555
0.991
0.360
0.522
0.048
0.039
0.667
0.173
0.942
0.094

表 4: 検索時間の比較

5 SQL 文の最適化
3.2 節で述べたように，SQL 文の書き方を工夫することで，検索時間を短縮できる．表 2 でノード数が 13以上のクエリでは，検索時間の最大，最小の差が大きくなっている．これらのクエリを調べてみたところ，クエリの出力数，深さには特に原因は見られなかった．
そこで，最大検索時間となったいくつかのクエリについて，本検索システムが作成した SQL 文の where 節の順序を人手でいくつか入れ替えてみたところ，全てのクエリにおいて，検索時間を短縮するような順序を発見できた．つまり，SQL 文の順序によって，検索時間が大きく変わってしまう．
本検索システムでは，SQL 文の作成過程において，各検索単位の素性を用いてはいない．しかし，今回の調査より，検索単位の素性によって，検索時間が早くなるような SQL 文の順序があることが分かった．
ノード数，深さ，3.3 節で求めた頻度情報などの素性

SQL1 文に適した部分木 (検索単位) を実験的に求めた．更に，候補数の少ないものから検索できるようにクエリを分割する手法を提案した．この手法により，実験ではほぼ全てのクエリに対して 0.1 秒以内で検索結果を出力することができた．
今後の課題として，以下のようなものが挙げられる．
• label を指定しないクエリによる提案手法の評価
実験• クエリと類似した部分木を持つ文を検索する手法の提案• Bonsai システムのユーザインタフェースの改善• コーパスの修正・作成機能，コーパスの一貫性を自動的に管理する機能などの機能拡張

参考文献[1] H. Cunningham, V. Tablan, K. Bontcheva, andM. Dimitrov. Language engineering tools for collaborative corpus annotation. In Proceedings of Corpus
Linguistics 2003, 2003.
[2] Mitchell P. Marcus, Beatrice Santorini, andMary Ann Marcinkiewicz. Building a large annotatedcorpus of english: The penn treebank. ComputationalLinguistics, Vol. 19, No. 2, 1993.
[3] 吉川正俊, 志村壮是, 植村俊亮. オブジェクト関係デー
タベースを用いた XML 文書の格納と検索. 情報処理学会論文誌, Vol. 40, No. 0, 1999.
[4] Masatoshi Yoshikawa, Toshiyuki Amagasa, Takeyuki
Shimura, and Shunsuke Uemura. Xrel: A path-basedapproach to storage and retrieval of xml documents
using relational database. ACM Transactions on Internet Technology, Vol. 1, No. 1, 2001.
[5] Oliver Plaehn and Thorsten Brants. Annotate – anefficient interactive annotation tool. In Proceedingsof the Sixth Conference on Applied Natural Language
Processing ANLP-2000, Seattle, WA, 2000.
[6] 工藤拓, 松本裕治. RDB を利用したタグ付きコーパス検索支援環境の構築. 情報処理学会研究報告 NL-144, pp.
135–142, 7 2001.