A Compact Index for Cartesian Tree Matching
A Compact Index for Cartesian Tree Matching
复制标题
笛卡尔树匹配的紧凑索引
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hwan
中科院分区：
文献类型：
--
作者：
Sung;Hwan
笛卡尔树匹配是最近提出的一种字符串匹配问题，若两个字符串对应的笛卡尔树相同，则它们匹配。它被认为适合于寻找关于其形状的模式，特别是在数值时间序列数据中。虽然许多相关问题已得到解决，但构建紧凑索引受到的关注相对较少。在本文中，我们提出了一种$3n + o(n)$位的索引，它能够在$O(m)$时间内计算笛卡尔树模式在文本中的出现次数，其中$n$和$m$分别是文本和模式的长度。据我们所知，这项工作是针对该问题的第一个用于索引的$O(n)$位紧凑数据结构。2012 ACM学科分类计算理论→模式匹配
Cartesian tree matching is a recently introduced string matching problem in which two strings match if their corresponding Cartesian trees are the same. It is considered appropriate to find patterns regarding their shapes especially in numerical time series data. While many related problems have been addressed, developing a compact index has received relatively less attention. In this paper, we present a 3n + o(n)-bit index that can count the number of occurrences of a Cartesian tree pattern in O(m) time where n and m are the text and pattern length. To the best of our knowledge, this work is the first O(n)-bit compact data structure for indexing for this problem. 2012 ACM Subject Classification Theory of computation → Pattern matching