File HuffmanWaveletTree.h

↰ Parent directory (ADS/succinct)

The wavelet tree shaped by the code of Huffman of Makinen and Navarro: a sequence :math:` x_0 , ldots , x_{n-1} ` of symbols of :math:` [ 0 , sigma ) ` in :math:` n ( H_0 + 1 ) ` bits and a little more, with access, rank and select of any symbol in time proportional to the length of its code, :math:` H_0 + 1 ` steps on average, against the :math:` lceil log_2 sigma rceil ` levels of the balanced tree and of the wavelet matrix [see File WaveletMatrix.h], which take :math:` n lceil log_2 sigma rceil ` bits.

Definition (ADS/succinct/HuffmanWaveletTree.h)

Detailed Description

The symbol c has the canonical code of Huffman of its frequency in x, of length :math:` ell_c , its bits from the highest; the tree is the trie of the codes, and its internal node v, reached by the prefix :math: pi_v , keeps the bit after :math: pi_v ` of the code of each item whose code starts with :math:` pi_v , in the order of the sequence. The bits of all the nodes are one vector B with rank and select [see :ref:`file_ADS_succinct_RankSelect.h, File CompactRankSelect.h], node v from the place :math:` o_v ` with :math:` R_v = rank_1( B , o_v ) ` kept; the item of place i in the node v moves to the place \([ i' = rank_b( B , o_v + i ) - rank_b( B , o_v ) \` of its child by the bit :math:\) b = B[ o_v + i ] , so that a descent along the code of c gives access( i ), with the rank of the symbol found (accessRank(), the LF-mapping of an FM-index in one descent), and :math: rank_c( i ) , one rank a step, and :math: select_c( k ) ` climbs from the leaf of c by one select a step, \([ k' = select_b( B , rank_b( B , o_v ) + k ) - o_v + 1 . \` The bits of B are :math:\) sum_c f_c ell_c < n ( H_0 + 1 ) ` for the frequencies :math:` f_c , by the bound of the code of Huffman, plus the directory of rank and select, 25% of them with RankSelect, 3.5% with CompactRankSelect (the parameter RS: time against bits), and :math: O( sigma ) ` words of the tree and of the codes.

The contracts [see File Contract.h]: the places and the counts are in range, select asks for an occurrence that exists (and the tree was built with select); the audit of the construction is that access() gives back each item. The functions are defined in HuffmanWaveletTree.tpp.

  1. Makinen, G. Navarro, Succinct suffix arrays based on run-length encoding, Proc. 16th CPM, LNCS 3537, 45-56, 2005, doi:10.1007/11496656_5

  1. Grossi, A. Gupta, J. S. Vitter, High-order entropy-compressed text indexes, Proc. 14th SODA, 841-850, 2003

    1. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the IRE 40(9), 1098-1101, 1952, doi:10.1109/JRPROC.1952.273898

  1. Navarro, Wavelet trees for all, Journal of Discrete Algorithms 25, 2-20, 2014, doi:10.1016/j.jda.2013.07.004

  1. Navarro, Compact Data Structures, Cambridge University Press, 2016, section 6.2.4, doi:10.1017/CBO9781316588284

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes