\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=1k=2k=3k=4k=5文字列52424223241111761563419メ463222001221707392メデ458021781211699388メディ443421311195692382メディア560881540メディアを8312000メディアを用8312000メディアを用い646000メディアを用いた\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\logN)$で，クラスごとの重複条件付きドキュメント頻度の表を作ることができることを示す．そのときに，重複条件付き文字列頻度という概念を提案し，重複条件付き文字列頻度の関数として重複条件付きドキュメント頻度が求まることを示す．最後に，実際に動作するシステムを作成し，332,918個のドキュメントで，69,312,280文字からなるコーパスで計測した計算時間を示す．ここで示すアルゴリズムは，$k$を固定したとき，ある文字列が$k$回以上出現するドキュメントの数を数え上げる問題について，ドキュメントの全文字数を$N$とすると，前処理は計算時間$O(N\logN)$，メモリ使用量$O(N)$であり，その後に値を求めるときには計算時間$O(\logN)$，メモリ使用量$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)\geq1\}\mid$$\end{itemize}われわれが求めたい重複条件付きドキュメント頻度も$tf(d,x)$から求められるものである．\begin{itemize}\item$df_k(x)$\:\文字列$x$が$k$回以上出現するドキュメントの数\\$$df_k(x)=\mid\{d|tf(d,x)\geqk\}\mid$$\end{itemize}
\section{SuffixArray}
クラス分けのために，SuffixArrayというデータ構造を用いる．SuffixArrayは文献\cite{SUFFIX}によって示されたデータ構造である(図\ref{suffix_array})．このデータ構造はあるテキストがあったときに，そのテキストのすべての文字からテキストの終了までの文字列(suffix;接尾辞)の集合を考え，その集合を辞書順に並べたものである．ここで，テキストの本体がメモリにあるとすると，一つの文字列を格納するのに，文字列の開始場所という一つの整数を格納すれば良い．このため，任意の部分文字列の場所を知ることができるにもかかわらず，必要な記憶容量は$O(N)$で済む．SuffixArrayは以下のルーチンで生成できる．\begin{center}\begin{verbatim}/*size:コーパスの文字数,text:コーパスの先頭を指すポインタ*/intsuffix_compare(structsuffix_struct*x,structsuffix_struct*y){returnstrcmp(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(structsuffix_struct),suffix_compare);\end{verbatim}\end{center}ドキュメント頻度を計算する場合，ドキュメントの長さに上限があればコーパス中の文字列はドキュメント毎に区切られていると見なすことができる．この条件の下で上記のアルゴリズムを使ってデータ構造を作成するためには，$O(N\logN)$時間必要である．\par\begin{figure}[htbp]\begin{center}\epsfxsize=9cm\epsfbox{suffix_array.eps}\caption{SuffixArrayのサンプルとある文字列の出現場所の特定}\label{suffix_array}\end{center}\end{figure}
\section{文字列のクラス分け}
文字列の文献\cite{DF1}の文字列のクラス分けの方法を使用するが，この論文では，重複条件付きドキュメント頻度を求める場合にもクラス分けを使用できることを述べる．クラス分けはsuffixを用いて定義される．SuffixArrayの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{SuffixArray上の文字列のクラス}\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)\geq1\}\mid=\mid\{d|tf(d,y)\geq1\}\mid=df(y)$$$$df_k(x)=\mid\{d|tf(d,x)\geqn\}\mid=\mid\{d|tf(d,y)\geqn\}\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]\par2つのクラス$C_1$，$C_2$に交わりがあったときには，$C_1$は$C_2$の上位のクラスであるか$C_1$は$C_2$の下位のクラスであるかのどちらかである．\\証明\par$C_1$と$C_2$に交わりがあるということは，\begin{center}\[\begin{array}{lr}i_1\leqi_2\leqj_1\leqj_2&(1)\\i_2\leqi_1\leqj_2\leqj_1&(2)\\i_1\leqi_2\leqj_2\leqj_1&(3)\\i_2\leqi_1\leqj_1\leqj_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\leqk_1\leqj_1-1)$である．一方，区間$[i_2,j_2]$では，$k_1=i_2-1$，$k_2=j_1\(i_2\leqk_2\leqj_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\leqj_1\leqj_2$の場合はクラスの階層の定義より，$C_2$が$C_1$の上位クラスである，または，等しいクラスである．\par$(2)$も$(1)$と同様に証明できる．また，$(3)$の場合はクラスの階層の定義より，$C_1$が$C_2$の上位クラスであるか等しいクラスであり，$(4)$の場合は，$C_2$が$C_1$の上位クラスである，または，等しいクラスである．\par以上より，2つのクラスに交わりがある場合は，一方がもう一方の上位クラス，または，下位クラスとなる．\\[性質5]\parSuffixArrayにおいて，すべての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より，SuffixArrayのすべての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{出現場所の重複条件}
重複条件付きドキュメント頻度の計測行う準備として，この論文で新しく使用する「文字列の出現場所ごとの重複条件」を定義する．重複条件付きドキュメント頻度の計測のために，クラス階層で寄せ集められる数を定義し，その数の関数として重複条件付きドキュメント頻度を求めることを行う．ここで使用する頻度を定義するために，文字列の出現場所の重複度と重複条件を使用する．すべての文字列の出現場所は，SuffixArray内の配列の番号で順序づけることができる．この順序をsuffix順と定義し，これを利用して文字列の出現場所の重複条件と重複度を定義する．\\[定義]\parある文字列$x$の出現場所の重複度が$k$であるとは，suffix順でその出現場所以下の場所で，かつ同一のドキュメントに属する文字列$x$の出現場所が$k$個あることとする．\\\par図\ref{chofuku}に重複度の例を示す．\parsuffix順で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]$$\forallx,y\inC,\\forallk;\foralld;\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\leqt$について，$$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)\geqk\}\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\leq8$，$tf(3,ab)=6\leq8$である，ドキュメント\#1，\#3は，重複度$k\geq8$となる文字列abが存在しないため，$cf_8$の数え上げに関係しない．ドキュメント\#2では，$tf(2,ab)=8$であるので重複度$k\geq8$となる文字列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リンクの場所の情報を求めると同時に，その表を現在の場所に更新すればよい．\parpreviousリンクを作成するプログラムは以下のような構造になる．このデータ構造を作成するには，ドキュメント数と同じメモリ領域を用意し，コーパス全体を一度スキャンすることになる．\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}\itemSuffixArrayをsuffix順が小さいものから見て行く．\itemクラスの開始場所を見つける．\itemクラスの終了場所を探す．\begin{itemize}\itemクラスは階層構造になっているため，そのクラスの終了場所が見つかる前に，他のクラスの開始場所が見つかることがある．この場合は，スタックにその開始場所をプッシュする．\itemクラスの終了場所が見つかれば，報告しスタックを回復する．\end{itemize}\end{enumerate}上記のアルゴリズムでクラスを求めていったとき，求めるクラスの先頭が発見できていて，まだ，その終りが発見できていないクラスを計算中のクラスと呼ぶことにする．アルゴリズムでは，スタック中のクラスを現在計算中のクラスとする．\par$common[i]$はコーパスの文字列と同じ大きさの配列で，SuffixArrayで次の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\logN)$以下の計算量では収まらない場合がある．具体的には同じ文字が長く連続するようなデータがこのケースになる．\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}abcabcabcabcdabcdebcde\end{verbatim}\subsection{SuffixArrayの作成とクラス検出の準備}第一段階では，SuffixArrayを作成し，commonをもとめ，PreviousLinkを作成する．例に対しては以下のようなデータが作成される．先頭から，\begin{itemize}\itemsuffixの番号\itemsuffixが属するドキュメントの番号\item同じドキュメントに属しているsuffixで，直前に現れたものの番号\item直後のsuffixと「先頭から一致している文字列」の長さ\itemそのsuffixの文字\end{itemize}である．\begin{verbatim}00-10:11-10:22-10:33-10:4003:abc5046:abcabc6053:abcabcabc7114:abcd8220:abcde9062:bc10095:bcabc110102:bcabcabc12173:bcd13284:bcde14330:bcde150111:c160154:cabc170161:cabcabc181122:cd192133:cde203140:cde211181:d222192:de233200:de242221:e253230:e\end{verbatim}\subsection{求められたクラスの表の例}本文で説明した方法で，$cf$が2より大きなクラスを求める．これを，クラスの先頭の場所を第1キー，長さを第2キーにしてソートし，同時に，重複条件付き文字列頻度から，文書頻度に変換する．その結果は，以下のようになる．この例では，$cf$が2より大きなクラスは全部で14個ある．クラスごとに，対応する区間，次に長さ，それぞれのクラスに対する統計値とクラスを代表する文字列となっている．クラスを代表する文字列とは，そのクラスのなかで最長の文字列である．この中には，区間の大きさが1のクラスは含まれていない．この情報の中にはクラスに含まれる最短の文字列が何であるかという情報が含まれていない．そのような文字列は，クラスを代表する文字列と先頭から比較していき，最も長く一致するものの中で最も上位のクラスの情報を取り出すことで対処している．クラスのソートで，区間の先頭を第1キーにすることでほぼ辞書順に並ぶ．区間の先頭が同じ場合には，長さが短いほうが優先されることで，結果としてクラスの代表する文字列は辞書順に並ぶ．\begin{verbatim}total=14Class[4,8]L=3tf=5df1=3df2=1df3=1df4=0S="abc"Class[5,6]L=6tf=2df1=1df2=1df3=0df4=0S="abcabc"Class[7,8]L=4tf=2df1=2df2=0df3=0df4=0S="abcd"Class[9,14]L=2tf=6df1=4df2=1df3=1df4=0S="bc"Class[10,11]L=5tf=2df1=1df2=1df3=0df4=0S="bcabc"Class[12,14]L=3tf=3df1=3df2=0df3=0df4=0S="bcd"Class[13,14]L=4tf=2df1=2df2=0df3=0df4=0S="bcde"Class[15,20]L=1tf=6df1=4df2=1df3=1df4=0S="c"Class[16,17]L=4tf=2df1=1df2=1df3=0df4=0S="cabc"Class[18,20]L=2tf=3df1=3df2=0df3=0df4=0S="cd"Class[19,20]L=3tf=2df1=2df2=0df3=0df4=0S="cde"Class[21,23]L=1tf=3df1=3df2=0df3=0df4=0S="d"Class[22,23]L=2tf=2df1=2df2=0df3=0df4=0S="de"Class[24,25]L=1tf=2df1=2df2=0df3=0df4=0S="e"\end{verbatim}\subsection{文字列に対する処理}与えられた任意の文字列に対して，上記の表を二分探索することで$tf，df_1(=df)，df_2，df_3，df_4$を求めることができる．二分探索であり，表の大きさは$O(N)$であるので，この処理は$O(\logN)$で終了する．\begin{verbatim}abc--Class[4,8]に該当（代表文字列）53110abcabcabc--Class[5,6]に該当（代表文字列）21100abcabcabcd--Class[7,8]に該当（代表文字列）22000abcdabca--Class[5,6]に該当（代表文字列でない）21100abcaabcab--Class[5,6]に該当（代表文字列でない）21100abcababcabc--Class[5,6]に該当（代表文字列）21100abcabcabcabca--表になく，コーパスに存在する11000abcabcaabcabcab--表になく，コーパスに存在する11000abcabcababcabcabc--表になく，コーパスに存在する11000abcabcabcabcabcabca--表になく，コーパスに存在しない00000abcabcabca\end{verbatim}
\section{実行時間の計測}
実行時間の計測は，どのようなドキュメントを用いても良いが，ここでは，技術用語のアブストラクトの集合を使用した．そこからアブストラクトの本文だけを抜き出し，一行を一つのドキュメントに整形したものである．332,918文書，69,312,280文字，130,993,215バイトのコーパスである．測定には，AthlonMP1.2Mhz，3GByteメモリのシステムを使用した．\subsection{ボトムラインシステム}最初の比較対象のシステムは，一番単純な方法で計測した場合である．文字列と重複度$k$が与えられたときに，$k$のドキュメント頻度をは，コーパスの先頭から順番に見るという方針で求めるものである．具体的には，以下のようなプログラムで求める．これば，クラス分けもクラスの階層構造も利用しないシステムとなっている．このシステムは定義が単純であるため速度の比較だけでなく，プログラムの動作の正答を用意し，提案するシステムが正しく動作していることの確認にも使用した．このシステムを{\ttlinear}と呼ぶことにする．\begin{verbatim}/*s1の先頭がs2で始まっているかどうかを検査する関数*/staticintstring_sub(char*s1,char*s2){while(*s2){if(*s1!=*s2){return0;}s1++;s2++;}return*s1;}/*改行までの間に，文字列がk回出現するかどうか調べ，出現した回数をカウントする回数．*/intdfn(intk,char*s){inti;/*stringposition*/intt;/*termfrequencyinadocument*/intn;/*documentfrequency*/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;}}returnn;}\end{verbatim}\subsection{ベースラインシステム}ベースラインシステムは，クラス分けを使用しているが，表を作成するときにクラスの階層構造を使用しないシステムである．クラスの検出のあと，下のCのプログラムを使って，$df_1$から$df_5$までを同時にもとめて表にする．このシステムを{\ttbase}と呼ぶことにする．\begin{verbatim}/*重複条件付きドキュメント頻度を一斉に求める関数結果は，staticな配列に保存する．*/staticintdfn[MAX_C];staticvoidcount_dfn(char*s,intlen){inti;/*stringposition*/intt;/*termfrequencyinadocument*/intn;/*documentfrequency*/intk;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{提案システム}提案するシステムはこの論文で記述した方法を用いたものであり，クラスの表を作成し，表の数値を計数するときに，クラスの階層の性質を使用したものである．このシステムを{\ttclass}と呼ぶことにする．\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{実行時間}に{\ttlinear}，{\ttbase}，{\ttclass}の実行時間を示す．表\ref{実行時間}の中の時間は，処理装置の使用時間を秒で示したものである．また，すべてのプログラムが同一の頻度を出力することも確認した．重複条件付きドキュメント頻度の分析対象とした文字列は，10ドキュメント，4156バイト，2190文字の部分文字列で，統計的に安定な頻度が3を越える文字列である．この文字列の数は，コーパスが大きくなるにつれ増加するが，その増加は緩やかである．{\ttlinear}システムは，前処理は必要なく，前処理の時間はテキストを読む時間だけである．この計測ではファイル処理の時間は除外しているので，前処理の時間は0.0となる．{\ttlinear}システムは直ちに結果を出力し始めるがコーパスのドキュメント数が増加することに比例して一つあたりの分析時間が大きくなっていく．10個のドキュメントの分析という小さな問題であっても，実用的に使用できるのは，ドキュメントの数が１万程度までである．{\ttbase}システムは，分析時間は高速になるが，前処理に$O(N^2)$の時間がかかることが観測される．実用的に使用できるのは，ドキュメントの数が数千個程度までである．提案するシステム({\ttclass})の実行時間は，実データにおいて，前処理$O(N\logN)$となっている．そして，分析時間を分析対象の文字数で割ることで求められる1文字列あたりの時間は，最大でも0.036ミリ秒であり，1000ドキュメントより大きなコーパスにおいて，$O(\logN)$となっている．332,918ドキュメントの前処理の時間は1223.4と$O(N\logN)$に比べて大きい．ほかに比べて増加しているのは，実験に使用したコンピュータの実装メモリに近いプロセスの大きさになったためだと考えられる．以上，クラス分けによる表の作成と，クラスの階層構造を利用することによって，はじめて10万を越えるドキュメント数に対して分析ができるようになったことがわかる．\begin{table}[htbp]\begin{center}\begin{tabular}{|r|r|r|}\hlineドキュメント数&コーパス文字数&文字列個数\\\hline316&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]}\\&前処理&分析&前処理&分析&前処理&分析\\\hline316&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バイト使用していることがわかる．表の検索のプログラムは，クラス分けの表とSuffixArrayを保持しており，プロセスの大きさの主要な部分は，その大きさである．表を作成するには，クラス検出のためのデータ構造や，重複度判定のためのデータ構造などがあり，分析処理よりもメモリを多く必要とする．\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(\logN)$で重複条件付きドキュメント頻度の分析を行うことは，文字列の統計処理の基本技術であり，ここで述べた単語の境界の分析以外にも応用範囲がある．\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\logN)$であり，表を引く処理が$O(\logN)$であることを確かめた．最後に，実行中のプロセスの大きさを調べることでメモリの負荷が$O(N)$であることを確認した．そして，この方法で10万を越える数のドキュメントについて，任意文字列に対する重複度付きドキュメント頻度の分析を行えたことを報告する．\acknowledgment本研究は平成14年度IPA未踏ソフトウェア創造事業のプロジェクトの一部であり，住友電気工業株式会社の援助による成果です．また，AT\&T\KennethW.Church氏，つくば大学\山本幹雄氏にはクラスシステムについて，直接，教えて頂きました．深く感謝します．\bibliographystyle{jnlpbbl}\bibliography{369}\begin{biography}\biotitle{略歴}\bioauthor{梅村恭司}{1983年東京大学大学院工学系研究科情報工学専攻修士課程修了．同年，日本電信電話公社電気通信研究所入所．1995年豊橋技術科学大学工学部情報工学系助教授，現在に至る．博士(工学)，記号処理，統計言語処理，システムプログラムの研究に従事ACM，ソフトウェア学会，電子情報通信学会，計量国語学会各会員．}\bioauthor{真田亜希子}{1978年生．2001年豊橋技術科学大学工学部情報工学課程卒業．同年豊橋技術科学大学大学院工学研究科情報工学専攻修士課程入学，現在に至る．}\bioreceived{受付}\biorevised{再受付}\bioaccepted{採録}\end{biography}\end{document}