Online computation of normalized substring complexity

2025/10/18 by Kucherov, Gregory, Nekrich, Yakov
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2510.16454

Abstract

The normalized substring complexity δ of a string is defined as max_k \c[k]/k\, where c[k] is the number of distinct substrings of length k. This simply defined measure has recently attracted attention due to its established relationship to popular string compression algorithms. We consider the problem of computing δ online, when the string is provided from a stream. We present two algorithms solving the problem: one working in O(log n) amortized time per character, and the other in O(log³ n) worst-case time per character. To our knowledge, this is the first polylog-time online solution to this problem.

Citations

• Dynamic Convex Hulls for Simple Paths
• Sketching and Streaming for Dictionary Compression
• Substring Complexity in Sublinear Space
• Compressed Data Structures for Dynamic Sequences
• Faster Compact On-Line Lempel-Ziv Factorization
• Optimal Dynamic Sequence Representations
• Sublinear Algorithms for Approximating String Compressibility
• Clustering by compression
• Dynamic Planar Convex Hull
• An analysis of the Burrows—Wheeler transform

Related

• Substring Complexities on Run-length Compressed Strings
• Sketching and Streaming for Dictionary Compression
• Substring Complexity in Sublinear Space
• Faster subsequence recognition in compressed strings
• Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms