文字列照合を用いた
XMLデータアクセス機構の提案
喜田 拓也* 宮本 哲† 竹田 正幸†
*九州大学附属図書館研究開発室
†九州大学システム情報科学府情報理学専攻
発表者： 喜田 拓也
発表内容
研究の目的
既存の手法
我々のアプローチ
文字列照合による処理の利点と問題点
提案アルゴリズム
誤検出を回避する方法
パスを考慮した照合処理
実験結果
XPathのサブセット
まとめ
情報処理学会九州支部 若手の会セミナー
2002
2/15
既存の手法
メモリ
XML文書
“”
person
Ｘ
Ｍ
Ｌ
パ
ー
サ
ー
XML文書
person
person/
name
“”
person/
name/first
Makiko
first
person/
name/last
last
Tanaka
Makiko
…
Tanaka
…
name
DOM
API
情報処理学会九州支部 若手の会セミナー
2002
プ
ロ
グ
ラ
ム
3/15
我々のアプローチ
XML文書
メモリ
<person>
<name>
<first>
Makiko
</first>
<last>
Tanaka
</last>
</name>
</person>
XML文書
文
字
列
照
合
ア
ル
ゴ
リ
ズ
ム
情報処理学会九州支部 若手の会セミナー
2002
プ
ロ
グ
ラ
ム
4/15
利点
処理が高速
XML文書
少ないメモリで可
様々な応用
木構造
巨大なXML文書や大量の文書群を一括に処理
複数の質問を同時に処理
情報処理学会九州支部 若手の会セミナー
2002
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)
情報処理学会九州支部 若手の会セミナー
2002
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遷移
情報処理学会九州支部 若手の会セミナー
2002
7/15
問題点
タグ名の一部分とマッチする
<body>
<h1>あのTVCM</h1>
<p>
<mother>
mother
</mother>
mを取ったらother、
<other>
他人
</other>
です．
</p>
</body>
情報処理学会九州支部 若手の会セミナー
2002
誤
っ
た
検
出
8/15
解決策
< 以外
の文字
<
>
> 以外
の文字
< 以外
の文字
14
<
15
o
0
> <
6
m
t
1
7
o
h
2
8
t
e
3
9
h
4
10
r
e
> 以外
の文字
情報処理学会九州支部 若手の会セミナー
2002
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
r
e
> 以外
の文字
情報処理学会九州支部 若手の会セミナー
2002
other
5
11
r
12
>
13
<mother>
10/15
パスを考慮した照合
苗字が「Tanaka」の人を探したい！
<person><name><last>がTanaka
（Xpathだと，要素 //person/name/last/ が「Tanaka」）
情報処理学会九州支部 若手の会セミナー
2002
11/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}
情報処理学会九州支部 若手の会セミナー
2002
12/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
情報処理学会九州支部 若手の会セミナー
2002
13/15
処理可能なXPathのサブセット
文字列照合による手法の限界
先行ノードの指定はできない！
複雑なフィルタの指定は照合速度を著しく低下させる。
LocationPath
::= '/' RelativeLocationPath
NodeTest ::= QName
RelativeLocationPath ::= Step
| NodeType '(' ')'
| RelativeLocationPath '/' Step
NodeType ::= 'node'
Step
::= AxisSpecifier NodeTest
| 'text'
AxisSpecifier ::= AxisName '::'
| 'comment'
AxisName
::= 'attribute'
| 'processing-instruction'
| 'child'
| 'descendant'
| 'descendant-or-self'
/descendant::cars/child::car/attribute::node()
| 'following'
| 'following-sibling'
| 'self'
//cars/car/@＊
| 'namespace'
情報処理学会九州支部 若手の会セミナー
2002
14/15
まとめ
XML文書に対する文字列照合処理
誤検出しない効率的な照合機械の構築
パスを考慮したアルゴリズム
Sgrepに比べ３倍以上高速
処理可能なXPathのサブセットを定義
今後の課題
XPathのサブセットに対する実装
XML文書を圧縮して処理を高速化
情報処理学会九州支部 若手の会セミナー
2002
15/15
© Copyright 2024 ExpyDoc
