Adaptive encodings for small and fast compressed suffix arrays

Compressed suffix arrays index large repetitive collections and are widely used in bioinformatics, version control, and natural language processing. The \(r\) -index and its variants combine the run-length Burrows–Wheeler transform (BWT) with a sample of the suffix array to achieve space proportional to the number of equal-symbol runs. While effective for near-identical strings, their size grows quickly when edited copies are added to the collection as the number of BWT runs is sensitive to variation. Existing approaches either apply extra compression at the cost of slower queries or prioritize speed at the expense of space, limiting practical tradeoffs at large scale. We introduce variable-length blocking (VLB), an adaptive encoding for BWT-based compressed suffix arrays. Our technique adapts the amount of indexing information to the local run structure: compressible regions retain less auxiliary data, while incompressible areas store more. Specifically, we recursively partition the BWT until each block contains at most \(w\) runs (a parameter), and organize the blocks into a tree. Accessing a position requires descending a root-to-leaf path followed by a short run scan. Compressible regions are placed near the root, while incompressible regions lie deeper and are augmented with additional indexing data to speed up access. This strategy balances space and query speed by reallocating bits saved in compressible areas to accelerate access to incompressible ones. The VLB-tree also improves memory locality by co-locating related BWT and suffix array information. Backward search relies on rank and successor queries over the BWT. We introduce a sampling technique that relaxes global correctness by guaranteeing that these queries are correct only along valid backward-search states. This restriction reduces space usage without affecting the speed or correctness of pattern matching. We further extend the concepts of the VLB-tree to encode suffix array samples and then to the subsampled \(r\) -index ( \(sr\) -index), thus producing a small fully functional compressed suffix array. Experiments show that VLB-tree variants outperform the \(r\) -index and \(sr\) -index in query time, while retaining space close to that of the \(sr\) -index. The move data structure, a recent encoding, is faster than the VLB-tree but uses considerably more space, yielding a clear space-time tradeoff.