木包含の拡張による類似部分木検索
Similar Subtree Search Using Extended Tree Inclusion

概要

本発表では、すべての木が根付きで節点にラベルがあるという条件下で、与えれらた大きな木構造(テキスト木)もしくは木構造の集合の中における、指定されたパターン木に似た(テキスト木の)部分木のすべての位置を特定する問題を扱う。木の編集距離は木の類似性の尺度として広く使われているが、無順序木に対する計算はNP困難である。そこで我々は、パターン木に対する挿入のコストと置換操作を考慮することにより「無順序木の包含」の概念を拡張し、無順序木の類似度に関する新たな尺度を提案し、それを計算するアルゴリズムを開発した。T1とT2をそれぞれパターン木とテキスト木とすると、T1の最大出次数が定数の時、我々のアルゴリズムの計算複雑さは、元々の「無順序木の包含」を計算するアルゴリズムと同じでO(|T1||T2|)である。人工的なデータと実際のデータを用いたコンピュータ実験により、提案アルゴリズムは高速でかつ大規模データに適用可能であり、木構造に対する典型的なentity resolution問題である文献データマッチングに対しとても有効であることが示された。また提案手法を拡張し、計算時間はO(|T1||T2|)のままで、T1に対する定数回の削除操作を許すアルゴリズムを開発した。

産業界への展開例・適用分野

文献検索などの、無順序木を用いたデータ構造に対する高速パターンマッチングアルゴリズムとして使うことができる。

研究者

氏名	専攻	研究室	役職/学年
田村 武幸	知能情報学専攻	阿久津	助教

---