File HuffmanFMIndex.h

↰ Parent directory (ADS/compression)

The FM-index on the wavelet tree shaped by the code of Huffman, the succinct suffix array of Makinen and Navarro: the transform L of Burrows and Wheeler of a text s of n bytes as a HuffmanWaveletTree [see File HuffmanWaveletTree.h], in :math:` n ( H_0 + 1 ) ( 1 + o( 1 ) ) ` bits, with the same operations as the FM-index of the notes [see File FMIndex.h], which keeps L as it is with counts every b places, :math:` 8 n + 32 sigma n / b ` bits.

Definition (ADS/compression/HuffmanFMIndex.h)

Detailed Description

  • count( P ) is the backward search: the rows prefixed by :math:` c P’ ` are :math:` [ C[ c ] + rank_c( first ) , C[ c ] + rank_c( last ) ) ` for the range [ first , last ) of P’, in :math:` O( p ( H_0 + 1 ) ) ` steps on average, each one a rank of the bits of the tree;

  • locate( P ) walks each row of the range by the LF-mapping, :math:` LF( r ) = C[ L[ r ] ] + rank_{L[ r ]}( r ) , found by one descent of the tree (accessRank()), until a row whose suffix starts at a multiple of :math: mu `, marked and sampled;

  • extract( i , j ) starts from the row of the sampled suffix at or after j and walks back by LF.

The symbols of L are the bytes plus 1, the end of the text being 0. The backward search takes the two ranks of a step by one descent of the tree, as they meet the same nodes. The samples are :math:` lceil n / mu rceil ` places and as many rows of :math:` lceil log_2 ( n + 1 ) rceil ` bits each, and the marks n + 1 bits with the compact rank of CompactRankSelect [see File CompactRankSelect.h], since a step of locate() tests the bit alone and the rank is needed once per occurrence; the parameter RS is the rank and select of the tree, RankSelect or CompactRankSelect. The transform comes from the suffix array of SA-IS [see File BurrowsWheeler.h], O( n ) time.

The contracts [see File Contract.h]: :math:` mu > 0 , n is below :math: 2^{32} , a pattern is not empty, :math: i le j le n `; each place found by locate() is an occurrence, an audit. The functions are defined in HuffmanFMIndex.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. Ferragina, G. Manzini, Indexing compressed text, Journal of the ACM 52(4), 552-581, 2005, doi:10.1145/1082036.1082039

  1. Ferragina, G. Manzini, V. Makinen, G. Navarro, Compressed representations of sequences and full-text indexes, ACM Transactions on Algorithms 3(2), 20, 2007, doi:10.1145/1240233.1240243

  1. Navarro, V. Makinen, Compressed full-text indexes, ACM Computing Surveys 39(1), 2, 2007, doi:10.1145/1216370.1216372

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes