Presentation is loading. Please wait.

Presentation is loading. Please wait.

文字列照合を用いた XMLデータアクセス機構の提案

Similar presentations


Presentation on theme: "文字列照合を用いた XMLデータアクセス機構の提案"— Presentation transcript:

1 文字列照合を用いた XMLデータアクセス機構の提案
喜田 拓也* 宮本 哲† 竹田 正幸† *九州大学附属図書館研究開発室 †九州大学システム情報科学府情報理学専攻 発表者: 喜田 拓也

2 発表内容 研究の目的 提案アルゴリズム XPathのサブセット まとめ 既存の手法 我々のアプローチ 誤検出を回避する方法
文字列照合による処理の利点と問題点 提案アルゴリズム 誤検出を回避する方法 パスを考慮した照合処理 実験結果 XPathのサブセット まとめ 情報処理学会九州支部 若手の会セミナー 2002

3 既存の手法 XML文書 メモリ XMLパーサー プログラム DOM API XML文書 person name first last
Makiko Tanaka person “” person/ name person/ name/first Makiko person/ name/last Tanaka DOM API プログラム XML文書 情報処理学会九州支部 若手の会セミナー 2002

4 我々のアプローチ XML文書 メモリ 文字列照合アルゴリズム プログラム XML文書 <person> <name>
<first> Makiko </first> <last> Tanaka </last> </name> </person> プログラム XML文書 情報処理学会九州支部 若手の会セミナー 2002

5 利点 処理が高速 少ないメモリで可 様々な応用 XML文書 木構造 巨大なXML文書や大量の文書群を一括に処理 複数の質問を同時に処理
情報処理学会九州支部 若手の会セミナー 2002

6 Knuth-Morris-Pratt (1974)
文字列照合問題 パタン 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

7 Aho-Corasick(AC)照合機械
パタン集合:={other, <mother>} o t h e r other 1 2 3 4 5 任意の 文字 < m o t h e r > 14 6 7 8 9 10 11 12 13 other <mother> goto遷移 failure遷移 情報処理学会九州支部 若手の会セミナー 2002

8 問題点 タグ名の一部分とマッチする 誤った検出 <body> <h1>あのTVCM</h1>
<p> <mother> mother </mother> mを取ったらother、 <other> 他人 </other> です. </p> </body> 誤った検出 情報処理学会九州支部 若手の会セミナー 2002

9 解決策 < > r o t h e m < > 13 6 7 8 9 10 11 12 1 2 3 4 5
> 以外 の文字 < 以外 の文字 r o t h e m < > 13 6 7 8 9 10 11 12 1 2 3 4 5 other <mother> > 以外 の文字 < 以外 の文字 15 14 情報処理学会九州支部 若手の会セミナー 2002

10 PMM構築方法 < > > < r o t h e m < > 14 15 15 14 13 6 7 8
> 以外 の文字 < 以外 の文字 14 15 > 以外 の文字 > < < 以外 の文字 15 14 r o t h e m < > 13 6 7 8 9 10 11 12 1 2 3 4 5 other <mother> 情報処理学会九州支部 若手の会セミナー 2002

11 パスを考慮した照合 苗字が「Tanaka」の人を探したい!
<person><name><last>がTanaka (Xpathだと,要素 //person/name/last/ が「Tanaka」) 情報処理学会九州支部 若手の会セミナー 2002

12 アイデア スタック (<last>,2) <person> (<name>,1) 1
(<xml>,0) スタック (<last>,2) 1 3 <person> <name> 2 <last> 以外のタグ r o t h e m < > 13 6 7 8 9 10 11 12 1 2 3 4 5 other <mother> > 以外 の文字 < 以外 の文字 15 14 ={<person>,</person>,<name>,</name>,<last>,</last>,…} ={Tanaka} 情報処理学会九州支部 若手の会セミナー 2002

13 実験結果 Sgrep(J. Jaakkola and P. Kilpeläinen)との比較 パタン Sgrep 38.44 37.02
//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

14 /descendant::cars/child::car/attribute::node()
処理可能なXPathのサブセット 文字列照合による手法の限界 先行ノードの指定はできない! 複雑なフィルタの指定は照合速度を著しく低下させる。 LocationPath ::= '/' RelativeLocationPath RelativeLocationPath ::= Step | RelativeLocationPath '/' Step Step ::= AxisSpecifier NodeTest AxisSpecifier ::= AxisName '::' AxisName ::= 'attribute' | 'child' | 'descendant' | 'descendant-or-self' | 'following' | 'following-sibling' | 'self' | 'namespace' NodeTest ::= QName | NodeType '(' ')' NodeType ::= 'node' | 'text' | 'comment' | 'processing-instruction' /descendant::cars/child::car/attribute::node() 情報処理学会九州支部 若手の会セミナー 2002

15 まとめ XML文書に対する文字列照合処理 Sgrepに比べ3倍以上高速 処理可能なXPathのサブセットを定義 今後の課題
誤検出しない効率的な照合機械の構築 パスを考慮したアルゴリズム Sgrepに比べ3倍以上高速 処理可能なXPathのサブセットを定義 今後の課題 XPathのサブセットに対する実装 XML文書を圧縮して処理を高速化 情報処理学会九州支部 若手の会セミナー 2002


Download ppt "文字列照合を用いた XMLデータアクセス機構の提案"

Similar presentations


Ads by Google