大規模なテキストに対する部分文字列出現頻度の推定 Substring

DEWS2008 E7-1
大規模なテキストに対する部分文字列出現頻度の推定
上村
卓史†
金田
悠作†
喜田
拓也†
有村
博紀†
† 北海道大学大学院情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目
E-mail: †{tue,y-kaneta,kida,arim}@ist.hokudai.ac.jp
あらまし
テキスト処理において，大規模な文字列 (テキスト) とある短い文字列 (クエリ) が与えられた
とき，テキスト中のクエリの出現頻度を知りたいという要求がある．しかし，主記憶容量の問題から，全
ての部分文字列の真の出現頻度を高速に計算する索引を保持することは困難である．本稿では，与えられ
た文字列のテキスト中の真の出現頻度を推定するためのデータ構造である動的刈り込み接尾辞木を提案し，
これを用いた任意の部分文字列の出現頻度の推定方法を与える．また，計算機実験により構築時間と推定
精度について評価した結果を示す．
キーワード
文字列出現頻度推定，接尾辞木
Substring Selectivity Estimation for Massive Text
Takashi UEMURA† , Yusaku KANETA† , Takuya KIDA† , and Hiroki ARIMURA†
† Graduate School of Information Science and Technology, Hokkaido University
N14 W9, Sapporo 060–0814, Japan
E-mail: †{tue,y-kaneta,kida,arim}@ist.hokudai.ac.jp
Abstract In text processing applications, we often need to know the frequency of a query in the given
massive text. However, it is difficult to construct the index structure which computes the all frequency of
all queries in the text in main memory. In this paper, we present a compact index structure which uses
constant size of main memory and estimates the true frequency of queries in the text. We also present
experimental results in the computational time and the performance of estimation.
Key words substring selectivity estimation, suffix trees
1. は じ め に
しかし，接尾辞木はテキスト長の数十倍という領域を
必要とするため，大きなテキストには適用し難いという
インターネットをはじめとした様々な応用において，大
問題がある．このため，限られた主記憶領域で索引を構
規模なテキストを扱う機会が増えている．中でも，与え
築し，近似を行って真の出現頻度を推定することが現実
られた大きな文字列 (テキスト)T の中に，文字列 (クエ
的である．本研究の目的は，より大きなテキストに対し
リ)P が何回出現するかという問題は，きわめて基本的か
て構築可能な，文字列の出現頻度をできるだけ高精度に
つ実際の応用においても重要である．特にクエリの個数
推定する索引を提案することである．
が多い場合，高速な計算には索引構造の構築が不可欠で
与えられたテキスト T に対し，任意のクエリの T 中の
ある．接尾辞木 [5] は，与えられたテキスト T のすべて
出現頻度を推定する手法としては，Krishnan ら [2] が提
の部分文字列を線形領域で表す，よく知られたデータ構
案した索引構造である頻度刈り込み接尾辞木を用いる手
造である．接尾辞木を用いることで，長さ m のクエリ P
法がある．頻度刈り込み接尾辞木は，接尾辞木から出現
の出現頻度を，T の長さに依存せず O(m · log |Σ|) 時間
頻度が閾値以下である部分文字列に対応するノードをす
で求めることができる．ここに，|Σ| はアルファベットの
べて削除することで得られる木構造であり，各ノードに
大きさである．
は対応する部分文字列の出現頻度を格納する．こうして
—1—
残されたノードのみを用いて，出現頻度を推定する文字
S ∈ Σ∗ に対して，S = xyz となる x, y, z ∈ Σ∗ が存在す
列 P をいくつかの部分文字列に分割し，それらの個別の
るとき，x, y, z をそれぞれ S の接頭辞，部分文字列，接
出現確率の積として P の出現確率を推定することができ
尾辞と呼ぶ．S の i 番目の文字を w[i] と表し，S の i 番
る．また，Jagadish らは同じ頻度刈り込み接尾辞木を用
目から j 番目までの部分文字列を S[i . . . j] で表す．i > j
いてさらに推定精度を改善させる手法を提案している [1]．
のとき，便宜的に S[i . . . j] = ε と定義する．
ただし，頻度刈り込み接尾辞木は一度接尾辞木を構築す
文字列 P が文字列 T [1 . . . n] 中に位置 i で出現すると
ることで得られるため，一時的には結局接尾辞木と同等
の主記憶領域を必要とするため，実際の大規模テキスト
は，P = S[i . . . |P |](1 <
=i<
= n − |P |) である i が存在す
ることをいう．T 中における P の出現頻度とはそのよう
に対しては適用が難しい．
な位置 i の個数であり，f (T, P ) と書く．ただし，P = ε
これに対し Ron ら [3] が提案した確率的接尾辞トライ
は，はじめにある閾値 q を与えることで，出現頻度が q
回以上になるまでノードの拡張を抑えることで構築する
ならば f (T, P ) = |T | と定義する．以降では，このよう
な文字列 T, P をそれぞれテキスト，クエリと呼ぶ．
本稿で取り組む問題は以下の通りである．
トライ構造である．確率的接尾辞トライは q を大きくと
部分文字列出現頻度推定問題: 与えられたテキスト T ∈ Σ∗
るほどノード数を抑えることができ，頻度刈り込み接尾
に対し，任意のクエリ P ∈ Σ∗ の T 中の出現頻度を推定
辞木のように一時的に大きな主記憶領域は必要としない．
するコンパクトな索引を構築せよ．
しかし，最終的なノード数を一定以下に制限するには，
文字列の長さから予測するなどして閾値をあらかじめ決
2. 2 接 尾 辞 木
長さ n >
= 1 の テ キ ス ト T を ，T [1 . . . n − 1] に 現
定する必要がある．また，文字列全体が与えられる前に，
れ な い 特 別 な 記 号 $ で 終 わ る 文 字 列 と 仮 定 す る ．T
任意の時点で推定を行いたい場合，ノード数が目標より
の接尾辞木は T のすべての接尾辞を表す圧縮トライ
少ないため高精度な推定が難しいという問題がある．
ST (T ) = (V, root, E, suf ) である．ここで，V はノード
つつ，与えられたテキスト T 中で出現頻度の高い文字列
2
の集合である．E は辺の集合で，E ⊂
=V である．ノー
ド s, t ∈ V について，(s, t) ∈ E のとき，s を t の親，
はできる限り索引化する，動的刈り込み接尾辞木を提案
t を s の子と呼ぶ．また，子を持たないノードを葉と
本稿では，使用する主記憶容量をある一定以下に保ち
する．この木は，ノード数が定められた値 M を超えな
呼ぶ．葉全体は接尾辞全体の集合と 1 対 1 で対応する．
い範囲では Ukkonen の接尾辞木構築アルゴリズム [4] に
root は木 ST (T ) の根である．root からノード s ∈ V
基づいて拡張を行う．そしてノード数が M を超えそうに
へのパス上にあるノード t ∈ V を s の祖先，s を t の
なったとき，出現頻度が最も低い文字列に対応するノー
子孫と呼ぶ．s は s 自身の祖先かつ子孫であることに注
ドをまとめて削除する．したがって，計算機の主記憶領
意する．任意の辺 e ∈ E には T の空でない部分文字列
域に合わせて容易に M を定めることができる．またテキ
ストが主記憶上に保持できる範囲ならば，はじめに文字
T [j . . . k]（1 <
=j<
=k<
= |T |）がラベル付けされる．ノー
ド t ∈ V へ向かう辺のラベル文字列を label (t) と書く
列長を決定することなく索引を構築できる．さらに，構
ことにする．便宜上，label (root) = ε と定義する．さら
築の途中でも M に応じて可能な限り多くの部分文字列
に，任意のノード s ∈ V について，root から s への祖
の出現頻度を保持して文字列出現頻度の推定を行うこと
先の列 root, a1 , a2 , . . . , s の各ラベル文字列を連結した文
ができる．
字列 label (root) · label (a1 ) · label (a2 ) · · · label (s) をノー
本稿の構成は以下の通りである．2 章では基本的な定
ド s が表す文字列と呼び，s と書く．suf は V 上の関数
義をしたのち従来手法について述べる．3 章では動的刈
suf : V → V であり，ノード s, t ∈ V と文字 a ∈ Σ に対
り込み接尾辞木の構築アルゴリズムを示す．4 章では計
して，s = a · t であるとき，suf (s) = t である．ここで，
算機実験を行った結果について述べる．5 章では本稿の
任意の実ノード s ∈ V について，s = a · t となる実ノー
結論を述べる．
ド t ∈ V が存在する [4]．この関数は s から t への辺 (s, t)
2. 準
とみなすこともできるので，これを接尾辞リンクと呼ぶ．
備
T のすべての接尾辞を表すトライからパス圧縮によっ
2. 1 基本的な定義
て削除され，接尾辞木 ST (T ) 上においては存在しない
アルファベットを Σ とする．Σ 上の文字列全体の集合
ノードを ST (T ) の仮想ノードと呼ぶ．これと区別するた
を Σ∗ で表す．文字列 x ∈ Σ∗ の長さを |x| と表す．特に長
め，以降は V の要素を ST (T ) の実ノードと呼ぶ．仮想
さが 0 の文字列を空語といい，ε で表す．Σ+ を Σ∗ \ {ε}
ノード u に対しても，実ノードと同様に u が表す文字列
∗
と定義する．文字列 x, y ∈ Σ の連結を x · y で表す．た
だし混乱のない限りはこれを単に xy と書く．ある文字列
を u で表す．
ノード s を指し示すポインタを参照と呼ぶ．参照 φ が
—2—
ノード s を指し示すとき，s が表す文字列 s と同一視す
ることにする．また，ノードと同様に φ が表す文字列を
φ と書く．
接尾辞木の葉はそれぞれ異なる接尾辞を表すから，葉
t の表す文字列 t の出現頻度 f (T, t) は常に 1 である．ま
手続き MO;
入力: P ST (T, p)，S ∈ Σ∗ ;
出力: f (T, S) の推定値 f 0 ;
1
φ = ε;
2
i = 0;
する部分木の葉の個数である．よって，ST (T ) の各ノー
3
f 0 = f (root);
ド s に対し，f (s) で f (T, s) を表し，s に f (s) を補助情
4
while i < |S|
報として持たせることにする．なお，仮想ノード u と，u
5
た，あるノード s が表す文字列 s の出現頻度は，s を根と
while phi · S[i] が DynPST に存在しない
の最も近い実ノードの子孫 s に対し，f (u) = f (s) であ
6
ることに注意する．
7
i = i + 1;
8
f 0 = f 0 ∗ p;
2. 3 頻度刈り込み接尾辞木
文字列 T ∈ Σ∗ と，ある閾値 p > 0 に対し，頻度刈り込
if φ == ε
9
10
break;
φ = suf (φ);
み接尾辞木 PruneST (T, p) とは，接尾辞木 ST (T ) から，
11
f0 = f (φ);
f (u) <
= p 以下であるすべてのノード u を削除したデータ
12
while phi · S[i] が DynPST に存在する
構造である．すなわち，PruneST (T, p) は T の (p + 1) 回
13
φ = phi · S[i];
以上現れる部分文字列のみからなる集合 {x | f (T, x) > p}
14
i = i + 1;
を表す圧縮トライに，各部分文字列の出現頻度を持たせ
15
f 0 = f (φ)/f0 ;
た木である．
16 return f 0 ;
2. 4 文字列出現頻度の推定
図 1 文字列出現頻度の推定
Jagadish ら [1] によって示された文字列出現頻度の推
定アルゴリズム MO を図 1 に示す．このアルゴリズム
は，頻度刈り込み接尾辞木のみならず，接尾辞木からノー
ドを削除することで得られるような一般の木構造の文字
手続き construct-ProbST ;
列索引に適用可能である．このような索引を刈り込み接
入力: 長さ n の文字列 T ，閾値 q;
尾辞木と呼ぶ．なお，文献 [1] では文字列の出現確率を推
出力: 確率的接尾辞トライ ProbST (T, q);
定することになっているが，本論文の記述に合わせて出
現頻度を推定するように変更を加えている．
文字列 αβ ，βγ の出現確率 Pr(αβ)，Pr(βγ) がわか
って お り，未 知 の 出 現 確 率 Pr(αβγ) を 推 定 し た い と
ProbST = root だけからなる木;
φ = root;
for i = 1 . . . n
while true
if φ · T [i] を表すノード s が ProbST に存在しない
す る ．MO 法 の 基 本 的 な 考 え 方 は ，Pr(αβγ|αβ) を
ノード s，辺 (φ, s) を作る;
label(s) = T [i]，f (s) = 1;
Pr(βγ|β) で近似することである．このとき，β が最長
となるように選ぶことに注意する．これを用いると，
Pr(αβγ) ≈ Pr(αβ) × P (βγ)/P (β) となる．これにより，
文字列 αβγ の出現頻度を f (T, αβ) × f (T, βγ)/f (T, β)
else if f (s) < q
f (s) = f (s) + 1;
else
φ = φ · T [i];
で推定する．
2. 5 確率的接尾辞トライ
break;
if φ == root;
Ron ら [3] が提案した確率的接尾辞トライは，ある閾
値 q > 0 に対して，出現頻度が q を超えた文字列に対応
するノードのみを拡張することで構築するトライである．
break;
φ = suf (φ);
return ProbST ;
確率的接尾辞トライの構築アルゴリズムを図 2 に示す．
このように木の拡張を制限することで，木の拡張を抑え
図 2 確率的接尾辞トライの構築手続き
てメモリの消費を抑えることができる．
を提案する．
3. 動的刈り込み接尾辞木
動的刈り込み接尾辞木の構築手続きを図 3 に示す．動
本節では大規模テキストからの部分文字列出現頻度推
作は以下の通りである．まず整数 M > 0 は最大ノード数
定を行うためのデータ構造である動的刈り込み接尾辞木
であり，これを超えないように木を管理する．ノード数が
—3—
手続き construct-DynPST (T, M );
手続き update
入力: 長さ n の文字列 T ，最大ノード数 M ;
入力: DynPST (T [1 . . . i − 1], M ), φ，T [i];
出力: 動的刈り込み接尾辞木 DynPST (T, M );
出力: DynPST (T [1 . . . i], M )，
φ;
1
DynPST = 根だけからなる木;
1
r = root;
2
φ = ε;
2
while φ · T [i] を表すノードが DynPST に存在しない
3
for i = 1 . . . n
3
4
δ = DynPST の葉が持つカウンタで最小の値;
4
5
σ =simulate(DynPST , φ, T [i]);
5
6
while (現在のノード数 + σ) > M
7
8
9
if φ は仮想ノード
φ を表す実ノード s を作る;
else
6
s = φ;
prune(DynPST , φ, δ);
7
s の子 t，辺 (s, t)，ラベル label(t) = (i, ∞) を作る;
update(DynPST , T [i], φ);
8
c(t) = 1;
9
if r 6= root
return DynPST ;
suf (s) = r;
10
図3
動的刈り込み接尾辞木の構築手続き
M 未満である限りは，Ukkonen [4] による接尾辞木のオ
ンライン構築アルゴリズムと同様の更新手続き update
を行う．時点 i において φ は 2 回以上 T [1 . . . i − 1] に出
11
r = s;
12
φ = suf (φ);
13 if r 6= root
14
suf (s) = r;
15 φ = φ · T [i];
16 return DynPST , φ;
現する最長の接尾辞を表すノードの参照である．手続き
simulate は，update を行うことで増加するノード数
図4
動的刈り込み接尾辞木の更新手続き
を見積もる手続きである．ある時点 i で update を行っ
たときにノード数が M を超える場合，更新の前に手続
き prune を行い，ノード数を削減してから木を拡張す
る．削除するノードを決定するため，各ノードにカウン
タ c(s) を持たせる．カウンタの初期値は常に 0 とする．
手続き simulate
入力: DynPST (T [1 . . . i − 1], M ), φ，T [i];
出力: 時点 i の update によって増加するノード数 σ;
一度も prune が行われなかったとき，各ノード s につい
1
σ = 0;
て f (s) は，接尾辞木と同様に s を根とする部分木のカウ
2
while φ · T [i] を表すノードが DynPST に存在しない
ンタの合計と等しい．以降ではこの合計値を s の合計頻
3
度と呼び，C(s) で表す．一度の prune によって削除さ
4
れるノードは，最も小さいカウンタの値 δ を持つノード
5
σ = σ + 1;
6
φ = suf (φ);
すべてである．またこのとき，削除されなかったノード
7
if φ は仮想ノード
σ = σ + 1;
return σ;
のカウンタも一律に δ 減らす．内部ノード s については，
合計頻度 C(s) を δ だけ減らしたい．すべての葉は δ だけ
図 5 update によって増加するノード数を見積もる手続き
カウンタを減らされるから，そのままでは C(s) は (s の
部分木の葉の数) × δ 減ることになる．ここで，s のすべ
ての子 t がそれぞれ正しく δ だけ C(t) を減らされたと仮
定すると，(子の数 − 1) × δ を s に足すことによって，結
果的に C(s) を δ だけ減らすことができる．ここで，∆ji
で時点 i から時点 j までの間に減らしたカウンタの値の
合計を表すことにする．
［補題 1］ 長さ n の文字列 T と最大ノード数 M が与え
られたとき，動的刈り込み接尾辞木 DynPST (T, M ) の
構築におけるすべての時点 0 <
= n において，ある空
=i<
でない文字列 S が f (T, S) > ∆i1 を満たすならば，S を
表すノード s が存在する．
証明 帰納法によって証明する．まず i = 0 では T [1 . . . 0] =
ε であり，f (T, S) > ∆i1 = 0 を満たす文字列 S は存在し
ない．よって成り立つ．
ある時点 1 <
= i − 1 < n でこの補題が成り立つと
仮定する．ここで，時点 i で刈り込みが行わない場合，
∆i1 = ∆i−1
であるから，時点 i で新たに現れること
1
で f (T, S) > ∆i1 となる T の部分文字列 S を除いて，
DynPST (T [1 . . . i − 1], M ) は ∆i1 回以上現れるすべての
文字列を表す．さらに時点 i で構築手続きを行うことで，
f (s) = ∆i1 であり以前の刈り込みで削除されたノードは
木に追加される．よって，刈り込みが行われなかった場
合にはこの補題は成り立つ．次に，時点 i で刈り込みが
行われた場合を考える．刈り込まれたノードの合計頻度
—4—
［補題 2］ T を長さ n の文字列とする．動的刈り込み
接尾辞木 DynPST (T, M ) の任意のノード s について，
n
C(s) <
= f (T, s) <
= C(s) + ∆1 が成り立つ．
手続き prune
入力: DynPST (T [1 . . . i − 1], M ), φ，δ;
証明 C(s) が増えるのは s または s を接頭辞とする文字
出力: 刈り込まれた DynPST (T [1 . . . i − 1], M );
列が現れた時であるから，明らかに C(s) <
= f (T, s) が成
while C(φ) == δ
り立つ．次に，s が刈り込みによって一度も削除されてい
if φ は仮想ノード
ないと仮定する．このとき f (T, s) = C(s) + ∆n
1 が成り
φ を表す実ノード s を作る;
立つ．また，s が何度か削除され，最後に作られた時点
else
を i とする．このとき，
s = φ;
c(s) = c(s) + 1;
f (T [i . . . n], s) = ∆n
i + C(s)
φ = suf (φ);
DynPST を深さ優先探索し，各ノード s に以下を行う:
if s は内部ノード
が成り立つ．さらに補題 1 より，時点 i − 1 について
i−1
f (T [1..i − 1], s) <
= ∆1
c(s) = c(s) + (s の子の数 − 1) × δ;
else
であるから，
c(s) = c(s) − δ;
if c(s) == 0
f (T [1..n], s) = f (T [1..i − 1], s) + f (T [i..n], s)
delete u;
i−1
n
<
= ∆1 + C(s) + ∆i
return DynPST ;
= C(s) + ∆n
1
図 6 動的刈り込み接尾辞木の刈り込み手続き
2
が成り立つ．
を δ とする．ここで，あるノード s が f (T, S) > ∆i1 で
あるにもかかわらず削除されたと仮定する．このとき，s
が最も後に作られた時点を j とする．時点 j − 1 で s は
存在しないから，
この結果から，DynPST (T, M ) の任意のノード s につ
いて，f (T, s) を単純に f 0 (s) = C(s) + ∆n
1 で近似するこ
とにする．また，DynPST (T, M ) に表わされていない文
字 q に対して，f (T, q) = ∆n
1 − 1 で近似する．
以上によって各ノード s に対して f (s) を推定した後，
j−1
f (T [1 . . . j − 1], s) <
= ∆1
頻度刈り込み接尾辞木と同様に MO 法によって任意の部
が帰納法の仮定より成り立つ．また c(s) = δ であるから，
時点 j, . . . , i − 1 で減らされたカウンタの値を考慮すると，
f (T [j . . . i], s) = ∆i−1
+δ
j
分文字列の出現頻度を推定することができる．
4. 計算機実験
本節では，刈り込み接尾辞木，確率的接尾辞トライ，動
が成り立つ．ここで時点 k = 1, . . . , i について s の出現
的刈り込み接尾辞木の 3 種類の索引構造の構築時間およ
び推定精度を測定する．以降では索引を構築する文字列
頻度を求めると，
をテキストと呼び，出現頻度を推定する文字列をクエリ
f (T [1 . . . i], s) = f (T [1 . . . j − 1], s) + f (T [j . . . i], s)
j−1
i−1
<
= ∆1 + ∆ j + δ
と呼ぶ．
4. 1 デ ー タ
テキスト，クエリ共に毎日新聞コーパスを用いた．ま
= ∆i−1
+δ
1
ず 1991 年の全データから本文データのみを抽出し，連
= ∆i1
結した文字列を作成した．各実験ではこの文字列の先頭
よって矛盾であり，仮定は誤りである．したがって，任
から必要なだけの長さをとり，テキスト T として用いる．
意の時点 1 <
= i − 1 < n でこの補題は成り立つ．
また，1992 年，1993 年の全データから同様に本文を抽
2
3. 1 文字列出現頻度の推定
出した文字列し，その部分文字列をクエリの候補とした．
動的刈り込み接尾辞木を用いて文字列出現頻度の推定
そのうちで，文字列中の一様にランダムな位置から始ま
を行う方法について述べる．DynPST の各ノード s が
る，ポアソン分布で平均長 µ = 3 の部分文字列を 10000
持つカウンタは手続き prune によって減らされている
個選択し，クエリの集合 Q とした．
ので，合計頻度 C(s) は f (s) そのものを表さない．した
4. 2 方
法
がって，s の合計頻度 C(s) から真の f (s) を推定する必
4. 2. 1 構築時間の測定
要がある．
テキスト長 |T | を 107 まで変化させ，テキスト長に対
—5—
表1
クエリに対する推定精度の測定
する構築時間の変化を測定した．ただし今回は確率的接
尾辞トライと動的刈り込み接尾辞木のみについて実験を
行った．
4. 2. 2 推定精度の測定
テキスト長 |T | を 107 とし，各クエリ S ∈ Q の出現
頻度の推定を行い，各索引の推定精度を測定した．評
図 7 確率的接尾辞トライと動的刈り込み接尾辞木の構築時間
の測定
価指標として，推定値 f 0 と真の出現頻度 f の相対誤差
(f 0 − f )/f の平均を用いた．ただし真値が 0 のときは除
算できないため，標準誤差を用いた．以降は真値が 0 の
クエリを 0-クエリと呼ぶことにする．
各索引のパラメータは，構築に必要なノード数を 106
個に制限し，これを満たすように設定した．動的刈り込
み接尾辞木は単に最大ノード数を M = 106 とした．確率
的接尾辞トライは最終的なノード数が 106 以下とするた
め，予備実験によってこれを満たす最大の閾値 q = 207
を求めた．刈り込み接尾辞木は接尾辞木を作る必要があ
るが，特別に刈り込み後のノード数が 106 以下になるよ
うな最大の閾値 p = 4 を求め，これを採用した．
4. 2. 3 オンライン推定精度の測定
この実験では確率的接尾辞トライと動的刈り込み接尾
辞木の 2 つを用いた．テキスト長 |T | を 107 とし，前節
の実験と同様に推定精度を測定した．この実験でも構築
図 8 0-クエリに対するオンライン推定精度
に必要なノード数を 106 個に制限した．ただし今回は，T
から 106 文字読み込むごとに同じクエリで測定を行った．
すなわち，オンラインで索引を構築し，テキストの一部
分から逐次的に推定を行った際の精度を調べた．
4. 3 結
果
4. 3. 1 構 築 時 間
結果を図 7 に示す．動的刈り込み接尾辞木は確率的接
尾辞トライに対して大幅に高速であり，107 文字のテキ
ストに対して 38 秒で構築を終えた．これは同様の更新手
続きによる接尾辞木構築と比較すると約 3 倍程度である
が，十分実用的であるといえる．
4. 3. 2 推 定 精 度
0-クエリに対する推定精度の標準誤差とその他のクエ
リ結果に対する推定精度の相対誤差を表 1 に示す．
0-クエリでは各索引ともほぼ変わらない結果となった
ため，ここでは出現頻度 1 以上のクエリの結果について
図 9 0-クエリ以外に対するオンライン推定精度
述べる．確率的接尾辞トライと動的刈り込み接尾辞木は，
—6—
誤差の絶対値はそれほど変わらなかった．これらに対し
を出した．確率的接尾辞トライは除外前とほぼ同じ結果
刈り込み接尾辞木は安定して良い結果を残している．こ
となった．動的刈り込み接尾辞木では逆に徐々に推定精
れは真の出現頻度が p 以上のクエリをすべて正確に計算
度が低下し，最終的に 14%程度になった．これはテキス
できるからであり，当然の結果である．なお，文献 [1] に
ト長に対して割り当てられるノード数が相対的に減少し
倣って p より大きな出現頻度のクエリのみを対象として
ているためと考えられる．
以上の結果から，一時的に接尾辞木を構築することが
推定を行うと，約 9.47%となった．
また，MO 法では，出現頻度が 0 のクエリに対しても
可能ならば刈り込み接尾辞木が，テキスト長があらかじ
テキスト長に比例したある最小の頻度を推定する．この
めわかっていてテキスト全体での出現頻度を推定したい
ため，0-クエリに対してはテキスト長に比例して大きな
ならば確率的接尾辞トライが，テキストから任意の時点
推定値が出やすくなっていた．
でオンライン推定したい場合，もしくは事前に出現頻度
4. 3. 3 オンライン推定精度
による閾値を定めることが困難である場合は動的刈り込
0-クエリに対する推定精度の標準誤差を図 8 に，その他
み接尾辞木がそれぞれ適しているといえる．
のクエリ結果に対する推定精度の相対誤差を図 9 に示す．
刈り込み接尾辞木では，テキスト長を増やすと徐々に
精度が高まり，|T | > 2 × 106 以降では最良の結果を出
5. お わ り に
本稿では大規模な文字列が与えられたときに任意の文
6
した．|T | >
= 9 × 10 で極端に精度が良くなっているが，
これについては後述する．確率的接尾辞トライではテキ
字列の出現頻度を推定するためのコンパクトな索引であ
スト長が短いと最も精度が悪いが，徐々に改善して最終
より，構築時に必要な領域を限定しつつ，実用的な速度
的な精度に漸近している．これはテキスト長が短いとき
で動作し，推定精度も刈り込み接尾辞木と比べてそれほ
にはあらかじめ決めた閾値が相対的に大きすぎるためで
ど劣化しないことを確認した．
あり，テキストが徐々に増える場合には向かないといえ
6
る動的刈り込み接尾辞木を提案した．また計算機実験に
各ノードのカウンタの値から真の出現頻度を推定する
る．動的刈り込み接尾辞木では，ノード数が 10 個にな
方法は，単にそれまでに減らしたカウンタの値の合計を
5
るまでは接尾辞木と同等であるため，0 <
= |T | <
= 7 × 10
までは誤差 0 で推定している．これは一度も刈り込みが
足すことで実現したが，これよりよい方法がある可能性
行われなかったためである．|T | = 8 × 105 以降は概ね
大きい場合，トライのように木に直接文字を格納してテ
25%から 35%を推移している．このことは，どの段階で
キスト本体を不要にするか，ノードと同様にテキストに
6
もある．また，テキストが主記憶上に保持できないほど
も 10 個のノード数なりに索引を構築するという動作か
対しても何らかの刈り込みを行い，必要な部分のみを保
ら予想された結果である．最終的な精度はそれほどよい
持する必要がある．さらに，実験では MO 法による推定
とはいえないが，これは刈り込みによって毎回ほぼ半分
精度を測定したが，より精度の高い推定アルゴリズム [1]
程のノード数に削減されるため，長期にわたって木に保
が提案されているため，それらを適用した実験が必要で
持されるノード数も半分程度しかないことから来ている
ある．
と考えられる．
|T | = 1.5 × 106 で極端に改善しているのは，
「のて」と
いうクエリが含まれていることによる．MO 法の動作と
しては，
「のて」が索引に存在しない場合，
「の」と「て」
の出現頻度を用いるため，誤って極端に高い値を推定し
6
てしまう．しかし 0 <
= 10 では真の出現頻度が 0
= |T | <
であり，このクエリが 0-に含まれていたため，自乗誤差
に大きく影響していた．事実，このクエリを除外して標
準誤差を求めると，ほぼ直線的に増加する結果となった．
ただし，それぞれ高頻度で出現する文字列 α, β から，実
際には低頻度でしか出現しない文字列 α, β の出現頻度を
誤って推定してしまうことは，一般に起こりうる問題で
ある．
ここで，
「のて」除外した場合の結果についても参考に
文
献
[1] H. V. Jagadish, R. T. Ng, and D. Srivastava. Substring selectivity estimation. In PODS ’99: Proceedings of the eighteenth ACM SIGMOD-SIGACTSIGART symposium on Principles of database systems, pp. 249–260, New York, NY, USA, 1999. ACM.
[2] P. Krishnan, J. S. Vitter, and B. Iyer. Estimating
alphanumeric selectivity in the presence of wildcards.
In SIGMOD ’96: Proceedings of the 1996 ACM SIGMOD international conference on Management of
data, pp. 282–293, New York, NY, USA, 1996. ACM.
[3] D. Ron, Y. Singer, and N. Tishby. The power of amnesia: Learning probabilistic automata with variable
memory length. Machine Learning, 25(2-3):117–149,
1996.
[4] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995.
[5] P. Weiner. Linear pattern matching algorithms. In
FOCS, pp. 1–11, 1973.
述べる．刈り込み接尾辞木では，テキスト長を増やすと
徐々に精度が高まり，|T | > 2 × 106 以降では最良の結果
—7—