この論文をさがす
抄録
Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009.
The following tree pattern matching problem is considered: Given two unordered labeled trees P and T, find all occurrences of P in T. Here P and T are called a pattern tree and a target tree, respectively. We first introduce a new problem called the pseudo-tree pattern matching problem. Then we show two efficient bit-parallel algorithms for the pseudo-tree pattern matching problem. One runs in O(L(P).n.l. [h/w]) time and O(n.l.[h/w]) space, and another one runs in O((L(P).n+h.2(l)).[h.l/W]) time and O((n + h.2(l)).[h.l/W]) space, where n is the number of nodes in T, h and l are the height of P and the number of leaves of P, respectively, and W is the length of a computer-word. The parameter L(P), called a recursive level of P, is defined to be the number of occurrences of the same label on a path from the root to a leaf. Hence we have L(P) <= h. Finally, we give an algorithm to extract all occurrences from pseud-occurrences in O(n.L(P).l(3/2)) time and O(n.L(P).l) space.
Article
Lecture Notes in Computer Science. 5664:554-565 (2009)
収録刊行物
-
- Lecture Notes in Computer Science
-
Lecture Notes in Computer Science 5664 554-565, 2009
SPRINGER VERLAG
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1050288613455047424
-
- NII論文ID
- 120007113643
-
- NII書誌ID
- AA0071599X
-
- ISSN
- 03029743
-
- HANDLE
- 10091/13658
-
- 本文言語コード
- en
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB
- CiNii Articles