Substring complexity computed efficiently using burrows-wheeler transform runs
Substring Complexity in BWT-Runs Bounded Space
Data Structures and Algorithms
Summary
Measuring how complex a string is involves counting unique pieces of it. The authors focus on a way to find the most complex parts of a string by looking at patterns in its transformed version, called the Burrows-Wheeler transform. They found a method that uses little memory and runs quickly, based on a property called runs in this transform. This helps analyze string complexity more efficiently than before.
What this means in practice
- •For data compression engineers: Improve compression algorithms by efficiently evaluating string complexity within limited memory.
- •For bioinformatics software developers: Analyze genomic sequences to identify complex regions using space-efficient substring complexity measures.
Authors
Johannes Fischer
Abstract
Given a string $T[1..n]$, its substring complexity is defined as $δ=\max_k d_k/k$, where $d_k$ is the number of its distinct substrings of length $k$ in $T$. We show how to compute it in $O(n+r\log r)$ time, using only $O(r)$ words of space, where $r$ denotes the number of runs in the Burrows-Wheeler transform.