\section{はじめに}
\label{intro}近年，自然言語処理の分野では，大規模な言語資源を利用した統計的手法が研究の中心となっている．特に，構文木付きコーパスは，統計的手法に基づく言語処理の高性能化のためだけでなく，言語学や言語処理研究の基本データとしても貴重な資源である．そのため，大規模な構文木付きコーパスの作成が必要となっている．しかし，大規模な構文木付きコーパスを全て人手により作成することは，多大なコストを必要とするため困難である．一方，現在の構文解析の精度では，構文木の付与を完全に自動化することが難しい．現実的には，構文解析器の出力から人手によって正しい構文木を選択し，それを文に付与することが望ましい．コーパス作成中には，文法や品詞体系の変更など，コーパス作成方針の変更により，コーパスへの修正が必要になることもあり，継続的な修正作業や不整合の除去などの機能を持った構文木付きコーパスの作成を支援するシステムが必要になる\cite{cunningham:2003:a}\cite{plaehn:2000:a}．このようなシステムの多くは，GUIツールを用いて，構文木付けをするコーパスのファイル形式や品詞ラベルの不整合を防ぐことにより，コーパス作成者を支援するのが主な機能である．しかし，それだけでは，正しい構文木付きコーパスの作成には，不十分であり，構文木の一貫性を保つための支援が必要となる．構文木の一貫性を保つための支援として，過去の事例を参照することは有効である．複数の構文木候補のうち，正しい木の選択を迷った場合に，すでに構文木を付与されたコーパス中から，作業中の構文木と類似した部分を持つ構文木を参照できれば，正しい構文木付けが容易になり，一貫性を保つための支援ができる．このためには，構文木付きコーパスを検索対象とし，木構造の検索が可能な構文木付きコーパス検索システムが必要となる．構文木付きコーパス検索システムは，木構造検索を行うことになるため，UNIXの文字列検索コマンド$grep$などの文字列検索よりも検索に時間を要することが多い．既存の構文木付きコーパス検索システム\cite{randall:2000:a,rohde:2001:a,konig:2003:a,bird:2004:a}においても，主な課題として，検索時間の高速化が挙げられているが，検索時間を高速化する優れた手法はまだ提案されていない．今後，コーパスの規模が更に大きくなると，検索時間の高速化は不可欠な技術となる．本論文では，高速な構文木付きコーパス検索手法を提案する．本論文で提案する検索手法は，構文木付きコーパスを関係データベースに格納し，検索にはSQLを用いる．部分木を検索のクエリとして与え，クエリと同じ構造を含む構文木を検索結果として出力する．クエリの節点数が多い場合，クエリを分割し，それぞれのクエリを別のSQL文で漸進的に検索する．クエリを分割すべきかどうか，分割するクエリの大きさや検索順序は，構文木付きコーパス中の規則の出現頻度を用いて自動的に決定する．6言語，7種類のコーパスを用いて評価実験を行い，4種類のコーパスにおいて，漸進的に検索を行う本手法により検索時間が短縮され，本手法の有効性を確認した．また，残りの3種類のコーパスにおいては，漸進的に検索を行わなくても多大な検索時間を要しないことを本手法で判定することができた．そして，クエリの分割が検索時間の短縮に効果があった4種類のコーパスと分割の効果がなかった3種類のコーパスの違いについて，コーパスに含まれる文数，ラベルの頻度，節点の平均分岐数の観点から考察を行い，節点の平均分岐数がその一因であることを確認した．
\section{構文木付きコーパスのデータベース化}
\label{database}構文木をデータベース化する手法として，XML文書を関係データベースを用いてデータベース化する吉川らの手法を適用した\cite{yoshikawa:1999:a}．吉川らの手法は，クエリとしてXPathを用い，XML文書を関係データベースに格納する．XPathとは，W3Cにより勧告されたXML文書中の特定の構文を表現する記述方法である．XML文書を検索する場合，クエリであるXPathをSQL文に変換し，クエリを含むXML文書を検索する．吉川らの手法の大きな特徴は，検索が高速である点である．その理由は，XML文書の木構造の各節点を出現位置という2つの数字で表現し，その大小関係により，節点の親子関係や兄弟関係を表現する点にある．本手法では，構文木の構造をXML文書の構文構造に対応させ，データベース化を行った．\subsection{出現位置}構文木をデータベースに格納するにあたり，構文木中の各節点対して，出現位置と呼ばれる節点間の関係を計算するための2つの数字を与える．出現位置は，({\itleft\_position}，{\itright\_position})の対で表現され，次のアルゴリズムにより決定する．\begin{itemize}\item葉\\左端からN番目の葉に対する出現位置は，(N,N)という整数値の対を与える．\item葉以外の節点\\変数{\itposition}を1以下の微小値$\alpha$で初期化する．根から深さ優先探索で辿り，節点を辿るときに$\alpha$を{\itposition}に加算し，葉を辿るきに葉の{\itleft\_position}または{\itright\_position}の値を代入する．節点を最初に通過するとき変数{\itposition}の値を{\itleft\_position}として，最後に通過するときに{\itright\_position}として決定する．ただし，$\alpha$は，木の最大の深さの逆数よりも小さい値でなければならない．\end{itemize}このアルゴリズムで決定した出現位置の例を\figurename\ref{fig:tree-yoshikawa}に示す．また，このように各節点に出現位置を与えることで，\figurename\ref{fig:yoshikawa-hougan}のように節点間の関係を出現位置の大小関係で表現することができる．\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f1.eps}\caption{出現位置の例}\label{fig:tree-yoshikawa}\end{center}\end{figure}\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f2.eps}\caption{包含関係と先行関係}\label{fig:yoshikawa-hougan}\end{center}\end{figure}\subsection{関係データベースへの格納}前節で計算した出現位置とともに各節点の情報を関係データベースに格納する．データベースは，{\itNodeTable}，{\itDocumentTable}，{\itLabelTable}の3つのテーブルにより構成される．テーブルの例をそれぞれ表\ref{tbl:node}，\ref{tbl:doc}，\ref{tbl:label}に示す．{\itNodeTable}は，構文木を構成する各節点に関する情報を格納する．各項目は，{\itID}が節点固有の値，{\itparentID}が節点の親の{\itID}，{\itdocID}が節点を含む構文木の{\itID}，{\itlabelID}が節点のラベルの{\itID}，{\itnextSibID}が節点の右隣の兄弟の{\itID}，{\itl\_pos,r\_pos}が節点の出現位置を表す．{\itDocumentTable}は，構文木が記述されているファイルに関する情報を格納する．各項目は，{\itdocID}が構文木固有の値，{\itfile}が構文木が記述されているファイル名を表す．{\itLabelTable}は，コーパスに含まれる記号，単語に関する情報を格納する．各項目は，{\itlabelID}がラベル固有の値，{\itlabel}がラベル名，{\itfrequency}がコーパスにおけるラベルの頻度を表す．\begin{table}[t]\caption{NodeTable}\input{table1.txt}\end{table}\begin{table}[t]\input{table2-3.txt}\end{table}
\section{構文木付きコーパスの検索手法}
\label{retieve}\subsection{クエリの定義}\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f3.eps}\caption{完全一致，部分一致の例}\label{fig:query}\end{center}\end{figure}前節では，構文木付きコーパスを関係データベースに格納する方法について述べた．本手法では，木構造をクエリとし，クエリを部分木として含む文を検索する．まず，クエリの例を\figurename\ref{fig:query}に示す．図中の``$\ast$''は，任意のラベルを意味する．さらに，クエリを部分木として含むかどうかの判定方法として，完全一致と部分一致の二種類を用意した．完全一致は，クエリの各節点の分岐数とコーパス内の対応する節点の分岐数が一致しなければならない．一方，部分一致は，この分岐数が必ずしも一致する必要がない．例えば，\figurename\ref{fig:query}において，完全一致で検索した場合，(a)の木は，各節点の分岐数，ラベルが一致するためにクエリと一致すると見なす．一方，(b)の木は，分岐数が異なるため，クエリと一致すると見なさない．しかし，部分一致で検索した場合，節点の分岐数は一致する必要がないため，両方の木がクエリと一致すると見なす．\subsection{構文木をクエリとした検索手法}本手法は，吉川らの手法と同様に検索を行うためにクエリである部分木を関係データベースのデータの操作，定義，検索などを行う言語SQLの文へ変換する．そして，変換したSQL文により該当した構文木をデータベース内から検索し，クエリを部分木として含む構文木を得る．クエリとそのクエリに対応するSQL文を\figurename\ref{fig:sql}に示す．\figurename\ref{fig:sql}中のSQL文のwhere構文以降が各節点の条件式となっている．システムは，条件を満たす節点をデータベース内を検索し，すべての条件を満たす節点をもつ構文木を出力する．\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f4.eps}\caption{クエリとそのSQL文の例}\label{fig:sql}\end{center}\vspace{-1.3\baselineskip}\end{figure}\subsection{予備実験}吉川らは，シュークスピアの戯曲をJonBosakがタグ付けしたXML文書\cite{bosak:1999:a}を用いた評価実験により，検索手法が高速であることを示した\cite{yoshikawa:1999:a}．そこで，吉川の手法を構文木付きコーパスに適用し，予備実験を行った．検索対象のコーパスとして，PennTreebankCorpus（48,884文）\cite{marcus:1994:a}を用いた．クエリは，PennTreebankCorpusからランダムに4文を抽出した．そして，4文から節点数が2から20の抽出可能なすべての部分木をクエリとして，部分一致により検索を行った．その結果を\tablename\ref{tbl:yobi}，\figurename\ref{fig:yobi}に示す．\begin{table}[t]\input{table4.txt}\end{table}\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f5.eps}\caption{予備実験結果}\label{fig:yobi}\end{center}\end{figure}実験結果より，クエリの節点数が7から12の間は，高速に検索を行っているが，節点数が7以下，12以上の場合，検索時間が非常に増加している．クエリの節点数が7以下の場合，クエリに一致する文が非常に多いために検索に時間を要とすると考えられる．一方，クエリの節点数が12以上の場合は，クエリと一致する文かどうかの判定，つまりSQL文の条件判定に検索時間を要していると考えられる．検索条件が多ければ，条件判定を行う処理が多くなり検索に時間を要する．吉川らが評価実験を行ったXML文書は，DTD(DocumentTypeDefinition)により，節点のラベルや構造があらかじめ定義されている．構文木付きコーパスにおいては，文脈自由文法がDTDに相当する．XML文書は，少ないDTDの規則で簡潔な構造を定義している場合が多く，文書間での大きな構造の違いは少ない．そのため，SQL文の条件は多くなりにくい．一方，構文木付きコーパスは，数千の規則を用いて文法を定義し，文によって様々な木構造が付与されている．そのため，XML文書よりもSQL文の条件が多くなる可能性が高く，検索時間が増加するケースが多くなることが予想できる．関係データベースの検索速度は，関係データベースシステムの種類，格納するデータ，検索に要するSQL文に依存する．関係データベースを構築する際，技術者が格納するデータをみて関係データベースシステムを選んだり，生成するSQL文の条件部分の優先度などの調整を経験的に行い，検索の効率化をはかることが多い．クエリの節点数が多くなると変換したSQL文の条件部分が多くなり，条件を満たすデータの検出時間がかかる．そのため，検索時間が大幅にかかるようになる．このような場合，人手により条件の記述順序の変更などにより，チューニングを行う．しかし，構文付きコーパスは，言語や対象文書の違いなど様々なコーパスが存在する．コーパスそれぞれを人手でチューニングすることは困難である．そのため，自動的に検索速度をチューニングする手法が必要である．\subsection{漸進的検索}\label{retrieve:separate}予備実験の結果から，クエリの節点数が7から12の間は，高速に検索が可能であることがわかった．例えば，節点数16のクエリの平均検索時間は，0.56秒である．それに対して，節点数8のクエリの平均時間は，0.09秒である．もし，節点数16のクエリを節点数8のクエリ2つに分割し検索できれば，検索を高速化することが可能である．本手法では，クエリをSQL一文で検索するのではなく，複数のSQL文に分割し，SQL一文に要する検索時間を短くすることで高速化を行う．また，単一のSQL文により効率よく絞り込みが行うことができるように，コーパス内のラベルの頻度をもとにクエリの分割方法を決定する．\subsubsection{検索単位}クエリの節点数が多い場合には，クエリを複数のクエリに分割し，漸進的に検索を行う手法を提案する．本論文では，分割されたクエリを検索単位，効率的に検索可能なクエリの節点数の最大値を最大検索単位節点数と定義する．コーパスが与えられたとき，コーパスから最大検索単位節点数を計算し，ノード数が多いクエリは最大検索単位節点数をもとに分割して，漸進的に検索を行う．まず，コーパスから，節点数2から31\footnote{節点数が31までなのは，実験で用いた関係データベースシステムのSQL文は，クエリとして最大31ノードまでしか制約をかけることができないためである}のクエリ（部分木）各50個をランダムに抽出する．そして，各節点数ごとに平均検索時間を算出する．そのデータから，以下の2つの条件を満たす最大値$i$を最大検索単位ノード数とする．\begin{itemize}\item節点数$i-n+1$から$i$の間のクエリの平均検索時間が$t$以下\item節点数$i+1$から$i+n$の間のクエリの平均検索時間が$t$以上\end{itemize}$n$と$t$は，最大検索単位節点数を決定する際のパラメータである．$n$は，正の整数，$t$は，秒数である．例えば，$n$を3，$t$を0.5（秒）をした場合，\figurename\ref{fig:decograph}の予備実験結果では，節点数13，14，15において平均検索時間が$t$を下回り，節点数16，17，18において平均検索時間が$t$を上回っている．このとき，最大検索単位節点数は，15となる．\begin{figure}[b]\begin{center}\includegraphics{14-4ia1f6.eps}\caption{最大検索単位節点数決定例}\label{fig:decograph}\end{center}\end{figure}\subsubsection{クエリの分割}前節で，コーパスに最適化された検索単位の節点数を決定する手法について述べた．しかし，クエリの分割方法，分割されたクエリの検索順序によって，検索時間は大きく変わる．もし，最初に検索する検索単位の出力数が少なければ，次に絞り込む検索範囲が狭まり，検索を効率よく行うことができる．つまり，絞り込みが早く行われるように分割や順序を決定することが望ましい．コーパス中の節点や文脈自由規則の頻度をもとにクエリの検索単位への分割，検索単位の検索順序を決定する．クエリの分割アルゴリズムを以下に示す．検索単位の検索順序は，分割された順である．\newlength{\StepW}\settowidth{\StepW}{Step9\quad}\hangafter=1\hangindent=\StepW\noindentStep1\quadクエリに含まれる節点のラベルのコーパス内での出現頻度を計算する．\hangafter=1\hangindent=\StepW\noindentStep2\quadクエリ内の最小頻度の節点を検索単位$U_0$とする．\hangafter=1\hangindent=\StepW\noindentStep3\quad$i=1$\hangafter=1\hangindent=\StepW\noindentStep3\quad検索単位$U_{i-1}$に含まれる節点に近接する最小頻度のラベルの節点で初期化する．\hangafter=1\hangindent=\StepW\noindentStep4\quad検索単位$U_{i}$に含まれる節点を持ち，検索単位$U_i$に加えても最大検索単位節点数を越えない部分木があれば，根の頻度が最小である部分木の節点を検索単位$U_i$へ追加する．\hangafter=1\hangindent=\StepW\noindentStep5\quadもし，Step4において，部分木を加えられたのであれば，Step4へ．そうでなければ，Step6へ．\hangafter=1\hangindent=\StepW\noindentStep6\quad$i=i+1$．クエリをすべて分割したならば，Step7へ．そうでなければ，Step3へ．\hangafter=1\hangindent=\StepW\noindentStep7\quad各検索単位をSQL文へ変換．クエリ分割方法を例を用いて説明する．クエリとして，\figurename\ref{fig:divide}の(1)が与えられ，最大検索単位節点数が5であると仮定する．まず，クエリに含まれる節点のラベルの出現頻度を計算する．その中で，最も出現頻度が低い``join''（出現頻度50）を検索単位$U_0$に加える．次に，節点(``join'')を含む部分木の中で，最も出現頻度が低い``VP''を根とする部分木（出現頻度179,161）の節点を加えることを考える．しかし，この部分木の節点を加えると最大検索単位節点数を越えるため$U_0$には加えない．（\figurename\ref{fig:divide}の(2)）次に，新たな検索単位$U_1$を$U_0$に含まれる節点と隣接する節点のうち最小頻度である節点(``VP'')初期化する．そして，``VP''を含む部分木を$U_1$に加えることを考える．``VP''を根とする部分木の節点を加えた場合，$U_1$の節点は，``VP'',``NP'',``PP-CLR'',``NP-TMP''の4つとなり，最大検索単位節点数を越えない．そのため，これらの節点を$U_1$に追加する．さらに，$U_1$に``VP''を根とする部分木の節点を加えることを試みるが最大検索単位節点数を越えるために加えられない．（\figurename\ref{fig:divide}の(3)）そして，新たな検索単位$U_2$を構築を始める．\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f7.eps}\caption{クエリ分割の例}\label{fig:divide}\end{center}\end{figure}最終的に，\figurename\ref{fig:divide}の(4)のように，クエリは3つの検索単位$U_0$，$U_1$,$U_2$に分割される．そして，それぞれの検索単位をSQL文へ変換し，検索を行う．そして，最初に決定した検索単位$U_0$により検索を行い，その結果に対して検索単位$U_1$により絞り込みを行う．絞り込みは，検索単位の初期化に利用した隣接する節点を次の検索単位のSQL文内の条件式として追加する．つまり，直前に利用したSQL文で次の検索単位に隣接する節点のIDを獲得し，その条件を次の検索単位のSQL文の条件として加える．例では，$U_1$に対応するSQL文の節点``n4''に関する条件式，$U_2$に対応するSQL文の節点``n3''に関する条件式が追加される条件式である．（\figurename\ref{fig:divide}の(5)）
\section{評価実験}
クエリ分割による検索の有効性を確認するために，7つの構文木付きコーパスを用いて，評価実験を行った．評価実験に使用したコーパスは，PennTreebankCorpus\cite{marcus:1994:a}，TIGERCorpus\cite{konig:2003:b}，PennKoreanTreebank\cite{han:2002:a}，FLORESTAsint\'{a}(c)tica\cite{afonso:2002:a}，PennChineseTreebank\cite{xue:2002:a}，東工大コーパス(RWC)\cite{noro:2004:a}，東工大コーパス(EDR)\cite{noro:2002:a}である．各コーパスの諸元を\tablename\ref{tbl:corpora}に示す．\begin{table}[t]\input{table5.txt}\end{table}\begin{figure}[b]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f8.eps}\caption{PennTreebankCorpus:完全一致}\label{fig:penn-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f9.eps}\caption{PennTreebankCorpus:部分一致}\label{fig:penn-p}\end{center}\end{minipage}\end{figure}\begin{figure}[t]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f10.eps}\caption{TIGERCorpus:完全一致}\label{fig:tiger-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f11.eps}\caption{TIGERCorpus:部分一致}\label{fig:tiger-p}\end{center}\end{minipage}\end{figure}\begin{figure}[t]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f12.eps}\caption{PennKoreanTreebank:完全一致}\label{fig:korean-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f13.eps}\caption{PennKoreanTreebank:部分一致}\label{fig:korean-p}\end{center}\end{minipage}\end{figure}\begin{figure}[t]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f14.eps}\caption{FLORESTAsint$\acute{a}$(c)tica:完全一致}\label{fig:floresta-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f15.eps}\caption{FLORESTAsint$\acute{a}$(c)tica:部分一致}\label{fig:floresta-p}\end{center}\end{minipage}\end{figure}\begin{figure}[t]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f16.eps}\caption{PennChineseTreebank:完全一致}\label{fig:chinese-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f17.eps}\caption{PennChineseTreebank:部分一致}\label{fig:chinese-p}\end{center}\end{minipage}\end{figure}\begin{figure}[t]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f18.eps}\caption{東工大コーパス(RWC):完全一致}\label{fig:tit-rwc-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f19.eps}\caption{東工大コーパス(RWC):部分一致}\label{fig:tit-rwc-p}\end{center}\end{minipage}\end{figure}\begin{figure}[t]\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f20.eps}\caption{東工大コーパス(EDR):完全一致}\label{fig:tit-edr-e}\end{center}\end{minipage}\hfill\begin{minipage}{0.47\hsize}\begin{center}\includegraphics{14-4ia1f21.eps}\caption{東工大コーパス(EDR):部分一致}\label{fig:tit-edr-p}\end{center}\end{minipage}\end{figure}評価実験では，最大検索単位節点数を決定するパラメータ$t$を0.5（秒），$n$を3とし，最大検索単位節点数を計算した．クエリは，コーパスからランダムに抽出した部分木を用い，節点数1から31までの各50個を用いた．検索方法としては，完全一致と部分一致の2種類を行った．各コーパスにおける評価実験結果を\figurename\ref{fig:penn-e}から\figurename\ref{fig:tit-edr-p}に示す．PennTreebankCorpus，TIGERCorpus，PennKoreanTreebankCorpus，FLORESTsint\'{a}(c)ticaの4つコーパスにおいては，完全一致による検索では節点数16以上，部分一致による検索では節点数11から13以上のクエリに対して，クエリの分割を行わずに検索を行った場合，急激に検索時間が増大することがわかる．一方，クエリを検索単位に分割することで高速に検索が行うことができた．また，対照的にPennChineseTreebankCorpus，東工大コーパス(RWC),東工大コーパス(EDR)では，完全一致と部分一致ともに許容検索時間を越えることがなく，最大検索単位節点数は最大の31と計算された．これら3つのコーパスにおいては，クエリの分割を行う必要がなかった．
\section{考察}
\label{discussion}評価実験で用いたコーパスは，大きく分けて2つに分類できる．1つは，分割せずに検索した場合，クエリを構成する節点数が増えると検索時間が非常に遅くなるものである．このタイプのコーパスは，PennTreebankCorpus，TIGERCorpus，PennKoreanTreebankCorpus，FLORESTsint\'{a}(c)ticaが当てはまる．もう1つは，クエリの節点数が増えても検索時間に影響を与えないものである．このタイプのコーパスとして，PennChineseTreebankCorpus，東工大コーパス(RWC),東工大コーパス(EDR)が当てはまる．このような違いが，コーパスのどの特徴と関連しているのか，コーパスの以下の特徴に着目し考察した．\begin{itemize}\itemコーパスの文数\itemラベルの頻度\item節点の平均分岐数\end{itemize}\subsection{コーパスの文数}コーパスの文数が検索時間に影響を与えることが考えられる．つまり，文数が多ければ検索に時間がかかり，少なければ時間がかからないはずである．しかし，\tablename\ref{tbl:corpora}からわかるようにPennKoreanTreebankCorpus（5,083文），FLORESTsint\'{a}(c)tica（8,307文）は，比較的コーパスに含まれる文数が少ないが，クエリの節点数が増加するとともに検索時間が大幅に増加している．また，PennChineseTreebank（15,168文）は文数が多いにも関わらず，節点数が増加しても検索時間は増加していない．さらにPennTreebankCorpusの文数を1,000文，5,000文，11,976文，48,884文と変化させ，検索時間の変化を調べた．クエリなどの実験環境は，評価実験で用いたものと同じである．その結果を\figurename\ref{fig:size}に示す．この結果からコーパスに含まれる文数が減少しても，節点数が増加するとともに検索時間が増大していることがわかった．つまり，コーパスの文数と検索時間増大の間には，関連性は低いものと考えられる．\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f22.eps}\caption{コーパスの文数と検索時間}\label{fig:size}\end{center}\end{figure}\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f23.eps}\caption{ラベルなしクエリによる実験結果}\label{fig:label}\end{center}\end{figure}\subsection{ラベルの頻度}クエリ内のラベルが検索時間に影響を与えることが考えられる．例えば，クエリに含まれるラベルが非常に稀にしか出現しないラベルであれば，非常に早く検索することができるはずである．しかし，\tablename\ref{tbl:corpora}からわかるように，PennTreebankCorpusはラベル（非終端記号）の異なり数が多いが検索時間が急激に増加している．一方，東工大コーパス(RWC)はラベルの異なりが少ないが，検索時間が増大していない．PennTreebankCorpus，東工大コーパス(RWC)を用いて，ラベルを``$\ast$''で置き換えたクエリを用いて，実験を行った．クエリは，評価実験を行ったときと同一である．その結果を\figurename\ref{fig:label}に示す．ラベルの情報がなくなったため，双方ともに評価実験よりも検索時間を要しているが，節点数と検索時間との関係に変化はなかった．ラベルの頻度と検索時間の増大は関連性が低いと考えられる．\begin{figure}[t]\begin{center}\includegraphics{14-4ia1f24.eps}\caption{節点の平均分岐数}\label{fig:branch}\end{center}\end{figure}\subsection{節点の平均分岐数}次に，コーパスの特徴として節点の平均分岐数に注目した．分岐数が多くなれば，構文木は複雑になり，検索に時間を要することが考えられる．そこで，全てのコーパスについて，それぞれの節点の平均分岐数を調べた．その結果を\figurename\ref{fig:branch}に示す．この結果から確かに検索時間が増大する傾向にあるコーパスは，平均子供数が比較的大きいことがわかる．しかし，PennKoreanTreebankとPennChineseTreebankの差はあまりなく，平均分岐数が決定的な原因であるとは考えがたい．だが，コーパス内の文の構造の複雑さが一因である可能性は確認できる．
\section{まとめ}
本論文では，構文木付きコーパスを高速に構造検索する手法を提案した．構文木付きコーパスのデータベース化は，木構造を持つXML文書を格納・検索する手法を用い，部分木で表現されたクエリをSQL文に変換して検索を行う．節点数の多いクエリに対する検索時間が増大するという問題を解決するために，クエリを分割し，漸進的に検索する手法を提案した．クエリの分割は，まずコーパスから最大検索単位節点数を計算し，最大検索単位節点数をもとに，効率的に検索できるようクエリを分割し，検索を行う．評価実験では，7つのコーパス中の4つに対して，クエリを分割せずに検索する手法よりも効率的に検索を行うことができることを示した．また，評価実験で用いたコーパスには，クエリの節点数が増加すると検索時間が非常に遅くなるものと，そうでないものの2種類が存在した．その違いの要因が，コーパスに含まれる構文構造の複雑さに起因するものであることについて考察した．今後の課題として，次のようなものがあげられる．\begin{itemize}\item節点が少ないクエリに対する検索の高速化\item検索時間とコーパスに含まれる構文構造の複雑さとの関連性の解明\itemコーパス作成支援システムへの応用\end{itemize}\bibliographystyle{jnlpbbl_1.3}\begin{thebibliography}{}\bibitem[\protect\BCAY{Afonso,Bick,Haber,\BBA\Santos}{Afonsoet~al.}{2002}]{afonso:2002:a}Afonso,S.,Bick,E.,Haber,R.,\BBA\Santos,D.\BBOP2002\BBCP.\newblock\BBOQ``Florestasint\'{a}(c)tica'':atreebankforPortuguese\BBCQ\\newblockIn{\BemProceedingsof{LREC}2002},\mbox{\BPGS\1698--1703}.\bibitem[\protect\BCAY{Bird,Chen,Davidson,Lee,\BBA\Zheng}{Birdet~al.}{2004}]{bird:2004:a}Bird,S.,Chen,Y.,Davidson,S.,Lee,H.,\BBA\Zheng,Y.\BBOP2004\BBCP.\newblock\BBOQExtending{XPath}toSupportLinguisticQueries\BBCQ\\newblockIn{\Bem{UWA}LanguageScienceGroup2004Program---SymposiumonSpeechandLanguageTechnology}.\bibitem[\protect\BCAY{Bosak}{Bosak}{1999}]{bosak:1999:a}Bosak,J.\BBOP1999\BBCP.\newblock{\BemThePlaysofShakespearein{XML}}.\bibitem[\protect\BCAY{Cunningham,Tablan,Bontcheva,\BBA\Dimitrov}{Cunninghamet~al.}{2003}]{cunningham:2003:a}Cunningham,H.,Tablan,V.,Bontcheva,K.,\BBA\Dimitrov,M.\BBOP2003\BBCP.\newblock\BBOQLanguageEngineeringToolsforCollaborativeCorpusAnnotation\BBCQ\\newblockIn{\BemProceedingsofCorpusLinguistics2003}.\bibitem[\protect\BCAY{hyeHan,Han,Ko,Yi,\BBA\Palmer}{hyeHanet~al.}{2002}]{han:2002:a}hyeHan,C.,Han,N.-R.,Ko,E.-S.,Yi,H.,\BBA\Palmer,M.\BBOP2002\BBCP.\newblock\BBOQPennKoreanTreebank:DevelopmentandEvaluation\BBCQ\\newblockIn{\BemProceedingsofthe{16th}PacificAsiaConferenceonLanguage,InformAtionandComputation}.\bibitem[\protect\BCAY{K{\"o}nig,Esther,Lezius,\BBA\Wolfgang}{K{\"o}niget~al.}{2003a}]{konig:2003:b}K{\"o}nig,Esther,Lezius,\BBA\Wolfgang\BBOP2003a\BBCP.\newblock\BBOQThe{TIGER}Language---ADescriptionLanguageforSyntaxGraphs,FormalDefinition\BBCQ\\newblock\BTR,Institutf{\"u}rMaschinelleSprachverarbeitung,UniversityofStuttgart.\bibitem[\protect\BCAY{K{\"o}nig,Esther,Lezius,Wolfgang,Voormann,\BBA\Holger}{K{\"o}niget~al.}{2003b}]{konig:2003:a}K{\"o}nig,Esther,Lezius,Wolfgang,Voormann,\BBA\Holger\BBOP2003b\BBCP.\newblock{\Bem{TIGERSearch}User'$s$Manual}.\bibitem[\protect\BCAY{Marcus,Kim,Marcinkiewicz,MacIntyre,Bies,Ferguson,Katz,\BBA\Schasberger}{Marcuset~al.}{1994}]{marcus:1994:a}Marcus,M.,Kim,G.,Marcinkiewicz,M.~A.,MacIntyre,R.,Bies,A.,Ferguson,M.,Katz,K.,\BBA\Schasberger,B.\BBOP1994\BBCP.\newblock\BBOQThePennTreebank:AnnotatingPredicateArgumentStructure\BBCQ\\newblockIn{\Bem{ARPA}'94}.\bibitem[\protect\BCAY{Noro,Hashimoto,Tokunaga,\BBA\Tanaka}{Noroet~al.}{2004}]{noro:2004:a}Noro,T.,Hashimoto,T.,Tokunaga,T.,\BBA\Tanaka,H.\BBOP2004\BBCP.\newblock\BBOQALarge-ScaleJapanese{CFG}DerivedfromaSyntacticalyAnnotatedCorpusandItsEvaluation\BBCQ\\newblockIn{\BemProceedingsofthe3rdWorkshoponTreebanksandLinguisticTheories},\mbox{\BPGS\115--126}.\bibitem[\protect\BCAY{Plaehn\BBA\Brants}{Plaehn\BBA\Brants}{2000}]{plaehn:2000:a}Plaehn,O.\BBACOMMA\\BBA\Brants,T.\BBOP2000\BBCP.\newblock\BBOQAnnotate---AnEfficientInteractiveAnnotationTool\BBCQ\\newblockIn{\BemProceedingsofthe6thConferenceonAppliedNaturalLanguageProcessing}.\bibitem[\protect\BCAY{Randall}{Randall}{2000}]{randall:2000:a}Randall,B.\BBOP2000\BBCP.\newblock{\Bem{CorpusSearch}User'sManual}.\bibitem[\protect\BCAY{Rohde}{Rohde}{2001}]{rohde:2001:a}Rohde,D.\BBOP2001\BBCP.\newblock{\Bem{Tgrep2}UserManual}.\bibitem[\protect\BCAY{Xue,Chiou,\BBA\Palmer}{Xueet~al.}{2002}]{xue:2002:a}Xue,N.,Chiou,F.-D.,\BBA\Palmer,M.\BBOP2002\BBCP.\newblock\BBOQBuildingaLarge-ScaleAnnotatedChineseCorpus\BBCQ\\newblockIn{\BemProceedingsof{COLING}2002}.\bibitem[\protect\BCAY{吉川正俊\JBA志村壮是\JBA植村俊亮}{吉川正俊\Jetal}{1999}]{yoshikawa:1999:a}吉川正俊\JBA志村壮是\JBA植村俊亮\BBOP1999\BBCP.\newblock\JBOQオブジェクト関係データベースを用いた{XML}文書の格納と検索\JBCQ\\newblock\Jem{情報処理学会論文誌},{\Bbf40}(SIG6(TOD3)),\mbox{\BPGS\115--131}.\bibitem[\protect\BCAY{野呂智哉\JBA白井清昭\JBA徳永健伸\JBA田中穂積}{野呂智哉\Jetal}{2002}]{noro:2002:a}野呂智哉\JBA白井清昭\JBA徳永健伸\JBA田中穂積\BBOP2002\BBCP.\newblock\JBOQ大規模日本語文法の開発—事例研究\JBCQ\\newblock\Jem{情報処理学会研究報告{NL}-150},\mbox{\BPGS\149--156}.\end{thebibliography}\begin{biography}\bioauthor{橋本泰一（正会員）{\unskip}}{1997年東京工業大学工学部情報工学科卒業．2002年同大学大学院情報理工学研究科博士課程修了．同年同大学大学院情報理工学研究科助手．現在，同大学統合研究院特任准教授．博士（工学）．自然言語処理，知識情報処理の研究に従事．言語処理学会，情報処理学会各会員．}\bioauthor{吉田恭介}{2003年東京工業大学工学部情報工学科卒業．2005年同大学大学院情報理工学研究科修士課程修了．}\bioauthor{野口正樹}{2004年東京工業大学工学部情報工学科卒業．2006年同大学大学院情報理工学研究科計算工学専攻修士課程修了．現在，同専攻博士課程に在学中．言語資源の検索・利用に関する研究を行っている．また，言語資源の構築や知的創造作業支援などにも興味を持っている．情報処理学会学生会員．}\bioauthor{徳永健伸（正会員）{\unskip}}{1961年生．1983年東京工業大学工学部情報工学科卒業．1985年同大学院理工学研究科修士課程修了．同年（株）三菱総合研究所入社．1986年東京工業大学大学院博士課程入学．現在，同大学大学院情報理工学研究科准教授．博士（工学）．自然言語処理，計算言語学，情報検索などの研究に従事．情報処理学会，人工知能学会，言語処理学会，計量国語学会，AssociationforComputationalLinguistics，ACMSIGIR各会員．}\bioauthor{田中穂積（正会員）{\unskip}}{1964年東京工業大学工学部情報工学科卒業．1966年同大学院理工学研究科修士課程修了．同年電気試験所（現産業技術総合研究所）入所．1980年東京工業大学助教授．1983年東京工業大学教授．現在，中京大学理工学部教授．工学博士．人工知能，自然言語処理に関する研究に従事．情報処理学会，電子情報通信学会，認知科学会，人工知能学会，言語処理学会，計量国語学会，AAAI，各会員．}\end{biography}\biodate\end{document}