Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism
Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism
复制标题
DOI：
10.1007/978-3-642-19222-7_8
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
Yusaku Kaneta;Hiroki Arimura;R. Raman
中科院分区：
文献类型：
--
作者：
Yusaku Kaneta;Hiroki Arimura;R. Raman
在本文中，我们考虑无序伪树匹配问题，这是一个给定两个无序标记树 PandT 的问题，通过保留节点标签和父子关系的多对一嵌入来查找 PinT 的所有出现。这个问题与仅具有子轴的 XPath 查询的树模式匹配问题密切相关。如果m>w，我们提出一种有效的算法，使用O(hm/w+mlog(w)/w)空间和O(mlog(w))预处理在单位成本算术RAM模型上及时解决加法问题，其中P中的节点数，T中的节点数，T的高度，w是字长。我们还讨论了针对无序树同态问题的算法的修改，该问题对应于仅具有后代轴的 XPath 查询的树模式匹配问题。
In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled treesPandT, finding all occurrences ofPinTvia such many-one embeddings that preserve node labels and parent-child relationship. This problem is closely related to tree pattern matching problem for XPath queries with child axis only. Ifm>w, we present an efficient algorithm that solves the problem intime usingO(hm/w+mlog(w)/w) space andO(mlog(w)) preprocessing on a unit-cost arithmetic RAM model with addition, wheremis the number of nodes inP,nis the number of nodes inT,his the height ofT, andwis the word length. We also discuss a modification of our algorithm for the unordered tree homeomorphism problem, which corresponds to a tree pattern matching problem for XPath queries with descendant axis only.