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 organization: | Department of Computer Science Practical Algorithms and Data Structures on Strings research group / Juha Kärkkäinen Bioinformatics Helsinki Institute for Information Technology Genome-scale Algorithmics research group / Veli Mäkinen Algorithmic Bioinformatics |
Date: | 2019-04 |
Language: | eng |
Number of pages: | 22 |
Belongs to series: | Algorithmica |
ISSN: | 0178-4617 |
DOI: | https://doi.org/10.1007/s00453-018-0475-9 |
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 |
Peer reviewed: | Yes |
Usage restriction: | closedAccess |
Total number of downloads: Loading...
Files | Size | Format | View |
---|---|---|---|
faster_minuter.pdf | 280.7Kb |
View/ |