File BalancedParentheses.h

↰ Parent directory (ADS/succinct)

A static sequence of balanced parentheses, 1 for ‘(’ and 0 for ‘)’, with the matching of Munro and Raman by the range min-max tree of Navarro and Sadakane: the base of the trees by parentheses [see File BPTree.h], which the notes count among the codes of 2n bits of a tree (the footnote on the binary trees of section 15.2.1) and which, unlike the codes by levels, also give the size of a subtree and the depth of a node.

Definition (ADS/succinct/BalancedParentheses.h)

Detailed Description

With the excess :math:` E( i ) , the number of ‘(’ minus the number of ‘)’ in :math: B[ 0 , i ] ` (and :math:` E( -1 ) = 0 `), every operation is a search of the first place, forward or backward from i, whose excess is at most a target t:

  • findClose( i ), the ‘)’ of the ‘(’ at i, is the first :math:` j > i ` with :math:` E( j ) = E( i ) - 1 `;

  • findOpen( j ), the ‘(’ of the ‘)’ at j, is :math:` k + 1 ` for the last :math:` k < j ` with :math:` E( k ) = E( j ) `;

  • enclose( i ), the ‘(’ of the pair that encloses the one at i, is :math:` k + 1 ` for the last :math:` k < i ` with :math:` E( k ) = E( i ) - 2 `;

and since the excess moves by :math:` pm 1 , the first place with an excess at most t has exactly t. The range min-max tree keeps, for each leaf of 512 bits, for each group of 16 leaves and for each node of a complete binary tree over the groups, the total excess of its range and its minimum prefix excess; every search runs on the excess relative to its start, so that it needs no rank: it scans the leaf of 512 bits of i (a byte at a time, with the excess, the minimum and the place of each target of each of the 256 bytes in tables), then the leaves of its group of 16 by their excess and minimum in 16 bits, then climbs the tree, whose leaves are the groups, to the first range on its side whose minimum reaches the target and goes down to its group, its leaf and its byte, in :math: O( log ( n / 8192 ) + 16 + 512 / 8 ) ` time; most searches of a tree end in the leaf of i, at the cost of a miss of the cache. The tree takes :math:` 32 / 512 ` bits per parenthesis for the leaves and at most :math:` 4 cdot 128 / 8192 ` for the groups, besides the rank directory [see File CompactRankSelect.h], 3.5% of the bits, since no search needs a rank. The excess of any place is :math:` E( i ) = 2 rank_1( i + 1 ) - ( i + 1 ) `, in O( 1 ) time.

Jacobson gives findClose() in O( log n ) time with the pioneers, and Munro and Raman in O( 1 ) time with two levels of pioneers and tables, in 2n + o( n ) bits; the range min-max tree of Navarro and Sadakane reaches O( 1 ) time with a tree of degree :math:` Theta( log n ) ` and tables, and its binary form with blocks of a few hundred bits, the one here, is the fastest in practice (Arroyuelo, Canovas, Navarro and Sadakane; Gog and Petri; Grossi and Ottaviano).

The contracts [see File Contract.h]: the sequence is balanced (an audit), findClose() and enclose() get a ‘(’ and findOpen() a ‘)’; the postconditions are the excesses of the definitions. The functions are defined in BalancedParentheses.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 15

    1. Munro, V. Raman, Succinct representation of balanced parentheses and static trees, SIAM Journal on Computing 31(3), 762-776, 2001, doi:10.1137/S0097539799364092

  1. Navarro, K. Sadakane, Fully functional static and dynamic succinct trees, ACM Transactions on Algorithms 10(3), 16, 2014, doi:10.1145/2601073

  1. Arroyuelo, R. Canovas, G. Navarro, K. Sadakane, Succinct trees in practice, Proc. 12th ALENEX, 84-97, 2010, doi:10.1137/1.9781611972900.9

  1. Gog, M. Petri, Optimized succinct data structures for massive data, Software: Practice and Experience 44(11), 1287-1314, 2014, doi:10.1002/spe.2198

  1. Grossi, G. Ottaviano, Design of practical succinct data structures for large data collections, Proc. 12th SEA, LNCS 7933, 5-17, 2013, doi:10.1007/978-3-642-38527-8_3

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes