文字列上のビット並列法を利用した木パターン照合アルゴリズム

概要

論文の詳細を見る
本論文では木パターン照合問題を考える。木パターン照合問題とは、木パターンPとデータ木Tが与えられたとき、Tの部分木でPに一致するすべての部分木を求める問題である。我々はこの問題に対し、文字列上のビット並列法を利用した木パターン照合アルゴリズムを与える。我々は、擬似パターン照合条件という、通常の照合条件を緩めた照合条件を考える。そのとき、無順序木に対して、木パターンPの高さが1ワード長以下であれば、我々のアルゴリズムは、O(nl)時間で擬似パターン照合条件を満足するすべてのTのノードを見つけることができる。ここで、nはTのノード数、lはPの葉数である。さらに、Pの高さと葉数の積が1ワード長以下ならば、アルゴリズムはO(n)時間で走る。この結果を使うと、順序木に対しては、通常の照合条件にマッチするノードをO(n+kN(P))時間で見つけることができる。ここで、kは擬似パターン照合するノード数であり、N(P)は、擬似パターン照合するノードがPと一致するかチェックするために訪問するTのノード数であり、N(P)≤nである。
一般社団法人情報処理学会の論文
2008-03-07