本論文では,拡張擬似木パターン照合問題という木パターン照合問題の一種について考える.一般に,木パターン照合問題とは,パターン木Pとターゲット木Tが与えられたとき,Tの中でPに一致する部分をすべて見つける問題である.拡張擬似木パターン照合問題は,先祖・子孫関係のみに着目した問題である.この問題はXMLデータの検索において重要な役割を演じている.本論文は,まず,記号をラベルにもつ木に対し、文字列上のビット並列法を利用した効率的なアルゴリズムを与える.そのあと,アルゴリズムを記号列のラベルをもつ木へ拡張する.