A compressed dynamic self-index for highly repetitive text collections

DOI10.1016/J.IC.2020.104518zbMATH Open1446.68045arXiv1711.02855OpenAlexW3000242028WikidataQ126344789 ScholiaQ126344789MaRDI QIDQ776840FDOQ776840

Authors: Takaaki Nishimoto, Yoshimasa Takabatake, Yasuo Tabei 

Publication date: 13 July 2020

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

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)