ある文字列を$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)$である．