Journal
THEORETICAL COMPUTER SCIENCE
Volume 483, Issue -, Pages 115-133Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2012.02.006
Keywords
Compression; Repetitive texts; Self-indexing; Lempel-Ziv; Succinct data structures
Categories
Funding
- Conicyt's Master Scholarship
- Millennium Institute for Cell Dynamics and Biotechnology (ICDB), Mideplan, Chile [ICM P05-001-F]
Ask authors/readers for more resources
We introduce LZ-End, a new member of the Lempel-Ziv family of text compressors, which achieves compression ratios close to those of LZ77 but is much faster at extracting arbitrary text substrings. We then build the first self-index based on LZ77 (or LZ-End) compression, which in addition to text extraction offers fast indexed searches on the compressed text. This self-index is particularly effective for representing highly repetitive sequence collections, which arise for example when storing versioned documents, software repositories, periodic publications, and biological sequence databases. (C) 2012 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
