半構造化テキストに対する
文字列照合アルゴリズム
喜田 拓也* 貴福 友晴† 竹田 正幸†
*九州大学附属図書館研究開発室
†九州大学システム情報科学府情報理学専攻
発表者： 喜田 拓也
発表内容
研究の目的
既存の手法
我々のアプローチ
文字列照合による処理の利点と問題点
提案アルゴリズム
誤検出を回避する方法
パスを考慮した照合処理
実験結果
まとめ
2001年度冬のLAシンポジウム
2/15
既存の手法
メモリ
XML文書
“”
person
Ｘ
Ｍ
Ｌ
パ
ー
サ
ー
XML文書
person
person/
name
“”
person/
name/first
Makiko
first
person/
name/last
last
Tanaka
Makiko
…
Tanaka
…
name
2001年度冬のLAシンポジウム
DOM
API
プ
ロ
グ
ラ
ム
3/15
我々のアプローチ
XML文書
メモリ
<person>
<name>
<first>
Makiko
</first>
<last>
Tanaka
</last>
</name>
</person>
XML文書
文
字
列
照
合
ア
ル
ゴ
リ
ズ
ム
2001年度冬のLAシンポジウム
プ
ロ
グ
ラ
ム
4/15
利点
処理が高速
XML文書
少ないメモリで可
様々な応用
木構造
巨大なXML文書や大量の文書群を一括に処理
複数の質問を同時に処理
2001年度冬のLAシンポジウム
5/15
文字列照合問題
パタン
テキスト
matching
Pattern matching is one of the most fundamental operations in string
processing. Recently, a new trend for accelerating pattern matching
has emerged: Speeding up pattern matching by text compression.
From the traditional criteria for data compression, i.e., compression
ratio and compression/decompression time, adaptive dictionary
methods such as the Lempel-Ziv family are often preferred. However,
such methods cannot speed up the pattern matching since an extra
work is needed to keep track of compression mechanism.
Knuth-Morris-Pratt (1974)
Boyer-Moore (1977)
Aho-Corasick (1975)
Shift-Or (1992)
2001年度冬のLAシンポジウム
6/15
Aho-Corasick(AC)照合機械
パタン集合：={other, <mother>}
0
任意の
文字
o
1
t
2
h
e
3
4
r
other
5
<
14
6
m
7
o
8
t
9
h
10
e
11
r
>
12
13
other <mother>
goto遷移
failure遷移
2001年度冬のLAシンポジウム
7/15
問題点
タグ名の一部分とマッチする
<body>
<h1>あのTVCM</h1>
<p>
<mother>
mother
</mother>
mを取ったらother、
<other>
他人
</other>
です．
</p>
</body>
2001年度冬のLAシンポジウム
誤
っ
た
検
出
8/15
解決策
< 以外
の文字
<
>
> 以外
の文字
< 以外
の文字
14
<
15
o
0
> <
6
m
t
1
7
o
h
2
8
t
e
3
9
h
4
10
> 以外
の文字
2001年度冬のLAシンポジウム
r
e
other
5
11
r
12
>
13
<mother>
9/15
PMM構築方法
< 以外
の文字
14
<
>
15
0
> 以外
の文字
< 以外
の文字
14
<
15
o
0
> <
6
m
t
1
7
o
h
2
8
t
e
3
9
h
4
10
> 以外
の文字
2001年度冬のLAシンポジウム
r
e
other
5
11
r
12
>
13
<mother>
10/15
属性の取り扱い
<mother>
<mother nature=“tender”>
<mother nature=“hard”>
同じタグ
<mother>
・
・
・
< 以外
の文字
14
<
0
<
> <
6
m
t
1
7
o
h
2
8
t
e
3
9
h
4
10
> 以外
の文字
2001年度冬のLAシンポジウム
r
e
> 以外
の文字
other
5
other
16
>
r
>
12
13
> <mother>
]
15
o
11
11/15
パスを考慮した照合
苗字が「Tanaka」の人を探したい！
<person><name><last>がTanaka
（Xpathだと，要素 //person/name/last/ が「Tanaka」）
2001年度冬のLAシンポジウム
12/15
アイデア
スタック
0
(<last>,2)
<person>
(<name>,1)
(<person>,0)
<person>
以外のタグ
1
(<xml>,0)
<name>
2
< 以外
の文字
o
0
14
t
h
1
e
2
3
<last>
r
4
5
other
<
>
6
> 以外
の文字
3
<
15
m
7
o
8
t
9
h
10
e
11
r
12
>
13
<mother>
={<person>,</person>,<name>,</name>,<last>,</last>,…}
={Tanaka}
2001年度冬のLAシンポジウム
13/15
実験結果
Sgrep(J. Jaakkola and P. Kilpeläinen)との比較
パタン
//text/"summers"
//test//"summers"
/site/regions/africa
/item/location/
"United_States"
Sgrep
38.44
37.02
51.85
提案アルゴリズム
12.40
12.30
12.23
CPU時間（秒）
テキスト：110MB(英文テキスト)
CPU : Celelon 366MHz
メモリ : 128MB
OS
: Kondara/MNU Linux 2.1 RC2
2001年度冬のLAシンポジウム
14/15
まとめ
XML文書に対する文字列照合処理
誤検出しない効率的な照合機械の構築
パスを考慮したアルゴリズム
Sgrepに比べ３倍以上高速
今後の課題
複数文字列を一度に置換するアルゴリズムの開発[3]
XML文書を圧縮して処理を高速化[6]
2001年度冬のLAシンポジウム
15/15
© Copyright 2024 ExpyDoc
