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