Download presentation
Presentation is loading. Please wait.
1
半構造化テキストに対する 文字列照合アルゴリズム
喜田 拓也* 貴福 友晴† 竹田 正幸† *九州大学附属図書館研究開発室 †九州大学システム情報科学府情報理学専攻 発表者： 喜田 拓也
2
発表内容 研究の目的 提案アルゴリズム 実験結果 まとめ 既存の手法 我々のアプローチ 誤検出を回避する方法 パスを考慮した照合処理
文字列照合による処理の利点と問題点 提案アルゴリズム 誤検出を回避する方法 パスを考慮した照合処理 実験結果 まとめ 2001年度冬のLAシンポジウム
3
既存の手法 XML文書 メモリ ＸＭＬパーサー プログラム DOM API XML文書 person name first last
Makiko Tanaka person “” person/ name person/ name/first Makiko person/ name/last Tanaka … DOM API プログラム XML文書 2001年度冬のLAシンポジウム
4
我々のアプローチ XML文書 メモリ 文字列照合アルゴリズム プログラム XML文書 <person> <name>
<first> Makiko </first> <last> Tanaka </last> </name> </person> プログラム XML文書 2001年度冬のLAシンポジウム
5
利点 処理が高速 少ないメモリで可 様々な応用 XML文書 木構造 巨大なXML文書や大量の文書群を一括に処理 複数の質問を同時に処理
2001年度冬のLAシンポジウム
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) 2001年度冬のLAシンポジウム
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遷移 2001年度冬のLAシンポジウム
8
問題点 タグ名の一部分とマッチする 誤った検出 <body> <h1>あのTVCM</h1>
<p> <mother> mother </mother> mを取ったらother、 <other> 他人 </other> です． </p> </body> 誤った検出 2001年度冬のLAシンポジウム
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 2001年度冬のLAシンポジウム
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> 2001年度冬のLAシンポジウム
11
属性の取り扱い r o t h e m < > r o t h e m < > 同じタグ
<mother> <mother nature=“tender”> <mother nature=“hard”> ・・・ 同じタグ <mother> r o t h e m < > 13 6 7 8 9 10 11 12 1 2 3 4 5 other <mother> > 以外 の文字 < 以外 の文字 15 14 r o t h e m < > 13 6 7 8 9 10 11 12 1 2 3 4 5 other <mother> > 以外 の文字 < 以外 の文字 15 14 16 ] 2001年度冬のLAシンポジウム
12
パスを考慮した照合 苗字が「Tanaka」の人を探したい！
<person><name><last>がTanaka （Xpathだと，要素 //person/name/last/ が「Tanaka」） 2001年度冬のLAシンポジウム
13
アイデア スタック (<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} 2001年度冬のLAシンポジウム
14
実験結果 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 2001年度冬のLAシンポジウム
15
まとめ XML文書に対する文字列照合処理 Sgrepに比べ３倍以上高速 今後の課題 誤検出しない効率的な照合機械の構築
パスを考慮したアルゴリズム Sgrepに比べ３倍以上高速 今後の課題 複数文字列を一度に置換するアルゴリズムの開発[3] XML文書を圧縮して処理を高速化[6] 2001年度冬のLAシンポジウム
Similar presentations
