Binary Jumbled Indexing: Suffix tree histogram
Luís Cunha, Mário Medina* · 2025
Read Binary Jumbled Indexing: Suffix tree histogram by Luís Cunha, Mário Medina* (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00111.txt.
Description
Luís Cunha and Mário Medina speed up a classic string puzzle in a paper whose text dates to 2024. Given a string of zeros and ones, the puzzle asks which mixes of zeros and ones appear inside it. A data structure answering such questions for every mix is called a jumbled index.
Earlier builders of the index slowed badly on strings with many runs of the same digit, and the authors prove that slowdown is typical, not rare. Their new algorithm grows a suffix tree to strip out repeated substrings before counting. The worst-case cost stays high, but leaner memory access makes it faster in practice. The work matters for pattern matching in texts and biological sequences.
Catalog record
| CREATOR | Luís Cunha, Mário Medina* |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00111