Fixed Block Compression Boosting in FM-Indexes : Theory and Practice

Show full item record



Permalink

http://hdl.handle.net/10138/308353

Citation

Gog , S , Kärkkäinen , J , Kempa , D , Petri , M & Puglisi , S J 2019 , ' Fixed Block Compression Boosting in FM-Indexes : Theory and Practice ' , Algorithmica , vol. 81 , no. 4 , pp. 1370-1391 . https://doi.org/10.1007/s00453-018-0475-9

Title: Fixed Block Compression Boosting in FM-Indexes : Theory and Practice
Author: Gog, Simon; Kärkkäinen, Juha; Kempa, Dominik; Petri, Matthias; Puglisi, Simon J.
Contributor: University of Helsinki, Department of Computer Science
University of Helsinki, Helsinki Institute for Information Technology
University of Helsinki, Helsinki Institute for Information Technology
Date: 2019-04
Language: eng
Number of pages: 22
Belongs to series: Algorithmica
ISSN: 0178-4617
URI: http://hdl.handle.net/10138/308353
Abstract: The FM index (Ferragina and Manzini in J ACM 52(4):552-581, 2005) is a widely-used compressed data structure that stores a string T in a compressed form and also supports fast pattern matching queries. In this paper, we describe new FM-index variants that combine nice theoretical properties, simple implementation and improved practical performance. Our main theoretical result is a new technique called fixed block compression boosting, which is a simpler and faster alternative to optimal compression boosting and implicit compression boosting used in previous FM-indexes. We also describe several new techniques for implementing fixed-block boosting efficiently, including a new, fast, and space-efficient implementation of wavelet trees. Our extensive experiments show the new indexes to be consistently fast and small relative to the state-of-the-art, and thus they make a good off-the-shelf choice for many applications.
Subject: Text indexing
Wavelet tree
FM-index
Compression boosting
Suffix array
Pattern matching
113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
faster_minuter.pdf 280.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record