\section{はじめに}
電子化テキストの爆発的増加に伴って文書要約技術の必要性が高まり，この分野の研究が盛んになっている\cite{okumura}．自動要約技術を使うことにより，読み手の負担を軽減し，短時間で必要な情報を獲得できる可能性があるからである．従来の要約技術は，文書全体もしくは段落のような複数の文の中から，重要度の高い文を抽出することにより文書全体の要約を行うものが多い．このような方法で出力される個々の文は，原文書中の文そのものであるため，文間の結束性に関してはともかく，各文の正しさが問題になることはない．しかし，選択された文の中には冗長語や不要語が含まれることもあり，またそうでなくとも目的によっては個々の文を簡約することが必要になる．そのため，特にニュース字幕作成を目的として，表層文字列の変換\cite{tao,kato}を行ない，1文の文字数を減らすなどの研究が行われている．また，重要度の低い文節や単語を削除することによって文を簡約する手法も研究されており，単語重要度と言語的な尤度の総和が最大となる部分単語列を動的計画法によって求める方法\cite{hori}が提案されている．しかし，この方法ではtrigramに基づいた局所的な言語制約しか用いていないので，得られた簡約文が構造的に不自然となる可能性がある．削除文節の選択に係り受け関係を考慮することで，原文の部分的な係り受け構造の保存を図る方法\cite{mikami}も研究されているが，この方法ではまず一文全体の係り受け解析を行い，次に得られた構文木の中の冗長と考えられる枝を刈り取るという，二段階の処理が必要である．そのため，一つの文の係り受け解析が終了しなければ枝刈りが開始できず，枝刈りの際に多くの情報を用いて複雑な処理を行うと，文の入力が終了してから簡約された文が出力されるまでの遅延時間が長くなる可能性がある．本論文では，文の簡約を「原文から,文節重要度と文節間係り受け整合度の総和が最大になる部分文節列を選択する」問題として定式化し，それを解くための効率の良いアルゴリズムを提案する．この問題は，原理的には枚挙法で解くことが可能であるが，計算量の点で実現が困難である．本論文ではこの問題を動的計画法によって効率よく解くことができることを示す\cite{oguro,oguro2}．文の簡約は，与えられた文から何らかの意味で``良い''部分単語列あるいは部分文節列を選択することに尽きる．そのとき，削除/選択の単位として何を選ぶか，選ばれる部分単語列あるいは部分文節列の``良さ''をどのように定義するか，そして実際の計算をどのように行うか，などの違いにより，種々の方式が考えられる．本論文では，削除/選択の単位として文節を採用している．この点は，三上らの方法と同じであるが，一文を文末まで構文解析した後で枝刈りを行うという考え方ではなく，部分文節列の``良さ''を定量的に計るための評価関数を予め定義しておき，その基準の下で最適な部分文節列を選択するという考え方を採る．その点では堀らの方法に近いが，削除/選択の単位がそれとは異なる．また評価関数の中に二文節間の係り受け整合度が含まれているので，実際の計算は係り受け解析に近いものになり，その点で堀らの方法とは非常に異なったものとなる．さらに，このアルゴリズムでは文頭から係り受け解析と部分文節列の選択が同時に進行するので，一つの文の入力が終了してから，その文の簡約文が出力されるまでの遅延時間を非常に短くできる可能性がある．オンラインの字幕生成のような応用では，この遅延時間はできるだけ短い方が良い．以下では，あらためて文簡約問題の定式化を行い，それを解くための再帰式とアルゴリズム，および計算量について述べる．そして，最後に文の簡約例を掲げ，このアルゴリズムによって自然な簡約文が得られることを示す．
\section{問題の定式化}
文節を削除/選択の単位として行う文の簡約は，原文からできるだけ``良い''部分文節列を選択することであると考えることができる．この問題を明確に定式化するためには，文節列の``良さ''を計る評価関数が必要である．このような評価関数は，理想的には，文脈を考慮した上で原文の意味を理解し，その意味を部分文節列がどの程度保つかという観点から定められるべきものであろう．しかし，そのような評価関数を構成することは現時点では困難である．そもそも，文の``意味''とは何かということさえ，現時点で明確に定義づけることは困難と思われる．そこで，本研究では，各文節の重要度と二文節間の係り受け整合度という限られた情報のみを用いて，現実的に定義や計算ができるようなアプローチを採る．すなわち，文の簡約においては，\begin{itemize}\item[a)]簡約された文が原文の持つ重要な情報をできるだけ保つこと，\item[b)]簡約された文ができるだけ文法的に良い構造を持つこと．\end{itemize}\noindentの２つが重要であることを考慮し，ここでは，部分文節列の``良さ"を計る評価関数を，a),b)に対応した２つの評価関数の和として以下のように定義する．まず，原文を文節列として$w_{0}w_{1}\cdotsw_{M-1}$と表し，その中の長さ$l\/$の部分文節列$w_{k_{0}}w_{k_{1}}\cdotsw_{k_{l-1}}$を考える．もし，各文節$w_{m}$の重要度を表す関数$q(m)$が与えられているとすると，この部分文節列の重要度はそれらの総和$\sum_{i=0}^{l-1}q(k_i)$で計ることができよう．もちろん，他の定義も可能であるが，ここでは，これを部分文節列の重要度を計る評価関数として採用する．また，文節$w_{m}$が文節$w_{n}$に係るときの係り受け整合度$p(m,n)$が与えられているとすると，このような係り受け整合度の総和が大きい値となる係り受け構造が存在するような文節列は，日本語文として見たとき，文法的に``良い''文節列であると考えられる．文節列$w_{k_{0}}w_{k_{1}}\cdotsw_{k_{l-1}}$上の係り受け構造は，係り文節番号を受け文節番号に対応させる写像\begin{displaymath}c:\{k_{0},k_{1},\cdots,k_{l-2}\}\longrightarrow\{k_{1},k_{2},\cdots,k_{l-1}\}\end{displaymath}によって表される．ただし$c$は\begin{itemize}\item[(1)]後方単一性:$k_{m}<c(k_{m})$\item[(2)]非交差性:$m<n$ならば$[c(k_m)\leqk_n\mbox{または}c(k_n)\leqc(k_m)]$\end{itemize}を満たす必要がある．本研究では，写像$c$を用いて，文節列$w_{k_{0}}w_{k_{1}}\cdotsw_{k_{l-1}}$の文法的な``良さ''を$\max_{c}\sum_{i=0}^{l-2}p(k_{i},c(k_{i}))$で定義することとする．ここで，最大化は可能な全ての係り受け構造に対して行う．以上のことから，本論文では文節列$w_{k_{0}}w_{k_{1}}\cdotsw_{k_{l-1}}$の``良さ''を計る評価関数$g$を次のように定義する:\begin{displaymath}g(k_{0},k_{1},...,k_{l-1})\stackrel{\triangle}{=}\left\{\begin{array}{l}q(k_0),\l=1のとき\\\max_c\sum_{i=0}^{l-2}p(k_i,c(k_i))+\sum_{i=0}^{l-1}q(k_i),2\leql\のとき\end{array}\right.\end{displaymath}\noindent評価関数$g$を用いると，$M$文節からなる原文を$N$文節からなる文に簡約する問題は次のように述べることができる．\bigskip\noindent{\bf文簡約問題\\}文節列$w_{0}w_{1}\cdotsw_{M-1}$の部分文節列$w_{k_{0}}w_{k_{1}}\cdotsw_{k_{N-1}}$$(0\leqk_{0}<k_{1}<\cdots<k_{N-1}\leqM-1)$の中で，関数$g(k_{0},k_{1},\cdots,k_{N-1})$が最大になるものを求めよ．\bigskip与えられた原文の部分文節列の総数は有限である．また，各部分文節列上の係り受け構造の総数も有限である．したがって，上の文簡約問題は，原理的には枚挙法で解くことができるが，計算量の点で現実的でない．本論文では，動的計画法の原理に基づき，この問題を効率的に解くアルゴリズムを導出する．評価関数$g$の定義には，文節重要度$q$と係り受け整合度$p$の２つの関数が含まれている．これらの関数をどのように定義するかは実際の応用においては重要な問題であるが，本論文ではこれについては議論しない．しかし，文節重要度$q$の定め方については，例えば\cite{hori}のような方法が考えられ，係り受け整合度$p$の定め方については係り受け解析の分野で研究されている\cite{ehara,zhang}などの方法が利用できると考えられる．{\bf3}節で導かれるアルゴリズムは，これらの関数の定義には依らない．二文節間の係り受け整合度の総和は，従来，係り受け解析にも用いられている評価関数であり，その意味で本手法による簡約文は，係り受け整合度$p$が適切に設定されていれば，原文の部分的な係り受け構造を保った自然な係り受け構造を持つことが期待できる．しかし，それにより原文の意味がどの程度保たれるかについては，最終的には人間の簡約結果と比較するなどの評価が必要となる．本論文では，そこまでは立ち入らず，上のような評価関数を用いて問題を定式化したとき，それを現実的な計算量で解くアルゴリズムが構成できることを示すことに重点を置いている．
\section{再帰式とアルゴリズム}
\subsection{再帰式}文簡約問題，すなわち関数$g(k_0,k_1,{\cdots},k_{N-1})$の最大化問題を解くために，その``部分解とそれらの間の関係''を考える．まず，先頭文節を$w_m$に，末尾文節を$w_n$に，文節列長を$l\/$に固定したときの最大化を考え，その最大値を表す関数$f$を以下のように定義する．\begin{definition}{最大値関数$f$}\hfill\[\textstylef(m,n,l)\stackrel{\triangle}{=}\max_{m=k_0<k_1<{\cdots}<k_{l-1}=n}g(k_0,k_1,{\cdots},k_{l-1})\]\end{definition}\noindentそうすると$f(m,n,l)$は次の再帰式を満たすことが示される．証明は付録とする．\begin{thesis}{再帰式}\label{def:recursion}\hfill\begin{itemize}\item[1.]$m=n$のとき:($l\$の動く範囲:$l=1$のみ)\begin{equation}f(m,n,l)=q(m)\label{eqn:eqn1}\end{equation}\item[2.]$m<n$のとき:($l\$の動く範囲:$2\leql\leqn-m+1$)\item[i.]$l=2$のとき\begin{equation}f(m,n,l)=f(m,m,1)+f(n,n,1)+p(m,n)\label{eqn:eqn2}\end{equation}\vspace*{1zh}\item[ii.]$l=3$のとき\begin{eqnarray*}\lefteqn{f(m,n,l)=\max\left\{\begin{array}{l}f(m,m,1)+\max_{m{\!<\!}m'{\!<\!}n}\{f(m',n,2)\}+p(m,n);\hspace*{3.5zw}\hfill(\arabic{equation}\rma)\\\max_{m{\!<\!}n'{\!<\!}n}\{f(m,n',2)+p(n',n)\}+f(n,n,1)\hfill(\arabic{equation}\rmb)\end{array}\right.}\label{eqn:eqn3}\end{eqnarray*}\addtocounter{equation}{1}\vspace*{1zh}\item[iii.]$l\geq4$のとき\begin{eqnarray*}\lefteqn{f(m,n,l)=}\\&&\max\left\{\begin{array}{l}f(m,m,1)+\max_{m{\!<\!}m'<n-l+3}\{f(m',n,l-1)\}+p(m,n);\hspace*{3.0zw}\hfill(\arabic{equation}\rma)\\\\\max_{1{\!<\!}l'{\!<\!}l-1,{\,}m+l'-2{<}n'{\!<\!}m'{<}n-l+l'+2}\\\{f(m,n',l')+f(m',n,l-l')+p(n',n)\};\hfill(\arabic{equation}\rmb)\\\\\max_{m+l-3{<}n'{\!<\!}n}\{f(m,n',l-1)+p(n',n)\}+f(n,n,1)\hfill(\arabic{equation}\rmc)\end{array}\right.\label{eqn:common}\end{eqnarray*}\addtocounter{equation}{1}\end{itemize}\end{thesis}\subsection{アルゴリズムの構成}再帰式は$2{\;\leq\;}l\/$のとき，$l'{<\,}l\/$となる$f(m,\cdot,l')$と$f(\cdot,n,l-l')$の全てが既に計算されていれば，高々3つの変数に関する最大化問題を解くことにより$f(m,n,l)$が計算できることを表している．すなわち式(\ref{eqn:eqn1})より，$f(\cdot,\cdot,1)$は，入力文節の重要度から直接計算できる．また，式(\ref{eqn:eqn2})より2文節の重要度とその間の係り受け整合度の和から，$f(\cdot,\cdot,2)$が計算できる．これらから始めて，$l=3$のときは$f(\cdot,\cdot,3)$を2変数$m',n'$が制約条件を満たす範囲で最大化を行ない，$4\leql\$では3変数$m',n',l'\/$が制約条件を満たす範囲で最大化を行なうという再帰的な処理によって，$f(m,n,l)$を計算することができる．\begin{figure}[hbtp]\begin{center}\includegraphics[width=70mm,clip]{table2.ps}\caption{$f(m,n,l)$を計算するとき参照される領域}\label{fig:region}\end{center}\end{figure}以上の事実に注意すると，計算済の$f(\cdot,\cdot,\cdot)$の値を図\ref{fig:region}のようなテーブルの升目に順次埋めていくアルゴリズムが構成できる．図\ref{fig:region}には$f(m,n,l)$を埋める場合を示した．再帰式によると，$f(m,n,l)$の計算は，その左の領域$f(m,\ast,1)\simf(m,\ast,l-1)$から$f(m,n',l')$を，その下の領域$f(\ast,n,1)\simf(\ast,n,l-1)$から$f(m',n,l-l')$を選択する組合わせの中から，それぞれの持つ$f$の値と両者の係り受け構造間の係り受け整合度の総和が最大となるような$m',n',l'\/$を探索することで行なわれていく．このとき，係り文節$w_m$は必ず受け文節$w_n$より文頭側にあること，文節列$w_mw_{m+1}{\cdots}w_n$を簡約する場合，簡約後の部分文節列の長さは原文節の長さより大きくなることがないことから，変数には以下のような制約が課せられる．\begin{itemize}\item$m{\;\leq\;}n$\item$m=n$のとき$l=1$\item$m<n$のとき$1<l{\;\leq\;}n-m+1$\end{itemize}これを図示したものが図\ref{fig:region2}である．また，ここでは$1\leqN\leqM$を満たす任意の$N$に対して最適解が探索できる領域を考えているが，$N$の最大値$N_{max}$があらかじめ定まっているときは，$l\/$の動く範囲を$1\leql\leq\min\{n-m+1,{\,}N_{max}\}$に制限できる．したがって$N_{max}<M$の場合には探索領域はさらに小さくてすみ，計算量と記憶量を減らすことができる．\begin{figure}[hbtp]\vspace{-3mm}\begin{center}\includegraphics[width=70mm,clip]{table3.ps}\caption{制約条件を満たさない領域}\label{fig:region2}\end{center}\end{figure}図\ref{fig:region}のテーブルの升目を埋める順序については，$f(m,n,l)$を計算する際に$f(m,n',l')$と$f(m',n,l-l')$が制約条件の範囲で全て計算済であるという条件さえ満たしていればよいので，その順序には大きな自由度がある．変数$l,m,n$を動かすとき，アルゴリズム\ref{alg:recursion}のように最外ループを$n$に関するループとすると，入力文節に同期した処理が可能なアルゴリズムとなる．すなわち，文頭文節からある文節までが入力されたとき，そこまでの情報に基づいてできる計算は，それより後の文節に関係なく済ませることができる．そして，もし必要ならば，その時点で{\bf3.3}に述べるバックトレースを行い，そこまでの入力に対する簡約文を出力することができる．また，最外ループを$l\/$に関するループとすれば，そのループの第$l$ステップの処理が終わった時点で，$N=l$としてバックトレースが可能になるので，文節数$1$から順に求めたい文節数までの簡約文を出力するアルゴリズムが構成できる．\begin{algorithm}{再帰式の実行}\label{alg:recursion}\rm\begin{tabbing}\hspace*{5mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\+\kill{\bffor}$n:=0${\bfto}$M-1${\do}\+\\{\bfbegin}\\{\bffor}$m:=n${\bfdownto}$0${\bfdo}\+\\{\bfbegin}\\{\bfif}($m=n$){\bfthen}$f(m,m,1):=q(m)$;\`\makebox[10zw]{\dotfill式(\ref{eqn:eqn1})}\\{\bfelse}\+\\{\bfbegin}\\{\bffor}$l:=2${\bfto}$n-m+1${\bfdo}\+\\{\bfbegin}\\{\bfif}($l=2$){\bfthen}$f(m,n,l):=$...;\`\makebox[10zw]{\dotfill式(\ref{eqn:eqn2})}\\{\bfelse}{\bfif}($l=3$){\bfthen}$f(m,n,l):=$...;\`\makebox[10zw]{\dotfill式(\ref{eqn:eqn3}a,\ref{eqn:eqn3}b)}\\{\bfelse}$f(m,n,l):=$...;\`\makebox[10zw]{\dotfill式(\ref{eqn:common}a,\ref{eqn:common}b,\ref{eqn:common}c)}\\{\bfend};\-\\{\bfend};\-\\{\bfend};\-\\{\bfend};\end{tabbing}\end{algorithm}\subsection{バックトレース}アルゴリズム１の計算結果から最適部分文節列を構成することを，ここでは「バックトレース」という．ここで用いるバックトレースの方法は\cite{ozeki}の手法に類似したものであり，形式的な証明も可能であるが，ここでは，考え方の概略とアルゴリズムを示すにとどめる．まず「係り受け構造の分解」について述べる．$v_{1}v_{2}\cdotsv_{K}$を文節列とし，その上の係り受け構造$c$を考える．$c$において，末尾の文節$v_{K}$に係る最も文頭側の文節を$v_{k}$とすると，$c$は$v_{1}v_{2}\cdotsv_{k}$上の係り受け構造と$v_{k+1}v_{2}\cdotsv_{K}$上の係り受け構造に分解できる．ただし，$v_{k}$が$v_{K}$に係るという情報を加えておく必要がある\cite{ozeki}．付録の証明から明らかなように，$f(m,n,l)$に対する再帰式の導出においては，この事実が以下のように利用されている．$f(m,n,l)$を計算するためには，$w_{m}$から始まり，$w_{n}$で終わる長さ$l$の部分文節列上の係り受け構造を考慮する必要がある．上に述べたことから，そのような係り受け構造は，$w_{n}$に係る最も文頭側の文節を$w_{n^{\prime}}$とするとき，$w_{n}$から始まり$w_{n^{\prime}}$で終わる長さ$l^{\prime}$の部分文節列上の係り受け構造と，ある文節$w_{m^{\prime}}$から始まり$w_{n}$で終わる長さ$l-l^{\prime}$の部分文節列上の係り受け構造に分解できる．ただし，$w_{n^{\prime}}$が$w_{n}$に係るという情報を加えておく必要がある．さて，再帰式の証明が示すように，$f(m,n,l)$を求めるためには，評価関数$g$を，上のように分解した部分文節列，および係り受け構造に関して最大化すればよい．それは，\begin{displaymath}f(m,n^{\prime},l^{\prime})+f(m^{\prime},n,l-l^{\prime})+p(n^{\prime},n)\end{displaymath}を，$l^{\prime}$，$m^{\prime}$，$n^{\prime}$に関して最大化することに帰着する．最大値を与えるこれらの変数の値を再び$l^{\prime}$，$m^{\prime}$，$n^{\prime}$と表せば，以上のことから，$f(m,n,l)$を与える最適部分文節列$A$は$f(m,n^{\prime},l^{\prime})$を与える最適部分文節列$B$と$f(m^{\prime},n,l-l^{\prime})$を与える最適部分文節列$C$の連接で与えられること，また$A$上の最適係り受け構造は$B$上の最適係り受け構造と$C$上の最適係り受け構造を併せたものに，$w_{n^{\prime}}$が$w_{n}$に係るという情報を加えたものになることが分かる．また，$m=n$の場合は$l=1$しか許されず，$f(m,n,l)$を与える最適部分文節列は``$w_{m}$''となる．したがって，アルゴリズム\ref{alg:recursion}の各ステップで最大値を与える$l^{\prime}$，$m^{\prime}$，$n^{\prime}$の値(最適分割点)を記憶しておけば，アルゴリズム\ref{alg:recursion}の終了後，任意の長さの簡約文と，必要ならばその上の係り受け構造を再帰的に得ることができる．最適分割点はバックトレースのための，いわゆるバックポインタの役割を果たす．実際の計算では，アルゴリズム\ref{alg:recursion}の各ステップにおいて最適分割点を記憶するための変数$bp[m,n,l]$を用意する．最適分割点は再帰式中の場合に応じて，次のように設定される．$m',n',l'\/$は再帰式の中で最大値を与えるそれらの変数の値を表す．\begin{definition}{最適分割点}\label{def:opt_point}\hfill\\\begin{itemize}\item[a)]$m=n$の場合\\何も記憶する必要がない．\item[b)]$m<n$の場合\\\begin{tabular}{rlll}{\rm(\ref{eqn:eqn2})}の場合&$bp[m,n,l].lp=1,$&$bp[m,n,l].np=m,$&$bp[m,n,l].mp=n$\\{\rm(\ref{eqn:eqn3}a)}の場合&$bp[m,n,l].lp=1,$&$bp[m,n,l].np=m,$&$bp[m,n,l].mp=m'$\\{\rm(\ref{eqn:eqn3}b)}の場合&$bp[m,n,l].lp=l-1,$&$bp[m,n,l].np=n',$&$bp[m,n,l].mp=n$\\{\rm(\ref{eqn:common}a)}の場合&$bp[m,n,l].lp=1,$&$bp[m,n,l].np=m,$&$bp[m,n,l].mp=m'$\\{\rm(\ref{eqn:common}b)}の場合&$bp[m,n,l].lp=l',$&$bp[m,n,l].np=n',$&$bp[m,n,l].mp=m'$\\{\rm(\ref{eqn:common}c)}の場合&$bp[m,n,l].lp=l-1,$&$bp[m,n,l].np=n',$&$bp[m,n,l].mp=n$\end{tabular}\end{itemize}\end{definition}与えられた文節列から$1\leqN\leqM$の範囲で任意に指定した長さ$N$の最適部分文節列を探索するには，まず，最も評価値の高い$f(m_o,n_o,N)$を見つけることから始める．そして，この$m_o,n_o,N$を出発点として，アルゴリズム\ref{alg:backtrace}で示す再帰関数を用いて最適部分文節列が得られる:\begin{eqnarray*}(m_o,n_o)&:=&\textstyle\argmax_{m,n}f(m,n,N);\\最適部分文節列&:=&out(m_o,n_o,N)\end{eqnarray*}\noindentここでは，最適分割点が一意に定まる場合を考えているが，これが複数個存在する場合には，その全てを記憶し，そのそれぞれに対して最適部分文節列を求めればよい．異なる最適分割点から，同じ最適部分文節列が得られる可能性があるが，この場合，これらの最適部分文節列上には複数の最適係り受け構造が存在している．\begin{algorithm}{バックトレース}\label{alg:backtrace}\rm($\oplus$は文字列の連接を表す)\begin{tabbing}\hspace*{5mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\=\hspace*{3mm}\+\kill{\bffunction}\$out(m,n,l)$:charstring;\+\\{\bfbegin}\\{\bfif}\($m=n$){\bfthen}$out:=$``$w_{m}$'';\\{\bfelse}\\{\bfbegin}\+\\$l^{\prime}:=bp[m,n,l].lp$;\\$n^{\prime}:=bp[m,n,l].np$;\\$m^{\prime}:=bp[m,n,l].mp$;\\$out:=out(m,n',l')\oplusout(m',n,l-l')$;\-\\{\bfend};\-\\{\bfend}.\end{tabbing}\end{algorithm}ここで，本アルゴリズムにおける最適分割点と簡約文の係り受け構造の対応について述べる．$bp[m,n,l]$は文節列$w_m\cdotsw_n$を長さ$l\/$に簡約するときの最適分割点であるが，再帰式の証明(付録)からわかるように，$n'=bp[m,n,l].np$は簡約結果において$w_n$に係る文節の中で最も文頭側にあるものの番号である．したがって，$w_{n'}$は$w_n$に係ることがわかる．これを再帰的に繰り返せば，簡約文中の全ての文節の係り先がわかる．すなわち，アルゴリズム\ref{alg:backtrace}を用いてバックトレースを行なうとき，$n'=bp[m,n,l].np$ならば$c(n')=n$であることを記憶し，まとめて出力すれば，簡約文中の全ての文節に対する$c$の値，つまり係り受け構造を知ることができる．\subsection{計算量}まず，アルゴリズム\ref{alg:recursion}における加算回数について考察する．計算ステップ$m,n,l$における加算回数を$F(m,n,l)$とすると$f(m,n,l)$に対する再帰式より，次のことが容易に分かる．\renewcommand{\baselinestretch}{}\tiny\normalsize\begin{itemize}\item[a)]$l=1$のとき:\begin{eqnarray*}F(m,n,1)&=&0\makebox[10zw]{\hfill(式(1)より)}\end{eqnarray*}\item[b)]$l=2$のとき:\begin{eqnarray*}F(m,n,2)&=&2\makebox[10zw]{\hfill(式(2)より)}\end{eqnarray*}\item[c)]$l=3$のとき:\begin{eqnarray*}F(m,n,3)&=&2\makebox[18zw]{\hfill(式(3a)より)}\\&&{}+(n-m-1)+1\makebox[10zw]{\hfill(式(3b)より)}\\&=&n-m+2\end{eqnarray*}\item[d)]$l\geq4$のとき：\begin{eqnarray*}F(m,n,l)&=&2\makebox[23.5zw]{\hfill(式(4a)より)}\\&&{}+2(l-3)\left(\begin{tabular}{c}{$n-m-l+3$}\\2\end{tabular}\right)\makebox[10zw]{\hfill(式(4b)より)}\\&&{}+(n-m-l+2)+1\makebox[14zw]{\hfill(式(4c)より)}\\&=&(l-3)(n-m-l+3)(n-m-l+2)+(n-m-l+5)\end{eqnarray*}\end{itemize}\renewcommand{\baselinestretch}{}\tiny\normalsize総加算回数$A(M)$は$F(m,n,l)$を$0\leqm\leqn\leqM-1$，$1\leql\leqn-m+1$について加え合わせたものになるが，$m=n$のときは$l=1$であり，そのとき$F(m,n,l)=0$であるから，\begin{eqnarray*}A(M)&=&\sum_{0\leqm<n\leqM-1}\;\sum_{2\leql\leqn-m+1}F(m,n,l)\end{eqnarray*}となる．詳細は省略するが，この右辺を計算すると，\begin{eqnarray*}A(M)&=&\tfrac{1}{360}{\times}(M-3)(M-2)(M-1)M(M+1)(M+2)\nonumber\\&&+\\tfrac{1}{24}{\times}(M-4)(M-3)(M-2)(M-1)\nonumber\\&&+\\tfrac{2}{3}{\times}(M-3)(M-2)(M-1)\nonumber\\&&+\\tfrac{1}{6}{\times}(M-1)(M-2)(M+9)\nonumber\\&&+\(M-1)M\nonumber\end{eqnarray*}が得られる．同様の計算により，総比較演算回数$C(M)$は\begin{eqnarray*}C(M)&=&\tfrac{1}{720}{\times}(M-3)(M-2)(M-1)M(M+1)(M+2)\nonumber\\&&+\\tfrac{1}{12}{\times}(M-4)(M-3)(M-2)(M-1)\nonumber\\&&+\\tfrac{1}{2}{\times}(M-2)(M-2)(M-1)\end{eqnarray*}で与えられる．\begin{table}[hntb]\center\caption{原文文節数$M$に対する加算回数$A(M)$と比較演算回数$C(M)$}\label{tbl:order}\begin{tabular}{rrr}$M$&$A(M)$&$C(M)$\\\hline5&79&27\\10&2628&1464\\20&159011&85443\\40&10624042&5438446\\\end{tabular}\end{table}\hspace{-11pt}したがって計算量のオーダは$A(M)$,$C(M)$共に$O(M^6)$となる．これはかなり大きな計算量のように見えるが，最高次の係数が小さいことと$M$は高々40程度までを考えておけばよいことから，計算が困難なほど大きな値にはならない．実際，$M=40$の場合，加算回数と比較演算回数は表\ref{tbl:order}で示したように，$A(40){\approx}1.1{\times}10^7,C(40){\approx}5.4{\times}10^6$であり，アルゴリズム\ref{alg:recursion}をCで実装しUltraSPARC-IIi(270MHz)上で処理したときの処理時間は，1秒以内である．また，アルゴリズム\ref{alg:backtrace}の実行時間は，これに比べて無視できる程度である．\vspace{-3mm}
\section{簡約例}
本手法の評価は今後の課題であるが，アルゴリズムの動作を示すため，文節重要度と係り受け整合度を仮に与えて実行した例を2つ示す．簡約文の係り受け構造も\cite{ozeki}による括弧表記を用いて示している．\begin{footnotesize}\bigskip\begin{minipage}{50zw}\begin{verbatim}文節数:簡約結果例1原文<<また><<<<<袖や>袖口>ポケット口などが><油汚れで><変色を>おこす>ことも>あります>8:<<<<<<袖や>袖口>ポケット口などが><油汚れで><変色を>おこす>ことも>あります>7:<<<<<<袖や>袖口>ポケット口などが><変色を>おこす>ことも>あります>6:<<<<<袖や>袖口>ポケット口などが><変色を>おこす>ことも>5:<<<<袖や>袖口>ポケット口などが><変色を>おこす>4:<<<袖口>ポケット口などが><変色を>おこす>3:<<<変色を>おこす>ことも>2:<<変色を>おこす>例2原文<<<年齢は><まだ>十四だが><<数えきれぬほど><<日本の>舞台を>踏んだので><日本語は>ぺらぺらだそうだ>8:<<<年齢は><まだ>十四だが><<<日本の>舞台を>踏んだので><日本語は>ぺらぺらだそうだ>7:<<<年齢は>十四だが><<<日本の>舞台を>踏んだので><日本語は>ぺらぺらだそうだ>6:<<十四だが><<<日本の>舞台を>踏んだので><日本語は>ぺらぺらだそうだ>5:<<<<日本の>舞台を>踏んだので><日本語は>ぺらぺらだそうだ>4:<<<舞台を>踏んだので><日本語は>ぺらぺらだそうだ>3:<<踏んだので><日本語は>ぺらぺらだそうだ>2:<<日本語は>ぺらぺらだそうだ>\end{verbatim}\end{minipage}\\\bigskip\\\end{footnotesize}本アルゴリズムで必要とされる係り受け整合度は，\cite{zhang}の係り受けペナルティに$-1$を乗じたものとした．ここで定義されているペナルティ関数は学習コーパス中の係り受け距離の頻度分布を元に作成されている．また文節重要度は，\begin{itemize}\item主部/述部や名詞/動詞を含む文節に形容詞や動作の程度や目的を表す文節より大きい値\item文末の動詞には大きな値\item形式名詞には小さな値\end{itemize}を人手で設定した．この例における具体的な値を表\ref{tbl:example}に示す．\begin{table}[hntbp]\label{tbl:example}\caption{例文における係り受け整合度$p$と重要度$q$の設定値}\label{tbl:example}\vspace*{-1zh}\begin{footnotesize}\begin{center}\begin{tabular}{lrl}単語&重要度&係り受け整合度(係り先の単語)これ以外は$-10000$\\\hline\hline(0)また&0.0&-5000(6),-26.3906(8)\\(1)袖や&10.0&-1.8232(2),-23.0259(3),-5000(4),\\&&-5000(5),-5000(6),-5000(7),-5000(8)\\(2)袖口&10.0&-7.2887(3)\\(3)ポケット口などが&35.0&-38.0221(6)\\(4)油汚れで&2.0&-18.9712(6),-32.8341(8)\\(5)変色を&40.0&-4.9419(6),-41.5261(8)\\(6)おこす&20.0&-17.869(7)\\(7)ことも&0.0&0.0(8)\\(8)あります&0.0&\\\hline(0)年齢は&20.0&-24.7498(2),-29.0142(3),-5000(6),-42.2318(8)\\(1)まだ&2.0&-10.7264(2),-19.3284(3),-5000(6),-43.3073(8)\\(2)十四だが&10.0&-5000(3),-5000(6),-28.3321(8)\\(3)数えきれぬほど&2.0&-21.9722(6),-5000(8)\\(4)日本の&12.0&-1.3933(5),-30.7385(6),-51.5329(7),-5000(8)\\(5)舞台を&10.0&-4.9419(6)\\(6)踏んだので&10.0&-8.4730(8)\\(7)日本語は&22.0&-0.0000(8)\\(8)ぺらぺらだそうだ&20.0&\\\hline\end{tabular}\end{center}\end{footnotesize}\end{table}例にあげた文は\cite{zhang}の手法で正しく係り受け解析できたものである．簡約文の文節数$N$を原文の文節数$M$に等しく設定すると簡約文は原文そのものしかあり得ない．したがって，その場合には本アルゴリズムは原文の係り受け解析のみを行なうことになり，その結果は\cite{zhang}の手法によるものと一致する．実際に簡約文を出力するためには，その長さ$N$を指定する必要がある．これは，現実の場面で文章全体をどの程度に圧縮したいかという要求と簡約文の品質を考え合わせて決めるものであるが，本手法を人が文を簡約するときの支援システムとして使用する場合には$N$の値を順次変化させ，それに応じて得られる簡約文の中から人が適切なものを選ぶという使い方も考えられる．また，評価関数の値を利用して，「できるだけ短く」と「できるだけ情報を保つ」という相反する要求のバランスを自動的に取ることも考えられるが，それは今後の問題である．
\section{おわりに}
文節重要度と係り受け整合度に基づいて，効率的に文の簡約を行なうアルゴリズムを提案した．このアルゴリズムは簡約文の係り受け構造も同時に出力できるので，簡約文を引き続き他言語に翻訳するときなどにも有用である．計算量は原文文節数の6乗のオーダとなるが，各変数の制約条件のために現実的な文節数に対して実行可能なものとなっている．また，最外ループを制御する変数の選び方には自由度があるため，即答性が求められる場合には文節の入力と同期して計算を進めるようにアルゴリズムを構成することが可能である．今後は，文節重要度や係り受け整合度の設定の仕方が簡約結果に与える影響や，文節重要度から定まる評価関数値と係り受け整合度から定まる評価関数値の適切な重み付けなどについて検討し，簡約手法としての評価を行なう予定である．\bibliographystyle{jnlpbbl}\bibliography{v08n3_01}\begin{appendix}
\section{再帰式の証明}
最も一般的な式(\ref{eqn:common}a)$\sim$(\ref{eqn:common}c)の場合について証明する．他の場合については，より容易に証明できる．\begin{eqnarray*}\lefteqn{f(m,n,l)}\nonumber\\&=&\textstyle\max_{m=k_{0}<k_{1}<\cdots<k_{l-1}=n}g(k_{0},k_{1},\cdots,k_{l-1})\nonumber\\&=&\textstyle\max_{m=k_{0}<k_{1}<\cdots<k_{l-1}=n}\{\max_{c}\sum_{i=0}^{l-2}p(k_{i},c(k_{i}))+\sum_{i=0}^{l-1}q(k_{i})\}\nonumber\\&=&\textstyle\max_{m=k_{0}<k_{1}<\cdots<k_{l-1}=n}\nonumber\\&&\max\left\{\begin{tabular}{l}$\max_{c}\sum_{i=1}^{l-2}p(k_{i},c(k_{i}))+p(k_{0},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})$;\\\\$\max_{1<l^{\prime}<l-1}\{\max_{c}\sum_{i=0}^{l'-2}p(k_{i},c(k_{i}))+\max_{c}\sum_{i=l'}^{l-2}p(k_{i},c(k_{i}))$\\$+p(k_{l'-1},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})\}$;\\\\$\max_{c}\sum_{i=0}^{l-3}p(k_{i},c(k_{i}))+p(k_{l-2},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})$\end{tabular}\right.\nonumber\\&&\mbox{(係り受け構造$c$を末尾の文節$x_{k_{l-1}}$に係る文節の中で最も左にあるもの}\nonumber\\&&\mbox{の位置により分類)}\nonumber\\\mathstrut\\&=&\max\left\{\begin{tabular}{l}$\max_{m=k_{0}<k_{1}<\cdots<k_{l-1}=n}$\\$\{\max_{c}\sum_{i=1}^{l-2}p(k_{i},c(k_{i}))+p(k_{0},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})\}$;\\\\$\max_{1<l'<l-1}$\\$[\max_{m=k_{0}<k_{1}<\cdots<k_{l-1}=n}$\\$\{\max_{c}\sum_{i=0}^{l'-2}p(k_{i},c(k_{i}))+\max_{c}\sum_{i=l'}^{l-2}p(k_{i},c(k_{i}))$\\$+p(k_{l'-1},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})\}]$;\\\\$\max_{m=k_{0}<k_{1}<\cdots<k_{l-1}=n}$\\$\{\max_{c}\sum_{i=0}^{l-3}p(k_{i},c(k_{i}))+p(k_{l-2},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})\}$\end{tabular}\right.\nonumber\\\mathstrut\\&=&\max\left\{\begin{tabular}{l}$\max_{m=k_{0}<k_{1}=m'}\max_{m'=k_{1}<\cdots<k_{l-1}=n}$\\$\{\max_{c}\sum_{i=1}^{l-2}p(k_{i},c(k_{i}))+p(k_{0},k_{l-1})+\sum_{i=1}^{l-1}q(k_{i})\}+q(k_{0})$;\\\\$\max_{1<l'<l-1}$\\$[\max_{m=k_{0}<\cdots<k_{l'-1}=n'},\max_{n'=k_{l'-1}<pk_{l'}=m'},\max_{m'=k_{l'}<\cdots<k_{l-1}=n}$\\$\{\max_{c}\sum_{i=0}^{l'-2}p(k_{i},c(k_{i}))+\max_{c}\sum_{i=l'}^{l-2}p(k_{i},c(k_{i}))$\\$+p(k_{l'-1},k_{l-1})+\sum_{i=0}^{l-1}q(k_{i})\}]$;\\\\$\max_{m=k_{0}<k_{1}<\cdots<k_{l-2}=n'}\max_{n'=k_{l-2}<k_{l-1}=n}$\\$\{\max_{c}\sum_{i=0}^{l-3}p(k_{i},c(k_{i}))+p(k_{l-2},k_{l-1})+\sum_{i=0}^{l-2}q(k_{i})+q(k_{l-1})\}$\end{tabular}\right.\nonumber\\\mathstrut\\&=&\max\left\{\begin{tabular}{l}$\max_{m<m'}$\\$\{\max_{m'=k_{1}<\cdots<k_{l-1}=n}$\\$[\max_{c}\sum_{i=1}^{l-2}p(k_{i},c(k_{i}))+\sum_{i=1}^{l-1}q(k_{i})]+p(m,n)+q(m)\}$;\\\\$\max_{1<l'<l-1},\\max_{n'<m'}$\\$[\max_{m=k_{0}<\cdots<k_{l'-1}=n'}\{\max_{c}\sum_{i=0}^{l'-2}p(k_{i},c(k_{i}))+\sum_{i=0}^{l'-1}q(k_{i})\}$\\$+\max_{m'=k_{l'}<\cdots<k_{l-1}=n}$$\{\max_{c}\sum_{i=l'}^{l-2}p(k_{i},c(k_{i}))+\sum_{i=l'}^{l-1}q(k_{i})\}$\\$+p(n',n)]$;\\\\$\max_{n'<n}$\\$\{\max_{m=k_{0}<k_{1}<\cdots<k_{l-2}=n'}$\\$[\max_{c}\sum_{i=0}^{l-3}p(k_{i},c(k_{i}))+\sum_{i=0}^{l-2}q(k_{i})]+p(n',n)+q(n)\}$\end{tabular}\right.\nonumber\\\mathstrut\\&=&\max\left\{\begin{tabular}{l}$f(m,m,1)+\max_{m<m'<n-l+3}\{f(m',n,l-1)\}+p(m,n)$;\\\\$\max_{1<l'<l-1,\m+l'-2<n'<m'<n-l+l'+2}$\\$\{f(m,n',l')+f(m',n,l-l')+p(n',n)\}$;\\\\$\max_{m+l-3<n'<n}\{f(m,n',l-1)+p(n',n)\}+f(n,n,1)$\end{tabular}\right.\end{eqnarray*}\end{appendix}\begin{biography}\biotitle{略歴}\bioauthor{小黒玲}{1996年電気通信大学電気通信学部情報工学科卒業．1998年同大学院博士前期課程修了．現在，同博士後期課程在学中．自動音声認識，自然言語処理に興味がある．日本音響学会会員．}\bioauthor{尾関和彦}{1965年東京大学工学部電気工学科卒業．同年NHK入社．1968年より1年間エジンバラ大学客員研究員．音声言語処理，パターン認識などの研究に従事．電子通信学会第41回論文賞受賞．現在，電気通信大学情報通信工学科教授．工学博士．電子情報通信学会，情報処理学会，日本音響学会，IEEE各会員．}\bioauthor{張玉潔}{1999年電気通信大学情報工学専攻博士後期課程修了．博士(工学)．同年，電気通信大学情報通信工学科助手．2000年ATR音声言語通信研究所客員研究員，現在に至る．日本語及び中国語処理の研究に従事．}\bioauthor{高木一幸}{1989年筑波大学大学院修士課程理工学研究科修了．同年日本アイ・ビー・エム(株)入社．1992年筑波大学大学院工学研究科博士課程入学．1995年同課程修了．博士(工学)．現在，電気通信大学電気通信学部情報通信工学科助手．日本音響学会，電子情報通信学会，情報処理学会，人工知能学会各会員．}\bioreceived{受付}\bioaccepted{採録}\end{biography}\end{document}