pith. sign in

arxiv: 1907.02308 · v1 · pith:Y7XPJD7Anew · submitted 2019-07-04 · 💻 cs.DS

The Alternating BWT: an algorithmic perspective

Raffaele Giancarlo , Giovanni Manzini , Antonio Restivo , Giovanna Rosone , Marinella Sciortino This is my paper

Pith reviewed 2026-05-25 09:20 UTC · model grok-4.3

classification 💻 cs.DS
keywords Burrows-Wheeler TransformAlternating Burrows-Wheeler Transformreversible transformationsrank-invertibilitybackward searchcompressed full-text indicessuffix sorting
0
0 comments X

The pith

The Alternating Burrows-Wheeler Transform shares rank-invertibility with the BWT and supports generalized backward search for compressed indices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the Alternating Burrows-Wheeler Transform, which applies an alternating lexicographical order rather than the standard one used by the BWT. Building on a prior characterization of reversible transformations, it shows that only the BWT and ABWT in that class possess rank-invertibility, a property that ensures efficient inversion. The study further establishes that the backward-search procedure extends efficiently to the ABWT, enabling its application in compressed full-text indices, and supplies an efficient computation method that pairs difference-cover suffix sorting with a linear-time minimal cyclic rotation algorithm under the alternating order.

Core claim

BWT and ABWT are the only transformations in the larger class of reversible transformations that are rank-invertible, and the backward-search procedure can be efficiently generalized to the ABWT, implying it can serve as the basis for efficient compressed full text indices. The ABWT can be efficiently computed by using a combination of the Difference Cover suffix sorting algorithm with a linear time algorithm for finding the minimal cyclic rotation of a word with respect to the alternating lexicographical order.

What carries the argument

Rank-invertibility, a property guaranteeing efficient invertibility that holds only for transformations using the standard or alternating lexicographical ordering rules.

If this is right

  • The ABWT supports efficient compressed full-text indices via the generalized backward-search procedure.
  • ABWT admits an efficient computation algorithm based on difference-cover suffix sorting plus linear-time minimal rotation under alternating order.
  • The rank-invertibility property distinguishes BWT and ABWT from the rest of the reversible class for algorithmic purposes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Reversible transforms outside BWT and ABWT likely require different inversion techniques that may not scale as well for indexing.
  • The dependence of rank-invertibility on the ordering rule suggests a route to test whether other ordering variants could acquire the same property.
  • Data structures built on BWT could be adapted to ABWT for strings whose periodic or cyclic properties interact favorably with alternating order.

Load-bearing premise

The larger class of reversible transformations is correctly characterized and rank-invertibility depends only on the ordering rule.

What would settle it

Identification of any other transformation inside the reversible class that satisfies rank-invertibility, or an input string on which backward search for the ABWT fails to run in time linear in the pattern length.

Figures

Figures reproduced from arXiv: 1907.02308 by Antonio Restivo, Giovanna Rosone, Giovanni Manzini, Marinella Sciortino, Raffaele Giancarlo.

Figure 1
Figure 1. Figure 1: Left: the matrix M(w) of all cyclic rotations of the word w = acaabr. Center: the matrix Mlex(w); the pair (caraab, 2) is the output bwt(w). Right: the matrix Malt(w); the pair (racaab, 0) is the output of ABW T (w). 1. Let F denote the first column of Mlex(w) (resp. Malt(w)), then F is obtained by lexicographically sorting the symbols of L. 2. For every i, 0 ≤ i < n, L[i] circularly precedes F[i] in the o… view at source ↗
Figure 2
Figure 2. Figure 2: Cyclic rotation matrices for the words s1 and s2. We use subscripts to distinguish the two occurrences of a in each word. |Σ| ≥ 3. We need to prove that if π 6= Id and π 6= Rev then BW TK is not rank-invertible. Note that any permutation π over the alphabet Σ induces a new ordering on any triplet of symbols in Σ. For example, if Σ = {a, b, c, d, e, f} the permutation π = (d, e, c, f, a, b) induces on the t… view at source ↗
Figure 3
Figure 3. Figure 3: Left: the matrix Malt of all cyclic rotations of the word ababba. Center: the ≺alt￾sorted suffixes of the Galois word ababba. Right: the ≺alt-sorted suffixes of the Lyndon conjugate aababb. The ≺alt-order of the last two suffixes is different from the alt-order of the correspondent cyclic rotations. Proposition 7.5. Let w be a primitive Galois word and let u ′ , u′′, v′ , v′′ be factors of w such that w =… view at source ↗
Figure 4
Figure 4. Figure 4: Left: the matrix Malt of all cyclic rotations of the word w = banana, sorted by using alt-order. The output is abwt(w) = bnnaaa. Center: the matrix Malt of the word banana$. The output is abwt(banana$) = abnn$aa. Right: the matrix Malt of the word ananab$, where ananab is the Galois conjugate of w. The output is abwt(ananab$) = b$nnaaa. The next corollary shows how to use FindGaloisRotation procedure to c… view at source ↗
read the original abstract

The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression. It has become a fundamental tool for designing self-indexing data structures, with important applications in several area in science and engineering. The Alternating Burrows-Wheeler Transform (ABWT) is another transformation recently introduced in [Gessel et al. 2012] and studied in the field of Combinatorics on Words. It is analogous to the BWT, except that it uses an alternating lexicographical order instead of the usual one. Building on results in [Giancarlo et al. 2018], where we have shown that BWT and ABWT are part of a larger class of reversible transformations, here we provide a combinatorial and algorithmic study of the novel transform ABWT. We establish a deep analogy between BWT and ABWT by proving they are the only ones in the above mentioned class to be rank-invertible, a novel notion guaranteeing efficient invertibility. In addition, we show that the backward-search procedure can be efficiently generalized to the ABWT; this result implies that also the ABWT can be used as a basis for efficient compressed full text indices. Finally, we prove that the ABWT can be efficiently computed by using a combination of the Difference Cover suffix sorting algorithm [K\"{a}rkk\"{a}inen et al., 2006] with a linear time algorithm for finding the minimal cyclic rotation of a word with respect to the alternating lexicographical order.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper provides a combinatorial and algorithmic study of the Alternating Burrows-Wheeler Transform (ABWT). Building on the class of reversible transformations from Giancarlo et al. 2018, it proves that BWT and ABWT are the only rank-invertible members of this class (a property guaranteeing efficient invertibility), shows that the backward-search procedure generalizes efficiently to ABWT (implying use in compressed full-text indices), and gives a linear-time ABWT construction via the difference-cover suffix sorting algorithm combined with a linear-time minimal cyclic rotation finder under alternating lexicographic order.

Significance. If the central claims hold, the work establishes a precise analogy between BWT and ABWT by isolating rank-invertibility as a distinguishing combinatorial property within the reversible class, while also extending ABWT to practical indexing applications. The explicit linear-time construction and the generalization of backward search are concrete algorithmic contributions that could broaden the set of transforms usable for self-indexes.

major comments (2)
  1. [Section on rank-invertibility uniqueness (likely §3 or §4)] The uniqueness proof that only BWT and ABWT are rank-invertible within the reversible class (the load-bearing claim for the combinatorial contribution) is stated to depend only on the ordering rule. However, this rests entirely on the precise definition of the class in the cited Giancarlo et al. 2018 paper; the manuscript must include an explicit recap of that definition (including any constraints on input strings, periodicity, or alphabet) to confirm no additional structural assumptions are implicitly used.
  2. [Section on backward-search generalization] The generalization of backward search to ABWT claims efficient implementation, but the manuscript provides no visible edge-case analysis or rank-update formulas for strings with periodic structure or when the alternating order produces different LF-mapping behavior than standard BWT; this is load-bearing for the indexing-application claim.
minor comments (2)
  1. [Introduction / Preliminaries] Notation for the alternating lexicographic order should be introduced with a small concrete example in the preliminaries to aid readability.
  2. Ensure the bibliography entry for Giancarlo et al. 2018 is complete and that all references to the reversible class are cross-cited consistently.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive summary and for identifying two points that require clarification or expansion. Both comments are addressed below with concrete plans for revision.

read point-by-point responses

  1. Referee: [Section on rank-invertibility uniqueness (likely §3 or §4)] The uniqueness proof that only BWT and ABWT are rank-invertible within the reversible class (the load-bearing claim for the combinatorial contribution) is stated to depend only on the ordering rule. However, this rests entirely on the precise definition of the class in the cited Giancarlo et al. 2018 paper; the manuscript must include an explicit recap of that definition (including any constraints on input strings, periodicity, or alphabet) to confirm no additional structural assumptions are implicitly used.

    Authors: We agree that the uniqueness proof would benefit from an explicit, self-contained recap of the reversible-transform class. In the revised manuscript we will insert a short subsection (new §2.2) that reproduces the definition from Giancarlo et al. 2018 verbatim, states the alphabet and string constraints, and notes the absence of periodicity restrictions. This addition will make the subsequent uniqueness argument independent of the reference. revision: yes

  2. Referee: [Section on backward-search generalization] The generalization of backward search to ABWT claims efficient implementation, but the manuscript provides no visible edge-case analysis or rank-update formulas for strings with periodic structure or when the alternating order produces different LF-mapping behavior than standard BWT; this is load-bearing for the indexing-application claim.

    Authors: The current manuscript derives the generalized LF-mapping and shows that rank queries remain O(1) per step under the alternating order, but we concede that periodic cases and explicit update formulas are not illustrated. We will add a dedicated subsection (new §4.3) containing (i) the precise rank-update recurrence for ABWT, (ii) a short proof that periodicity does not alter the asymptotic cost, and (iii) two worked examples (one periodic, one non-periodic) that compare the ABWT and BWT LF-mappings side-by-side. revision: yes

Circularity Check

1 steps flagged

Minor self-citation on class definition; uniqueness and generalization proved as independent combinatorial facts

specific steps
  1. self citation load bearing [Abstract]
    "Building on results in [Giancarlo et al. 2018], where we have shown that BWT and ABWT are part of a larger class of reversible transformations, here we provide a combinatorial and algorithmic study of the novel transform ABWT. We establish a deep analogy between BWT and ABWT by proving they are the only ones in the above mentioned class to be rank-invertible"

    The scope of the uniqueness claim is delimited by the class definition taken from the self-cited prior work; while the proof itself is new, the central premise that only BWT and ABWT are rank-invertible is meaningful only inside that externally supplied (self-authored) characterization.

full rationale

The paper cites overlapping-author prior work solely to define the larger class of reversible transformations and then proves rank-invertibility uniqueness and backward-search generalization as new results inside that class. No step reduces a claimed prediction or uniqueness theorem to a fitted parameter, self-referential definition, or unverified self-citation chain. The derivation consists of explicit combinatorial arguments that remain externally falsifiable and do not collapse by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard combinatorial properties of lexicographic and alternating orders plus the correctness of the 2018 reversible-transform class; no numerical parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption The class of reversible transformations introduced in Giancarlo et al. 2018 is well-defined and closed under the operations used here.
    Invoked when the paper states that BWT and ABWT are the only rank-invertible members of that class.
  • standard math Standard properties of cyclic rotations and suffix arrays hold under the alternating lexicographic order.
    Required for the linear-time minimal-rotation algorithm and the difference-cover sorting adaptation.

pith-pipeline@v0.9.0 · 5814 in / 1502 out tokens · 22878 ms · 2026-05-25T09:20:34.569163+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages · 1 internal anchor

  1. [1]

    Belazzougui and G

    D. Belazzougui and G. Navarro. Optimal lower and upper bounds for representing sequences. ACM T. Algorithms , 11(4):31:1–31:21, 2015

    work page 2015

  2. [2]

    Bonomo, S

    S. Bonomo, S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. Sorting conjugates and suffixes of words in a multiset. International Journal of Foundations of Computer Science , 25(08):1161–1175, 2014

    work page 2014

  3. [3]

    K. S. Booth. Lexicographically least circular substrings. Inf. Process. Lett., 10(4/5):240–242, 1980

    work page 1980

  4. [4]

    Burrows and D

    M. Burrows and D. J. Wheeler. A block sorting data compression a lgo- rithm. Technical report, DIGITAL System Research Center, 199 4

    work page

  5. [5]

    Chapin and S

    B. Chapin and S. Tate. Higher compression from the burrows- wheeler transform by modified sorting. In DCC, page 532. IEEE Computer Society, 1998. Full version available from https://www.uncg.edu/cmp/faculty/srtate/papers/bwtsort.pdf

    work page 1998

  6. [6]

    C. J. Colbourn and A. C. H. Ling. Quorums from difference covers . Inf. Process. Lett., 75(1-2):9–12, 2000. 24

    work page 2000

  7. [7]

    A. Cox, M. Bauer, T. Jakobi, and G. Rosone. Large-scale compr ession of genomic sequence databases with the Burrows-Wheeler transf orm. Bioinformatics, 28(11):1415–1419, 2012

    work page 2012

  8. [8]

    Crochemore, J

    M. Crochemore, J. D´ esarm´ enien, and D. Perrin. A note on theBurrows- Wheeler transformation. Theor. Comput. Sci. , 332:567–572, 2005

    work page 2005

  9. [9]

    Daykin, R

    J. Daykin, R. Groult, Y. Guesnet, T. Lecroq, A. Lefebvre, M. L onard, and . Prieur-Gaston. A survey of string orderings and their applica tion to the Burrows-Wheeler transform. Theor. Comput. Sci. , 2017

    work page 2017

  10. [10]

    Dolce, A

    F. Dolce, A. Restivo, and C. Reutenauer. On generalized Lyndo n words. Theor. Comput. Sci. , 2018

    work page 2018

  11. [11]

    J.-P. Duval. Factorizing words over an ordered alphabet. J. Algorithms, 4(4):363–381, 1983

    work page 1983

  12. [12]

    P. Fenwick. The Burrows-Wheeler transform for block sorting text com- pression: Principles and improvements. Comput. J. , 39(9):731–740, 1996

    work page 1996

  13. [13]

    Ferenczi and L

    S. Ferenczi and L. Q. Zamboni. Clustering Words and Interval Ex- changes. Journal of Integer Sequences , 16(2):Article 13.2.1, 2013

    work page 2013

  14. [14]

    Ferragina, R

    P. Ferragina, R. Giancarlo, G. Manzini, and M. Sciortino. Boostin g textual compression in optimal linear time. J. ACM , 52(4):688–713, 2005

    work page 2005

  15. [15]

    Ferragina and G

    P. Ferragina and G. Manzini. Opportunistic data structures wit h appli- cations. In FOCS 2000 , pages 390–398. IEEE Computer Society, 2000

    work page 2000

  16. [16]

    Ferragina and G

    P. Ferragina and G. Manzini. Indexing compressed text. J. ACM , 52:552–581, 2005

    work page 2005

  17. [17]

    Gagie, G

    T. Gagie, G. Manzini, and J. Sir´ en. Wheeler graphs: A framewor k for BWT-based data structures. Theor. Comput. Sci. , 698:67–78, 2017

    work page 2017

  18. [18]

    I. M. Gessel, A. Restivo, and C. Reutenauer. A bijection betwe en words and multisets of necklaces. Eur. J. Combin. , 33(7):1537 – 1546, 2012

    work page 2012

  19. [19]

    I. M. Gessel and C. Reutenauer. Counting permutations with g iven cycle structure and descent set. J. Comb. Theory A , 64(2):189–215, 1993

    work page 1993

  20. [20]

    Giancarlo, G

    R. Giancarlo, G. Manzini, A. Restivo, G. Rosone, and M. Sciortino . Block Sorting-Based Transformations on Words: Beyond the Magic BWT. In DLT, pages 1–17. Springer International Publishing, 2018. 25

    work page 2018

  21. [21]

    A New Class of Searchable and Provably Highly Compressible String Transformations

    R. Giancarlo, G. Manzini, G. Rosone, and M. Sciortino. A new class of searchable and provably highly compressible string transformat ions. CoRR, abs/1902.01280, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  22. [22]

    Giancarlo, A

    R. Giancarlo, A. Restivo, and M. Sciortino. From first principles t o the Burrows and Wheeler transform and beyond, via combinatorial opt i- mization. Theor. Comput. Sci. , 387:236 – 248, 2007

    work page 2007

  23. [23]

    D. Gusfield. Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology . Cambridge University Press, 1997

    work page 1997

  24. [24]

    K¨ arkk¨ ainen and P

    J. K¨ arkk¨ ainen and P. Sanders. Simple linear work suffix array construc- tion. In Automata, Languages and Programming, volume 2719 of LNCS, pages 943–955. Springer Berlin Heidelberg, 2003

    work page 2003

  25. [25]

    K¨ arkk¨ ainen, P

    J. K¨ arkk¨ ainen, P. Sanders, and S. Burkhardt. Linear work suffix array construction. J. ACM , 53:918–936, 2006

    work page 2006

  26. [26]

    Kimura and A

    K. Kimura and A. Koike. Ultrafast SNP analysis using the Burrows - Wheeler transform of short-read data. Bioinformatics, 31(10):1577– 1583, 2015

    work page 2015

  27. [27]

    Li and R

    H. Li and R. Durbin. Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics, 26(5):589–595, 2010

    work page 2010

  28. [28]

    Lothaire

    M. Lothaire. Applied Combinatorics on Words (Encyclopedia of Math- ematics and its Applications) . Cambridge University Press, New York, NY, USA, 2005

    work page 2005

  29. [29]

    M¨ akinen, D

    V. M¨ akinen, D. Belazzougui, F. Cunial, and A. I. Tomescu. Genome- Scale Algorithm Design: Biological Sequence Analysis in th e Era of High- Throughput Sequencing. Cambridge University Press, 2015

    work page 2015

  30. [30]

    Mantaci, A

    S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. An extens ion of the Burrows-Wheeler Transform. Theor. Comput. Sci. , 387(3):298–312, 2007

    work page 2007

  31. [31]

    Mantaci, A

    S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. A new com- binatorial approach to sequence comparison. Theory Comput. Syst. , 42(3):411–429, 2008

    work page 2008

  32. [32]

    Mantaci, A

    S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. Burrows- Wheeler Transform and Run-Length Enconding. In Combinatorics on Words - 11th International Conference, WORDS 2017. Proceedings , volume 10432 of LNCS, pages 228–239. Springer, 2017. 26

    work page 2017

  33. [33]

    Mantaci, A

    S. Mantaci, A. Restivo, G. Rosone, M. Sciortino, and L. Versar i. Mea- suring the clustering effect of BWT via RLE. Theor. Comput. Sci. , 698:79–87, 2017

    work page 2017

  34. [34]

    Mantaci, A

    S. Mantaci, A. Restivo, and M. Sciortino. Burrows-Wheeler tra nsform and Sturmian words. Information Processing Letters, 86:241–246, 2003

    work page 2003

  35. [35]

    Mantaci, A

    S. Mantaci, A. Restivo, and M. Sciortino. Distance measures fo r bio- logical sequences: Some recent approaches. Int. J. Approx. Reasoning , 47(1):109–124, 2008

    work page 2008

  36. [36]

    G. Manzini. An analysis of the Burrows-Wheeler transform. J. ACM , 48(3):407–430, 2001

    work page 2001

  37. [37]

    Manzini and P

    G. Manzini and P. Ferragina. Engineering a lightweight suffix arra y construction algorithm. Algorithmica, 40:33–50, 2004

    work page 2004

  38. [38]

    G. Navarro. Compact Data Structures - A Practical Approach . Cam- bridge University Press, 2016

    work page 2016

  39. [39]

    Pak and A

    I. Pak and A. Redlich. Long cycles in abc-permutations. Functional Analysis and Other Mathematics , 2:87–92, 2008

    work page 2008

  40. [40]

    Prezza, N

    N. Prezza, N. Pisanti, M. Sciortino, and G. Rosone. SNPs detec tion by eBWT positional clustering. Algorithms for Molecular Biology , 14(1):3, 2019

    work page 2019

  41. [41]

    Restivo and G

    A. Restivo and G. Rosone. Burrows-Wheeler transform and pa lindromic richness. Theor. Comput. Sci. , 410(30-32):3018 – 3026, 2009

    work page 2009

  42. [42]

    Restivo and G

    A. Restivo and G. Rosone. Balancing and clustering of words in th e Burrows-Wheeler transform. Theor. Comput. Sci. , 412(27):3019 – 3032, 2011

    work page 2011

  43. [43]

    Reutenauer

    C. Reutenauer. Mots de Lyndon g´ en´ eralis´ es 54.S´ em. Lothar. Combin., pages 16, B54h, 2006

    work page 2006

  44. [44]

    Rosone and M

    G. Rosone and M. Sciortino. The Burrows-Wheeler Transform b e- tween Data Compression and Combinatorics on Words. In The Nature of Computation. Logic, Algorithms, Applications - 9th Conf erence on Computability in Europe, CiE 2013. Proceedings , volume 7921 of LNCS, pages 353–364. Springer, 2013

    work page 2013

  45. [45]

    Schindler

    M. Schindler. A fast block-sorting algorithm for lossless data co mpres- sion. In DCC, page 469. IEEE Computer Society, 1997. 27

    work page 1997

  46. [46]

    Shiloach

    Y. Shiloach. Fast canonization of circular strings. J. Algorithms , 2(2):107–121, 1981

    work page 1981

  47. [47]

    Simpson and S

    J. Simpson and S. J. Puglisi. Words with simple Burrows-Wheeler tr ans- forms. Electronic Journal of Combinatorics , 15, article R83, 2008

    work page 2008

  48. [48]

    L. Yang, X. Zhang, and T. Wang. The Burrows-Wheeler similarity dis- tribution between biological sequences based on Burrows-Wheeler trans- form. Journal of Theoretical Biology , 262(4):742–749, 2010. 28

    work page 2010