DEIM Forum 2016 A1-1

ウェーブレット木を用いた N-gram IDF の近似計算手法
白川 真澄†

原隆浩†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{shirakawa.masumi,hara}@ist.osaka-u.ac.jp
あらまし

N-gram IDF は，語の大域的重みである IDF を単語 N-gram に理論的に拡張したものであり，異なる長さの単語 N-gram 間で重みを比較できるという特長を持つ．また，単語 N-gram の新たな特徴量として，幅広い応用が期待できる．しかし，N-gram IDF の算出には，N-gram を構成する単語の論理積に対する文書頻度が必要であるため，計算量が大きいという問題があった．そこで本稿では，ウェーブレット木を用いて N-gram IDF の近似値を算出する手法を提案する．提案手法は，各 N-gram に対し，構成単語の論理積に対する文書頻度が指定した値に一致するような部分文書集合をウェーブレット木上で動的に構築する．これにより，部分文書集合において計算した N-gram IDF の誤差がポアソン分布により推測可能となる．評価実験において，提案手法が，特徴語抽出および Web 検索クエリ分割のアプリケーションにおける性能を維持しつつ，英語版 Wikipedia 全体を 100 倍程度高速に処理できることを示した．
キーワード

N-gram IDF，ウェーブレット木，ポアソン分布

1. は じ め にしていた．しかしこのアルゴリズムは，理論的な下限 [3] に近い計算量でありながら，英語版 Wikipedia を文書集合としてInverse Document Frequency（IDF）[9] は，単語の大域的出現頻度 5 回以上の全ての単語 N-gram の重みを計算するのに重みとして最も広く用いられており，実際に TF-IDF [16] や（推測値で）1 年以上要することが明らかとなった．そのため，

Okapi BM25 [14] など，代表的な重み付け手法の大域的重みと近似手法により，N-gram IDF の重みをより高速に計算するこして採用されている．その理由として，IDF の簡潔さと頑健性とが課題であった．

が挙げられる．IDF は，対象の単語が出現する文書の数（文書本研究では，ウェーブレット木によるアルゴリズムを拡張し，頻度）を算出するだけで重みが求まるという簡潔さにも関わらN-gram IDF の重みを近似的に計算する手法を提案する．提案ず，様々な文献 [2], [10], [12], [13] において頑健性が示されてい手法の基本的なアイデアは，部分文書集合を用いて文書集合全る．一方で，IDF は複合語あるいは単語 N-gram に対してうま体における文書頻度を推定するというものである．ここで，単く機能しないという問題がある．これは，単語 N-gram として純に部分文書集合を抽出して N-gram IDF を算出した場合，文は文書頻度が大きいほどその単語の並びが特別な意味を持つ傾書集合全体から得られるべき本来の重みとの誤差にばらつきが向があるのに対し，語の重みは文書頻度が小さいほど大きくな生じる．本研究ではまず，ポアソン分布に基づく分析により，るという，相反する性質によるものである．この問題に対処す

N-gram IDF の誤差の分布が，部分文書集合の大きさではな

るため，これまで自己相互情報量（PMI）や名詞句抽出など，

く，観測した文書頻度によって決まることを明らかにする．上

単語 N-gram を処理するための手法をヒューリスティックに組記の事実に基づき，ウェーブレット木上で，指定した文書頻度

み合わせる必要があった．

がちょうど観測されるような部分文書集合を動的に構築する手

筆者らはこの問題に対し，単語 N-gram に適用可能な重みと法を提案する．提案した近似計算手法が，厳密計算手法と比べして N-gram IDF を提案した [17], [18]．N-gram IDF は，コルて 100 倍程度高速に英語版 Wikipedia を処理できることを示

モゴロフ複雑性により定義される情報距離に基づく，単語 N-す．また，特徴語抽出や Web 検索クエリ分割のアプリケーショ

gram に対する理論的な重みである．具体的には，単語 N-gramンにおいて，性能の低下が発生しないことを実証する．

を構成する単語が全て含まれる文書の数（構成単語の論理積に対する文書頻度）を算出することにより重みが求まる．異なる
長さの単語 N-gram 間で N-gram IDF の大小関係を比較する

2. N-gram IDF
N-gram IDF [17], [18] は，コルモゴロフ複雑性により定義さことにより，テキスト中の重要な語句を検出できる．また，単れる情報距離に基づき，単語の重みとして用いられている IDF

語 N-gram の新たな特徴量として，様々なアプリケーションにを，単語間結合度を表す理論的な距離である MED [4] と組み合

おいて N-gram IDF を利用できる．

わせて単語 N-gram に拡張したものである．単語 N-gram g に

N-gram IDF は，重みの計算式自体は簡潔であるが，計算量は大きい．これは，複数の単語が全て含まれる文書を列挙する
処理が，論理積の条件を含むクエリ（intersection query，AND

対する N-gram IDF は以下のように計算される．

N IDFd (g) = log|D|df (w1 , · · · , wN )(1)

N IDFi (g) = log|D| · df (g)df (w1 , · · · , wN )2(2)クエリ）に該当するためである．文献 [17], [18] では，ウェーブ
レット木によるアルゴリズム [6] を用いて AND クエリを処理䝔䜻䝇䝖: “to be or not to be to live or to die”䝅䞁䝪䝹䝸䝇䝖㻦㻌䛾ୖ఩㻞␒┠䛾䝡䝑䝖䛿

to

be

or

die
or

to

be
live
not
die
to
live
not
or to

ฟ⌧఩⨨: ͢ ͦ ͢͡ ͨ ͤ ͣ ͩ ͡ ͥ ͪ ͧ
not or be┤๓䛾༢ㄒ: to to to to or be live
図1

0

1

͢͢͢͢͡͡
͢͢͢͢͡͡

ͤͣͤͤͣ
͢͢͢͡͡

0

1

ͣͣ ͤͤͤ

図 2 ウェーブレット木の例．

接尾辞配列（接尾辞木と同等）の例．

アルゴリズム 1: Access
Input: 位置 i

式 (1)，(2) はそれぞれ直接的および間接的な N-gram IDF の書数），df (g) は D における g の文書頻度，df (w1 , · · · , wN ) は

01͡͡ ͢͢͢͢

テキスト「to be or not to be to live or to die」に対する拡張

重みとして定義される．なお，|D| は文書集合 D のサイズ（文Output: シンボル s = L[i]1j = i, s = B1 [j], ps = 0, pe = n;2

for k = 1 to ⌈log |S|⌉ − 1 do

D における g の構成単語 w1 , · · · , wN の論理積に対する文書頻3pb = ps + rank0 (Bk , pe ) − rank0 (Bk , ps );度である．文献 [17], [18] では，式 (2) が単語 N-gram の長さに4

if Bk [ps + j] == 0 then

依らない公平な重みとして利用できることが示されている．ま5j = rank0 (Bk , ps + j) − rank0 (Bk , ps );た，式 (1)，(2) ともに単語 N-gram の特徴量として利用できる．

6

pe = pb ;7

3. 厳密計算手法
本研究の提案手法は，先行研究 [17], [18] で用いられている

N-gram IDF の厳密計算手法の拡張であるため，本章では厳密計算手法について詳しく説明する．厳密計算手法では，文書集
合 D を入力とし，D に出現する全ての有効な単語 N-gram gについて df (w1 , · · · , wN )（および df (g)）を計算する．ここで，䜘䜚ͤͣͤͤͣ͢͢͢͢͡͡
͢͢͢͢͢͡͡͡͡͡͡

else

8

j = rank1 (Bk , ps + j) - rank1 (Bk , ps );9

ps = pb ;

10

end

11

s = s << 1;

12

s = s + Bk+1 [ps + j];

13

end

有効な単語 N-gram を，文書集合における出現頻度（注 1） が δ 以
上の極大部分文字列と定義する．極大部分文字列 [11] とは，自ンボル s ∈ S = {0, 1, 2, · · · , |S| − 1} のリスト L[0, n − 1] を身を含み自身より長い単語 N-gram の中で出現頻度が一致する

考える．ウェーブレット木は，L を ⌈log |S|⌉ 個のビットのリものが存在しない単語 N-gram（注 2） である．文書集合中の有効

スト Bk [0, n − 1]（k = 1, · · · , ⌈log |S|⌉）として表現する．B1

な単語 N-gram を列挙するため，拡張接尾辞配列 [1] を用いる．

は L の上位 1 番目のビットを格納する．B2 は L の上位 2 番目

図 1 は拡張接尾辞配列の例を表している．拡張接尾辞配列におのビットを格納するが，その順番は上位 1 番目のビットによりいて，子ノード（直後の単語）と直前の単語がそれぞれ複数存

ソートされる．すなわち，上位 1 番目のビットが 0 のシンボル，

在するノードが極大部分文字列となる．図 1 において，そのよ

1 のシンボルがそれぞセグメントとして順番に格納される．まうなノードはルートノードを除いて「or」「to」「to be」の三種

た，同じセグメント内では B1 における順番が保持される．こ類である．
「be」は直前の単語が全て「to」であるため，極大部

れにより，下記の O(1) の rank 関数を用いて，B1 から対応す

分文字列とはならない．極大部分文字列の数は，入力テキスト処理である AND クエリを各単語 N-gram に対して実行し，る B2 のビットを一意に特定できる．
0
rankb (B, i) =ビット b の B[0, i − 1] 中の数

df (w1 , · · · , wN ) を得る．AND クエリの実行にはウェーブレッ

k > 2 の Bk についても同様に，上位 k 番目のビットが，Bk−1

ト木を利用する．ウェーブレット木 [7] は，様々な操作に対しの各セグメントにおけるビットによってソートされた後に格納て高速に処理可能なデータ構造であり，近年，AND クエリにされる．結果的にウェーブレット木は，各シンボルの上位 k 番

対する文書検索に対しても高速に処理できることが示されてい目のビットにしたがって上位 k + 1 番目のビットをノード 0 ある [6]．N 個の単語を条件として文書集合 D を検索したとき，

るいは 1 に分類する二分木となる．図 2 にウェーブレット木のの長さ（単語数）の二倍を超えないことが保証されている．
有効な単語 N-gram を列挙した後，厳密計算手法の重要な計算量は O(N · α · log |D|) となり，これは理論的な下限値 [3]α(i = 0)(0 < i <= n)例を示す．図 2 において，L[8] = 1（ビット表現で 01）の上位に近い．なお，α は alternation complexity [6] と呼ばれ，少な

2 番目のビットは，ビット B1 [8] = 0 の B1 [0, 7] 中の数が 5 でくとも文書頻度以上となる．

あるため，B2 [5] = 1 であるとわかる．

近似計算手法はウェーブレット木を用いたアルゴリズムの拡張であるため，ここでウェーブレット木について詳述する．シ

アルゴリズム 1 は位置 i に対応するシンボル L[i] をウェーブ
レット木 B1 , · · · , B⌈log |S|⌉ 上で参照する関数である．深さ k の（注 1）：文書頻度とは異なることに注意．

各ノード（セグメント）は，Bk 中の開始位置 ps と終了位置 pe ，

（注 2）：単語を最小単位とした場合，任意の文字列は単語 N-gram となる．

すなわち Bk [ps , pe − 1] によって表現される．このとき，深さᩥ᭩㞟ྜ㻦
“to be”,“or not to be”,༢ㄒ䝸䝇䝖:
᥋ᑿ㎡㓄ิ:
ᩥ᭩䝸䝇䝖:“to live”,“or to die”

“to be or not to be to live or to die”䜽䜶䝸㻦 “to be”㐺ྜᩥ᭩㻦㻌͑͢͡͝“to be”䜽䜶䝸㻦㻌“to” “be”㐺ྜᩥ᭩㻦㻌͑͢͡͝
“be”
“to”

ͤͣͤͤͣ͢͢͢͢͡͡
͢͢͢͢͢͡͡͡͡͡͡

ͤͣͤͤͣ͢͢͢͢͡͡
͢͢͢͢͢͡͡͡͡͡͡

ͤͣͤͤͣ͢͢͢͢͡͡
͢͢͢͢͢͡͡͡͡͡͡

1͢͢͢͢͡͡
͢͢͢͢͡͡

ͤͣͤͤͣ
͢͢͢͡͡

0

0

͡͡ ͢͢͢͢

1

0

1

ͤͣͤͤͣ
͢͢͢͡͡

͢͢͢͢͡͡
͢͢͢͢͡͡

ͤͣͤͤͣ
͢͢͢͡͡

0

0
1

0
͢͢͢͢͡͡
͢͢͢͢͡͡

1͡͡ ͢͢͢͢

01

ͣͣ ͤͤͤ

01

͡͡ ͢͢͢͢

01

ͣͣ ͤͤͤ

図 4 図 3 のウェーブレット木における文書頻度の算出の例．左の図は

1

単語 2-gram「to be」，右の図は二単語「to」「be」の例である．

ͣͣ ͤͤͤ

アルゴリズム 2: CountDF

図 3 文書リストに対するウェーブレット木の例．

Input: 単語の開始位置 is [0, m − 1], 単語の終了位置

k + 1 の子ノード 0 および 1 は，境界位置 pb（ps <= pb <= pe ）によって分けられる．具体的には，子ノード 0 は Bk+1 [ps , pb − 1]，ie [0, m − 1], 単語の出現回数 o[0, m − 1], 深さ k = 1, 開
始位置 ps = 0, 終了位置 pe = n

Output: 文書頻度 df

子ノード 1 は Bk+1 [pb , pe − 1] となる．各子ノードの長さはそれぞれ Bk [ps , pe − 1] 中のビット 0 および 1 の数に一致する．
アルゴリズム 1 は，Bk 中のセグメント中の位置 j （初期位置

12

if k > ⌈log |D|⌉ then // 葉ノードに到達
return 1;

3

end

4

df = 0, f0 = true, f1 = true;を用いて変更しながら，ウェーブレット木を B1 から B⌈log |S|⌉5

pb = ps + rank0 (Bk , pe ) − rank0 (Bk , ps );まで順にたどっていく．次の j は，Bk [ps + j] が 0（あるいは6init is0 [0, m − 1], ie0 [0, m − 1], is1 [0, m − 1], ie1 [0, m − 1];1）のとき，Bk [ps , j − 1] におけるビット 0（あるいは 1）の数

7

for j = 0 to m − 1 doi），ps（初期位置 0），pe（初期位置 n）をそれぞれ rank 関数を計算することで得られる．また，Bk [ps + j] が 0 のときは次8is0 [j] = rank0 (Bk , ps + is [j]) − rank0 (Bk , ps );の終了位置を pb に，1 のときは次の開始位置を pb に設定する．

9ie0 [j] = rank0 (Bk , ps + ie [j]) − rank0 (Bk , ps );

最終的に，各 k において対応するビット Bk [ps + j] をつなげたビット列が L[i] となる．

10

is1 [j] = rank1 (Bk , ps + is [j]) − rank1 (Bk , ps );11

ie1 [j] = rank1 (Bk , ps + ie [j]) − rank1 (Bk , ps );12

if ie0 [j] − is0 [j] < o[j] then

ウェーブレット木を用いた文書頻度の算出 [6] は，アルゴリ

13

ズム 1 を拡張することで実現できる．文書集合 D を単語のリ

14

end

スト LW [0, n − 1] として表現する．LW から拡張接尾辞配列

15

if ie1 [j] − is1 [j] < o[j] thenを構築することにより，有効な単語 N-gram の集合 Gv が得

16

られる．また，この処理の過程で，LW を接尾辞によりソー17トした接尾辞配列 LSA [0, n − 1] が生成される．その後，単語[]
LW LSA [i] の出現する文書が LD [i] となるような文書リスト

18

end

19

if f0 then // 子ノード 0 を探索

LD [0, n − 1] を作成する．LSA [i] はソートされているため，任20

意の単語 N-gram gv ∈ Gv が出現する文書を LD 中のセグメン

f0 = false;

f1 = false;end

df = CountDF (is0 , ie0 , o, ps , pb , k + 1);

21

end

22

if f1 then // 子ノード 1 を探索

トとして表現できる．そして，LD に対してウェーブレット木

23を構築する．図 3 は文書リストに対するウェーブレット木の例

24

df = df + CountDF (is1 , ie1 , o, pb , pe , k + 1);
endを表している．LW は図 1 と同じであるため，LSA は図 1 の出現位置の順番に一致する．また，LD は図 2 のシンボルリス
トと同一であるため，構築されたウェーブレット木は図 2 と等しくなる．ここで，単語 N-gram gv ∈ Gv を含む文書集合は

LD 中の連続した区間として表されるため，図 4 のように単語
N-gram あるいは単語を表す区間の開始位置と終了位置についてウェーブレット木をたどることで文書頻度を算出できる．このとき，AND クエリ（図 4 右）であっても，全ての開始位置と終了位置の組について同時にウェーブレット木をたどり，到達できた葉ノードの数をみることで文書頻度が得られる．
アルゴリズム 2 はウェーブレット木上で文書頻度を算出する再帰関数である．初期の引数は単語 N-gram を構成する m 個の単語であり，それぞれ開始位置 is [j]，終了位置 ie [j]，出現回数 o[j] の三つ組に変換される．なお，通常 o[j] = 1 であるが，同じ単語が一つの単語 N-gram の中に複数回出現する場合のみ

2 以上となる．また，深さ k，セグメントの開始位置 ps および終了位置 pe はそれぞれ 1，0，n（すなわち B1 [0, n − 1]）として初期化される．j + 1 番目の単語について，深さ k + 1 の子
ノード 0 における開始位置 is0 [j] と終了位置 ie0 [j]，子ノード 1における開始位置 is1 [j] と終了位置 ie1 [j] をそれぞれ rank 関
数によって計算する．このとき，子ノードにおける長さ（開始
位置と終了位置の差）が o[j] より小さい場合，その子ノードでの単語の出現回数は必ず o[j] 未満となるため，これ以上子ノードをたどる必要がない．アルゴリズム 2 は再帰的に子ノードをたどり，葉ノードに到達した回数を数えることで，文書頻度を
算出する．

表1

4. 近似計算手法

ポアソン分布のパラメータ（平均値）に対する信頼区間．

95%信頼区間

99%信頼区間

下限値

上限値

下限値

上限値

1

0.03

5.57

0.01

7.43

k

3. 章で説明した厳密計算手法は，下限 [3] に近い計算量を達成しているが，依然としてサイズの大きいコーパス（英語版

5

1.62

11.67

1.08

14.15

10

4.80

18.39

3.72

21.40

という問題がある．これは，多くの単語 N-gram について，構成

20

12.22

30.89

10.35

34.67

単語の論理積に対する文書頻度 df (w1 , · · · , wN ) が |D| に近く

50

37.11

65.92

33.66

71.27

なるためである．このとき，α（alternation complexity）は |D|100

81.36 121.63

Wikipedia など）に対しては現実的な処理時間を達成できないとして近似できるため，厳密計算手法の計算量 O(N · α · log |D|)α
は O(N · |D|) となる．これは単一の単語 N-gram の重みを計算するときの計算量であり，有効な単語 N-gram の数が O(|D|)
であることを考慮すると，全体の計算量はコーパスサイズ |D|に対して O(|D|2 ) で増加する．
本研究では計算量を削減するため，近似計算手法を提案する．
提案手法は，コーパスサイズ |D| に対して O(|D| · log |D|) 程
度の計算量を達成しつつ，N-gram IDF の誤差分布を一つのパラメータにより制御可能とする．これにより，厳密値を用いた場合と比べてアプリケーションにおける性能を低下させない程度の誤差を許容するよう手法を調整できる．以下ではまず，ポアソン分布による誤差の分析を行い，その後，ウェーブレット
木を用いた近似計算手法について説明する．
提案手法のアプローチは，部分文書集合を用いて文書集合全体における文書頻度を推定するというものである．本節ではまず，部分文書集合で観測した文書頻度と，文書集合全体における文書頻度の関係性を明らかにする．無作為に抽出された部分
文書集合 Ds ⊂ D が与えられたとき，Ds における単語 N-gram

g の文書頻度の期待値 ⟨dfs (g)⟩ は以下のとおりである．
|Ds |⟨dfs (g)⟩ =· df (g)|D|
一方，文書集合 Ds で文書頻度 dfs (g) を観測したとき, D における文書頻度の期待値 ⟨df (g)⟩ はを用いて以下のように計算される．

()
Pλ (X = x) = exp x log λ − λ − log Γ(x + 1)
部分文書集合 Ds で観測される文書頻度 dfs (g) は，Ds の抽出が無作為であるとき，λs = ⟨dfs (g)⟩ のパラメータを持つポア
ソン分布に従う．このとき，dfs (g) と ⟨dfs (g)⟩ の誤差の分布はポアソン分布の信頼区間を用いて推定できる．表 1 にポアソン分布の信頼区間の一例を示す [20]．単位間隔において事象を k回観測したとき，ポアソン分布のパラメータ λ は，指定した信頼水準（表 1 では 95%または 99%）で下限値と上限値の間にある．たとえば，部分文書集合 Ds において文書頻度 dfs (g) = 20
る確率が 99%となる．

IDF の誤差は，文書頻度の期待値と観測した文書頻度との差
(L)

(U )

によって決まる．λsと λsをそれぞれ文書頻度 dfs を観測したときの λs の下限値および上限値とする．このとき，単語N-gram g の IDF の下限値 IDF (L) (g) と上限値 IDF (U ) (g) はそれぞれ以下のようになる．

IDF (L) (g) = log|Ds |IDF (U ) (g) = log

λs
|Ds |

(4)

(U )

(5)

(L)

λs

式 (3)，(4)，(5) より，IDF の誤差の下限値および上限値は以下のように計算できる．

|D|· dfs (g)
|Ds |

(L)

となるため，dfs (g) から推測される IDF 値は以下のようになる．

|D|
|Ds |
⟨IDF (g)⟩ = log= log⟨df (g)⟩dfs (g)

なお，数値安定性のため，一般にガンマ関数の自然対数 log Γを観測したとき，パラメータ λs が 10.35 から 34.67 の間であ

4. 1 ポアソン分布による誤差の分析⟨df (g)⟩ =76.12 128.76⟨IDF (g)⟩ − IDF (U ) (g) = log

|Ds |
|Ds |
λs
− log (L) = log
dfs (g)
df
s (g)
λs

⟨IDF (g)⟩ − IDF (L) (g) = log

|Ds |
|Ds |
λs
− log (U ) = log
dfs (g)
df
s (g)
λs

(U )

(3)

本節における問題は，推測された重み ⟨IDF (g)⟩ が実際の重

(L)

λs

(U )

と λs

は観測した文書頻度 dfs (g) によって決まるため，

み IDF (g) とどの程度異なるかを分析することである．本研究

結果的に IDF の誤差は dfs (g) のみに影響を受ける．すなわち，

では，ポアソン分布を用いてこの問題を解決する．ポアソン分

部分文書集合の大きさ |Ds | は IDF の誤差に影響しない．

布 [8] は，一定の時間あるいは空間内（単位間隔）である事象

上 記 の 誤 差 は N IDFd (g) に つ い て も 同 様 に い え る ．

が発生する回数の確率を表す離散確率分布である．単位間隔で

N IDFi (g) の場合，誤差は 2 倍になる．df (g) が既知であるの平均発生回数が既知で，かつ各事象が独立である場合，そのとして，期待値 ⟨N IDFi (g)⟩ は以下のように計算される．

事象はポアソン分布に従う．ポアソン分布のパラメータ λ は，単位間隔での平均発生回数であり，同時に分散でもある．パラメータ λ のポアソン分布に従う確率変数 X （x = 0, 1, 2, · · · ）は，以下の式を満たす．

Pλ (X = x) =λx e−λx!

⟨N IDFi (g)⟩ = log|D| · df (g)⟨df (w1 , · · · , wN )⟩2|D| · df (g))2·dfs (w1 , · · · , wN )|Ds |= log ( |D|= log|Ds |2 · df (g)|D| · dfs (w1 , · · · , wN )2

なお，dfs (w1 , · · · , wN ) は部分文書集合 Ds における N-gram

g の構成単語 w1 , · · · , wN の論理積に対する文書頻度である．

アルゴリズム 3: CountSubsetDF⟨dfs (w1 , · · · , wN )⟩ を Ds における文書頻度の期待値とすると，Input: 単語の開始位置 is [0, m − 1], 単語の終了位置
ie [0, m − 1], 単語の出現回数 o[0, m − 1], 規定の文書頻度

dfs (w1 , · · · , wN ) は λs = ⟨dfs (w1 , · · · , wN )⟩ のパラメータを
(L)

(U )

持つポアソン分布のサンプルとみなせる．λs

および λsdfp , 観測した文書頻度 dfo = 0, 深さ k = 1, 開始位置 ps

を，= 0, 終了位置 pe = n

dfs (w1 , · · · , wN ) を観測したときの λs の下限値および上限値とすると，N IDFi (g) の下限値および上限値は以下のようになる．
(L)

N IDFi(g) = log(U )N IDFi|Ds | · df (g)( (U ) )2|D| · λs2(g) = log

Output: 文書頻度 dfs , 非文書頻度 dfs
1
2|Ds |2 · df (g)( (L) )2
|D| · λs

if k > ⌈log |D|⌉ then // 葉ノードに到達
return 1;

3

end

4

dfs = 0, dfs = 0, f0 = true, f1 = true;5pb = ps + rank0 (Bk , pe ) − rank0 (Bk , ps );6

init is0 [0, m − 1], ie0 [0, m − 1], is1 [0, m − 1], ie1 [0, m − 1];

最終的に，N IDFi (g) の誤差の下限値と上限値は以下のように

7

for j = 0 to m − 1 do計算される．

8(U )⟨N IDFi (g)⟩ − N IDFi (g) = log( (L) )2λs
dfs (w1 , · · · , wN )2(L)λs= 2 logdfs (w1 , · · · , wN )( (U ) )2λs(L)⟨N IDFi (g)⟩ − N IDFi (g) = log
dfs (w1 , · · · , wN )2= 2 log9ie0 [j] = rank0 (Bk , ps + ie [j]) − rank0 (Bk , ps );10

is1 [j] = rank1 (Bk , ps + is [j]) − rank1 (Bk , ps );11

ie1 [j] = rank1 (Bk , ps + ie [j]) − rank1 (Bk , ps );12

if ie0 [j] − is0 [j] < o[j] then

14

end

15

if ie1 [j] − is1 [j] < o[j] then16dfs (w1 , · · · , wN )17ある場合，N IDFi (g) は IDF (g) や N IDFd (g) と比較して誤f0 = false;

13

(U )
λs

したがって，部分文書集合において観測した文書頻度が同じで

is0 [j] = rank0 (Bk , ps + is [j]) − rank0 (Bk , ps );f1 = false;
end

18

end

19

if f0 then // 子ノード 0 を探索

20

差が 2 倍になる．

(dfs , dfs ) =CountSubsetDF (is0 , ie0 , o, dfp , dfo , ps , pb , k + 1);

4. 2 ウェーブレット木を用いた近似計算手法

21

部分文書集合を用いた近似計算手法として，部分文書集合に22

対して構築されたウェーブレット木において文書頻度を計算す

23る方法が考えられる．しかし，前節より，部分文書集合から計24算した N-gram IDF の誤差の分布は部分文書集合において観測

if dfo == dfp thendfs = 2⌈log |D|⌉−k−1 ;else
dfs = 2⌈log |D|⌉−k ;25
26

した文書頻度によって決まるため，単語 N-gram ごとの重みの誤差を予測できないという問題がある．また，部分文書集合に

else // 子ノード 0 の非文書頻度を計算

end

27

end

28

if dfo + dfs <= dfp then

おける文書頻度が 0 となる場合も少なくない．全ての有効な単29

if f1 then // 子ノード 1 を探索

語 N-gram について N-gram IDF の誤差を制御するためには，

30(dfs , dfs ) = (dfs , dfs ) +観測される文書頻度が一定となるように単語 N-gram ごとに調整された部分文書集合を構築する必要がある．

CountSubsetDF (is1 , ie1 , o, dfp , dfo + dfs , pb , pe , k + 1);
31

そこで，単語 N-gram ごとに指定した数の文書頻度が得られ32るような部分文書集合をウェーブレット木上で動的に構築する

33

手法を提案する．提案手法の重要なアイデアは，アルゴリズム

34

2 の再帰呼び出しを規定の文書頻度 dfp が観測された段階で止めるというものである．これを実現するため，ウェーブレット
木における文書頻度の計算において，非文書頻度 dfs （対象の語を含まない文書の数）を導入し，サイズが |Ds | = dfs + dfsとなるように部分文書集合 Ds = {0, 1, 2, · · · , |Ds | − 1} を構築

dfs = dfs + 2⌈log |D|⌉−k−1 ;else
dfs = dfs + 2⌈log |D|⌉−k ;
end

36
37

end

38

end

39

if k == 1 then
< dfp thenif dfs =40
41

2くなるため，全体として O(|D| ) から O(|D| · dfp · log |D|
)程
dfp

42

度に削減できる．dfp は自由に指定できるため，誤差の大きさ

43と処理速度のトレードオフを調整できる．

44

提案手法の再帰関数をアルゴリズム 3 に示す．アルゴリズム

if dfo + dfs == dfp then

35

していく．計算量は，O(N · α · log |D|) における α が dfp に近α

3 はアルゴリズム 2 を修正したものである．アルゴリズム 2 にelse // 子ノード 1 の非文書頻度を計算

45

dfs = |D| − dfs ;else
dfs = dfs − 1;endend

加えて，初期の引数に規定の文書頻度 dfp を要する．また，各100,000,000

時点で観測した文書頻度 dfo を引数として渡すことで，いつ再10,000,000判断する．出力は，文書頻度 dfs と非文書頻度 dfs の二種類であり，部分文書集合を意味する．アルゴリズム 2 との大きな違いは，子ノード 0 あるいは 1 をこれ以上探索する必要がな
いとわかった場合（f0 あるいは f1 が false である場合），その子ノード以下の非文書頻度 dfs を計算する点である．ウェー
ブレット木が高さ ⌈log |D|⌉ + 1 の完全二分木であるとすると，
深さ k + 1 以下にある文書の数は 2⌈log |D|⌉−k となるため，子ノードを探索することなく非文書頻度を計算できる．しかし実際には，文書数がちょうど 2 のべき乗でない限りはウェー

1,000,000ฎ⌮᫬㛫䠄⛊䠅帰を止めるか，すなわち，dfp がすでに観測されたかどうかをApprox100
Approx50
Approx20
Approx10
Approx5

Exact

100,000
10,000
1,000
100
10
1
㻿㼡㼎㼟㼑㼠㻝㻛㻝㻜㻜㻜 㻿㼡㼎㼟㼑㼠㻝㻛㻝㻜㻜 㻿㼡㼎㼟㼑㼠㻝㻛㻝㻜
䝁䞊䝟䝇

඲య

図 5 厳密計算手法と近似計算手法の処理時間の比較．

5. 評 価 実 験

ブレット木は完全二分木とはならない．そのため，子ノード以提案手法の処理時間，提案手法を用いて得られた N-gram

下が完全二分木となっていない場合について考慮する必要が

IDF の近似値の誤差分布，および近似値を用いた場合のアプリ

ある．ここで，文書集合をインクリメンタルな整数，すなわちケーションにおける性能評価を行った．

D = {0, 1, 2, · · · , |D| − 1} として考える．ウェーブレット木は，

5. 1 処 理 時 間

上位 k 番目のビットに基づいて整数を深さ k + 1 の 0 あるい

厳密計算手法と比較して，提案した近似計算手法がどの程度は 1 のノードに割り振るため，深さ ⌈log |D|⌉ + 1 に位置する

高速に N-gram IDF を計算できるかを評価した．コーパスと葉ノードは，左から右の順に作成される．結果として得られる

して，2013 年 10 月 1 日の英語版 Wikipedia のダンプデータ

ウェーブレット木は，各深さの最も右にあるノード以外は完全（4,379,810 記事）を用いた．また，コーパスサイズに対する処

二分木となることが保証される．また，ウェーブレット木を左

1
1
理時間の比較を行うため，英語版 Wikipedia 全体の 1000， 100，から順番に探索していくと，最も右にあるノードを探索すると

1の大きさのコーパスを作成した．以降では上記のコーパス
10

きには全てのノードをチェックしていることになるため，このをそれぞれ Subset1/1000，Subset1/100，Subset1/10 と呼ぶ．

場合は最後に dfs を |D| − dfs として再設定することで正しい

dfp を 5，10，20，50，100 と変化させ，それぞれについて近値になる．なお，これは全体の文書集合 D における文書頻度

似計算手法の処理時間を計測した．上記の dfp のときの提案

が dfp 以下である場合にのみ起こる．

手法をそれぞれ Approx5，Approx10，Approx20，Approx50，

アルゴリズム 3 は現時点までに観測した文書頻度 dfo（とノーApprox100 と呼ぶ．また，厳密計算手法を Exact とする．

ド 0 において追加で観測した文書頻度 dfs の和）が dfp を超え

図 5 は各コーパス中の全ての有効な単語 N-gram（δ = 5）にたときに再帰を止める．言い換えれば，dfo + dfs = dfp のとき

ついて N-gram IDF を計算したときの厳密計算手法および近似

は再帰を続ける．これは，部分文書集合のサイズ |Ds | を正規計算手法の処理時間を表す．なお，有効な単語 N-gram の数は化するためである．dfo + dfs が dfp に到達した時点ですぐに再それぞれ 108,261（Subset1/1000），920,378（Subset1/100），

帰を終了した場合，ちょうど dfp を観測するような部分文書集

8,694,915（Subset1/10），87,491,762（全体）であった．厳密計合としては |Ds | が最も小さくなる．提案手法では，dfo + dfs

算手法の処理時間は，コーパスサイズ |D| に対し O(|D|2 ) で増が dfp を超えるまで再帰を継続し，ちょうど dfp を観測するよ加していることがわかる．また，厳密計算手法では Wikipedia

うな部分文書集合のサイズの平均を |Ds | として採用する．具

全体を処理することができなかった．そのため先行研究 [17], [18]体的には，dfo + dfs = dfp のとき，dfs を 12 として加えること

では，単語 N-gram に含まれる単語の文書頻度に対して文書頻でこれを実現する．dfo + dfs が dfp を超えた場合に再帰を終了

1
度が 2000に満たないものを省くという足切り処理を行った上し，最後に dfs から 1 減算する（dfs = dfp となる）．

で，メモリを 60GB 以上搭載した計算機（Intel(R) Xeon(R)アルゴリズム 3 は，部分文書集合 Ds = {0, 1, 2, · · · , |Ds |−1}

E5-2643 v2 @ 3.50GHz）を 2 台用いて 12 日かけて重みを計で観測した文書頻度がポアソン分布に従うように，文書集合

算した．その結果，約半数となる 39,610,779 の有効な単語 N-

D の文書の順番がランダムであることを想定している．s しgram について重みを得た．計算量が O(|D|2 ) であることから，

かし実際には，作成日時などの基準に基づいて文書が整列さ

厳密計算手法によって Wikipedia 全体を処理するためには，1

れていることが多い．そこで提案手法は，ランダム置換リスト

年以上かかることが予測される．

LR [0, |D| − 1] を用いて事前に文書集合の順番をランダムに入れ替える．具体的には，文書番号 i（0 <= i < |D|）に対して提案した近似計算手法についてみると，厳密計算手法と比較して大幅に処理時間を短縮できていることがわかる．特に，

LR [i]（0 <= LR [i] < |D|）がユニークかつランダムな番号となるようにする．なお，ランダムな置換は Fisher-Yates シャッフ1
コーパスサイズが大きい場合，処理時間は厳密計算手法の 100

ル [5] などのアルゴリズムを用いて線形時間で可能である．その計算機 1 台で，Wikipedia 全体に含まれる全ての有効な単語

して，文書リスト LD における文書番号 i を LR [i] に置き換え

N-gram について N-gram IDF を 1 日以内に計算できた．まてから，LD に対してウェーブレット木を構築する．

た，Approx100 でも，5 日以内に処理を終えることができた．

程度に短縮できている．Approx10（dfp = 10）のとき，上記༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ

6,000
5,000
4,000
3,000
2,000
1,000
0

4,000
2,000
0
-4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
ㄗᕪSubset1/1000，Approx100
༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ

Subset1/1000，Approx20

120,000
100,000
80,00060,00040,00020,0000-4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
ㄗᕪSubset1/100，Approx20

Subset1/100，Approx100

600,000
500,000
400,000
300,000
200,000
100,0000

1,200,000
1,000,000
800,000
600,000
400,000
200,0000-4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
ㄗᕪSubset1/10，Approx20

R-PrecApprox5•• 0.358

Approx10•• 0.367

Approx20•• 0.376

Approx50

0.382

Approx100

0.384

Exact

0.386

「••」は両側 t 検定において有意水準 99%で Exact より性能が低いことを表す．
-4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0ㄗᕪ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ༢ㄒ㻺㻙㼓㼞㼍㼙䛾ᩘ

手法

6,000

-4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
ㄗᕪ

60,00050,00040,00030,00020,00010,0000

表 2 特徴語抽出における性能評価．

8,000

2 log 76.12≈ −0.79，2 log 128.76≈ 0.73 と大幅に小さくなる．
100
100以上の結果より，提案手法による誤差が制御可能であることを，実際のデータを用いて実証できた．

5. 3 アプリケーションにおける性能評価
N-gram IDF の近似値がどの程度の誤差であればアプリケー-4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
ㄗᕪSubset1/10，Approx100

図 6 N-gram IDF の厳密値と近似値の誤差の分布．

近似計算手法の計算量は O(|D| · α · log |D|) であり，この ααは大まかに dfp として見積ることができる．しかし実際には，
図 5 において，コーパスサイズ |D| に対して見積った計算量よりも少し長い時間がかかっている．その理由の一つとして，小さいコーパスにおいては，より多くの割合の単語 N-gram について，構成単語の論理積に対する文書頻度が dfp よりも小さくなる（すなわち dfs < dfp ）ことが挙げられる．たとえば，Sub-

set1/1000 では 72%の単語 N-gram が dfs < 100 であるのに対し，Wikipedia 全体では 11%の単語 N-gram のみが dfs < 100となっていた．dfs < dfp のとき，一つの単語 N-gram について重みを計算するときの処理時間が O(N · dfp · log |D|
) ではな
dfp
く O(N · dfs · log |D|) となる．より多くの単語 N-gram についdfsて dfs < dfp となる場合，全体としての処理時間が短縮される．
また別の理由として，単語 N-gram の平均の長さ（N の平均）
がコーパスサイズに伴って大きくなることが挙げられる．単語

N-gram の平均の長さはそれぞれ 1.87（Subset1/1000），2.39（Subset1/100），2.93（Subset1/10），3.50（全体）であった．
単一の単語 N-gram の処理にかかる時間が O(N · dfp · log |D|)
dfp
であることから，単語 N-gram の平均の長さが全体の処理時間に影響していると考えられる．

5. 2 誤差の分布
5. 1 節で計算した N-gram IDF について，厳密値と近似値の誤差を検証した．図 6 は厳密値と近似値の誤差をヒストグラムとして表したものである．図 6 では，Approx20（dfp = 20）および Approx100（dfp = 100）について，Subset1/1000，Sub-

set1/100，Subset1/10 のそれぞれのコーパスにおける厳密値との誤差を計算している．なお，dfs <= dfp を満たす単語 N-gram
は，近似計算手法においても厳密値が得られるため，ヒストグ
ラムから除外した．図 6 より，誤差の分布が dfp のみによって決まっていることがわかる．これは 4. 1 節における分析と一致する．また，Approx20 の誤差は，表 1 を用いると，99%のションにおける性能が低下しないのかを検証する．先行研
究 [17], [18] と同様に，特徴語抽出および Web 検索クエリ分割のアプリケーションにおいて評価を行った．

5. 3. 1 特徴語抽出
特徴語抽出では，英語版 Wikipedia を用いて実験を行った．

Wikipedia では，各ページにおける特徴的な語がアンカーテキ
ストとして別の Wikipedia のページにリンクされているため，
これを正解データとして利用した．Wikipedia から選んだラン
ダムな 1,678 記事の第一段落をテストセットとし，テキストに含まれるアンカーテキストおよび太字の語（主に記事のタイトルが太字で表記される）を正解の特徴語とした．第一段落のみをテキストとして利用することで，多くの語の出現頻度が 1 となる状況が発生するため [19]，大域的重みである N-gram IDF
をより直接的に評価できる．第一段落から作成したデータセッ
トは，平均して 60.2 の単語（最大 291，最小 8），6.7 の特徴語
（最大 30，最小 3）を含む．それぞれの手法を用いて特徴語のランク付きリストを生成した後，各記事の正解数 R に対して上位 R の出力の適合率である R-Prec を計測した．
表 2 は特徴語抽出タスクにおける評価結果である （注 3）．dfp
が 50 あるいは 100 のとき，厳密値を用いた場合とほぼ同等の性能を近似値を用いて達成できている．また，厳密計算手法
において足切りされた単語 N-gram のうち，近似計算手法によってうまく抽出できたものも存在していた．たとえば，「angloamerican playing cards」という特徴語は，それ自体の出現回
1
数が，全ての構成単語の出現回数に対して 2000未満であったため，厳密計算手法では足切りされていた．近似計算手法では全ての有効な単語 N-gram について N-gram IDF を計算可能であるため，上記の特徴語を抽出できていた．一方で，dfp が小さい場合（20 以下），R-Prec は有意に低下していた．以上
より，特徴語抽出においては，dfp をある程度大きく（50 以上）することで，計算量を削減しつつ性能を維持できる．

5. 3. 2 Web 検索クエリ分割
Web 検索クエリ分割では，Roy らの情報検索ベースのデー
タセット [15] を用いた．このデータセットは 13,959 の Web

確率で 2 log 10.35≈ −1.90 から 2 log 34.67≈ 1.58 までの間と2020（注 3）：文献 [17], [18] と数値が異なるが，これは括弧などの特定の記号を除去

なり，図 6 と一致する．Approx100 の場合，それらの誤差はする処理を導入したためである．

られた N-gram IDF の誤差は，部分文書集合のサイズではな

表 3 Web 検索クエリ分割における性能評価．
手法

nDCG nDCG MAP MAP MRR MRR

く，部分文書集合で観測した文書頻度によって決まるためであ

@5

@10

@5

@10

@5

@10

Approx5• 0.725• 0.739

0.899

0.892

0.580

0.590

Approx10

0.728

0.741

0.899

0.892

0.577

0.587

Approx20

0.730

0.742

0.901

0.894

0.583

0.592

Approx50

0.730

0.743

0.900

0.893

0.587

0.596

出や Web 検索クエリ分割の性能が低下しないことを実証した．

Approx100

0.729

0.741

0.899

0.893

0.580

0.589

今後の課題として，さらなる高速化のため，単語 N-gram の

Exact

0.730

0.742

0.900

0.893

0.582

る．評価実験により，提案手法が厳密計算手法よりも 100 倍程
度高速に英語版 Wikipedia 全体を処理できることを示した．また，提案手法による N-gram IDF の近似値を用いても特徴語抽

0.593

足切り手法の考案が挙げられる．本研究では，出現回数が閾「•」は両側 t 検定において有意水準 95%で Exact より性能が低いことを表す．

値以上の全ての単語 N-gram を候補として N-gram IDF を計

ページ，500 のクエリ，クエリに対する Web ページの関連性算したが，実際には多くの単語 N-gram は重複する他の単語のスコア（Qrel）を含む．Qrel は 3 人の被験者が 3 段階（2：N-gram に完全に被覆され，最終的なアプリケーションの性能

強く関連がある，1：関連がある，0：関連がない）でクエリに寄与しない．そのため，不要な単語 N-gram を正確に足切り

中の全単語を含む Web ページを評価したものである．情報する手法を用いることで，アプリケーションの性能を維持しつ

検索ベースのクエリ分割では，与えられたクエリ（例：「larryつ，処理時間をさらに短縮できると考えられる．

the lawnmower tv show」）に対し，クエリを語句に分割（例：謝辞「larry the lawnmower」「tv show」）し，それらの語句が出現する Web ページのみを出力に含める（すなわち Web 検索に本研究の一部は，文部科学省科学研究費補助金・基盤研究

おける引用符を利用する）ことによって情報検索の性能がどの(A)(26240013)，JST 国際科学技術共同研究推進事業（戦略的程度向上するかを測定する．なお，クエリに対する文書の関連

国際共同研究プログラム），文部科学省国家課題対応型研究開

度は TF-IDF を用いて測る．分割された語句のうち，どの語句発推進事業−次世代 IT 基盤構築のための研究開発−「社会シに引用符を付けるかを決めるのは難しい問題であるため，Roy

ステム・サービスの最適化のための IT 統合システムの構築」

ら [15] はその中で最適な組合せをとった場合のスコアを測定の研究助成によるものである．ここに記して謝意を表す．
文している．本研究では，Roy らの評価方法に従う．評価尺度も

Roy らと同様に，nDCG，MAP，MRR を上位 5 および 10 のWeb ページに対して測定した．MAP と MRR は Qrel を二値（関連がある，関連がない）に変換する必要があるため，MAP
では 2 と 1 を，MRR では 2 のみを関連があるとみなした．

[1]

[2]
[3]
[4]

表 3 は Web 検索クエリ分割タスクにおける評価結果である．

dfp = 5 の場合を除いて，厳密値を用いた場合と同等の性能を
近似値を用いて達成できている．特筆すべき点として，特徴語
抽出タスクと比べて，小さい dfp で十分な性能を達成できた点が挙げられる．これは，クエリ分割タスクにおいては，特徴語

[5]
[6]

[7]
[8]

として一つの意味を表現するユニットを完全に抽出する必要が[9]ないためである．クエリ分割タスクでは，特徴語の一部あるいは特徴語を含む長い単語 N-gram であっても，検索結果を絞り[10]

込むのに有効な単語 N-gram であればよい．また，別の理由と[11]

して，Web 検索クエリは複数の不連続な語句によって成り立っ[12]ていることが挙げられる．自然文からの特徴語抽出とは異なり，[13]

語句の切れ目がより明確であることが多いため，抽出すべき単語 N-gram の候補を絞り込みやすい．上記の理由から，dfp が小さい場合，すなわち，近似値の誤差が大きい場合でも，クエリ分割において性能を維持できたと考えられる．

6. お わ り に本研究では，単語 N-gram の大域的重みである N-gram IDF

[14]
[15]

[16]

[17]
[18]

の近似計算手法を提案した．提案手法は，部分文書集合を用いて重みを近似的に算出するというアイデアに基づき，ウェーブ
レット木において指定した文書頻度をちょうど観測するような部分文書集合を動的に構築する．これは，部分文書集合から得

[19]

[20]

献

M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch. Replacing Suﬃx
Trees with Enhanced Suﬃx Arrays. Journal of Discrete Algorithms,
2(1):53–86, 2004.
A. Aizawa. An Information-Theoretic Perspective of TF-IDF Measures. Information Processing and Management, 39(1):45–65, 2003.
J. Barbay and C. Kenyon. Adaptive Intersection and t-Threshold
Problems. In SODA, pages 390–399, 2002.
F. Bu, X. Zhu, and M. Li. Measuring the Non-compositionality ofMultiword Expressions. In COLING, pages 116–124, 2010.
R. Durstenfeld. Algorithm 235: Random Permutation. Communications of the ACM, 7(7):420, 1964.
T. Gagie, G. Navarro, and S. J. Puglisi. New Algorithms on Wavelet
Trees and Applications to Information Retrieval. Theoretical Computer Science, 426–427:25–41, 2012.
R. Grossi, A. Gupta, and J. S. Vitter.
High-Order EntropyCompressed Text Indexes. In SODA, pages 841–850, 2003.
F. A. Haight. Handbook of the Poisson Distribution. Wiley, New York,1967.
K. S. Jones. A Statistical Interpretation of Term Specificity and its
Application in Retrieval. Journal of Documentation, 28:11–21, 1972.
D. Metzler. Generalized Inverse Document Frequency. In CIKM,
pages 399–408, 2008.
D. Okanohara and J. Tsujii. Text Categorization with All Substring
Features. In SDM, pages 838–846, 2009.
K. Papineni. Why Inverse Document Frequency? In NAACL, pages
1–8, 2001.
S. Robertson. Understanding Inverse Document Frequency: On theoretical arguments for IDF. Journal of Documentation, 60(5):503–520,
2004.
S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. In TREC, pages 109–126, 1994.
R. S. Roy, N. Ganguly, M. Choudhury, and S. Laxman. An IR-based
Evaluation Framework for Web Search Query Segmentation. In SIGIR, pages 881–890, 2012.
G. Salton, A. Wong, and C.-S. Yang. A Vector Space Model for
Automatic Indexing. Communications of the ACM, 18(11):613–620,
1975.
白川真澄, 原 隆浩, 西尾章治郎. コルモゴロフ複雑性に基づく IDF の単語 N-gramへの適用. 第 7 回データ工学と情報マネジメントに関するフォーラム, 2015.
M. Shirakawa, T. Hara, and S. Nishio. N-gram IDF: A Global Term
Weighting Scheme Based on Information Distance. In WWW, pages
960–970, 2015.
M. Timonen. Term Weighting in Short Documents for Document Categorization, Keyword Extraction and Query Expansion. PhD thesis,
University of Helsinki, 2013.
G. van Belle, L. D. Fisher, P. J. Heagerty, and T. Lumley. Biostatistics: A Methodology For the Health Sciences. Wiley, New York, 2ndedition, 2004.