A compressed dynamic self-index for highly repetitive text collections

DOI10.1016/J.IC.2020.104518MaRDI QIDQ776840zbMATH OpenOpenAlexWikidataFDO

Authors Takaaki Nishimoto, Yoshimasa Takabatake, Yasuo Tabei

Publication date 13 July 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.02855

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: We present a novel compressed dynamic self-index for highly repetitive text collections. Signature encoding is a compressed dynamic self-index for highly repetitive texts and has a large disadvantage that the pattern search for short patterns is slow. We improve this disadvantage for faster pattern search by leveraging an idea behind truncated suffix tree and present the first compressed dynamic self-index named TST-index that supports not only fast pattern search but also dynamic update operation of index for highly repetitive texts. Experiments using a benchmark dataset of highly repetitive texts show that the pattern search of TST-index is significantly improved.

Recommendations

• Self-indexing based on LZ77
• On compressing and indexing repetitive sequences
• Self-indexed grammar-based compression
• Combinatorial Pattern Matching
• Compressed indexes for dynamic text collections

Cites work

• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• A self-index on block trees
• A universal algorithm for sequential data compression
• At the roots of dictionary compression: string attractors
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed indexing with signature grammars
• Fixed block compression boosting in FM-indexes: theory and practice
• Fully dynamic data structure for LCE queries in compressed space
• Hybrid indexes for repetitive datasets
• Hybrid indexing revisited
• Lempel-Ziv index for \(q\)-grams
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• On compressing and indexing repetitive sequences
• Optimal bounds for the predecessor problem and related problems
• Optimal-Time Dictionary-Compressed Indexes
• Small-space LCE data structure with constant-time queries
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Storage and Retrieval of Individual Genomes
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Truncated suffix trees and their application to data compression.
• Universal compressed text indexing

Cited in

(3)

• ESP-index: a compressed index based on edit-sensitive parsing
• Self-indexing based on LZ77
• On compressing and indexing repetitive sequences

Describes a project that uses

Uses Software

• PATRICIA
• r-index

This page was built for publication: A compressed dynamic self-index for highly repetitive text collections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776840)