Document

テキスト検索は
文字列検索でも木検索でもない
京都大学人文科学研究所附属漢字情報研究センター
安岡孝一
テキスト処理とコンピュータの出会い
• IBM 704 (1954)
入出力にCPY命令を使用
• 連続したメモリの内容を順次入出力
• FORTRAN I (1956)
「Hollerith field」をFORMAT文に導入
• 定数長の連続した文字の列
• メモリ空間上に連続的に配置
文字列(string)の登場
• ALGOL 60 (1960)
BNFによって定式化
「string」を1次元の文字の列として定義
<proper string> ::= <any sequence of basic symbols not containing ‘ or ’>|<empty>
<open string> ::= <proper string>|‘<open string>’|<open string><open string>
<string> ::= ‘<open string>’
多くの実装では「string」をメモリに連続配置
文字列処理の実用化
• IBM System/360 (1964)
メモリ単位を8bit=1byteに
1文字=1byte (EBCDIC)
• PL/I (1964)
CHARACTER型を規定
文字列に対する比較操作が可能に
文字列検索アルゴリズムの登場
• Morris-Pratt (1970)
部分マッチング後の検索キーのシフト量を増加
• Knuth-Morris-Pratt (1974)
Morris-Prattをさらに改良
• Aho-Corasick (1975)
複数の検索キーに対し平行して検索
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
Aho-Corasickアルゴリズム
ex) ITALYとTIEとTULIAを検索
T
A
I
E
L
Y
I
A
I
T
U
L
INSTITUTE FOR RESEARCH IN HUMANITIES
逆方向文字列マッチング
• Boyer-Moore (1977)
検索キーの末尾からマッチングをおこなう
非マッチング時の検索キーのシフト量を増加
• Commentz-Walter (1979)
複数の検索キーに対しBoyer-Mooreを適用
Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索
I
7
T
6
A
T
T
7
U
6
L
5
5
5
L
I
I
4
4
3
Y
E
L 1
I 1
A
T 2
U 3
その他 3
INSTITUTE FOR RESEARCH IN HUMANITIES
Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索
I
7
T
6
A
T
T
7
U
6
L
5
5
5
L
I
I
4
4
3
Y
E
L 1
I 1
A
T 2
U 3
その他 3
INSTITUTE FOR RESEARCH IN HUMANITIES
Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索
I
7
T
6
A
T
T
7
U
6
L
5
5
5
L
I
I
4
4
3
Y
E
L 1
I 1
A
T 2
U 3
その他 3
INSTITUTE FOR RESEARCH IN HUMANITIES
Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索
I
7
T
6
A
T
T
7
U
6
L
5
5
5
L
I
I
4
4
3
Y
E
L 1
I 1
A
T 2
U 3
その他 3
INSTITUTE FOR RESEARCH IN HUMANITIES
Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索
I
7
T
6
A
T
T
7
U
6
L
5
5
5
L
I
I
4
4
3
Y
E
L 1
I 1
A
T 2
U 3
その他 3
INSTITUTE FOR RESEARCH IN HUMANITIES
Commentz-Walterアルゴリズム
ex) ITALYとTIEとTULIAを検索
I
7
T
6
A
T
T
7
U
6
L
5
5
5
L
I
I
4
4
3
Y
E
L 1
I 1
A
T 2
U 3
その他 3
INSTITUTE FOR RESEARCH IN HUMANITIES
漢字テキスト検索への応用
• 1文字≠1byte
ex) 「安岡の1族」を日本語EUCで表現
安
岡
の
1 族
B0 C2 B2 AC A4 CE 31 C2 B2
単純なバイト列マッチングでは検索に失敗？
漢字テキスト検索への応用
• 1文字≠1byte
• 異体字による曖昧検索
ex) 「帝國大學」の検索
「帝国大学」も「帝國大学」も「帝国大學」も…
「國」の異体字: 国、囯、囻、圀、囶
「學」の異体字: 学、斈、斆、斅
幾何級数的に組み合わせが増える
漢字テキスト検索への応用
• 篠原－有川 (1985)
Aho-Corasickを漢字テキスト用に改良
ex) 日本語EUCで「十週休」と「十周休」を検索
BD
A1～AF
B1～FE
A1～FE
BD
BD
B5
BC
FE
B5
D9
漢字における逆方向マッチング
• 日本語EUCやシフトJISでは難しい
• UTF-8を考案(1993)
– ISO 10646 (Unicode)の変形の一種
– 1文字を1～6バイトで表現
• 1バイト目には00～7F、C0～FEを使用
• 2バイト目以降には80～BFを使用
安
岡
の
1 族
E5 AE 89 E5 B2 A1 E3 81 AE 31 E6 97 8F
UTF-8での逆方向マッチング
• Commentz-Walterを使用可能
∵ 文字間にマッチングすることはありえない
88
ex) 「大学」「大學」「大斈」を検索
E5
11
A4
10
A7
9
E5
E5
8
8
E6
8
AD
AD
96
7
7
A6
B8
88
7
1
96
2
A4
5
A6
1
A7
4
AD
2
B8
1
E5
3
E6
3
他
6
漢字テキスト検索への応用
• 1文字≠1byte
• 異体字による曖昧検索
• テキストの非１次元性
漢字テキストの非１次元性
• ルビつきテキストの検索
やすおかこういち
私は安岡孝一です。
安岡孝一です
漢字テキストの非１次元性
• ルビつきテキストの検索
やすおかこういち
私は安岡孝一です。
私はやすおか
漢字テキストの非１次元性
• ルビつきテキストの検索
やすおかこういち
私は安岡孝一です。
安岡こういち
漢字テキストの非１次元性
• ルビつきテキストの検索
やすおかこういち
私は安岡孝一です。
漢字テキストの非１次元性
• ルビつきテキストの検索
• 本文に埋め込まれた注の検索
故宮の神(玄の避諱)武門に向かった。
神武門
漢字テキストの非１次元性
• ルビつきテキストの検索
• 本文に埋め込まれた注の検索
故宮の神(玄の避諱)武門に向かった。
故宮の玄武門
漢字テキストの非１次元性
• ルビつきテキストの検索
• 本文に埋め込まれた注の検索
故宮の神(玄の避諱)武門に向かった。
テキスト検索は文字列検索ではない
• テキストの非１次元性にどう対処するか
– XML/XHTMLを使う？
ex) XHTMLにおけるRuby Annotation (2001)
<p>私は<ruby xml:lang=“ja”>
<rbc><rb>安</rb><rb>岡</rb><rb>孝</rb><rb>一</rb></rbc>
<rtc><rt>やす</rt><rt>おか</rt><rt>こう</rt><rt>いち</rt></rtc>
</ruby>です。</p>
<p>私は<ruby xml:lang=“ja”>
<rbc><rb>安</rb><rb>岡</rb><rb>孝</rb><rb>一</rb></rbc>
<rtc><rt>やす</rt><rt>おか</rt><rt>こう</rt><rt>いち</rt></rtc>
</ruby>です。</p>
p
私は
です。
ruby
rbc
rtc
rb
rb
rb
rb
rt
rt
rt
rt
安
岡
孝
一
やす
おか
こう
いち
木構造がテキストの流れと合致しない
p
私は
です。
ruby
rbc
rtc
rb
rb
rb
rb
rt
rt
rt
rt
安
岡
孝
一
やす
おか
こう
いち
テキスト検索は文字列検索ではない
• テキストの非１次元性にどう対処するか
– Directed Acyclic Graphでテキストを実装？
検索アルゴリズムは？
DAGテキストの検索アルゴリズム
• Aho-Corasick風アルゴリズム
– 深さ優先で容易に実装可能
– パスが縮退した際の打ち切りは容易
• Commentz-Walter風アルゴリズム
– 深さ優先で実装可能
通ってきたノードを記憶する必要あり
– パスが縮退した際の打ち切り条件が複雑
DAGテキストの検索アルゴリズム
• 分岐と縮退によるパス数の爆発
• 縮退時の打ち切りは？
– Aho-Corasick風アルゴリズム
初期状態に戻れば確実に打ち切れる
– Commentz-Walter風アルゴリズム
「その他」が起これば確実に打ち切れる
今後の課題
• DAGテキスト検索アルゴリズムの高速化
– パス数の爆発を抑えられるか？
– 縮退時の打ち切り条件をtightにできるか？
– もっと効率のよいアルゴリズムはないか？
テキスト検索は
文字列検索でも木検索でもない
京都大学人文科学研究所附属漢字情報研究センター
安岡孝一

Download Report