Substring complexities on run-length compressed strings

DOI10.1007/978-3-031-20643-6_10zbMath1525.68042arXiv2205.12421OpenAlexW4312828769MaRDI QIDQ6111584

Itagaki Tomohiro, Akiyoshi Kawamoto

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

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

zbMATH Keywords

run-length compressionsubstring complexitycompressibility measure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Cites Work

• Sorting in linear time?
• Universal compressed text indexing
• Collage system: A unifying framework for compressed pattern matching.
• Towards a definitive measure of repetitiveness
• A combinatorial view on string attractors
• Sublinear algorithms for approximating string compressibility
• Sensitivity of string compressors and repetitiveness measures
• Data compression via textual substitution
• On the Complexity of Finite Sequences
• Algorithms on Strings, Trees and Sequences
• Grammar-based codes: a new class of universal lossless source codes
• Deterministic sorting in O(nloglogn) time and linear space
• Optimal-Time Dictionary-Compressed Indexes
• Optimal rank and select queries on dictionary-compressed text
• At the roots of dictionary compression: string attractors

This page was built for publication: Substring complexities on run-length compressed strings