半構造化テキストに対する文字列照合アルゴリズム.ppt

2001年度冬のLAシンポジウム 半構造化テキストに対する文字列照合アルゴリズム 喜田 拓也*　貴福 友晴?　竹田 正幸? *九州大学附属図書館研究開発室?九州大学システム情報科学府情報理学専攻 発表内容 研究の目的 既存の手法 我々のアプローチ 文字列照合による処理の利点と問題点 提案アルゴリズム 誤検出を回避する方法 パスを考慮した照合処理 実験結果 まとめ 既存の手法 我々のアプローチ 利点 巨大なXML文書や大量の文書群を一括に処理 複数の質問を同時に処理 文字列照合問題 Aho-Corasick(AC)照合機械 問題点 タグ名の一部分とマッチする 解決策 PMM構築方法 属性の取り扱い パスを考慮した照合 アイデア 実験結果 Sgrep(J. Jaakkola and P. Kilpel?inen)との比較 まとめ XML文書に対する文字列照合処理 誤検出しない効率的な照合機械の構築 パスを考慮したアルゴリズム Sgrepに比べ３倍以上高速 今後の課題 複数文字列を一度に置換するアルゴリズムの開発[3] XML文書を圧縮して処理を高速化[6] * * 発表者：　喜田 拓也 XML文書 XML文書 メモリ プログラム DOM API … … Tanaka person/name/last Makiko person/name/first “” person/name “” person person name first last Makiko Tanaka ＸＭＬパーサー XML文書 XML文書 メモリ プログラム 文字列照合アルゴリズム person name first Makiko /first last Tanaka /last /name /person 木構造 処理が高速 少ないメモリで可 様々な応用 XML文書 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. matching パタン テキスト Knuth-Morris-Pratt (1974) Boyer-Moore (1977) Aho-Corasick (1975) Shift-Or (1992) 6 7 8 9 10 11 12 13 0 1 2 3 4 5 14 r o t h e r o t h e m other mother 任意の文字 goto遷移 failure遷移 パタン集合：?={other, mother} other body h1あのTVCM/h1 p mother mother /mother mを取ったらother、 other 他人 /other です． /p /body 誤った検出 r o t h e r o t h e m 13 6 7 8 9 10 11 12 0 1 2 3 4 5 other mother 以外の文字 以外の文字 15 14 以外の文字 以外の文字 r o t h e r o t h e m 13 6 7 8 9 10 11 12 0 1 2 3 4 5 other mother 以外の文字 以外の文字 15 14 以外の文字 以外の文字 14 15 0