Position Heaps for Cartesian-Tree Matching on Strings and Tries
Position Heaps for Cartesian-Tree Matching on Strings and Tries
复制标题
字符串和尝试上笛卡尔树匹配的位置堆
DOI：
10.1007/978-3-030-86692-1_20
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shunsuke Inenaga
中科院分区：
文献类型：
--
作者：
Akio Nishimoto;Noriki Fujisato;Yuto Nakashima;Shunsuke Inenaga
笛卡儿树模式匹配是最近引入的一种模式匹配方案，它检测序列数据流中与查询模式结构相似的片段。形式上，笛卡尔树模式匹配查找文本字符串的所有子字符串$$S'$$ S ‘，使得$$S'$$ S ’的笛卡尔树与查询模式的笛卡尔树相吻合。在本文中，我们提出了一个新的索引结构，称为笛卡尔树位置堆（CPH）。设输入文本字符串的长度为m，查询模式的长度为np，字母表大小为$$\sigma $$ σ。我们表明，S的CPH，记为$$\mathsf {CPH}(S)$$ CPH (S)，支持模式匹配查询$$O(m (\sigma + \log (\min \{h, m\})) + occ )$$ O (m (σ + log (min {h)，m})) + 0 cc)时间与0 (n)空间，其中CPH的高度和$$ occ $$ occ是模式出现的次数。我们展示了如何在$$O(n \log \sigma )$$ O（n log σ）时间和O(n)工作空间内构建$$\mathsf {CPH}(S)$$ CPH (S)。此外，我们将问题扩展到文本是标记树（即trie）的情况。给定一个包含nnodes的tree $$\boldsymbol{T}$$ T，我们证明了$$\boldsymbol{T}$$ T的CPH，记为$$\mathsf {CPH}(\boldsymbol{T})$$ CPH (T)，支持在$$O(m (\sigma ^2 + \log (\min \{h, m\})) + occ )$$ O (m (σ 2 + log （min）中的树上进行模式匹配查询{H}，m)) + o c c)时间与$$O(N \sigma )$$ o (N σ)空间。我们还展示了在$$O(N \sigma )$$ O （N σ）时间内运行$$\mathsf {CPH}(\boldsymbol{T})$$ CPH (T)的构造算法$$O(N \sigma )$$ O （N σ）工作空间。
TheCartesian-tree pattern matchingis a recently introduced scheme of pattern matching that detects fragments in a sequential data stream which have a similar structure as a query pattern. Formally, Cartesian-tree pattern matching seeks all substrings $$S'$$ S ′ of the text stringSsuch that the Cartesian tree of $$S'$$ S ′ and that of a query patternPcoincide. In this paper, we present a new indexing structure for this problem, called theCartesian-tree Position Heap(CPH). Letnbe the length of the input text stringS,mthe length of a query patternP, and $$\sigma $$ σ the alphabet size. We show that the CPH ofS, denoted $$\mathsf {CPH}(S)$$ CPH ( S ) , supports pattern matching queries in $$O(m (\sigma + \log (\min \{h, m\})) + occ )$$ O ( m ( σ + log ( min { h , m } ) ) + o c c ) time withO(n) space, wherehis the height of the CPH and $$ occ $$ occ is the number of pattern occurrences. We show how to build $$\mathsf {CPH}(S)$$ CPH ( S ) in $$O(n \log \sigma )$$ O ( n log σ ) time withO(n) working space. Further, we extend the problem to the case where the text is a labeled tree (i.e. a trie). Given a trie $$\boldsymbol{T}$$ T withNnodes, we show that the CPH of $$\boldsymbol{T}$$ T , denoted $$\mathsf {CPH}(\boldsymbol{T})$$ CPH ( T ) , supports pattern matching queries on the trie in $$O(m (\sigma ^2 + \log (\min \{h, m\})) + occ )$$ O ( m ( σ 2 + log ( min { h , m } ) ) + o c c ) time with $$O(N \sigma )$$ O ( N σ ) space. We also show a construction algorithm for $$\mathsf {CPH}(\boldsymbol{T})$$ CPH ( T ) running in $$O(N \sigma )$$ O ( N σ ) time and $$O(N \sigma )$$ O ( N σ ) working space.