H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
情報知識ネットワーク特論
情報検索２：全文テキスト検索
有村博紀・喜田拓也
北海道大学大学院情報科学研究科
コンピュータサイエンス専攻
E-mail: {arim,kida}@ist.hokudai.ac.jp
1
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
全文テキスト検索
Tries
Suffix Trees
Suffix Arrays
4
1
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
フルテキストサーチ
問題
z 入力：長い文字列（テキスト） T があらかじめ与
えられている．
z 出力：短い文字列（パターン）P を与えられたと
き，P がT に部分文字列として出現するような，
すべての位置を返せ．
目標：
z テキスト長 |T| にできるだけ依存せず，
O(|P|)時間くらいで，答えを計算する
アルゴリズムを作りたい．
情報知識ネットワーク特論（有村博紀）
5
H16/10/19, 北大大学院情報科学研究科
情報検索技術
情報検索の種類
z キーワード検索
z 全文テキスト検索
情報検索モデル
z ブール式モデル (Boolean)
z ベクトル空間モデル (Vector space)
z 確率的モデル (Probabilistic)
z 文字列照合 (String Pattern Matching)
6
2
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
全文テキスト検索
全文テキスト検索 (full-text search)
z 任意の文字列 P を問合せとして受け取り，
z パターン P を部分文字列として含むすべての
文書（または出現位置）を答えとして返す．
z 転置ファイル索引では苦手
実装方法
z 全文テキスト索引を用いる（今回）．
z 文字列照合アルゴリズムを用いる (喜田先生)
7
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
全文テキスト索引
接尾辞索引
z 接尾辞木 (Suffix trees, McReight 1967)
z 接尾辞配列 (Suffix arrays, Manber & Myers
1990～)
z 圧縮接尾辞配列 (CSA, Compressed suffix
arrays, FM, Sadakane, 2000年代～)
z 接尾辞オートマトン (DAWG, Haussler et al. '80s,
Inenaga et al.)
8
3
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
ウォーミングアップ
文字列の辞書
z （数十文字から数百文字以上の）長い文字列の
集合 S を，効率よく計算機上に格納したい．
z 所属性をO(M)時間くらいで判定したい．
（Mは文字列Pの長さ）
z 二分探索？
z ハッシュ？
z 平衡木？ B木
9
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
トライ (Trie構造）
z 可変長文字列の集合を格納するための効率
よいデータ構造
z 長さMの文字列の所属をO(M)時間で判定
z いわゆるデジタル探索木
z 実装
• 各ノードは，文字と「子供へのポインタ」をもつ
• 枝分かれは，ハッシュまたはリストで実装
• 実装手法で速度がものすごく違う
z 出典：
• Edward Fredkin, "Trie memory", CACM (1960)
• D. E. Knuth, The Art of Computer Programming
10
4
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
トライ
次の文字列集合を格納するトライを作れ
z archive
z ear
z architechture
z butter
z back
z cutter
z cat
z cute
z dog
z bad
z bear
文字列質問：dog, duck, bear, but
接頭辞質問：but, cut
情報知識ネットワーク特論（有村博紀）
11
H16/10/19, 北大大学院情報科学研究科
フルテキストサーチ
問題
z 入力：長い文字列（テキスト） T があらかじめ与
えられている．
z 出力：短い文字列（パターン）P を与えられたと
き，P がT に部分文字列として出現するような，
すべての位置を返せ．
目標：
z テキスト長 |T| にできるだけ依存せず，
O(|P|)時間くらいで，答えを計算する
アルゴリズムを作りたい．
12
5
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
接尾辞木 (Suffix tree)
与えられたテキストTのすべての部分語を
効率よく格納するデータ構造
z Tのすべての接尾辞から作られた圧縮トライ
z O(N)領域で格納可能 (テキストNバイト＋接尾辞木
16Nバイト)
z 与えられた長さMの文字列Pのテキスト中の出現を,
O(M)時間でみつけられる．
応用
z 多種多様な文字列処理の高速化
z ゲノムや自然言語処理
13
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
Suffix Tree (接尾辞木)
(1976, McCreight)
Text
1
2
3
4
5
6
7
8
9
a
b
c
a
b
b
c
a
$
a
b
b c
c a
b
a
b
$
c
a
$
4
1
$
8
b
Suffix tree
c
a
c
a
b
c
b
a
b $
$
c
a
$
5
2
$
b $
b
c
a
$
6
3
7
9
14
6
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
接尾辞配列：基本アイディア
接尾辞（Suffix)
重要な性質
z 部分文字列は，接尾辞の接頭辞
Suffix of the text
SEMI INFINITE STRINGS ARE ALSO CALLED SISTRI
STRINGS
Substring
すべての接尾辞を辞書順でソートする
情報知識ネットワーク特論（有村博紀）
15
H16/10/19, 北大大学院情報科学研究科
接尾辞木 (Suffix tree)
接尾辞木のテキストからの構築
z 単純な方法では，O(N2)時間が必要
• 長さO(N)のN本の接尾辞をトライに挿入するから．
z すごいこと： 接尾辞木をO(N)時間で作ること
ができる (Weiner 1973, McCreight 1976
z 作り方： 口頭で．
接尾辞木の問題点
z 実装では，接尾辞木16Nバイトのスペースが大きい．
z 構築アルゴリズムが複雑
16
7
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
接尾辞配列 (Suffix array)
辞書順にソートした接尾辞の先頭ポインタを左か
ら右に格納した１次元の整数配列
z 接尾辞木と同じ情報をもち，O(N)領域で格納．
接尾辞木より少ないバイト数で実現可能
• 1N + 4Nバイト（ 32ビットメモリ空間）
z 1980年代末に，Gonnet & Tompa のグループと
Manber & Meyer のグループが独立に発見．
計算効率
z 文字列ソートによりO(N log N)時間で構築できる
z 文字列検索が二分探索でO(M log N)時間で可能
17
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
Suffix array: 接尾辞をならべる
Text S
1
2
3
4
5
6
7
8
9
a
b
c
a
b
b
c
a
$
c
c
c
c
c
c
c
a
a
a
a
a
a
a
a
S9
$
$
$
$
$
$
$
$
$
Suffixes
S1
a
S2
b
b
S3
c
c
c
S4
a
a
a
a
S5
b
b
b
b
b
S6
b
b
b
b
b
b
S7
S8
18
8
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
Suffix array: 先頭をそろえて
Text T
1
2
3
4
5
6
7
8
9
a
b
c
a
b
b
c
a
$
c
a
$
a
$
$
Suffixes
S1
S2
S3
S4
S5
S6
S7
S8
S9
a
b
c
a
b
b
c
a
$
b
c
a
b
b
c
a
$
c
a
b
b
c
a
$
a
b
b
c
a
$
b
b
c
a
$
b
c
a
$
19
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
Suffix array: 辞書順にソート
1
2
3
4
5
6
7
8
9
a
b
c
a
b
b
c
a
$
a
b
b
c
a
$
a
a
b
$
c
a
b
b
c
a
$
b
b
b
b
c
c
a
c
a
a
$
b
$
b
c
a
$
b
c
a
$
Text T
Suffixes
S4
S1
S8
S5
S6
S2
S7
S3
S9
c
c
$
a
a
$
b
20
9
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
Suffix array: 接尾辞のポインタを格納
Text T
1
2
3
4
5
6
7
8
9
a
b
c
a
b
b
c
a
$
3
4
5
6
7
8
9
4
1
8
5
6
2
7
3
9
S1
S8
S5
S6
S2
S7
S3
S9
a
a
a
b
b
b
c
c
$
b
b
$
b
c
c
a
a
b
c
c
a
a
$
b
c
a
a
$
b
a
b
$
21
c
情報知識ネットワーク特論（有村博紀）
b
2
b
1
S4
Suffix Array SA
H16/10/19, 北大大学院情報科学研究科
接尾辞配列 (Suffix array)
文字列 P の検索
z 接尾辞配列上で2分探索を行う
z O(M log N)時間で長さMの文字列Pの検索が可能
z テキストへランダムアクセスをするので，ディスク上の
索引には向かない．
接尾辞配列の構築
z 文字列のソーティング (MM 1990,Sadakane 1999)
最近の研究
z ゲノムや自然言語処理への応用
z 圧縮接尾辞配列 (Ferragina et al.; Sadakane,
2000-)
22
10
H16/10/19, 北大大学院情報科学研究科
情報知識ネットワーク特論（有村博紀）
Suffix tree & array
b
b c $
c a
b
a
b 8
$
c
a
4
$
1
b
3
4
5
6
7
8
9
b b c a $
(1990, Manber etal.)
zCompactly
represent
all the substrings
represents
all the
in O(n) space.
substrings
with a 1-dimensional
integer array.
c
a
c
a
b
c
a
b
$
b $
c
5 a
6
$
2
2
Suffix
Suffix tree
array
(1976, McCreight)
a
1
a b c a
Data structures for efficiently storing all
of O(n2) substrings in O(n) space
Suffix tree
Text
$
1
3
$
7
3
4
5
6
7
8
9
4 1 8 5 2 6 3 7 9
Problems
9
b
b
c
a
$
2
az
bz
b
cz
a
$
b c c $
aNotaspace
b b
efficient.
c c a a
bDynamic
$ b reconstruction
cis not easy.
c a a b $
aNot suitable
a b for$ b
c
bimplementation
$ b on the
a
bsecondarycstorage.
a
$
c
$
a
$
23
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
他の全文テキスト検索手法
文字列パターン照合
前処理として，与えられた問合せ文字列(パターン）Pを「コンパ
イル」して，パターン照合機械 MPをつくる．
z パターン照合機械MPを，入力テキストT上で逐次的に走らせて，
T中のPの出現をすべて検出する．
z KMP, BM, AC, etc. etc.
z
特徴：
長所： あらかじめ索引をつくる必要がないため，更新が頻繁な
テキストに向く．
z 長所： 柔軟な／高度な検索が可能
z 短所： テキスト長O(N)だけの時間はかかる．
z
演習：
z
文字列パターン照合は，本当に大規模応用には向かないか?
24
11
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
まとめ
情報検索
z 蓄積された大量のデータから，利用者が
ほしい情報をとりだすこと
z データ＝文書集合
25
情報知識ネットワーク特論（有村博紀）
H16/10/19, 北大大学院情報科学研究科
まとめ：情報検索技術
情報検索の種類
z キーワード検索
z 全文テキスト検索
索引構造（ファイル構造）
z 転置ファイル（Inverted files)
z トライ (Trie)
z 接尾辞木 (Suffix trees)
z 接尾辞配列 (Suffix arrays)
その他の話題 (PageRank, 協調フィルタリング）
26
12
© Copyright 2024 ExpyDoc
