Optimal-Time Move Structure Construction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911620853137408 |
|---|---|
| author | Brown, Nathaniel K. Sanaullah, Ahsan Zhang, Shaojie Langmead, Ben |
| author_facet | Brown, Nathaniel K. Sanaullah, Ahsan Zhang, Shaojie Langmead, Ben |
| contents | The move structure represents a permutation $π$ of $[0,n)$ as a covering set of $O(r)$ disjoint intervals (contiguous subsets of $[0,n)$), where $r$ is the minimum number of intervals whose values permute together. Formally, $r = 1 + |\{i\in [1,n) : π(i) - 1 \neq π(i-1)\}|$. The move structure takes $O(r)$ words of space. Given the index of the interval containing $i$, it allows computing $π(i)$ and the index of the interval containing $π(i)$ in $O(1)$-time. Therefore, for permutations where $r \ll n$, it allows their representation and navigation in significantly compressed space. The previous best $O(r)$-space move structure construction algorithm takes $O(r\log r)$-time. In this paper, we describe a construction algorithm achieving optimal $O(r)$-time and space. We also show that using our improved algorithm within a recent previous work allows the computation of the longest common prefix array in $O(r)$-working space and optimal $O(n)$-time given the run-length-encoded Burrows-Wheeler transform. Finally, we implement our improved move structure construction algorithm and find that it is faster than the previous best algorithm while using comparable memory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22147 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal-Time Move Structure Construction Brown, Nathaniel K. Sanaullah, Ahsan Zhang, Shaojie Langmead, Ben Data Structures and Algorithms The move structure represents a permutation $π$ of $[0,n)$ as a covering set of $O(r)$ disjoint intervals (contiguous subsets of $[0,n)$), where $r$ is the minimum number of intervals whose values permute together. Formally, $r = 1 + |\{i\in [1,n) : π(i) - 1 \neq π(i-1)\}|$. The move structure takes $O(r)$ words of space. Given the index of the interval containing $i$, it allows computing $π(i)$ and the index of the interval containing $π(i)$ in $O(1)$-time. Therefore, for permutations where $r \ll n$, it allows their representation and navigation in significantly compressed space. The previous best $O(r)$-space move structure construction algorithm takes $O(r\log r)$-time. In this paper, we describe a construction algorithm achieving optimal $O(r)$-time and space. We also show that using our improved algorithm within a recent previous work allows the computation of the longest common prefix array in $O(r)$-working space and optimal $O(n)$-time given the run-length-encoded Burrows-Wheeler transform. Finally, we implement our improved move structure construction algorithm and find that it is faster than the previous best algorithm while using comparable memory. |
| title | Optimal-Time Move Structure Construction |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.22147 |