Substring Complexities on Run-length Compressed Strings

2022/05/25 by Kawamoto, Akiyoshi, I, Tomohiro
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2205.12421

Abstract

Let S_T(k) denote the set of distinct substrings of length k in a string T, then the k-th substring complexity is defined by its cardinality |S_T(k)|. Recently, δ= max \ |S_T(k)| / k : k ≥ 1 \ is shown to be a good compressibility measure of highly-repetitive strings. In this paper, given T of length n in the run-length compressed form of size r, we show that δ can be computed in C_sort(r, n) time and O(r) space, where C_sort(r, n) = O(min (r \lg\lg r, r \lg_r n)) is the time complexity for sorting r O(\lg n)-bit integers in O(r) space in the Word-RAM model with word size Ω(\lg n).

Related

• Substring Complexity in Sublinear Space
• Sublinear Algorithms for Approximating String Compressibility
• Adaptive Learning of Compressible Strings
• Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness
• Online computation of normalized substring complexity