\documentstyle[jnlpbbl,epsf]{jnlp_j_b5}

\setcounter{page}{43}
\setcounter{巻数}{9}
\setcounter{号数}{5}
\setcounter{年}{2002}
\setcounter{月}{10}
\受付{2001}{1}{31}
\再受付{2002}{5}{27}
\採録{2002}{7}{17}

\setcounter{secnumdepth}{2}

\title{文字列を$k$回以上含む文書数の計数アルゴリズム}
\author{梅村 恭司\affiref{TUT} \and 真田 亜希子\affiref{TUT}}

\affilabel{TUT}
{豊橋技術科学大学工学部情報工学系}
{Dept. of Information and Computer Sciences, Toyohashi University
 of Technology}

\headauthor{梅村，真田}
\headtitle{文字列を$k$回以上含む文書数の計数アルゴリズム}

\jabstract{この論文で計算するものは，ある文字列を$k$回以上含む
ドキュメントの総数($df_k$)である．全ての部分文字列に対してこれらの
統計量を保存する場合$O(N^2)$の表が必要となり，コーパスの大きさを
考えると，この表は実用的でなく，通常の計算機では実際に作ることは
難しい．しかし，$k=1$の場合，Suffix Array，文字列のクラス分けを
利用して，統計量をクラス毎に保存することで，これを$O(N)$の表に
できるという報告がある\cite{DF1}．
このクラスは同じ統計量を持つ文字列の集合であり，コーパス内の全ての
文字列の統計量はクラス毎に作成した統計量の表から取り出すことができる．
しかし，この方法は$k \geq 2$の場合には使用できない．
我々は，$k \geq 2$の場合にも使用でき，表を用いることに
よって文字列の統計量を計算するアルゴリズムを提案する．
本稿では$df_k$の性質を述べた後，単純な計算方法と提案する
アルゴリズムとの比較を行う．このアルゴリズムは，前処理として表を
作成するために$O(N \log N)$の計算時間と$O(N)$のメモリを使用し，
その表を用いて$O(\log N)$時間で文字列の統計量を取り出すことができる．}

\jkeywords{文字列頻度，文書頻度，Suffix Array}

\etitle{Counting documents that contain substrings\\ 
 more than $k$ times}
\eauthor{Kyoji Umemura\affiref{TUT} \and Akiko Sanada\affiref{TUT}}

\eabstract{The statistics we compute is $df_k$: the number of documents 
which contain certain strings more than $k$ times. We can hardly 
keep the statistics of all substrings because we need $O(N^2)space$ 
where $N$ is the size of corpus. Yamamoto et al. show that it is 
possible to produce a table for $k=1$ in $O(N)space$ using Suffix Array 
and the concept of "class of string". However, this method cannot 
solve the problem where $k \geq 2$. We present an algorithm that can 
be used for $k \geq 2$ and we can compute the statistics by using 
the table.
In this report, we explain $df_k$ and compare the proposed algorithm 
with simple methods. This algorithm takes $O(N \log N)time$ and 
$O(N)space$ to produce the table and $O(\log N)time$ to obtain 
statistics from the table.}

\ekeywords{Corpus frequency, Document frequency, Suffix Array}

\begin{document}
\maketitle
\thispagestyle{empty}

\section{はじめに}

ある文字列を$k$回以上含むドキュメント数には，文字列の意味に関連する性質が
ある．この論文では，このドキュメント数を重複度$k$のドキュメント頻度と呼び，
特に$k$を指定しない場合には，重複条件付きドキュメント頻度と呼ぶことにする．
図\ref{dfn-sample}は，332,918個の日本語アブストラクトの本文を対象に，様々
な文字列に対し，$k$を変化させて，重複度$k$のドキュメント頻度を計測したもので
ある．文字列が意味のある単語の部分である場合には，$k$の増加にしたがっても，
文書数の減少は緩やかである．たとえば，「メ」「メデ」「メディ」「メディア」
などについては，$k$が一つ増加するごとに，ドキュメントの数が半減する傾向が
観察される．一方，単語の切れ目を含む文字列の場合，$k$が増えるにしたがって
文章数が1/4以下になることが観測できる．この性質を使って，文書中のキーワー
ドを辞書を使わないで検出するということが可能であるという報告
\cite{Keyword}がある．
重複条件付きドキュメント頻度を単語の境界の検出に使用するには，任意の文字列
について，その重複度付ドキュメント頻度を求めることが必要である．たとえば，
文献\cite{Keyword}の文書分析では，頻度３を越える文字列について重複条件付き
ドキュメント頻度を計算しており，平均440バイト程度の1ドキュメントについて，
1400個程度の文字列が調査の対象となっている．単純な方法で重複度
付ドキュメント頻度を求めると，文字列ごとにコーパス長に比例する計算時間が
かかることになり，後述するように一つのドキュメントを処理するのも大変であ
る．さらに，キーワードをドキュメントの全体にわたって調査すると，この処理
を332,918回繰り返すことになり，単純な方法では計算時間がかかりすぎるという問
題がある．

\begin{figure}[htbp]
\begin{center}
\begin{verbatim}
    k=1     k=2     k=3     k=4     k=5 文字列
  52424   22324   11117    6156    3419 メ
   4632    2200    1221     707     392 メデ
   4580    2178    1211     699     388 メディ
   4434    2131    1195     692     382 メディア
    560      88      15       4       0 メディアを
     83      12       0       0       0 メディアを用
     83      12       0       0       0 メディアを用い
     64       6       0       0       0 メディアを用いた
\end{verbatim}
\caption{重複条件付きドキュメント頻度の例}
\label{dfn-sample}
\end{center}
\end{figure}


ここで，重複度を考慮しないドキュメント頻度（単純ドキュメント頻度）につい
ては，ドキュメント頻度が同じ文字列をクラス分けができ，そのクラスごとに頻度
を計測することが可能であるという報告\cite{DF1}がある．
例中の「メディアを用」と「メディアを用い」の二つの文字が
同じドキュメント頻度を持っているが，このような文字列
が一つのクラスに属する文字列の例である．
報告\cite{DF1}によると，
コーパスの文字数を$N$とした場合に，クラス数は最大で$2N-1$である．
よって，$O(N)$の大きさの表に，任意の文字列の単純ドキュメント頻度を保持す
ることができる．しかし，重複度を考慮した場合に同じクラス分けが使えるかど
うか明らかではないという問題が残る．

また，クラス分けをして，表を作成するならば，重複条件付きのドキュメント
頻度は，クラスごと，つまりそのクラスを代表する一つの文字列についてのみ
求めればよいが，
単純な方法では，代表の文字列の個数が$O(N)$，それぞれの計算に$O(N)$かかる
ことになり，全体で$O(N^2)$の処理となる．$N$がおよそ$10^8$程度のコーパ
スでは，実際に前処理が終わらないという問題が残る．文献\cite{DF1}は単純ド
キュメント頻度について，この問題の解決方法を示している．この方法は，文字
出現頻度から重複を除いて単純ドキュメント頻度を求めている．しかし，重複の
構造が複雑な重複条件付きドキュメント頻度の計測には，重複を除くという考
え方が使用できない．

この論文では，重複条件付きドキュメント頻度の計測についても，クラス分けが使用
できることを示し，その前処理として重複度の上限を与えた場合に，$O(N \log
N)$で，クラスごとの重複条件付きドキュメント頻度の表を作ることができるこ
とを示す．そのときに，重複条件付き文字列頻度という概念を提案し，重複条件付
き文字列頻度の関数として重複条件付きドキュメント頻度が求まることを示す．最後
に，実際に動作するシステムを作成し，332,918個のドキュメントで，
69,312,280文字からなるコーパスで計測した計算時間を示す．

ここで示すアルゴリズムは，$k$を固定したとき，ある文字列が$k$回以上出現す
るドキュメントの数を数え上げる問題について，ドキュメントの全文字数を$N$
とすると，前処理は計算時間$O(N\log N)$，メモリ使用量$O(N)$であり，その後
に値を求めるときには計算時間$O(\log N)$， メモリ使用量$O(N)$である．


\section{記号の定義}

$tf(d,x)$を，ドキュメント$d$に含まれる文字列$x$の個数と定義する．この論
文で扱う頻度は，$tf(d,x)$で定義できるものである．$cf(x)$は，文字列頻度と
呼ばれるものであり，$df(x)$は単純ドキュメント頻度と呼ばれるものである．


 \begin{itemize}

  \item $cf(x)$\ :\ ドキュメント集合中に文字列$x$が出現する数\\
$$    cf(x) = \sum_{d}tf(d,x)$$
  \item $df(x)$\ :\ 文字列$x$が1回以上出現するドキュメントの数\\
$$    df(x) = \mid \{ d | tf(d,x)\geq 1 \} \mid$$

 \end{itemize}

われわれが求めたい重複条件付きドキュメント頻度も$tf(d,x)$から
求められるものである．
 \begin{itemize}
  \item $df_k(x)$\ :\ 文字列$x$が$k$回以上出現するドキュメントの数\\
$$    df_k(x) = \mid \{ d | tf(d,x)\geq k \}\mid$$
  \end{itemize}

\section{Suffix Array}

クラス分けのために，Suffix Arrayというデータ構造を用いる．
Suffix Arrayは文献\cite{SUFFIX}によって示されたデータ構造である(図\ref
{suffix_array})．このデータ構造はあるテキストがあったときに，そのテキス
トのすべての文字からテキストの終了までの文字列(suffix;接尾辞)の集合を
考え，その集合を辞書順に並べたものである．
ここで，テキストの本体がメモリにあるとすると，一つの文字列を格納するのに，
文字列の開始場所という一つの整数を格納すれば良い．このため，任意の部分文
字列の場所を知ることができるにもかかわらず，必要な記憶容量は$O(N)$で済む．
Suffix Arrayは以下のルーチンで生成できる．

 \begin{center}
  \begin{verbatim}
  /* size: コーパスの文字数, text: コーパスの先頭を指すポインタ */
  int suffix_compare(struct suffix_struct * x, struct suffix_struct * y)
  {
    return strcmp(text + x->position, text + y->position);
    /* x->position,y->positionはそれぞれx,yに対応する場所を指すポインタ */
  }

  for(i=0;i<size;i++) { suffix[i].position = i; }
  qsort(suffix, size, sizeof(struct suffix_struct),
        suffix_compare);
  \end{verbatim}
 \end{center}

ドキュメント頻度を計算する場合，ドキュメントの長さに上限があれば
コーパス中の文字列はドキュメント毎に区切られていると見なすことができる．
この条件の下で上記のアルゴリズムを使ってデータ構造を作成するためには，
$O(N \log N)$時間必要である．\par


 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=9cm
   \epsfbox{suffix_array.eps}
   
   \caption{Suffix Arrayのサンプルとある文字列の出現場所の特定}
   \label{suffix_array}
  \end{center}
 \end{figure}


\section{文字列のクラス分け}

文字列の文献\cite{DF1}の文字列のクラス分けの方法を使用するが，この論文で
は，重複条件付きドキュメント頻度を求める場合にもクラス分けを使用できるこ
とを述べる．クラス分けはsuffixを用いて定義される．Suffix Arrayのsuffixは
辞書順に並んでいるので，文字列の先頭部分が次のsuffixと共通であることが多
い．そこで，$common[i]$を$suffix[i]$と$suffix[i+1]$の文字列の先頭からの
共通部分とする．文献\cite{DF1}のクラスの定義を下に示す．\par

ここで，定義の記述を簡単にするため$j-1<i$の場合$min_{k=i}^{j-1}=∞$とする．
そして，$common[-1] = -1$，$common[N] = -1$とする．
区間の境界での$common$の大きい方である
$outgoing(i,j) = max(common[i-1],common[j])$
と定義し，区間内部での$common$の最小のもの
$inner(i,j)=min_{k=i}^{j-1}(common[k])$と定義する．\\
\par

\newpage
[定義]\par
区間$[i,j]$がクラスを形成するとは，
$inner(i,j) > outgoing(i,j)$であることをいう．\\
\par

$inner(i,j)$は区間全体で共通部分となる文字列の長さであり，
$inner(i,j)>outgoing(i,j)$であるとは区間を広げると全体で共通となる
文字列が短くなるという意味となる．

区間$[i,j]$がクラスを形成するとき，区間$[i,j]$に共通する「長さ
$outgoing(i,j)+1$から$inner(i,j)$までの部分文字列」の集合を，その区間に
対応する文字列のクラスと定義する．

図\ref{suffix_array_class}で，区間$[i,j]=[2,2]$，$[i,j]=[1,4]$，$[i,j]=[1,3]$
を見た場合，
 \begin{center}
  \[
  \begin{array}{lllllll}
 outgoing(2,2) & = & max(common[1],common[2])   & = & max(6,3) & = & 6\\
 inner(2,2)    & = & min_{k=2}^{1}(common[k])   & = & ∞\\
   \\
 outgoing(1,4) & = & max(common[0],common[4])   & = & max(2,0) & = & 2\\
 inner(1,4)    & = & min_{k=1}^{3}(common[k])   & = & 3\\
   \\
 outgoing(1,3) & = & max(common[0],common[3])   & = & max(2,6) & = & 6\\
 inner(1,3)    & = & min_{k=1}^{2}(common[k])   & = & 3\\
   \end{array}
  \]
 \end{center}
となり，区間$[2,2]$は$inner(2,2)>outgoing(2,2)$，区間$[1,4]$は
$inner(1,4)>outgoing(1,4)$となるのでクラスを形成するが，区間$[1,3]$は
$inner(1,3)<outgoing(1,3)$となるのでクラスを形成しない．

 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=7cm
   \epsfbox{suffix_array_class.eps}
   
   \caption{Suffix Array上の文字列のクラス}
   \label{suffix_array_class}
  \end{center}
 \end{figure}

文献\cite{DF1}によると，クラ
ス数は最大でも$2N-1$であり，その表は作成し記憶することが実際的
な大きさである．\\

\par
[$occurence(C)$の定義]\par
クラス$C$で定まる区間$[i,j]$について，集合${suffix[i],...,suffix[j]}$を
$occurence(C)$とする．$occurence(C)$は，出現場所を示す整数の集合となる．\\


\par
[性質1]\par
クラス$C$があったとき，$C$の任意の2要素$x$，$y$について，任意のドキュメン
トを$d$とすると，$tf(d,x) = tf(d,y)$である．\\


証明\par
$tf(d, x)$は，$d$の中に出現する$x$の個数であるが，
これは，$x$の出現する場所で，その場所がドキュメント$d$
に属する回数に等しい．$x$の出現する場所は，$x$の属するクラス$C$の
$occurence(C)$で求まる．$tf(d, x)$は，$occurence(C)$の
各要素である整数が，ドキュメント$d$に属しているかどうか
で求めることができる．つまり，
$x$の属する$C$について，$x$の出現する位置の集合$occurence(C)$
を求めて，それから$tf(d, x)$を決定できる．

ここで，$y$が$x$と
同じクラスの属していれば，両方とも$occurence(C)$が同じ
であるため，$tf(d,x) = tf(d, y)$となる．\\
\par

[性質2]\par
クラス$C$があったとき，$C$の任意の2要素$x$，$y$について，

 \begin{itemize}
  \item $cf(x)=cf(y)$
  \item $df(x)=df(y)$
  \item $df_k(x)=df_k(y)$
 \end{itemize}

が成立する．\\

証明\par

性質1より，$tf(d,x)=tf(d,y)$なので，$tf(d, x)$を
使用して定義できる頻度はすべて等しい．すなわち，

\par
$$cf(x) = \sum_{d}tf(d,x) = \sum_{d}tf(d,y) = cf(y)$$
$$df(x)  =\mid \{ d|tf(d,x)\geq 1 \}\mid
         =\mid \{ d|tf(d,y)\geq 1 \}\mid = df(y)$$
$$df_k(x)=\mid \{ d|tf(d,x)\geq n \}\mid 
         =\mid \{ d|tf(d,y)\geq n \}\mid = df_k(y)$$
\\

証明は単純であるが，$df_k(x)$の性質は未知であるため，同じクラス
に属する文字列について，その値が等しいことを示すことは必要である．

 
\section{クラスの階層関係}

クラスごとの頻度の表を高速に作成するために，クラス間の階層
関係を利用するが，まず，クラスの階層関係を定義する．

区間$[i_1, j_1]$がクラス$C_1$を形成し，区間$[i_2, j_2]$がクラス
$C_2$を形成していて，区間$[i_1,j_1]$が区間$[i_2, j_2]$に含まれ
ているとき，$C_1$は$C_2$の下位のクラスと定義する．また，$C_2$は
$C_1$の上位のクラスと定義する．\\

 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=7cm
   \epsfbox{class_kankei.eps}
   
   \caption{クラスの階層関係}
   \label{class_kankei}
  \end{center}
 \end{figure}


[性質4]\par
2つのクラス$C_1$，$C_2$に交わりがあったときには，$C_1$は$C_2$の
上位のクラスであるか$C_1$は$C_2$の下位のクラスであるかのどちらかである．\\


証明\par

$C_1$と$C_2$に交わりがあるということは，

 \begin{center}
  \[
   \begin{array}{lr}
    i_1 \leq i_2 \leq j_1 \leq j_2 & (1)\\
    i_2 \leq i_1 \leq j_2 \leq j_1 & (2)\\
    i_1 \leq i_2 \leq j_2 \leq j_1 & (3)\\
    i_2 \leq i_1 \leq j_1 \leq j_2 & (4)\\
   \end{array}
  \]
 \end{center}

のいずれかである．\par
$(1)$の場合，$i_1<i_2$であると仮定する．区間$[i_1,j_1]$では
$$ max(common[i_1-1],common[j_1]) < min_{k_1=i_1}^{j_1-1}(common[k_1]) $$
となるので，$common[j_1]<common[k_1]\ (i_1 \leq k_1 \leq j_1-1)$である．
一方，区間$[i_2,j_2]$では，$k_1=i_2-1$，$k_2=j_1\ (i_2 \leq k_2
\leq j_2-1)$となる$k_1$，$k_2$が存在する．従って，
$$common[k_1]=common[i_2-1]>common[k_2]=common[j_1]$$
となり，区間$[i_2,j_2]$は
$$ max(common[i_2-1],common[j_2]) < min_{k_2=i_2}^{j_2-1}(common[k_2]) $$
を満たさず，$i_1<i_2$の場合クラス$C_2$を形成しないので$C_1$と$C_2$に交わ
りはない．\par
$i_1=i_2 \leq j_1 \leq j_2$の場合はクラスの階層の定義より，$C_2$が$C_1$
の上位クラスである，または，等しいクラスである．\par
$(2)$も$(1)$と同様に証明できる．また，$(3)$の場合はクラスの階層の定義よ
り，$C_1$が$C_2$の上位クラスであるか等しいクラスであり，$(4)$の場合は，
$C_2$が$C_1$の上位クラスである，または，等しいクラスである．\par
以上より，2つのクラスに交わりがある場合は，一方がもう一方の上位クラス，
または，下位クラスとなる．\\


[性質5]\par
Suffix Arrayにおいて，すべてのsuffixはクラスによって階層構造を形成する．\\


証明\par

$common[-1]=common[N]=-1$より，最上位クラスは，すべてのsuffixを含むクラス
である．
また，性質4よりあるクラスが他のクラスの部分クラスでない限り交わることはない．
このとき，部分クラスでは上位クラスよりその区間が短くなる．\par
以上のことから，すべての文字列の出現場所は文字列クラスによって階層構造を
形成する．\\


[性質6]\par
任意の区間$[i,j]$について，$[i,j]$を含む区間でクラスを形成する区間がある．
\\

区間$[i,i]$において$outgoing(i,i)<∞$，$inner(i,i)=∞$なので，
$inner(i,i)>outgoing(i,i)$となり，区間$[i,i]$は1つのsuffixからなる最下位クラスを
形成する．\\

\par
証明\par
性質5より，Suffix Arrayのすべてのsuffixはクラスによって階層構造を形成する．
\\
\par
[記号]\par
任意の区間$[i,j]$について，それを含むクラスを形成する区間のうち，
もっとも下位のものを$[i,j]$から定まるクラスとし，$Class^{\ast}([i,j])$
と記述する．

任意の区間について，それを含むもっとも下位のクラスが一意に定まる
ことは，計算量を押さえたアルゴリズムを構成するときに
必要な性質である．$Class^{\ast}([i,j])$は，後述する頻度を計数する
ところで使用する．

\section{重複条件付きドキュメント頻度の計測における問題点}

すべてのクラスについて，それに属する文字列のドキュメント頻度を単純な方法
で求めるとすると，通常の計算機では実用上問題がある．クラスの大きさが高々
$2N$であったとしても，$df(x)$，$df_2(x)$，$df_3(x)$のように条件を満たす
集合を作って，その大きさを計測すると，各$x$の処理に$O(N)$時間かかり，
$x$が$N$個あれば，全体では$O(N^2)$時間必要となる．これは，コーパスの大き
さから考えて，通常の計算機では実行できない処理となる．\par

文字列の出現頻度であれば，クラス階層に従って頻度の合計を求めることが
できる．すなわち，下位のクラスの文字列頻度を合計して，上位の
文字列頻度とすることができる．言い換えれば，長い文字列の頻度
から，短い文字列の頻度をもとめることができる．
しかし，ドキュメント頻度は，直接寄せ集めることがで
きない．たとえば，図\ref{chofuku_df}のようなコーパスについて考える．文字
列abcは6回出現し，それが出現するドキュメントの数が4個である．また，文字
列abxは7回出現し，それが出現するドキュメントの数が5個である．このとき文
字列abに続く文字のパターンがabcとabxの2つだけであったとすると，
suffixの構造は図\ref{chofuku_df}に示されたような構造になる．
この状況で，abの出現回数は6+7回である．しかし，この状況で，abが出現す
るドキュメントの数は9個とはいえない．abcとabxが両方出現するドキュメント
を2個と数えることが間違いだからである．\cite{DF1}で示される
ように，単純なドキュメント頻度の計数であれば，重複して数えている
ところを差し引くという方法があるが，
ドキュメントを計測する条件が，その文字列が2回以上出現するドキュメント数
であった場合，クラスの上下によるドキュメント頻度の変化はさらに複雑になり，
重複を差し引くという方法は使用できない．

 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=12cm
   \epsfbox{chofuku_df.eps}
   
   \caption{重複がある場合のドキュメント頻度}
   \label{chofuku_df}
  \end{center}
 \end{figure}

\section{出現場所の重複条件}

重複条件付きドキュメント頻度の計測行う準備として，この論文で新しく使用す
る「文字列の出現場所ごとの重複条件」を定義する．

重複条件付きドキュメント頻度の計測のために，クラス階層で寄せ集められる数を
定義し，その数の関数として重複条件付きドキュメント頻度を求めることを行う．
ここで使用する頻度を定義するために，文字列の出現場所の重複度と重複条件
を使用する．

すべての文字列の出現場所は，Suffix Array内の配列の番号で順序づけることが
できる．この順序をsuffix順と定義し，これを利用して文字列の出現場所の重複
条件と重複度を定義する．\\

[定義]\par
ある文字列$x$の出現場所の重複度が$k$であるとは，suffix順でその出現場所以
下の場所で，かつ同一のドキュメントに属する文字列$x$の出現場所が$k$個ある
こととする．\\
\par

図\ref{chofuku}に重複度の例を示す．\par
suffix順でabx(suffix[3])以下の場所にあるのは，abc(suffix[0])と
abd(suffix[1])，abe(suffix[2])，abx(suffix[3])である．ここで，文字列abx
についてdocument\#1での文字列abの重複度$k$を求めると，ドキュメント中に文字列
abc，abd，abxが出現するので，$k=3$である．\\

 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=10cm
   \epsfbox{chofuku.eps}
   
   \caption{重複度$k$}
   \label{chofuku}
  \end{center}
 \end{figure}

[性質7]\par
文字列$x$がドキュメント$i$に$t$個出現するとき，$t$個の出現場所について，
すべて重複度を求め，それをsuffix順に並べると$1,...,t$となる．


\section{重複条件付き文字列頻度}

[記号]\par
$x$を文字列としたとき，重複条件付き文字列頻度$cf_k(x)$と
重複条件付きドキュメント文字列頻度$tf_k(d,x)$と書く．\\

[定義]\par
 $cf_k(x)$はコーパス中で，重複度が$k$以上の文字列$x$の出現数とする．\\

[定義]\par
 $tf_k(d,x)$はドキュメント$d$中で，重複度が$k$以上の文字列$x$の
出現数とする．\\

[性質8]
$$\forall x,y\in C,\ \forall k; \forall d; \ tf_k(d, x)=tf_k(d, y)$$\\

文字列$x$の属するクラスを$C$とする．
重複度は，場所と文字列に関係するので注意が必要であるが，suffix順
で順番をつけるので，$occurence(C)$が定まれば，それぞれの
要素についての重複度が一意に定まる．したがって，
$tf_k(d, x)$は$tf(d,x)$と同様に$d$と$occurence(C)$の関数となる．


\section{重複条件付き文字列頻度とドキュメント頻度の関係}

ドキュメント頻度と重複条件付き文字列頻度には下の単純な関係がある．\\

[定理\ \ 文字列頻度とドキュメント頻度の関係]
$$  df_k(x) = cf_{k}(x) - cf_{k+1}(x)$$

証明\par

$tf(d,x) = t$ のとき，$k \leq t$について，
$$ tf_{k}(d,x) - tf_{k+1}(d,x) = 1$$

$tf(d,x) = t$ のとき
$tf_t(d,x) = 1$, $tf_{t+1}(d,x)=0$, $tf_{t+2}(d,x)=0$, 以下0が続くので，
$k>t$について，
   $$tf_{k}(d,x) - tf_{k+1}(d,x) = 0$$

$cf_k(x) = \sum_{d} tf_k(d,x)$であるので，
\begin{eqnarray*}
 cf_{k}(x) - cf_{k+1}(x)
     &=& \sum_{d}(tf_{k}(d,x) - tf_{k+1}(d,x))\\
     &=& \mid \{ d | tf(d,x) \geq k \} \mid\\
     &=& df_k(x)\\
\end{eqnarray*}

あるテキストにおいて，$cf_k$と$df_k$を実際に求めた例を図\ref{df_cf}に示
す．
\par
図\ref{df_cf}の3つのドキュメントで，文字列abについて$cf_k$，$df_k$
を求める．まず，$cf_k$を計算する．$tf(1,ab)=7 \leq 8$，
$tf(3,ab)=6 \leq 8$である，ドキュメント\#1，\#3は，重複度$k \geq 8$と
なる文字列abが存在しないため，$cf_8$の数え上げに関係しない．
ドキュメント\#2では，$tf(2,ab)=8$であるので重複度$k \geq 8$となる
文字列abが一つだけ($tf-k+1=1$)存在する．したがって，$cf_8(ab)=1$．
同様に，$cf_7(ab)$は，$tf(1,ab)-k+1=7-7+1=1$，$tf(2,ab)-k+1=8-7+1=2$
となり，ドキュメント\#1，\#2によってそれぞれ1と2がカウントアップ
されるので，$cf_7(ab)=1+2=3$となる．他も同様である．
この様に$cf_k$が求められたので，定理「文字列頻度とドキュメント頻度の
関係」を用いることで，$df_k$を計算できる．

 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=10cm
   \epsfbox{df_cf.eps}
   
   \caption{重複条件付き文字列頻度とドキュメント頻度}
   \label{df_cf}
  \end{center}
 \end{figure}

[性質9]\par
あるクラス$C$があったとき，その要素$x,y$については任意の$k$について，
$$cf_k(x) = cf_k(y)$$


証明\par
$cf_k(x) = \sum_{d}tf_k(d,x)$，$tf_k(d,x)=tf_k(d,y)$なので，
$$cf_k(x) = \sum_{d}tf_k(d,x) = \sum_{d}tf_k(d,y) = cf_k(y)$$


\section{重複度判定のためのデータ構造}

ここでは重複度を判定するためのデータ構造であるpreviousリンク(文献[DF1])
について説明する．

previousリンクはそれぞれのsuffixについて，同じドキュメントに属し，
かつsuffix順で前にある最も近いsuffixの順位を記録しておく．
もしそのような場所がなければ，-1をpreviousリンクとする．
このデータ構造はコーパスの大きさに比例した大きさのメモリ領域である．
\par

文字列$x$のある出現重複度が$k$以上であることの判定は，その出現場所から
previousリンクを$k$回たどれるかどうかと，たどれる場合，その文字列が
まだ出現しているかを計測することで判定できる(図\ref{chofuku_struct})．\par

 \begin{figure}[htbp]
  \begin{center}
   \epsfxsize=12cm
   \epsfbox{chofuku_struct.eps}
   
   \caption{重複度判定のためのデータ構造}
   \label{chofuku_struct}
  \end{center}
 \end{figure}

このデータ構造を作るには，ドキュメント数と同数の整数配列を用意して，
それぞれの文字列の出現ごとに，ドキュメントの番号を求め，その配列から
previousリンクの場所の情報を求めると同時に，
その表を現在の場所に更新すればよい．
\par
previousリンクを作成するプログラムは以下のような構造になる．
このデータ構造を作成するには，ドキュメント数と同じメモリ領域を用意し，
コーパス全体を一度スキャンすることになる．

\begin{verbatim}
 /* id_max: ドキュメント数， size: コーパスの文字数 */
  for(i=0;i<id_max;i++) { last_suffixes[i] = -1; }
  for(i=0;i<size;i++) {
    suffix[i].previous_suffix = last_suffixes[suffix[i].id];
    last_suffixes[suffix[i].id] = i;
  }
\end{verbatim}

重複度判定は，このpreviousリンクを$k$回たどることができ，
かつその文字列が同じドキュメントにあるかどうかで判定できる．

(注)実際のプログラムでは，計算量を押さえるため，単純に重複度を
判定せず，この重複度の判定と別の処理を同時に行っている．

\section{クラス検出のアルゴリズム}
クラスを検出するアルゴリズムの概略は以下のように行う．

\begin{enumerate}
 \item Suffix Arrayをsuffix順が小さいものから見て行く．
 \item クラスの開始場所を見つける．
 \item クラスの終了場所を探す．
       \begin{itemize}
        \item クラスは階層構造になっているため，そのクラスの終了場所が
              見つかる前に，他のクラスの開始場所が見つかることがある．
              この場合は，スタックにその開始場所をプッシュする．
        \item クラスの終了場所が見つかれば，報告しスタックを回復する．
       \end{itemize}
\end{enumerate}

上記のアルゴリズムでクラスを求めていったとき，求めるクラスの先頭が発見で
きていて，まだ，その終りが発見できていないクラスを計算中のクラスと呼ぶ
ことにする．アルゴリズムでは，スタック中のクラスを現在計算中のクラスとする．
\par 

$common[i]$はコーパスの文字列と同じ大きさの配列で，Suffix Arrayで次
のsuffixと文字列が一致している長さである．
この文字列はドキュメントの長さを越えることはなく，
したがって，計算量のオーダを増やすことはない．\par

文字列のクラスは，$common[i]$の増減にしたがっている．$common[i]$が
増加したときは，現在計算中のクラスを計算終了していないクラスとして
登録し，新しいクラスが開始したものとして処理する．\par

$common[i]$が減少しているときは次の2つのケースがある．

 \begin{itemize}
  \item 現在のクラスは終了するが，実は現在のクラスと同じsuffixの場所
        から始まったクラスが，現在のクラス以外にもある場合．
  \item 現在のクラスを終了し，スタックトップのクラスの処理を
	継続しなければならない場合．
 \end{itemize}

2番目のケースで，スタックトップの計算途中のクラスの処理を継続する
ときには，このクラスがすぐに終了しているかどうかの検査から
処理を継続する．


クラスの発見をするには$common[i]$ごとに，クラス終了判定の操作を行うこ
とになる．2番目のケースでは，計算途中のクラスの数だけ
繰り返しが起きるのだが，その繰り返しの数を合計しても
クラスの最大数を越えることはない．したがって，
クラスの最大数と$common[i]$の個数からこの操作は$O(N)$で完了でき
る．\par


現在計算中のクラスについて，以下の性質が成り立つ．\\

[性質10]\par
現在計算中のsuffixから始まり，ドキュメントの区切りまでの文字列を
属するクラス毎に分類すると，そのクラスは現在計算中のクラスとなる．

\section{単純な重複条件付き文字列頻度の計数}

重複度$k$が与えられていたとき，すべての文字列$x$に対して重複度が$k$以上
である$cf_k(x)$を求めることを考える．重複度は文字列と場所の関数であるが，
同一クラスに属する文字列の重複度が異なることはない．また，同一クラスに属
する文字列について，$cf_k(x)$は等しい．そこでクラスの数だけのカウンタを
用意し，各suffixについて処理を行なうことでも計数できる．これを単純な方法
とよぶ．この方法はメモリ領域$O(N)$であるが，計算時間が問題となる．

\par

計数の方法は，ある場所について，そこから始まるクラスの集合を求め，すべて
のクラスに対してカウンタを用意し，クラス毎に重複度が$k$以上であるかを判
定して，カウンタに1を加えるというものである．この方法を単純に行うと，一
つのsuffixに関連するクラスが多数になり得るため，$O(N \log N)$以下の計算量
では収まらない場合がある．具体的には同じ文字が長く連続するようなデータが
このケースになる．

\par

\section{重複条件付き文字列頻度の計数}

重複条件付き文字列頻度の計数を単純な方法で行うと，一つのsuffixに対し，そ
れが含まれるクラスをすべて求め，そのクラスのすべてに対してカウンタの更新
を行わなければならない．しかし，以下の性質を利用することですべてのクラス
に対しカウンタを更新することを避けられる．\\

[性質11]\par
ある場所が与えられたとき，そのsuffixの先頭の文字列に対応するクラスの集
合が求められるが，そのクラスには一意の階層関係がある．\\

[性質12]\par
ある場所が与えられたとき，そこのsuffixの先頭の文字列に対応するクラスのう
ち，あるクラスの文字列について重複度が$k$であったとすると，そのクラスより
上位のクラスの重複度は$k$以上である．\par

この２つの性質のため，カウンタの加算を一つのsuffixと一つの重複度$k$に
に対して一つにすることができる．つまり，あるsuffixで重複度$k$以上となるクラ
スのうち，最下位のクラスのカウンタだけを加算しておき，下位クラス
の計数が終了したときに，上位のクラスのカウンタにその計数値を加算していく
ことで，すべてのクラスの計数値を得ることができる．

\section{クラスの発見と頻度計算}

\subsection{クラスの始まりを発見したときの処理}
あるクラスの始まりは$common[i]$が増加したことで発見できる．
このとき，現在計測している重複条件付き文字列頻度の情報は
ほかのクラスの情報と同様にスタックに待避させ，
重複条件付き文字列頻度は0に初期化して
新たに計数する．

\subsection{重複度判定とクラス選択の融合}

ある場所で，重複度が$k$より大きいクラスのなかで最も下位のクラスを
特定する操作は，重複度判定と融合することができる．重複度の判定はprevious
リンクを$k$回たどった場所$i$と，現在の場所$j$の区間が一つのドキュメント
に含まれるかどうかで行うので，逆にその区間を含むクラスの集合を求めておき，
その中で$Class^{\ast}([i,j])$を求めることができる．\par

この操作は，さらにクラスの検出と同時に行うことができる．これは，
「ある場所で，重複度が$k$より大きい$Class^{\ast}([i,j])$」
を定める区間$[i,j]$が，現在の場所$j$を終りに持つため，
検出の途中では計算未終了のクラスとなっていることを利用する．\par

具体的には，まず，previousリンクを$k$回たどったところにある文字列の
出現を求める．次に，その出現場所と最初の出現場所を含む文字列から，共通
かつ計算中の$Class^{\ast}([i,j])$を特定する．
そのクラスの重複条件付き文字列頻度を加算する．


\subsection{クラスの終了を発見したときの処理}

あるクラスの終了は$common[i]$が減少することで発見できる．
このとき，上位クラスへ計数の値を伝える処理をする．
下位クラスの計数が終了したときに上位クラス
のカウンタに，その計数値を加算することで，結果的にすべてのクラスに加算す
るのと同じ値を得ることができる．

\section{実行例}

サンプルとして処理するデータは以下のファイルである．
一行が一つのドキュメントになっている．

\begin{verbatim}
abcabcabc
abcd
abcde
bcde
\end{verbatim}

\subsection{Suffix Arrayの作成とクラス検出の準備}

第一段階では，Suffix Arrayを作成し，commonをもとめ，Previous Linkを
作成する．例に対しては以下のようなデータが作成される．

先頭から，
\begin{itemize}
 \item suffixの番号
 \item suffixが属するドキュメントの番号
 \item 同じドキュメントに属しているsuffixで，直前に現れたものの番号
 \item 直後のsuffixと「先頭から一致している文字列」の長さ
\item そのsuffixの文字
\end{itemize}
である．

\begin{verbatim}
    0   0    -1  0:
    1   1    -1  0:
    2   2    -1  0:
    3   3    -1  0:
    4   0     0  3:abc
    5   0     4  6:abcabc
    6   0     5  3:abcabcabc
    7   1     1  4:abcd
    8   2     2  0:abcde
    9   0     6  2:bc
   10   0     9  5:bcabc
   11   0    10  2:bcabcabc
   12   1     7  3:bcd
   13   2     8  4:bcde
   14   3     3  0:bcde
   15   0    11  1:c
   16   0    15  4:cabc
   17   0    16  1:cabcabc
   18   1    12  2:cd
   19   2    13  3:cde
   20   3    14  0:cde
   21   1    18  1:d
   22   2    19  2:de
   23   3    20  0:de
   24   2    22  1:e
   25   3    23  0:e
\end{verbatim}









\subsection{求められたクラスの表の例}

本文で説明した方法で，$cf$が2より大きなクラスを求める．
これを，クラスの先頭の場所を第1キー，
長さを第2キーにしてソートし，同時に，重複条件付き文字列頻度から，文書頻度に
変換する．その結果は，以下のようになる．この例では，$cf$が2より大きなクラス
は全部で14個ある．クラスごとに，対応する区間，次に長さ，それぞれのクラス
に対する統計値とクラスを代表する文字列となっている．
クラスを代表する文字列とは，そのクラスのなかで最長の文字列である．
この中には，区間の大きさが1のクラスは含まれていない．

この情報の中にはクラスに含まれる最短の文字列が何であるかという情報が
含まれていない．そのような文字列は，クラスを代表する文字列と先頭から
比較していき，最も長く一致するものの中で最も上位のクラスの情報を
取り出すことで対処している．

クラスのソートで，区間の先頭を第1キーにすることで
ほぼ辞書順に並ぶ．
区間の先頭が同じ場合には，長さが短い
ほうが優先されることで，結果として
クラスの代表する文字列は辞書順に並ぶ．

\begin{verbatim}
total=14
Class[   4,   8] L=3 tf=5 df1=3 df2=1 df3=1 df4=0 S="abc"
Class[   5,   6] L=6 tf=2 df1=1 df2=1 df3=0 df4=0 S="abcabc"
Class[   7,   8] L=4 tf=2 df1=2 df2=0 df3=0 df4=0 S="abcd"
Class[   9,  14] L=2 tf=6 df1=4 df2=1 df3=1 df4=0 S="bc"
Class[  10,  11] L=5 tf=2 df1=1 df2=1 df3=0 df4=0 S="bcabc"
Class[  12,  14] L=3 tf=3 df1=3 df2=0 df3=0 df4=0 S="bcd"
Class[  13,  14] L=4 tf=2 df1=2 df2=0 df3=0 df4=0 S="bcde"
Class[  15,  20] L=1 tf=6 df1=4 df2=1 df3=1 df4=0 S="c"
Class[  16,  17] L=4 tf=2 df1=1 df2=1 df3=0 df4=0 S="cabc"
Class[  18,  20] L=2 tf=3 df1=3 df2=0 df3=0 df4=0 S="cd"
Class[  19,  20] L=3 tf=2 df1=2 df2=0 df3=0 df4=0 S="cde"
Class[  21,  23] L=1 tf=3 df1=3 df2=0 df3=0 df4=0 S="d"
Class[  22,  23] L=2 tf=2 df1=2 df2=0 df3=0 df4=0 S="de"
Class[  24,  25] L=1 tf=2 df1=2 df2=0 df3=0 df4=0 S="e"
\end{verbatim}

\subsection{文字列に対する処理}

与えられた任意の文字列に対して，上記の表を二分探索することで
$tf， df_1(=df)， df_2， df_3， df_4$を求めることができる．
二分探索であり，表の大きさは$O(N)$であるので，
この処理は$O(\log N)$で終了する．

\begin{verbatim}
abc                -- Class[4,8]に該当（代表文字列）
5 3 1 1 0 abc
abcabc             -- Class[5,6]に該当（代表文字列）
2 1 1 0 0 abcabc
abcd               -- Class[7,8]に該当（代表文字列）
2 2 0 0 0 abcd
abca               -- Class[5,6]に該当（代表文字列でない）
2 1 1 0 0 abca
abcab              -- Class[5,6]に該当（代表文字列でない）
2 1 1 0 0 abcab
abcabc             -- Class[5,6]に該当（代表文字列）
2 1 1 0 0 abcabc
abcabca            -- 表になく，コーパスに存在する
1 1 0 0 0 abcabca
abcabcab           -- 表になく，コーパスに存在する
1 1 0 0 0 abcabcab
abcabcabc          -- 表になく，コーパスに存在する
1 1 0 0 0 abcabcabc
abcabcabca         -- 表になく，コーパスに存在しない
0 0 0 0 0 abcabcabca
\end{verbatim}


\section{実行時間の計測}

実行時間の計測は，どのようなドキュメントを用いても良いが，ここでは，
技術用語のアブストラクトの集合を使用した．そこからアブストラク
トの本文だけを抜き出し，一行を一つのドキュメントに整形したものである．
332,918文書，69,312,280文字，130,993,215バイトのコーパスである．測定には，
Athlon MP 1.2Mhz，3G Byte メモリのシステムを使用した．


\subsection{ボトムラインシステム}

最初の比較対象のシステムは，一番単純な方法で計測した場合である．文字列と
重複度$k$が与えられたときに，$k$のドキュメント頻度をは，コーパスの先頭から順
番に見るという方針で求めるものである．具体的には，以下のようなプログラム
で求める．これば，クラス分けもクラスの階層構造も利用しないシステムとなっ
ている．このシステムは定義が単純であるため速度の比較だけでなく，プログラ
ムの動作の正答を用意し，提案するシステムが正しく動作していることの確認
にも使用した．このシステムを{\tt linear}と呼ぶことにする．


\begin{verbatim}
/* s1の先頭がs2で始まっているかどうかを検査する関数 */
static int string_sub(char *s1, char *s2)
{ 
  while(*s2) {
    if(*s1 != *s2) { return 0; }
    s1++;
    s2++;
  }
  return *s1;
}

/* 改行までの間に，文字列がk回出現するかどうか調べ，
   出現した回数をカウントする回数． */
int dfn(int k, char *s)
{ 
  int i; /* string position */
  int t; /* term frequency in a document */
  int n; /* document frequency */
  n = 0;
  t = 0;
  for(i=0;i<size;i++) {
    if(string_sub(&text[i], s)) t++;
    if(text[i]=='\n') {
      if(t>=k) n++;
      t = 0;
    }
  }
  return n;
}

\end{verbatim}

\subsection{ベースラインシステム}

ベースラインシステムは，クラス分けを使用して
いるが，表を作成するときにクラスの階層構造を
使用しないシステムである．クラスの検出のあと，
下のCのプログラムを使って，$df_1$から$df_5$
までを同時にもとめて表にする．このシステムを
{\tt base}と呼ぶことにする．

\begin{verbatim}
/* 重複条件付きドキュメント頻度を一斉に求める関数
   結果は，staticな配列に保存する．
*/
static int dfn[MAX_C];
static void count_dfn(char *s, int len)
{ 
  int i; /* string position */
  int t; /* term frequency in a document */
  int n; /* document frequency */
  int k;
  n = 0;
  t = 0;
  for(k=0;k<MAX_C;k++) { dfn[k]=0; };
  for(i=0;i<size;i++) {
    if(strncmp(&text[i], s, len)==0) t++;
    if(text[i]=='\n') {
      for(k=0;k<MAX_C;k++) {
        if(t>k) dfn[k]++;
      }
      t = 0;
    }
  }
}
\end{verbatim}

\subsection{提案システム}

提案するシステムはこの論文で記述した方法を用いたものであり，
クラスの表を作成し，表の数値を計数するときに，クラスの階層
の性質を使用したものである．
このシステムを{\tt class}と呼ぶことにする．

\subsection{計測}

実験は，10個のドキュメントのなかに含まれる文字列頻度が3をこえるすべての
文字列について，$cf$，$df_0$，$df_1$，$df_2$，$df_3$，$df_4$，$df_5$を求
めることを行った．コーパスの文字数$N$による効果を測定するために，
使用するコーパスを，先頭から，316ドキュメント，
1000ドキュメント，3162ドキュメント，10000ドキュメント，
31623ドキュメント，100000ドキュメント，
332918ドキュメントと変化させた実行時間を計測した．
実行時間は，前処理の時間と，重複条件付きのドキュメント頻度を求める時間とに
分けて計測した．表\ref{実行時間}に{\tt linear}，{\tt base}，{\tt class}
の実行時間を示す．
表\ref{実行時間}の中の時間は，処理装置の使用時間を秒で示したもので
ある．また，すべてのプログラムが同一の頻度を出力することも確認した．

重複条件付きドキュメント頻度の分析対象とした文字列は，10ドキュメント，
4156バイト，2190文字の部分文字列で，統計的に安定な頻度が3を越える文字列
である．この文字列の数は，コーパスが大きくなるにつれ増加するが，その増加
は緩やかである．

{\tt linear}システムは，前処理は必要なく，前処理の時間はテキストを読む時間だけ
である．この計測ではファイル処理の時間は除外しているので，前処理の時間は
0.0となる．{\tt linear}システムは直ちに結果を出力し始めるがコーパスのドキュメ
ント数が増加することに比例して一つあたりの分析時間が大きくなっていく．
10個のドキュメントの分析という小さな問題であっても，実用的に使用できるの
は，ドキュメントの数が１万程度までである．

{\tt base}システムは，分析時間は高速になるが，前処理に$O(N^2)$の時間が
かかることが観測される．
実用的に使用できるのは，ドキュメントの数が数千個程度までである．

提案するシステム({\tt class})の実行時間は，実データにおいて，
前処理$O(N \log N)$となっている．
そして，分析時間を分析対象の文字数で割ることで求められる1文字列あ
たりの時間は，最大でも0.036ミリ秒であり，
1000ドキュメントより大きなコーパスにおいて，$O(\log N)$と
なっている．332,918ドキュメントの前処理の時間は1223.4と$O(N\log N)$に比べ
て大きい．ほかに比べて増加しているのは，実験に使用したコンピュータの
実装メモリに近いプロセスの大きさになったためだと考えられる．

以上，クラス分けによる表の作成と，クラスの階層構造を利用すること
によって，はじめて10万を越えるドキュメント数に対して分析が
できるようになったことがわかる．

\begin{table}[htbp]
\begin {center}
\begin{tabular}{|r|r|r|}
\hline
ドキュメント数&コーパス文字数&文字列個数\\ \hline
	316&   66547&	 6119\\
	1000&  221457&	 6957\\
	3162&  724945&	 8018\\
	10000& 2336198&  9189\\
	31623& 6862825& 10349\\
	100000&20095547&11214\\
	332918&69312280&12270\\ \hline 
\end{tabular}
\vspace*{3mm}
\\
\begin{tabular}{|r|rr|rr|rr|}
\hline
{ドキュメント数}&
\multicolumn{2}{|c|}{linear\ [sec]}&
\multicolumn{2}{|c|}{base\ [sec]}&
\multicolumn{2}{|c|}{class\ [sec]}\\
&前処理&分析&前処理&分析&前処理&分析\\ \hline
316&  0.0&  89.2&  81.4&0.10&  0.3 &0.10\\ 
1000& 0.0& 312.3& 891.6&0.14&  1.1 &0.14\\ 
3162& 0.0&1173.8&9802.6&0.19&  4.4 &0.19\\ 
10000&0.0&4315.8&    - &  - & 17.5 &0.26\\
31623& - &    - &    - &  - & 59.9 &0.31\\
100000&- &    - &    - &  - &202.6 &0.38\\
332918&- &    - &    - &  - &1223.4&0.44\\ \hline
\end{tabular}
\vspace*{2mm}
\caption{実行時間の計測}
\label{実行時間}
\end{center}
\end{table}

\vspace*{4em}
\subsection{メモリ容量負荷}

プログラムで使用するメモリの量を示すために，
実行しているプロセスの大きさを計測する．
これを表\ref{プロセス}に示す．
計測では分析する重複度の上限は5に設定している．

表\ref{プロセス}より，提案するシステムのメモリ負荷は，
$O(N)$となっていることがわかる．そして，
表の作成に，1クラスあたり100バイト，
表の検索に，1クラスあたり 50バイト使用している
ことがわかる．表の検索のプログラムは，
クラス分けの表とSuffix Arrayを保持しており，
プロセスの大きさの主要な部分は，その大きさである．
表を作成するには，クラス検出のためのデータ
構造や，重複度判定のためのデータ構造などが
あり，分析処理よりもメモリを多く必要とする．

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|l||r|r|r|r|}
\hline
ドキュメント数     &      10000&   31623&   100000&   332918\\
\hline
$cf>2$のクラスの数 &     787844& 2303978&  6815815& 24018652\\
表の作成プロセス   &        80M&    234M&     626M&    2366M\\
分析処理プロセス   &        40M&    116M&     333M&    1175M\\
\hline
\end{tabular}
\vspace*{2mm}
\caption{メモリ使用量の計測}
\label{プロセス}
\end{center}
\end{table}

\newpage

\section{そのほかの応用}

任意の文字列について，前処理の後に$O(\log N)$で重複条件付きドキュメント
頻度の分析を行うことは，文字列の統計処理の基本技術であり，ここで述べた単
語の境界の分析以外にも応用範囲がある．

\subsection{情報検索への応用}

日本語，中国語などの情報検索では２文字の文字列に対して，ドキュメント頻度
を計測して，2文字に対して情報検索の重みを計算することが行われている．
$df_2(x)/df_1(x)$は，Adaptationと呼ばれる量で，ドキュメントの確率という
空間において，ドキュメントにある文字列が出現するということを条件としたと
き，そのドキュメントに2回文字列が出現する確率の推定値である．文献
\cite{DF2}は英語において，その確率が統計的に単語の性質を識別できることを
示している．この量を使って検索対象の文字列を区分けすると検索精度が向上
するという報告\cite{IR}がある．あらかじめ表を作成するのが難しいため，こ
の報告の処理対象は2文字に限られていたが，ここで述べた方法を使っ
て，任意の長さの文字列から検索に効果のある文字列を選びだし，情報検索の性
能を向上させるのは有望な応用の一つだと考えられる．

\subsection{遺伝子情報への応用}

文献\cite{Keyword}は，自然言語で書かれたドキュメントを分析対象として，辞
書を使わず，重複条件付きドキュメント頻度からキーワードを抽出していたが，こ
れは「あるドキュメントに繰り返し現れる文字列」を効果的に取り出すシステム
と解釈できる．これを遺伝子情報に適用して，「遺伝子に繰り返し現れるDNA配
列」を検出するのは有望な応用の一つと考えられる．遺伝子の長さを考えると，
ここで示した方法をつかってはじめて，遺伝子のドキュメント頻度の分析ができ
るようになると考えられる．

\subsection{プログラミングツールへの応用}

文献\cite{TOOL}は，文字列の頻度を分析して，プログラム中にまれにしか現れ
ない文字列を検出し，それがプログラムの欠損の判定に効果があることを示して
いる．このツールにおいて，使用しているのは文字列の総出現頻度だけであるが，
重複条件付きドキュメント頻度はプログラム中の構造がより精密に判定できる情報
源である．あらたな情報が提供されれば，このようなツールの検出性能が向上す
ることが期待できる．

\section{まとめ}

この論文では，重複条件付きドキュメント頻度の性質を述べたあと，それを前処理
で表にする方法を述べた．その経過において，まず，出現場所の集合という
概念を示すことで，既存のクラス分けの方法が重複条件付きドキュメント頻度の
計数に使えることを述べた．次に，クラスの階層関係を利用して計数できる重複
条件付文字列頻度を説明し，それを用いて重複条件付きドキュメント頻度の表を構
成できることを述べた．最後に，クラス分けの効果とクラスの階層構造の利用が
処理に効果があることを，332,918個のドキュメントをもつコーパスで検証し，ド
キュメントの長さを$N$とするとき，前処理の処理時間が$O(N \log N)$であり，
表を引く処理が$O(\log N)$であることを確かめた．最後に，実行中のプロセス
の大きさを調べることでメモリの負荷が$O(N)$であることを確認した．そして，
この方法で10万を越える数のドキュメントについて，任意文字列に対する重複度
付きドキュメント頻度の分析を行えたことを報告する．

\acknowledgment
本研究は平成14年度IPA未踏ソフトウェア創造事業のプロジェクトの一部であり，
住友電気工業株式会社の援助による成果です．また，AT\&T\ Kenneth W. Church
氏，つくば大学\ 山本幹雄氏にはクラスシステムについて，直接，教えて頂きま
した．深く感謝します．



\bibliographystyle{jnlpbbl}
\bibliography{369}

\begin{biography}
\biotitle{略歴}
\bioauthor{梅村 恭司}{
1983年 東京大学大学院工学系研究科情報工学専攻修士課程修了．
同年，日本電信電話公社電気通信研究所入所．
1995年豊橋技術科学大学工学部情報工学系助教授，
現在に至る．
博士(工学)，記号処理，統計言語処理，システムプログラムの研究に従事
ACM，ソフトウェア学会，電子情報通信学会，計量国語学会各会員．}
\bioauthor{真田 亜希子}{
1978年生．2001年豊橋技術科学大学工学部情報工学課程卒業．
同年豊橋技術科学大学大学院工学研究科情報工学専攻修士課程入学，
現在に至る．}

\bioreceived{受付}
\biorevised{再受付}
\bioaccepted{採録}
\end{biography}

\end{document}
