A linearly computable measure of string complexity
In this very interesting paper, the authors introduce the notion of the \(I\)-complexity of a given string, which counts the number of distinct substrings in it, and investigate its properties. They prove that this measure of string complexity is computable in linear time and space from the well-known longest common prefix array (LCP array), the companion data structure of the suffix array. They also introduce the repetitions array, which is a permutation of the LCP array, and develop its properties. It is shown that the number of strings with \(I\)-complexity up to a given value is bounded and a large family of strings with almost maximal complexity is presented. The authors prove that most strings have high \(I\)-complexity. Their measure of complexity is compared with the Lempel-Ziv complexity, their main differences are discussed, and it is shown that in spite of their very distinct behavior on infinitely many strings, their values are close. Finally, the authors discuss a number of open problems and ongoing research on \(I\)-complexity.
- A Mathematical Theory of Communication
- A Pseudorandom Sequence--How Random Is It?
- A Theory of Program Size Formally Identical to Information Theory
- Clustering by Compression
- Compression of individual sequences via variable-rate coding
- Finite-state complexity and the size of transducers
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 1010621 (Why is no real title available?)
- scientific article; zbMATH DE number 1747450 (Why is no real title available?)
- scientific article; zbMATH DE number 1786458 (Why is no real title available?)
- scientific article; zbMATH DE number 3095523 (Why is no real title available?)
- Lempel-Ziv Dimension for Lempel-Ziv Compression
- On extending de Bruijn sequences
- On the Complexity of Finite Sequences
- Process complexity and effective random tests
- Relations between varieties of kolmogorov complexities
- Resource-bounded Kolmogorov complexity revisited
- Suffix Arrays: A New Method for On-Line String Searches
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Volume and entropy of regular timed languages: analytic approach
- Volume and Entropy of Regular Timed Languages: Discretization Approach
- A new distance metric on strings computable in linear time
- Physical complexity of symbolic sequences
- Joint string complexity for Markov sources: small data matters
- Maximizing T-complexity
- Joint string complexity for Markov sources
- Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
- scientific article; zbMATH DE number 1336330 (Why is no real title available?)
- scientific article; zbMATH DE number 1747450 (Why is no real title available?)
- scientific article; zbMATH DE number 2182449 (Why is no real title available?)
- The combinatorial complexity of a finite string
- Substring complexities on run-length compressed strings
- On average sequence complexity
This page was built for publication: A linearly computable measure of string complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441859)
