2024-03-29T07:28:38Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000702692023-04-27T10:00:04Z01164:02592:05970:06157
拡張擬似木パターンマッチング問題に対するビット並列アルゴリズムBit-Parallel Algorithms for Extended Pseudo-tree Pattern Matching Problemjpnhttp://id.nii.ac.jp/1001/00070269/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=70269&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of Japan信州大学工学部長野工業高等専門学校山本, 博章宮嵜, 敬本論文では,無順序木に対し,拡張擬似木パターン照合問題という木パターン照合問題の一種について考える。一般に,木パターン照合問題とは,パターン木 P とターゲット木 T が与えられたとき,T の中で P に一致する部分をすべて見つける問題である。拡張擬似木パターン照合問題は,先祖・子孫関係のみに着目した問題である.この問題は XML データの検索において重要な役割を演じている.我々はこの問題に対し,文字列上のビット並列法を利用した効率的なアルゴリズムを与える。In this paper, we are concerned with a special case of the tree pattern matching problem for XML query evaluation, which is called extended pseudo-tree pattern matching problem. This problem focuses on only ancestor-descendant relationship. Then we show efficient bit-parallel algorithms for this pattern matching problem. Our algorithms runs faster than the existing algorithms for pattern trees of small size.AN1009593X研究報告アルゴリズム(AL)2010-AL-1314182010-09-152010-09-03