Cartesian Forest Matching

Bastien Auvray, Julien David, Richard Groult, Thierry Lecroq · 2025

Read Cartesian Forest Matching by Bastien Auvray, Julien David, Richard Groult, Thierry Lecroq (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-02704.txt.

Introduction

Auvray, David, Groult, and Lecroq extend pattern matching from ordered trees to forests in twenty twenty-five. A Cartesian tree encodes a sequence by its heap-like order of values. Their forest version handles partly ordered sequences. Algorithms for exact and near matching on trees adapt to forests with linear average time. A signature scheme and filters speed the exact search in practice. They also show forests match Schröder trees one to one, tying the new notion to a classic family.

Catalog record

CREATORBastien Auvray, Julien David, Richard Groult, Thierry Lecroq
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-02704

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cartesian Forest Matching Bastien Auvray, Julien David, Richard Groult, Thierry Lecroq Abstract In this paper, we introduce the notion of Cartesian Forest, which generalizes Cartesian Trees, in order to deal with partially ordered sequences. We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in average linear time. We adapt the notion of Cartesian Tree Signature to Cartesian Forests and show how filters can be used to experimentally improve the algorithm for the exact matching. We also show a one to one correspondence between Cartesian Forests and Schröder Trees. 1 Introduction Pattern matching consists of searching for one or all the occurrences of a pattern in a text. It is an essential task in many computer science applications. It can take different forms. For instance it can be done online when the pattern can be preprocessed or offline when the text can be preprocessed. Occurrences can be exact or approximate. When the pattern and the text are sequences of characters, it is known as string matching. When searching patterns in time series data, the notion of pattern matching is a bit more involved. Solutions can use Cartesian Trees that where introduced by Vuillemin in 1980 [ 19 ] . Cartesian Tree Matching has been introduced by Park et al. [ 15 , 16 ] . Given a pattern, it consists of finding the factors of a text that share the same Cartesian Tree as the Cartesian Tree of the pattern. Since then it has gained a lot of interest. Efficient solutions for practical cases for online search were given in [ 17 ] . Expected linear time algorithms are given in [ 1 ] for approximate Cartesian Tree Matching with one difference. Indexing structures in the Cartesian Tree pattern matching framework are presented in [ 12 , 10 , 14 ] . Methods for computing regularities are given in [ 9 ] and methods for computing palindromic structures are presented in [ 6 ] . An algorithm for episode matching (given two sequences p and t , finding all minimal length factors of t that contains p as a subsequence) in Cartesian Tree framework is presented in [ 13 ] . Practical methods for finding longest common Cartesian substrings of two strings appeared in [ 5 ] . Very recently, dynamic programming approaches for approximate Cartesian Tree pattern matching with edit distance has been considered in [ 11 ] and longest common Cartesian Tree subsequences are computed in [ 18 ] . Efficient algorithms for determining if two equal-length indeterminate strings match in the Cartesian Tree framework are given in [ 8 ] . Cartesian Trees are defined on arbitrary sequences where there can be values with multiple occurrences. In that case, ties can be broken in any way. In this article, in order to better deal with equal values we introduce Cartesian Forests . We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in average linear time. We then show a one to one correspondence between Cartesian Forests and Schröder Trees. More specifically we give algorithms for computing a Schröder Tree and a special type of words with parentheses given a Cartesian Forest. We also adapt the notion of Cartesian Tree Signature introduced in [ 4 ] to Cartesian Forests, and show how this notion can be used to experimentally improve the computation. 2 Definitions In this paper, a sequence is always defined on an ordered alphabet. For a given sequence x , |x| denotes the length of x . A sequence v is factor of a sequence x if x=uvw for any sequences u and w . A sequence u is a prefix (resp. suffix ) of a sequence x if x=uv (resp. x=vu ). For a sequence x of length m , x[i] is the i -th element of x and x[i\ldots j] represents the factor of x starting at the i -th element and ending at the j -th element, for 1\leq i\leq j\leq m . 2.1 Cartesian Tree and Cartesian Forest Definition 1 (Cartesian Tree C(x) ) Given a sequence x of length m , the Cartesian Tree of x , denoted by C(x) , is the binary tree recursively defined as follows: • if x is empty, then C(x) is the empty tree; • if x[1\ldots m] is not empty and x[h] is the smallest value of x , C(x) is the binary tree with h as its root, the Cartesian Tree of x[1\ldots h-1] as the left subtree and the Cartesian Tree of x[h+1\ldots m] as the right subtree. We denote by \operatorname{rb}(T) the list of nodes on the right branch of a Cartesian Tree T . The Cartesian Tree of a sequence can be built online in linear time and space [ 7 ] . Informally, let x be a sequence such that C(x[1\ldots h-1]) is already known. In order to build C(x[1\ldots h]) , one only needs to find the nodes j_{1}<\cdots<j_{k} in \operatorname{rb}(C(x[1\ldots h-1])) such that x[j_{1}]>x[h] . If j_{1} is the root of C(x[1\ldots h-1]) then h becomes the root of C(x[1\ldots h]) otherwise let j_{0} be the parent node of j_{1} , then node h will be the root of the right subtree of j_{0} . In both cases, j_{1} will be the root of the left subtree of node h . Then \operatorname{rb}(C(x[1\ldots h])=\operatorname{rb}(C(x[1\ldots h-1]))\setminus(j_{1},\ldots,j_{k})\cup(h) . All these operations can be easily done by implementing \operatorname{rb} with a stack. The amortized cost of such an operation can be shown to be constant. Cartesian Trees are defined on arbitrary sequences where there can be multiple occurrences of the smallest value.In that case, ties can be broken in any way. Usually the first occurrence of the smallest value is chosen to be the root of the tree. In order to better deal with equal values we now introduce Cartesian Forests. We first introduce the combinatorial object in itself, then we define what the Cartesian Forest of a sequence is. Definition 2 (Cartesian Forest F ) A Cartesian Forest F can be: • empty, • a sequence of k planar trees rooted in (r_{1},\ldots,r_{k}) , with k\geq 1 , such that r_{1} has a left Cartesian sub-Forest and a right Cartesian sub-Forest, and r_{i} has only a right Cartesian sub-Forest for all i\in\{2,\ldots,k\} (the left sub-Forest is necessarily empty). Figure 1 shows examples of one Cartesian Forestand two forests that are not Cartesian. Figure 1: On the left is a valid Cartesian Forest. In the middle, it is not a valid Cartesian Forest because the second tree in the right sub-Forest of r^{\prime}_{1} has a left sub-Forest. On the right, a planar forest is not Cartesian: the second tree has a left sub-Forest. Definition 3 (Cartesian Forest F(x) of a sequence x ) Given a sequence x of length m , the Cartesian Forest of x , denoted by F(x) , is recursively defined as follows: • if x is empty, then F(x) is the empty forest; • if x[1\ldots m] is not empty, let (r_{1},\ldots,r_{k}) be the ordered sequence of all the k positions of the

Read the complete text