    \documentclass[japanese]{jnlp_JS2.0}
\usepackage{jnlpbbl_1.3}
\usepackage[dvips]{graphicx}
\usepackage{amsmath}
\usepackage{hangcaption_jnlp}
\usepackage{udline}
\setulminsep{1.2ex}{0.2ex}
\let\underline



\Volume{18}
\Number{2}
\Month{June}
\Year{2011}

\received{2010}{8}{5}
\revised{2010}{12}{20}
\accepted{2011}{2}{10}

\setcounter{page}{119}


\jtitle{文書量に不変な定数\\—Yuleの$K$, Golcherの$\mathit{VM}$—}
\jauthor{木村　大翼\affiref{Author_1} \and 田中久美子\affiref{Author_1}}
\jabstract{
本稿では，文書量に不変な定数を考える．このような定数には，言語や文書の
複雑さや冗長性を定量化して捉える計算言語学上の意義がある．
これらの指標は既存研究でさまざまなものが提案されてきたが，
ほとんどの場合英語を中心とする小規模な文書を対象としてきた．
本研究では英語以外のさまざまな言語や，大規模な文書も対象として扱い，
主に先行研究において値が文長に依らないとされる 3 つの指標 $K$, $Z$, 
$\mathit{VM}$ と本研究で新たに試みた指標である $H$ と $r$ の 5 つの指標に対し，
値が一定となるかどうかの実験を行った． 
結果，値が言語の種類や文長に依らずに一定となる指標は $K$ と $\mathit{VM}$ の 2 つの指標であった．
なおかつこの 2 つの指標の値には自然言語と
プログラミング言語の間で有意な差が見られ，言語の複雑さや冗長性をある観点で表し
た指標となっていると考えることができる．
}
\jkeywords{定数，多言語の文書，言語モデル，複雑さ，冗長性}

\etitle{A Study on Constants of Natural Language Texts}
\eauthor{Daisuke Kimura\affiref{Author_1} \and Kumiko Tanaka-Ishii\affiref{Author_1}} 
\eabstract{
This paper considers various measures which become constant for any
large lengths of a given natural language text.  Consideration of such
measures gives some hints for studies of complexity of natural language. Previously,
such measures have been studied mainly for relatively small English
texts.  In this work, we consider the measures for texts other than
English and also for large scale texts.  Among the measures, we consider
Yule's $K$, Orlov's $Z$, and Golcher's $\mathit{VM}$, which are previously
empirically argued their convergence, and in addition, the entropy
$H$, and $r$, the measure related to the scale-free network. Our
experiments show that both $K$ and $\mathit{VM}$ are convergent for texts of
various language, whereas the other measures are not.
}
\ekeywords{constants, multilingual texts, complexity, language models, redundancy}

\headauthor{木村，田中}
\headtitle{文書量に不変な定数}

\affilabel{Author_1}{東京大学大学院情報理工学系研究科}{Graduate School of Information Science and Technology, The University of Tokyo}



\begin{document}
\maketitle


\section{はじめに}

本稿は，文書，あるいはある観点で集められた文書群が与えられたとき，それ
について文書量に依存しない定数—これを本稿では文書定数と定義する—を
計算する方式に関する報告である．

文書定数は，古くは文書の著者判定を主たる目的として探究された．最も古い
代表的なものとして，1940年代に提案されたYuleの$K$がある．現在では，
著者判定に対しては，言語モデルや機械学習に基づく方法など，代替となる手
法が数多く提案されている．このため，何も文書や文書群をあえて定数という
一つの数値に還元して判定を行う必要はない．しかし，文書あるいは文書群が
ある一貫した特質を持つのであれば，その特質を定数に還元しようとするこ
と自体は，工学上の個別の応用を超えて，より広く計算言語学上の興味深いテー
マであると筆者らは考える．

文書あるいは文書群に通底する一貫性の種類には，内容や，難易度などさまざ
まなものが考えられ，言語処理分野では文書分類や，難易度判定としてそれを
捉える工学的方法が考案されてきた．文書定数の場合には，もともとの研究の
発端が著者判定にあったために著者の語彙量，語彙の偏り度合，あるいは
個別文書の複雑さなど，語彙の複雑さを計測し数値化する問題として考えられ
てきた．一般に，文書の大きさが増すほど，文書の複雑さは増大するが，一方
で，漱石の「坊っちゃん」の一部分にはその全体にも通底する固有の特質があると
捉えることもできよう．これを定数として表そうとすることは，記号列として
の文書に一貫する複雑さのある側面を考えることにつながると考えられる．
そして，対象としうる文書は個別作品だけではない．特定の内容の文書群
や，特定の言語の文書群でこれらの定数を考えることは，自然言語の記号列の有
する特質に光を当てることにはならないか．

文書定数を考えることは，本稿でも報告するように，易しい問題ではない．そ
の一つの理由は，自然言語の文書において
hapax legomena—頻度が1回きりの単語—が語彙に対して占め
る割合が比較的大きいことにあろう．たとえば，
サイコロであれば，各目の出る確率を推定す
るのに必要な施行回数は推定することができる．一方で，文書の場合には，さ
まざまな統計的推定には文書量が常に不十分な状態のままである~\cite{kyo,Baayen}．
すなわち，文書定数を考えることは，確かな言語モ
デルが不在のまま，量が常に足りていない状態のままで定数を考える，という問
題として位置付けられよう．

次節でまとめるが，文書定数に関する研究は，すでにさまざまなものがあり，
単語に注目するものと文字列に注目するものに大別される．近
年の研究では，それらのほとんどが文書長に応じて単調変化してしまうことが
報告され，その中で，文書定数となる指標は，筆者らの知る範囲では，現在の
ところ2つしかない．この現状の中で，本稿の意義は以下の4点にまとめるこ
とができる．第一に，過去の研究で定数とされているものうちの
一つが定数ではないと実験的に示したことである．
第二に，過去の提案に加え，近年研究されている言語の大域的
特性を捉える複雑系ネットワークや言語エントロピーといった数理的枠組みか
ら，文書の特性を大域的に捉える指標を新たに吟味し，これらがやはり文書定数と
ならないことを示すことである．以上の意味で，本稿では，新しい文書定数を提
案するものではなく，文書定数としては依然として，既に提案されていたもののうち 
2つのみである，という結論となる．
第三に，文書定数に関する研究は，英語を中心として展開し，やや広くても印
欧語族についてのみの報告しかない．本稿では，日本語や中国語に関しても実
験を行い，過去に提案されてきた文書定数が非印欧語族に対しても定数として
成り立つかどうかを論じる．第四に， 過去の研究の大半では，短い個別文書に
関して定数となるかどうかが調べられてきた．本稿では，数百MBにわたる文書
群での実験結果も報告する．


\section{関連研究} \label{TandB}

過去の研究には単語に基づくものと，文字列に基づくものの二種類のものが提
案されている．

単語ユニグラムに基づく文書定数を得ようとしたもっとも古い学者の一人は前述の
ようにYule である~\cite{Yule}．Yuleの目的は，著者判定にあり，単語ユニグラ
ムに基づく指標$K$を提案した．これを受け，Herdanが60年代に独自の
式を提案している~\cite{herdan}．その後は，個別の提案が続き，近年，
Tweedie とBaayen が，単語ユニグラムのみに基づく指標に関し，網羅的な研究を行っ
ている~\cite{BaayenTweedie}．彼らは単語ユニグラムに基づく既存の12の指標に関し，実
際に定数となるかどうかを調べた．対象とした文書は，「不思議の国のアリス」
など英語の複数の短い個別文書である．彼らの実験では，12の指標が文書中の単
語はランダムに発生するという仮定のもとで提案されていることを受け，文書
中の単語を出現順にそのまま扱うものではなく，文書全体の単語をランダムに
入れ替えてシャッフルすることを行った上で，指標を計測した．その上で，12
の指標の中で$K$と$Z$については小規模な英語文書では文長によらず値がほぼ
一定となるが，そのほかの指標は一定とはならないことが報告されている．
さらに，TweedieとBaayenは，指標が文書の著者判別に用いることができるかを探究した．各文書を
$K$-$Z$空間で表し，クラスター分析などの別手法と比較した結果，$K$と$Z$の二
つの特徴量だけで著者を表すことができると結論づけた．

本稿では，単語ユニグラムに関して，TweedieとBaayenの報告とは異なる見解を実
験を根拠に示す．それは指標$K$と$Z$のうち，$Z$は文書定数を構成しないとい
うものである．$Z$は，次節で詳しく説明するが，Zipfの法則を背景とする点で
複雑系ネットワークとの関係が深い．この点で，言語の大域的特性を表す言語のべ
き乗則から単純に考えられる定数$r$を考えることができるが，それも定数とはな
らないことを合わせて示す．また，TweedieとBaayenは，英語の短い文書のみを
対象としたが，本稿では，日本語や中国語も対象とする．

文書定数としては，言語エントロピーにまつわる一連の研究を考える必要があ
る．Shannon \cite{Shannon}によって提案されて以来，言語エントロピーを計算す
る方法が，文字列に基づく方法，nグラムに基づく方法の両方で考えられて
きた~\cite{cover}．言語エントロピーは，文字列の冗長性を特徴付ける以上，
文書においてもある下限値に収束する定数として計測されうる
ことが期待される． 言語処理の分野でも~\cite{brown} が
単語nグラムに基づく言語エントロピーのupper boundを計測す
る方法を示しているが，データ量に対して，推定量がどのように推移するかに
ついての考察は述べられていない．また，\cite{genzel}が
エントロピーレート（一文字あたりのエントロピー）が定数である，という仮説を示し
ている．しかし，論文の内容は，エントロピーレートに関わる計算
式のある項が増大することを理由とする間接的なものに基づき，
エントロピーレートが本当に定数を為すといえるかは何ともい
えない．また，nグラムに基づく方法は，
スムージングと関連してパラメータ推定を要する点が文書定数を求める上では，
難しい．このような中，筆者らは，文字列に基づくエントロピーの計算方法と
して，パラメータ推定を要せず，収束性が数学的
に示されているFarachらの計算方法~\cite{Farach}を用い$H$を計算し，その文
長依存性を本稿では考える．

\begin{figure}[b]
 \begin{center}
  \includegraphics{18-2ia3f1.eps}
 \end{center}
 \caption{各文字がランダムに出現する場合のVM}
 \label{zu:Golcher}
\end{figure}

最後に，近年Golcherが文字列の繰り返しに
基づく画期的な指標$\mathit{VM}$を提案した~\cite{Golcher}．詳細は後述するが，
Golcherは接尾辞木の内部ノード数を文長で割った値が，文書定数であることを
示したばかりでなく，20の印欧語族は0.5付近で同じ値となることを示した．
またプログラミング言語やランダムテキストについては文長に対して値が変化
し，自然言語の場合と変化の様子がかなり異なるという結果が報告されている．
たとえば，
図\ref{zu:Golcher}は，Golcherの見解に沿って，筆者らが生成した図であるが，
$n$文字がランダムに出現する場合の$\mathit{VM}$は，横軸を文字数の対数，
縦軸を$\mathit{VM}$として，振動することがわかる．
Golcherの実験でもわれわれの結果でも，言語の
文書は$\mathit{VM}$は文長に依らず定数となる．
Golcherはなぜ$\mathit{VM}$が一定になるのかについての理論的な考察は展開して
おらず，それは将来の課題としている．
Golcherは印欧語族に対してのみ結果を示しているが，本稿では，日本語や中国
語についてもGolcherの値が定数となることを示す．


\section{指標} 
\label{sihyou}

前節で説明したように，本稿では単語に基づく指標として，$K$, $Z$, $r$, ま
た，文字列に基づく指標として$\mathit{VM}$と$H$を用いた．以下，各指標を順に説明する．


\subsection{単語に基づいた指標}
  
\subsubsection*{Yuleの指標 $K$}

指標$K$は文書の語彙の豊富さを示す指標として1944年に統計学者のYule
によって提案された~\cite{Yule}．今，文書の総単語数（単語数で計測した際の
文書長）を$N$, 単語の種類
を$V$とし，文書中に$m$回出現する単語の種類を$V(m,N)$とすると，$K$は
\begin{equation}
K = C\Big[-\frac{1}{N}+{\sum_{m=1}^{m=N}V(m, N)\left(\frac{m}{N}\right)^2}\Big] 
\label{k}
\end{equation}
で定義される．ここで$C$は$K$の値が小さくなりすぎないようにするための係数
であり，Yuleは$C=10^{4}$とした．この$C$の値に本質的な意味はない．
また，Yuleは文書の生成モデルにつぼモデル
と呼ばれる文書中の単語はランダムに出現するものとしたモデルを仮定している．
このモデルにおいて$N$が十分大きい時には，この$K$の期待値が一定となること
を数学的に証明することができる~\cite{Baayen}．

$K$が語彙の豊富さを表すことを以下簡単に説明する． 
今，文書中からランダムに単語を一つ選ぶことを考える．
すると式(\ref{k})において$(\frac{m}{N})$は文書中$m$回出現する単語が選択
される確率を表す．よって$(\frac{m}{N})^2$はそのような単語が連続で選択さ
れる確率である．
ここで同じ単語が連続で選択される確率が大きい場合は文書の語彙が乏しい場合，逆に確率
が小さい場合は語彙が豊富な場合と見なすことができる．
式(\ref{k})より前者の場合は$K$の値は大きくなり，後者の場合は$K$の値は小さくなることがわか
る．このように$K$は同じ単語が連続で出現する確率に基づいた語彙の豊富さを
表す指標である．
  

\subsubsection*{Zipfの法則に基づいた指標 $Z$}\label{zipf}

文書中に現れる各単語の出現頻度はZipfの法則に従うということが経
  験的に知られている~\cite{Zipf}．$Z$はこのZipfの法則に基づいた指標であ
る．今，文書の総単語数（単語数で計測した際の文書長）を$N$, 
単語の種類を$V_N$とし，$z$を文書中に出現する単語の回数に関して
降順に並べた時の順位を表す変数とする．
ここで順位が$z$である単語が文書中に出現する回数を$f(z,N)$とする
と，$f(z,N)$と$z$の間に
\begin{equation}
f(z,N)=\frac{C}{z^a}  （Cは規格化定数で\sum_{z}f(z,N)=Nを満たすように
定める） 
\label{eq zip}
\end{equation}
というべき乗則の関係がおおよそ成り立つ．また式(\ref{eq zip})において
$a=1, C=V_N$とおくと文書中に$m$回出現する単語の種類$V(m,N)$が
\begin{equation}
V(m,N)=\frac{V_N}{m(m+1)} 
\label{eq vmn}
\end{equation}
と表現されることが導かれる．

Orlovらは1983年にZipfの法則を拡張して，総単語数が$N$である文書の単語
の種類$V_N$の期待値$E[V_N]$が一つのパラメータ$Z$を用いて
\begin{equation}
E[V_N] =  \frac{Z}{{\rm log}(pZ)}\frac{N}{N-Z}{\rm log}\left(\frac{N}{Z}\right) 
\label{Z}
\end{equation}
と表すことができることを示した~\cite{Orlov}．ここで$p$は文書中に最も多く出現する単語の相対頻
度であり，文書ごとにほぼ一定の定数と見なされる．

$Z$は，文書が与えられた際に式(\ref{eq vmn})の関係が最もよく当てはまる
単語数である．また式(\ref{Z})において$N$を固定して考えてみると，$Z$
の値が大きくなるにつれて文書の単語の種類の期待値である$E[V_N]$の値が大き
くなるので，指標$Z$は文書の語彙の豊富さを表す指標だと解釈
することができる．

最後に$Z$の計算方法について述べる．式(\ref{Z})において単語数が$N$である時の単語の種類の期待値
$E[V_N]$を実際の文書の$V_N$で置き換えると
\[
V_N=\frac{Z}{{\rm log}(pZ)}\frac{N}{N-Z}
{\rm log}\left(\frac{N}{Z}\right) 
\]
を得る．この式は$Z$について陽に解くことができないので解析的な解を得るこ
とはできない．したがって$Z$を求める際には
\[
f(Z)= \frac{Z}{{\rm log}(pZ)}\frac{N}{N-Z}{\rm log}\left(\frac{N}{Z}\right)-V_N
\]
とおいて$f(Z)=0$をニュートン法の反復解法を用いて数値的に解く．


\subsubsection*{複雑系ネットワークに基づいた指標 $r$}

指標$r$は，$Z$が複雑系の観点からの指標であることを受け，
本研究で新たに試みた関連指標であり，文書の単語のネットワーク構造に
着目したものである． まず文書から構成される無向グラフ
$\Omega=(W,E)$について説明する．文書中の単語の種類を$V$とすると，
$W$は$W=\{w_i\}$ $(i=1,\ldots ,V)$で定義される各単語を頂点とする頂点集
合である．また，$E$は$E=\{(w_i,w_j)\}$ で定義される単語間のつながり
を表す枝集合であり，2つの単語$w_i$と$w_j$が連続して現れる場合に枝が存在
する．つまりここで考えているネットワークは文書中の各単語を頂点として連
続して現れる単語間に枝を張ったネットワークである．

本稿では文書の単語から構成されるネットワークとして上記のようなものを考え
る．これ以外にも単語ネットワークの構築方法には構文解析結果を用いるもの
や，文書の単語間の共起関係に基づいたネットワークなど複数考えることができる．
しかし，単語から構成されるどのようなネットワークを考え
たとしても，本稿の目的である文書の複雑さといった文書の大域的な特性を考
えた場合には，いずれのネットワークにおいても類似した性質が現れると考え
られる．実際にいくつかを実験的に試してみたが，文書量に対して一定となるか
どうかの観点では，大勢に影響はなかった．
ゆえに本稿では，文書の単語から構成されるネットワークとして上記
を扱う．
   
さて，ここで得られたネットワークの各頂点の次数分布に着目する．グラフ
において頂点の次数が$k$である確率を$P(k)$とおく．図\ref{fig:deg}は英語
とJavaの場合の次数分布の両対数をとった図である．図の横軸は次数$k$の対数
であり，縦軸は$P(k)$の対数である． いずれもある次数まではほぼ直線になっ
ている．このことから単語のネットワークの次数分布はある次数まではベキ分
布に従っていると考えられる．このような性質はスケールフリー性
~\cite{Barabasi}と呼ばれ，現実のさまざまな複雑系ネットワークで現れる性質であ
る．

\begin{figure}[b]
 \begin{center}
  \includegraphics{18-2ia3f2.eps}
 \end{center}
 \caption{英語とJavaの場合の次数分布}
 \label{fig:deg}
\end{figure}

ベキ分布は
\begin{equation}
P(k)=ck^{-\gamma} 
\label{beki}
\end{equation}
という形で表される．ここで$c$は正規化定数であり，
$\sum_{k=1}^{\infty}P(k)=1 $の条件から定まる．ここで式(\ref{beki})の両辺
において対数をとれば
\begin{equation}
{\rm log}P(k)=-\gamma{\rm log}k+{\rm log}c 
\label{log} 
\end{equation}
となりベキ分布は両対数グラフにおいて直線になることがわかる．

 今，式(\ref{log})の両対数グラフ上での傾き$-\gamma$に着目し，指標$r$を
\begin{equation}
r=-\gamma        
\label {eqr}
\end{equation}
で定義する．この指標が一定になるかということに関して特に理論的な背景は
ないが，$r$は前節までで紹介した$Z$と同様に言語のべき乗則に関する指標で，言語の
大域的特性を示すものである以上，文書ごとに文長に依らず一定となることが期待される．

最後に$r$の計算方法について述べる．本稿で$r$を求める際には，まず実際
に文書の単語から構成されるネットワークをつくり，ネットワークの各頂点の次
数を調べ，図\ref{fig:deg}のような次数分布を得る．次に，この次数分布の傾
きである$r$を得る際には，次数が2から$\sum_{k=1}^{n}P(k)\geq
A$を満たす最小の次数$n$までの範囲で，
最小二乗法を用いて傾きを推定した\footnote{実験ではAは0.95とした.}．これは次数が1の場合
と次数がある大きさを超えた範囲では，いずれの文書から構成される
ネットワークにおいても，図\ref{fig:deg}のように次数分布がべき分布から大きく外
れているためである．


\subsection{文字列に基づいた指標}

\subsubsection*{Golcherの指標 $\mathit{VM}$}

$\mathit{VM}$ は文字列の繰り返しの量を表す指標として
近年Golcherによって提案された指標であり，接尾辞木の構造を利用したものである~\cite{Golcher}．
接尾辞木とは，文字列が与えられた時の接尾部を木構造で表したデータ構
造であり，接尾部に対するパトリシア木である~\cite{Gusfield}．
以下与えられた文字列を$S$，その文字列の長さを$T$, $S$ の$i$番
目の文字を$S[i]$, $S$の$i$番目から$j$番目までの部分文字列を$S[i,j]$
$(i,j\in\{1,\ldots ,T\}, i \leq j)$をとする．文字列$S$の接尾辞木${\cal T}$
は以下のように定義される~\cite{Ukkonen,Gusfield}．
 \begin{quote}
 根から葉へと向かう有向木${\cal T}$が次の条件を満たす時，${\cal T}$は$S$の接尾辞
 木であるという．
  \begin{itemize}
 \item 1から$T$までの整数がラベル付けされたちょうど$T$個の葉が存在する．
 \item 内部節点は少なくとも2つの子をもち，各枝には$S$に含まれる空ではな
       い文字列が対応する．
 \item 同じ節点からの枝のラベルは必ず異なる文字から始まる．
 \item すべての葉$i$に対して根から葉$i$までの経路のラベルは
       $S[i,T]$となる．
 \end{itemize}
\end{quote}

Golcherの用いる接尾木辞は，$S$に含まれない文字を終端記号として文字列の
最後につけて接尾辞木を構築する．たとえば，図\ref{fig:cocoa}は文字列
`cocoa'の接尾辞木である．




これを用いて，$\mathit{VM}$の定義，説明を行う．今，与えられた文字列$S$の文字数
を$T$, $S$の接尾辞木における内部節点の数を$k$ とすると指標$\mathit{VM}$は
\begin{equation}
 VM = \frac{k}{T}  
\label{eq:v}
\end{equation}
で定義される．長さ$m$の接尾辞木は$m$個の葉を持つことから，内部節点の数
は最大でも$m-2$個である．よって$0\leq k < T-2$であるから$\mathit{VM}$の値の範囲
は$0\leq VM < 1$となる．ここでUkkonenのアルゴリズムによると，接尾辞木
の内部接点はこれまでに現れていない共通部分が新たに現れる場合に増える．
したがって$\mathit{VM}$はある種の文字列の繰り返しの量を表していると考えること
ができる．


 \begin{figure}[t]
 \begin{center}
  \includegraphics{18-2ia3f3.eps}
 \end{center}
 \caption{`cocoa' の接尾辞木}
 \label{fig:cocoa}
 \end{figure}
 
最後に$\mathit{VM}$の計算方法について述べる．
式(\ref{eq:v})で定義される$\mathit{VM}$の値を
求めるためには接尾辞木の内部節点の数を求めればよい．
最も素朴な方法としては，直接接尾辞木を構成することによって求める方法が考
えられる．しかし，一般に接尾辞木の構成に必要な
空間領域は，入力の文書の数十倍となり，大規模な文書を扱う場合には
直接接尾辞木を構成する方法は現実的ではない．本稿では，
より効率的なデータ構造である接尾辞配列と高さ配列を用いて，接尾辞木の擬似巡回を
行うことによって内部節点の数を求めた．アルゴリズムは~\cite{Kasai01}に詳しい．


\subsubsection*{文書のエントロピー $H$}

ここで紹介するエントロピー$H$は情報理論の分野においてShannonに
よって1948年に導入された~\cite{Shannon}．
文書を構成する有限個のアルファベットの集合を$\chi$とし，$X$を$\chi$上の
確率変数とする．この時，各アルファベット$x\in \chi$の文書における出現確
率を$P_X(x)={\rm Pr}( X=x )$とおくとエントロピー$H$は，
\begin{equation}
H = -\sum_{x \in \chi}P_X(x){\rm log}P_X(x) 
\label {entropy}
\end{equation}
で定義される．


文書のエントロピーを求めるためには式(\ref{entropy})より各アルファベット
$x$に対し，その出現確率$P_X(x)$を知る必要があるが，文書から得られる出現
確率はあくまで真の出現確率の近似であり，文書から直接求めることはできな
い． 言語処理では文章のエントロピーを求める方法についてはさまざまな試み
がある~\cite{cover,brown}．本稿では，エントロピーの値の推定方法とし
て，収束性が証明されている一つの方法であることから，Farachらによる手法
を用いた~\cite{Farach}．

今与えられた文書を一つの文字列と見なしてこれを$S$とし，その長さを$T$,
$S$の$i$番目から$j$番目までの部分文字列を$S[i,j]$ $(i,j\in\{1,\ldots,T\},
i \leq j)$とする．次に$S$の各位置$i$ $(1 \leq i \leq T)$に対してそれ
より以前の最大マッチング$L_i$を以下のように定義する．
\begin{equation}
L_i={\rm max}\{k: S[j, j+k]=S[i, i+k]\} \quad (j\in\{1,...,i-1\}, 1 \leq j \leq j+k \leq i-1)
\label{eq L}
\end{equation}
つまり$L_i$は$S$の$i$番目から始まる文字列と，1番目から$i-1$番目までの文
字列との最大共通部分文字列長である．そしてこれら$L_i$の平均値$\bar{L}$を，
\[
\bar{L}=\frac{1}{T}\sum_{i=1}^{i=T}L_i
\]
とする．この時Farachらのエントロピーの推定値$H$は，
\begin{equation}
H=\frac{{\rm log}_2T}{\bar{L}}
\end{equation}   
で定義される．今，真のエントロピーの値を$H_t$とすると，この手法によって得
られる推定値$H$は，$T\to\infty$の時に$|H_t-H|=O(1)$となることが数学的に示されて
いる．


\section{実験}

本研究では個別文書と，数十MB〜200~MBの自然言語やプログラミング言語
の文書を用いて\ref{sihyou}章で説明した$K, Z, r, VM, H$の各指標の文長に
対する値の変化を調べる実験を行った．


以下\ref{env}節で実験データや実行環境を説明した後に，
\ref{result_small}節で小規模文書での実験結果，
\ref{result_normal}
節で大規模文書に対する結果を図とともに述べる．


\subsection{実験データおよび実験環境}
\label{env}

\subsubsection{実験データ}

今回の実験で用いた文書は表\ref{tb:many large}の通りである．

個別文書に関しては，\cite{BaayenTweedie}とは異なり，英語だけではなく，日
本語，フランス語， スペイン語の文章も対象とした．用いたデータは表
\ref{tb:many large}の第一ブロックに示した．

\cite{BaayenTweedie}らの研究を概観すると，定数になるかどうかを吟味する
には，小規模な個別文書では長さが不十分であることもよくある．そこで， 日
本語，英語，中国語の新聞コーパスについても定数となるかどうかを調べる．
また，得られる定数が言語の特徴量を表すかどうかを吟味するため，比較対象
としてプログラミング言語のデータも用いる．このためには，Java,
RubyとLispのソースを用いた．
ここで日本語と中国語については$\mathit{VM}$と$H$ の値を計算する際に
は日本語（ローマ字），中国語(pinyin)の文書を用いた場合，ならびに，元のテ
キストを用いた場合の両方を報告する．その他の言語に関してはいずれの指標
の場合も表\ref{tb:many large}にある各言語の文書を用いて実験を行った．
また，プログラミングにおける単語は以下のように定義した．まず，
JavaとRubyについてはソースを記号で分割し，分割された各要素を単語とした．
例えば `if(i $<$ 5) break;' であれば `if', `(', `i', `$<$', `5', `)',
`break`, `;' の8つの要素が単語である．Lispの場合はこれらの要素から`(' と
`)'の2つを除いたものを単語とした．

 \begin{table}[t]
  \caption{実験で用いた言語データ}
  \label{tb:many large}
\input{03table01.txt}
  \end{table}


\subsubsection{実験で用いたプログラム}

今回の実験においてはいくつかの外部プログラムを利用した．ここでそれらの
プログラムについて記載する．

まず単語に基づいた指標$K, Z, r$ の値を計算するために文書を単語に分割する
必要がある．日本語の場合は形態素解析ソフト
Mecab\footnote{http://mecab.sourceforge.net/}を，中国語については，
ICTCLAS\footnote{http://ictclas.org/}を用いて単語に分割した．
文字列に基づいた指標$H, VM$については，日本語，中国語に関しては，ローマ
字，pinyin変換したものについても計算した．中国語に関してはあらかじめ
pinyin表記で書かれた別の文書を用いたが，日本語の場合は
KAKASI\footnote{http://kakasi.namazu.org/index.html.ja}を用いてローマ字に変換した．

各指標の計算方法は，\ref{sihyou}節で示したとおりである．


\subsection{個別文書に対する結果}
\label{result_small}

\begin{figure}[b]
\vspace{-1\baselineskip}
\noindent
\begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f4.eps}
  \end{center}
  \caption{個別文書に対する$K$}
  \label{fig:small_k}
 \end{minipage}
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f5.eps}
  \end{center}
  \caption{個別文書に対する$\mathit{VM}$}
  \label{fig:small_v}
 \end{minipage}
\end{figure}
\begin{figure}[b]
\noindent
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f6.eps}
  \end{center}
  \caption{個別文書に対する$Z$}
  \label{fig:small_z}
 \end{minipage}
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f7.eps}
  \end{center}
  \caption{個別文書に対する$r$}
  \label{fig:small_r}
 \end{minipage}
\end{figure}
\begin{figure}[b]
 \begin{center}
  \includegraphics{18-2ia3f8.eps}
 \end{center}
 \caption{個別文書に対する$H$}
 \label{fig:small_h}
\end{figure}

個別文書に関する結果を図\ref{fig:small_k}--\ref{fig:small_h}について示す．
英語の文書のみならず，他の印欧語族や日本語といった文書については，$K$,
$\mathit{VM}$については一定となる一方で，
\pagebreak
$Z$, $r$, $H$については大域的には単調変化する
結果となった．
\cite{BaayenTweedie}の結果では，$Z$が一定となることが示されていた．しか
し，実験では一貫して$Z$が一定とはならないことが示されている．同様に，類
似の複雑系の指標としての$r$もやはり一定とはならなかった．


\subsection{大規模文書に対する結果} 
\label{result_normal}

文長に対する各指標の値と，参考のためにシャッフル後の結果について述べる．
ここで文書をシャッフルするとは，各文書ごとに文書中の単語の順番をランダ
ムに入れ替えることを言い，シャッフル後の結果とは，この操作を20回繰り返
した際の指標の平均値である．このように単語順序をランダムに入れ替えるの
は，もともとTweedieとBaayen~\cite{BaayenTweedie}が行っていた方法で，数式
上の仮定を満たすためであり，文書定数を考える上で前処理としての妥当性は
疑問である．とはいえ，文書には確かに局所的な揺れやぶれがあるので，大域
的特性を概観し，元文書に対する指標の推移を比較検討するために示すもので
ある．このシャッフルは先行研究との対比のため$K$と$Z$の2つの
指標に対してのみ結果を示す．
以下の図では，横軸は文書の単語数の対数をとったものであり，縦軸は
指標の値である．

\begin{figure}[b]
\noindent
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f9.eps}
  \end{center}
  \caption{各言語の{\it K}}
  \label{fig:many_k}
 \end{minipage}
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f10.eps}
  \end{center}
  \caption{各言語の{\it K}（シャッフル後の平均値）}
 \label{fig:many_sh_k}
 \end{minipage}
\end{figure}

図\ref{fig:many_k}は各文書に対する$K$であり，図\ref{fig:many_sh_k}は
シャッフル後の結果である．まず$K$については自然言語の場合，いずれの言語に
おいても文書の単語数の対数に対して値はほぼ一定となった．プログラミング
言語の場合は自然言語と比べて若干の変化が見られたが，単語数が10万を超え
ると同様に値はほぼ一定となった．文書中の単語の順番をランダムに入れ替え
た場合ではいずれの言語の場合でも文書の単語数の対数に対してほぼ完全に一
定となった．シャッフル前と後で$K$の値はほとんど変化していないことから，
$K$は文書中の単語がランダムに出現するという仮定が背後にある指標にも拘わ
らず，ランダム性が崩れた実際の文書においても値がほとんど変わらずほぼ一
定となったということが興味深い． また，プログラミング言語の$K$の値は自
然言語の値と比べてかなり大きくなり，両言語間の$K$の値に大きな差が出る結
果となった．


$\mathit{VM}$については日中をアルファベットに変換した場合の結果をまず吟味する．
図\ref{fig:many_v}は各文書に対する$\mathit{VM}$であり，
図\ref{fig:many_v2}は図\ref{fig:many_v}を拡大したものである．
日本語の場合に値が英語，中国語と比較してわずかに大きくなっているが，い
ずれも文書量の対数に対して値はほぼ一定でおよそ0.5の値をとった．プログラ
ミング言語の場合は自然言語の場合よりも変化が見られるが，単調に変化する
傾向はみられない．プログラミング言語に関する$\mathit{VM}$の値は自然言語よりも大
きく，およそ0.65 の値をとり，両言語間で値に大きな差が表れた．これは，自
然言語の冗長性が，プログラミング言語のそれよりも一律に小さいことを示し
ているだろう．

\begin{figure}[b]
\noindent
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f11.eps}
  \end{center}
  \caption{各言語の{\it VM}}
  \label{fig:many_v}
 \end{minipage}
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f12.eps}
  \end{center}
  \caption{各言語の{\it VM}（図\ref{fig:many_v}の拡大図）}
  \label{fig:many_v2}
 \end{minipage}
\end{figure}
\begin{figure}[b]
\noindent
  \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f13.eps}
  \end{center}
  \caption{日本語と中国語の原文の{\it VM}}
 \label{fig:raw_v}
 \end{minipage}
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f14.eps}
  \end{center}
  \caption{日本語と中国語の原文の$\mathit{VM}$（図\ref{fig:raw_v}の拡大図）}
 \label{fig:raw_v2}
 \end{minipage}
\end{figure}

次にアルファベットに変換しない場合の日本語，中国語の文字列
をそのまま用いた場合の$\mathit{VM}$の結果を図\ref{fig:raw_v}と図\ref{fig:raw_v2}に示す．
これらの図には比較のため，アルファベットに変換した場合の日本語，中国語の
結果も含まれている．

まず$\mathit{VM}$の値は，アルファベットに変換しない場合の日本語，中国語の文字列
をそのまま用いた場合でも，アルファベットに変換した場合と同様に
文書量の対数に対して値はほぼ一定となることがわかる．しかし$\mathit{VM}$の値の大き
さに注目すると，その値は日本語，中国語のいずれ
の場合もおよそ0.35であり，アルファベットに変換した場合の0.5という値より
小さくなっている．これは日本語，中国語の原文におけるアルファベットサイズ
が変換後のそれよりも遥かに大きいため，文書中で繰り返し出現する文字列の種
類が減少し，接尾辞木の内部節点の数が少なくなったからだと考えられる．

\begin{figure}[b]
\noindent
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f15.eps}
  \end{center}
  \caption{各言語の{\it Z}}
  \label{fig:many_z}
 \end{minipage}
  \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f16.eps}
  \end{center}
  \caption{各言語の{\it Z}（シャッフル後の平均値）}
 \label{fig:many_sh_z}
 \end{minipage}
\end{figure}
\begin{figure}[b]
\noindent
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f17.eps}
  \end{center}
  \caption{各言語の{\it r}}
  \label{fig:many_r}
 \end{minipage}
 \begin{minipage}{0.5\textwidth}
  \begin{center}
   \includegraphics{18-2ia3f18.eps}
  \end{center}
  \caption{各言語の{\it H}}
  \label{fig:many_h}
 \end{minipage}
\end{figure}

その他の3つの指標$Z, r, H$について述べる．
    図\ref{fig:many_z}--\ref{fig:many_h}は
それぞれ各文書に対する$Z, r, H$の結
果である．
まず複雑系に関連した指標である$Zとr$は$Z$におけるLispを除いて
文長に対して値が単調に増加する結果となった．Lispは$Z$において値が微増す
るにとどまり，ほぼ一定となった．
$Z$や$r$は，言語に内在する大域的な構造を一挙に捉えるものであ
るが，それは一般的には一定値にはならないということである．また，文字列のエントロ
ピー$H$は文長に対して値が単調に減少する結果となった．なお，ここで示す
$H$は日中についてはアルファベット表記に変換した結果である．
さらに，$Z$についてはシャッフル後も同様にLispを除いて値が一定とはならなかった．
他の言語においては全く一定にならなかった$Z$がLispに限り，値が微増するに
とどまったという結果は大変興味深い．

以上の実験に加えて$\mathit{VM}$と$H$の2つの指標については，文書の文字列を
逆順にしたものに対しても実験を行ったので，その結果を簡単に述べる．これは$\mathit{VM}$と$H$が
本研究で検討している指標の中で文字列の順序に依存する指標であるからであり，
文書の文字列を逆順にすることによって，文字列の前から後ろへの依存性だけではなく，後ろから前への依
存性を調査した．結果としては，文字列を逆順にしても，$\mathit{VM}$と$H$の値は
文長が増加するにつれて文字列の順序を変えない場合の値とほぼ同じになっ
た．



\section{考察}

まず，文長に依存せず指標が一定となるかどうかの観点から考察する． 前章で
の実験の結果から自然言語，プログラミング言語において文長に依らず値がほ
ぼ一定となる指標は本研究の範囲では，$K$と$\mathit{VM}$の2つの指標であることが示
された． 

$\mathit{VM}$については非印欧語族である日本語，中国語においてもアルファベット表
記ならば値がおよそ0.5となった．これはアルファベット—あるいは荒い近似
としての音—という限られた言語要素を用いて行う言語表現中に内在する冗長
性の度合を表しているものと考えられる．また日本語，中国語の本来の表記を
用いて同様に$\mathit{VM}$の値を計算すれば，用いる文字の種類がアルファベットの場
合より大きいことから文字列の繰り返しは少なくなり，値は0.5より小さくなる
ことが示された．すなわち，用いることができる言語上の要素数が大きくなる
と，冗長性は小さくて済むことを表している．いずれにせよ，\ref{TandB}節で
示したように，要素がランダムに生起する場合には振動する指標が，言語では
一定となることは実に興味深い．

次に値が一定とならなかった指標について論じる．$Z$はTweedieらの先行研究
において小規模な英語文書において値が文長によらず一定となるという結果で
あったが，個別文書においても，大規模文書においてはLispを除
いたいずれの言語においても一定とはならずに文長に対して単調に変化した． 
ここでLispについては微増との結果となった．このように，
過去に提案されてきた指標は，言語によっては一定となる場合もある．本稿では，
「さまざまな文書において普遍に一定量となる指標」に焦点を当てているので，$Z$はそれには該当
しない．しかし，どの指標がどのような特性を持つ言語に対して一定となるのか
については，今後の課題といえよう．
$Z$と同様に複雑系に関連
した$r$については$Z$と同じように値が文長に対して変化する結果となった．
エントロピー$H$については，厳密な推定が難しい言語の確率モデルに依存しな
い計算方法を用いても，やはり一定とはならなかった．
ここで$H$はnグラムから計算することができ，
また$\mathit{VM}$の定義に用いられる接尾辞木は，潜在的なnグラム確率から作られ
ると考えることができる．このことから，$H$と$\mathit{VM}$は値の収束性において
同じ性質を持つと予想されたが，本研究の範囲では異なる性質を示した．

最後に指標の判別力という観点から考察する．判別は，個別文書（作品別），
著者（著者判別），より広くある一定の内容で集められた文書群（新聞の文書
  分類など），言語（英語が日本語かなど），語族（印欧語族とシナ・チベッ
  ト語族など），自然言語vs.プログラミング言語など異なる解像度で行うこと
が考えられる．

本研究の結果では，$K$と$\mathit{VM}$は，自然言語とプログラミング言語間において値
に有意な差が見られた．この傾向は$K$と$\mathit{VM}$ほどではないが他の指標にも見ら
れた．このことは2つの言語間に本質的な複雑さの差があることを示していると
考えられ，特に$K$と$\mathit{VM}$はその差をはっきりと捉えていると考えられる． よ
り高い解像度での判別問題は，語族や言語の判別については，少なくとも$\mathit{VM}$
については，表記システムで用いるアルファベットの大きさに依存する．$K$と
$Z$で，個別文書の判別が可能であると~\cite{BaayenTweedie}では述べられては
いるが，その問題については，今日ではより高性能な機械学習手法の方が手法
として妥当であると考えられる．すなわち，文書定数が自然言語の冗長性を反映
していると見られることが，文書定数の計算言語学上の
一つの意義であると考えられる．



\section{まとめ}

本研究では既存の指標$K$, $Z$, $\mathit{VM}$と新たに試みた指標$r$, $H$の5つの指標
に対して自然言語とプログラミング言語の文書を複数用いて
文長に依らずにその値が一定になるかを吟味した．

Yuleの$K$は文書中の語彙の豊かさを表す古典的な指標であるのに対し，Olrovの$Z$と
$r$は複雑系に基づく指標である．$\mathit{VM}$は接尾辞木に基づく文書の繰
り返しを表す指標であり，$H$は文書のエントロピーである．文書定数の文脈で
は$r$と$H$は今回新たに試みた指標である．

実験では個別文書，ならびに大規模な自然言語とプログラミング言語の文書を
用いて，各指標の文長に対する値の変化の様子を網羅的に調べた．その結果
$K$と$\mathit{VM}$ の2つの指標のみ文長によらず値がほぼ一定となった． さらにこの
2 つの指標は自然言語とプログラミング言語間において値に有意な差が見られ
た． またその他の$Z$, $r$, $H$については文長に対して値が単調に変化する
結果となった．


以上の結果から，Tweedieらの小規模な英語文書において$K$と$Z$は一定となる
という先行研究結果については，$K$に関してはいえるものの，$Z$に関しては
大規模文書において一定とならないことがわかった．またGolcherの先行研究結
果との対比においては，本研究の結果では，アルファベット表記を用いると，
日本語，中国語といった非印欧語族の言語においても$\mathit{VM}$は印欧語族同様，ほ
ぼ一定の0.5の値となることがわかった．




\acknowledgment

検定に関して有益なコメントを頂いた
東京大学大学院情報理工学系研究科の駒木文保教授に感謝の意を表する．

\bibliographystyle{jnlpbbl_1.5}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Baayen}{Baayen}{2001}]{Baayen}
Baayen, R.~H. \BBOP 2001\BBCP.
\newblock {\Bem Word Frequency Distributions}.
\newblock Kluwer Academic Publishers.

\bibitem[\protect\BCAY{Barab{\'a}si \BBA\ Albert}{Barab{\'a}si \BBA\
  Albert}{1999}]{Barabasi}
Barab{\'a}si, A.-L.\BBACOMMA\ \BBA\ Albert, R. \BBOP 1999\BBCP.
\newblock \BBOQ Emergence of scaling in random networks.\BBCQ\
\newblock {\Bem Science}, {\Bbf 286}, \mbox{\BPGS\ 509--512}.

\bibitem[\protect\BCAY{Brown, Pietra, Pietra, Lai, \BBA\ Mercer}{Brown
  et~al.}{1983}]{brown}
Brown, P.~F., Pietra, S., Pietra, V. J.~D., Lai, J.~C., \BBA\ Mercer, R.~L.
  \BBOP 1983\BBCP.
\newblock \BBOQ An estimate of an upper bound for the entropy of English.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 18}  (1), \mbox{\BPGS\
  31--40}.

\bibitem[\protect\BCAY{Cover \BBA\ Thomas}{Cover \BBA\ Thomas}{2006}]{cover}
Cover, T.~M.\BBACOMMA\ \BBA\ Thomas, J.~A. \BBOP 2006\BBCP.
\newblock {\Bem Elements of Information Theory}.
\newblock Wiley-Interscience.

\bibitem[\protect\BCAY{Farach, Noordewier, Savari, Shepp, Wyner, \BBA\
  Ziv}{Farach et~al.}{1995}]{Farach}
Farach, M., Noordewier, M., Savari, S., Shepp, L., Wyner, A., \BBA\ Ziv, J.
  \BBOP 1995\BBCP.
\newblock \BBOQ On the Entropy of DNA: Algorithms and Measurements Based on
  Memory and Rapid Convergence.\BBCQ\
\newblock In {\Bem Proceedings of the sixth annual ACM-SIAM symposium on
  Discrete algorithms}, \mbox{\BPGS\ 48--57}.

\bibitem[\protect\BCAY{Genzel \BBA\ Charniak}{Genzel \BBA\
  Charniak}{2002}]{genzel}
Genzel, D.\BBACOMMA\ \BBA\ Charniak, E. \BBOP 2002\BBCP.
\newblock \BBOQ Entropy Rate Constancy in Text.\BBCQ\
\newblock In {\Bem Annual Meeting of the Association for the ACL}, \mbox{\BPGS\
  199--206}.

\bibitem[\protect\BCAY{Golcher}{Golcher}{2007}]{Golcher}
Golcher, F. \BBOP 2007\BBCP.
\newblock \BBOQ A Stable Statistical Constant Specific for Human Language
  Texts.\BBCQ\
\newblock In {\Bem Recent Advances in Natural Language Processing}.

\bibitem[\protect\BCAY{Gusfield}{Gusfield}{1997}]{Gusfield}
Gusfield, D. \BBOP 1997\BBCP.
\newblock {\Bem Algorithms on Strings, and Sequences: Computer Science and
  Computational Biology}.
\newblock Cambridge University Press.

\bibitem[\protect\BCAY{Herdan}{Herdan}{1964}]{herdan}
Herdan, G. \BBOP 1964\BBCP.
\newblock {\Bem Quantitative Linguistics}.
\newblock Butterworths.

\bibitem[\protect\BCAY{影浦}{影浦}{2000}]{kyo}
影浦峡 \BBOP 2000\BBCP.
\newblock \Jem{計量情報学—図書館／言語研究への応用}.
\newblock 丸善.

\bibitem[\protect\BCAY{Kasai, Lee, Arimura, Arikawa, \BBA\ Park}{Kasai
  et~al.}{2001}]{Kasai01}
Kasai, T., Lee, G., Arimura, H., Arikawa, S., \BBA\ Park, K. \BBOP 2001\BBCP.
\newblock \BBOQ Linear-Time Longest-Common-prefix Computation in Suffix Arrays
  and Its Applications.\BBCQ\
\newblock In {\Bem Proceedings of the 12th Annual Symposium on Combinatorial
  Pattern Matching}, \mbox{\BPGS\ 181--192}. Springer-Verlag.

\bibitem[\protect\BCAY{Orlov \BBA\ Chitashvili}{Orlov \BBA\
  Chitashvili}{1983}]{Orlov}
Orlov, J.~K.\BBACOMMA\ \BBA\ Chitashvili, R.~Y. \BBOP 1983\BBCP.
\newblock \BBOQ Generalized Z-distribution generating the well-known
  `rank-distributions'.\BBCQ\
\newblock {\Bem Bulletin of the Academy of Sciences of Georgia}, {\Bbf 110},
  \mbox{\BPGS\ 269--272}.

\bibitem[\protect\BCAY{Shannon}{Shannon}{1948}]{Shannon}
Shannon, C. \BBOP 1948\BBCP.
\newblock \BBOQ A mathematical theory of communication.\BBCQ\
\newblock {\Bem Bell System Technical Journal}, {\Bbf 27}, \mbox{\BPGS\
  379--423, 623--656}.

\bibitem[\protect\BCAY{Tweedie \BBA\ Baayen}{Tweedie \BBA\
  Baayen}{1998}]{BaayenTweedie}
Tweedie, F.~J.\BBACOMMA\ \BBA\ Baayen, R.~H. \BBOP 1998\BBCP.
\newblock \BBOQ How variable may a constant be? Measures of lexical richness in
  perspective.\BBCQ\
\newblock {\Bem Computers and the Humanities}, {\Bbf 32}, \mbox{\BPGS\
  323--352}.

\bibitem[\protect\BCAY{Ukkonen}{Ukkonen}{1995}]{Ukkonen}
Ukkonen, E. \BBOP 1995\BBCP.
\newblock \BBOQ On-line construction of suffix-trees.\BBCQ\
\newblock {\Bem Algorithmica}, {\Bbf 14}, \mbox{\BPGS\ 249--260}.

\bibitem[\protect\BCAY{Yule}{Yule}{1944}]{Yule}
Yule, G.~U. \BBOP 1944\BBCP.
\newblock {\Bem The Statistical Study of Literary Vocabulary}.
\newblock Cambridge University Press.

\bibitem[\protect\BCAY{Zipf}{Zipf}{1949}]{Zipf}
Zipf, G.~K. \BBOP 1949\BBCP.
\newblock {\Bem Human Behaviors and the Principle of Least Effort: An
  Introduction to Human Ecology}.
\newblock Addison-Wesley Press.

\end{thebibliography}


\begin{biography}
\bioauthor{木村　大翼}{
2010年東京大学工学部計数工学科卒業．
現在，同大学大学院情報理工学系研究科に在学中．
構造データを対象とした機械学習に興味をもつ．
}
\bioauthor{田中久美子}{
東京大学大学院情報理工学系研究科准教授．1997年東京大学大学院工学系研究
科情報工学専攻博士課程修了，博士（工学）．工業技術院電子技術総合研究所，
東京大学大学院情報学環講師などを経て2005年より現職．自然言語や記号系に
普遍に内在する数理構造に興味を持つ．
} 

\end{biography}


\biodate


\end{document}
