Pith. sign in

REVIEW 2 major objections 6 minor 34 references

Re-Pair In Small Space

T0 review · 2 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Re-Pair grammar compression is computable in quadratic time in text-sized working space, including the text itself.

desk verdict Valuable small-space Re-Pair algorithm with a real, fixable bug in the main frequency-counting lemma; deserves serious review. read the letter →

arxiv 1908.04933 v3 pith:LLF4OW7T submitted 2019-08-14 cs.DS

Dominik Köppl , Tomohiro I , Isamu Furuya , Yoshimasa Takabatake , Kensuke Sakai , Keisuke Goto This is my paper · ORCID
classification cs.DS
keywords Re-Pairgrammarcompressionin-placealgorithmsmall-spacecomputationfrequencytablebigramrestoremodelexternalmemory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Re-Pair is a grammar-compression scheme that repeatedly replaces the most frequent non-overlapping bigram by a fresh non-terminal. This paper tries to establish that the whole Re-Pair grammar can be computed in $O(n^2)$ time using $\max((n/c)\lg n, n\lceil\lg \sigma_m\rceil)+O(\lg n)$ bits of working space, with the text itself counting as part of that space; for a large integer alphabet with $\sigma = \Omega(n)$, that is the first non-trivial in-place Re-Pair algorithm. The demonstration works in the restore model, so the original input can be overwritten and later recovered in the time of the computation with $O(\lg n)$ extra bits. The same round-based skeleton yields a bit-parallel variant running in $O(n^2 \lg \log_\tau n \lg \lg \lg n / \log_\tau n)$ time when $\tau = o(n)$, plus parallel and external-memory versions. A sympathetic reader would care because Re-Pair's main practical obstacle is not its compression ratio but the large frequency tables its textbook computation maintains, and this paper attacks exactly that obstacle.

What carries the argument

The load-bearing object is a growing frequency table $F$, physically stored in the text space freed by replacing bigrams with single non-terminals, together with a threshold $t$ fixed at each round as $F$'s lowest stored frequency. Lemma 2.2 is the trade-off subroutine: to find the $d$ most frequent bigrams it splits the text into overlapping blocks of length $d$, builds a candidate table per block, counts candidates by scanning the text with binary search, and merges partial tables, costing $O(\max(n,d)\, n \lg d / d)$ time in $2d\lceil\lg(\sigma^2 n/2)\rceil$ bits. $F$'s rounds grow its capacity $f_k$ by a constant factor $\gamma > 1$, so only $O(\lg n)$ recomputations are needed, and each turn's update rule—decrement frequencies adjacent to replaced occurrences, add bigrams that newly contain the non-terminal, drop entries below $t$—keeps $F$ synchronized with the text.

What would settle it

Run the algorithm on a unary text $a^{2k}$ with the trade-off parameter $d=1$: Lemma 2.2's left-to-right scan reports $2k-1$ occurrences of the bigram $aa$, whereas Re-Pair's definition of frequency demands $k$ non-overlapping occurrences. Comparing the frequency stored in $F$ against a direct run-aware count on this input settles whether the subroutine is correct.

Watch

Extended reading notes

Core claim

The paper's central claim is that Re-Pair can be driven by a frequency table $F$ that is stored in the space freed up by the very replacements it guides. At the start of round $k$ the table holds $f_k$ bigrams and a threshold $t$, the table's lowest frequency; as long as $F$ is non-empty after a turn, it still contains a most frequent bigram, so the next turn can simply take the highest-frequency entry. Only when $F$ empties is it rebuilt, with capacity multiplied by a factor $\gamma > 1$; because $\gamma$ is bounded away from 1, only $O(\lg n)$ rebuilds occur, and each rebuild uses a trade-off subroutine (Lemma 2.2) that partitions the text into overlapping blocks and counts the $d$ most frequent bigrams in $O(\max(n,d)\, n \lg d / d)$ time with $2d\lceil\lg(\sigma^2 n/2)\rceil$ bits. The result is Theorem 2.3's $O(n^2)$ time and text-sized working space, with variants for bit-parallel counting, parallelism, external memory, and MR-Re-Pair.

Load-bearing premise

Lemma 2.2's proof assumes that a single left-to-right scan that finds each scanned bigram in a candidate table and increments its counter yields the non-overlapping frequency Re-Pair needs; on a run of $L$ equal characters that scan records $L-1$ occurrences of the repeated bigram, while only $\lfloor L/2 \rfloor$ non-overlapping copies exist. Since every round's table is seeded by this subroutine, the main theorem inherits that assumption.

Editorial extensions

If this is right

  • Re-Pair becomes computable in text-sized working memory plus $O(\lg n)$ bits, so large-scale grammar compression no longer requires frequency tables that dwarf the input.
  • The restore model guarantees the original text can be recovered in the time of the whole computation with only $O(\lg n)$ extra bits, so overwriting the input is safe.
  • For integer alphabets with $\sigma = \Omega(n)$, this is the first non-trivial in-place Re-Pair algorithm; earlier space-efficient Re-Pair algorithms assumed a constant alphabet.
  • The same frequency-table skeleton gives a parallel CRCW variant running in $O(n^2/p)$ time with $O(p\lg n)$ extra bits and an external-memory variant whose I/O cost is bounded by scans and sorting instead of a large heap.
  • When the terminal-plus-nonterminal alphabet $\tau$ satisfies $\tau = o(n)$, bit-parallel broadword search lowers the time to $O(n^2 \lg \log_\tau n \lg \lg \lg n / \log_\tau n)$ in the same space.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The round-growth pattern is a general recipe: any compressor whose bottleneck is a candidate or frequency table could grow that table inside the space its own output frees up, using a threshold to avoid frequent rebuilds.
  • The broadword bigram-counting primitive of Section 3 is reusable on its own for other small-space string algorithms that need bigram frequencies under tight memory.
  • A natural extension is to make the Lemma 2.2 scan run-aware for repeated bigrams, counting $\lfloor L/2 \rfloor$ inside a run of $L$ equal characters instead of $L-1$ occurrences; such a count would match Re-Pair's non-overlapping definition directly and should preserve the time bound.
  • The practical bottleneck is the early rounds with tiny $f_k$; combining the paper's heuristics (majority vote when one bigram dominates, temporary full table for small alphabets) into an adaptive start could make the $O(n^2)$ worst case rare on real corpora.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper proposes an algorithm that computes the Re-Pair grammar compression for a text of length n over an integer alphabet in O(n^2) time using max((n/c) lg n, n⌈lg σ_m⌉)+O(lg n) bits of working space including the text space, working in the restore model. The central tool is a trade-off lemma (Lemma 2.2) that computes the d most frequent bigrams in O(max(n,d) n lg d / d) time and 2d⌈lg(σ^2 n/2)⌉+O(lg n) bits, which is invoked O(lg n) times in the main sequential algorithm. The paper also gives a bit-parallel variant (Theorem 3.1), a parallel variant (Theorem 5.3), an external-memory variant (Theorem 6.1), an adaptation to MR-Re-Pair (Section 4), and a C++ implementation (Section 2.5).

Significance. If the main theorem is correct, this is the first non-trivial in-place Re-Pair algorithm for large integer alphabets, and the same framework extends to parallel and external-memory settings, which would be a meaningful contribution. The paper also includes an implementation and practical heuristics, and the bit-parallel section (Section 3.1) correctly handles the delicate case of repeated-character bigrams by using runs and parity of ending positions. However, the central Lemma 2.2, on which Theorems 2.3, 3.1, 5.3, and 6.1 all rely, counts overlapping occurrences rather than the non-overlapping frequencies required by the paper's own definition of Re-Pair, so the main correctness claim is not established as written.

major comments (2)
  1. [Section 2.3, capacity of F] The proof of Lemma 2.2 computes frequencies by scanning the text from left to right and incrementing a counter for every position whose bigram appears in F'. For a run of L identical characters, this counts L−1 occurrences of the repeated bigram, whereas the paper defines the frequency of a bigram as its number of non-overlapping occurrences (Section 1.2), which is floor(L/2). This is not a cosmetic discrepancy: for T = aaaaabcbcbcb, the scan reports aa with count 4 and bc with count 3, so with d = 1 it selects aa as the most frequent bigram, while the non-overlapping frequencies are aa = 2 and bc = 3, making bc the correct choice. Since Theorem 2.3 invokes Lemma 2.2 O(lg n) times and every replacement decision in the main loop is based on the resulting table F, the algorithm can diverge from the Re-Pair replacement rule from the first turn. The paper itself describes the correct treatment in Section 3.1 (Case b = c), counting runs via even/odd ending positions; that technique can be ported to Lemma 2.2 by skipping to the end of each run and adding floor(L/2), while preserving the O(n lg d) per-scan time. As written, however, the proof of Lemma 2.2 does not implement this, so the central theorem is not established. I consider this a load-bearing correctness issue that must be resolved in a revision.
  2. [Section 2.3, capacity of F] The proof of Theorem 2.3 does not rigorously establish that the freed text space at the beginning of each round is large enough to store the frequency table F together with the working space of Lemma 2.2. The text says 'suppose that we have enough space available for storing the frequencies of α f_k bigrams' and then gives a growth calculation using constants α and β, but it never proves by induction that the space actually freed by previous replacements reaches this size. Since the claimed space bound (max((n/c) lg n, n⌈lg σ_m⌉) + O(lg n) bits including the text) is a central contribution, the authors should supply an explicit invariant that relates the number of freed characters, the bit width ⌈lg σ_{i+1}⌉, and the capacity α f_k, and verify it for large alphabets (σ = Ω(n)), where Lemma 2.2's frequency table has entries of size Θ(lg n) bits. Without such an invariant, the in-place space claim is not fully supported.
minor comments (6)
  1. [Section 2.1, proof of Lemma 2.2] The extended substring S_j has length d+2 and can contain up to d+1 distinct bigrams, while the frequency table F' has only d entries; the proof's statement that 'there are at most d different bigrams in S_j' is false in general. Increase F' to d+1 entries or note that constants absorb the extra slot.
  2. [Section 2.1, Lemma 2.2] The time bound O(max(n,d) n lg d / d) is undefined for d = 1 because lg 1 = 0. Either state the result for d ≥ 2 and handle d = 1 separately with an O(n^2) bound, or adjust the formula.
  3. [Section 2.3, Eq. (1)] The summation notation with O(lg n) as the upper limit is informal; replacing it with an explicit bound such as sum_{k=0}^{C lg n} for a constant C would make the time analysis more precise.
  4. [Section 3.1, Case b = c] The handling of runs that cross chunk borders is described only in prose; a formal statement of how the run lengths are accumulated and how the even/odd parity is applied across chunk boundaries would improve reproducibility.
  5. [Section 2.5, implementation] The implementation fixes the bit width of the text space to 16 bits and assumes a byte alphabet, so the reported experiments do not exercise the bit-width enlargement step that is central to the in-place space claim of Theorem 2.3. This simplification should be stated more prominently.
  6. [Abstract] The notation O(n^2) ∩ O(n^2 lg log_τ n lg lg lg n / log_τ n) is unconventional; since the second term is never larger than the first, describing the bound as O(n^2) with the refinement given in Theorem 3.1 would be clearer.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; central Re-Pair derivation is self-contained, though Lemma 2.2 has a correctness issue with overlapping equal-character bigrams.

full rationale

The paper's central claim (Theorem 2.3) is derived from Lemma 2.2, a frequency-table construction over text partitions, plus an invariant-maintenance argument for the table F and a growth analysis (Eq. 1). None of these steps fits parameters to data or assumes the theorem it is trying to prove. The threshold t, capacities f_k, and constants alpha, beta, and gamma are introduced as analytic quantities and bounded inside the proof, not tuned from empirical observations; benchmarks in Section 2.5 are illustrative and not used as inputs to the algorithm. Self-citations ([13], [16], [27]) appear in related-work discussion and in the MR-Re-Pair adaptation; they are not load-bearing for the main sequential, parallel, or external-memory Re-Pair theorems. In particular, [13] is used only to argue the optional MR-Re-Pair adaptation, and even there the paper gives an algorithmic construction (extending occurrences) rather than importing the claimed result. The major caveat is Lemma 2.2's proof: it says frequencies are computed 'by scanning the text from left to right' and locating each scanned bigram, which counts overlapping occurrences; Section 1.2 defines frequency as non-overlapping. For a run of equal characters this can select a different most frequent bigram than the Re-Pair definition. That is a correctness gap in the derivation, not circularity, because the false step does not make the output equivalent to the input by construction. Overall, no circular step was found; the derivation is self-contained relative to its stated (though partly buggy) assumptions.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central construction needs no fitted constants. The main axioms are the word RAM and restore models, the ability to reuse freed text space for the frequency table, and a false counting assumption in Lemma 2.2 that must be corrected.

assumptions (4)
  • standard math Word RAM model with word size Ω(lg n) and restore model
    Section 1.2 defines the model; all complexity claims are relative to it.
  • domain assumption Text can be enlarged from ni⌈lg σ_i⌉ bits to ni⌈lg σ_{i+1}⌉ bits without extra memory
    Section 2.2 states 'we assume that we can enlarge the text ... without additional extra memory.' This is needed because the total space bound counts only max((n/c) lg n, n⌈lg σ_m⌉) bits.
  • ad hoc to paper A left-to-right scan that increments a counter for every matching position computes the non-overlapping frequency of a bigram
    Used in Lemma 2.2 proof; false for repeated-character bigrams, contradicting the paper's own non-overlap definition and the special handling in Lemma 3.3.
  • standard math In-place heapsort sorts n items in O(n lg n) time
    Lemma 2.1, used in the sorting steps of the frequency table construction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Re-Pair In Small Space." pith.science (2026). https://pith.science/paper/LLF4OW7T

@misc{pith2026190804933,
  author       = {Pith},
  title        = {Pith review of: Re-Pair In Small Space},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LLF4OW7T}},
  note         = {Machine review of arXiv:1908.04933}
}
abstract

Re-Pair is a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large scale data sets. As a solution for this problem we present, given a text of length $n$ whose characters are drawn from an integer alphabet, an $O(n^2) \cap O(n^2 \lg \log_\tau n \lg \lg \lg n / \log_\tau n)$ time algorithm computing Re-Pair in $n \lg \max(n,\tau)$ bits of space including the text space, where $\tau$ is the number of terminals and non-terminals. The algorithm works in the restore model, supporting the recovery of the original input in the time for the Re-Pair computation with $O(\lg n)$ additional bits of working space. We give variants of our solution working in parallel or in the external memory model.

Figures

Figures reproduced from arXiv: 1908.04933 by the authors.

Figure 1
Figure 1. Step-by-step execution of the first turn of our algorith [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Operations used in Figs. 4 and 5 for two bit vectors [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Step-by-step execution of rmPreRun(X) and rmSufRun(X) introduced in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Broadword matching all occurrences of a character in a s [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Finding a bigram bb in a string S of bit length q, where q is the largest multiple of 2 ⌈lg σ⌉ fitting into a computer word, divided by ⌈lg σ⌉. In the example, we represent the strings M, B, E, and X as arrays of integers with bit width x := ⌈lg σ⌉ and write 1 and 0 fo…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Aggarwal and J

    A. Aggarwal and J. S. Vitter. The input/output complexity of so rting and related problems. Com- mun. ACM , 31(9):1116–1127, 1988

    work page 1988

  2. [2]

    The smallest grammar problem revisited

    H. Bannai, M. Hirayama, D. Hucke, S. Inenaga, A. Jez, M. Lohre y, and C. P. Reh. The smallest grammar problem revisited. arXiv 1908.06428 , 2019. 15

    work page Pith review arXiv 1908

  3. [3]

    K. E. Batcher. Sorting networks and their applications. In Proc. AFIPS , volume 32 of AFIPS Conference Proceedings, pages 307–314, 1968

    work page 1968

  4. [4]

    Practical and Effective Re-Pair Compression

    P. Bille, I. L. Gørtz, and N. Prezza. Practical and effective Re-P air compression. arXiv 1704.08558, 2017

    work page Pith review arXiv 2017

  5. [5]

    Bille, I

    P. Bille, I. L. Gørtz, and N. Prezza. Space-efficient Re-Pair comp ression. In Proc. DCC , pages 171–180, 2017

    work page 2017

  6. [6]

    R. S. Boyer and J. S. Moore. MJRTY: A fast majority vote algorit hm. In Automated Reasoning: Essays in Honor of Woody Bledsoe , Automated Reasoning Series, pages 105–118, 1991

    work page 1991

  7. [7]

    T. M. Chan, J. I. Munro, and V. Raman. Selection and sorting in th e “restore” model. ACM Trans. Algorithms, 14(2):11:1–11:18, 2018

    work page 2018

  8. [8]

    Charikar, E

    M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat. The smallest grammar problem. IEEE Trans. Information Theory , 51(7):2554–2576, 2005

    work page 2005

Show all 34 references
  1. [9]

    Crochemore, R

    M. Crochemore, R. Grossi, J. K¨ arkk¨ ainen, and G. M. Landau. Computing the Burrows-Wheeler transform in place and in small space. J. Discrete Algorithms , 32:44–52, 2015

    2015

  2. [10]

    F. A. da Louza, T. Gagie, and G. P. Telles. Burrows-Wheeler tra nsform and LCP array construction in constant space. J. Discrete Algorithms , 42:14–22, 2017

    2017

  3. [11]

    De Luca, V

    P. De Luca, V. M. Russiello, R. Ciro Sannino, and L. Valente. A stu dy for image compression using Re-Pair algorithm. arXiv e-prints , 2019

    2019

  4. [12]

    M. L. Fredman and D. E. Willard. Surpassing the information theo retic bound with fusion trees. J. Comput. Syst. Sci. , 47(3):424–436, 1993

    1993

  5. [13]

    Furuya, T

    I. Furuya, T. Takagi, Y. Nakashima, S. Inenaga, H. Bannai, an d T. Kida. MR-RePair: Grammar compression based on maximal repeats. In Proc. DCC, pages 508–517, 2019

    2019

  6. [14]

    Ganczorz

    M. Ganczorz. Entropy lower bounds for dictionary compressio n. In Proc. CPM , volume 128 of LIPIcs, pages 11:1–11:18, 2019

    2019

  7. [15]

    Ganczorz and A

    M. Ganczorz and A. Jez. Improvements on Re-Pair grammar co mpressor. In Proc. DCC , pages 181–190, 2017

    2017

  8. [16]

    K. Goto. Optimal time and space construction of suffix arrays a nd LCP arrays for integer alphabets. ArXiv e-prints , 2017

    2017

  9. [17]

    Jiang and K

    S. Jiang and K. G. Larsen. A faster external memory priority q ueue with decreasekeys. In Proc. SODA, pages 1331–1343, 2019

    2019

  10. [18]

    K¨ arkk¨ ainen, D

    J. K¨ arkk¨ ainen, D. Kempa, and S. J. Puglisi. Lightweight Lempel-Ziv parsing. In Proc. SEA, volume 7933 of LNCS, pages 139–150, 2013

    2013

  11. [19]

    J. C. Kieffer and E. Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Information Theory , 46(3):737–754, 2000

    2000

  12. [20]

    D. E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwi se Tricks & Tech- niques; Binary Decision Diagrams . Addison-Wesley, 12th edition, 2009

    2009

  13. [21]

    N. J. Larsson and A. Moffat. Offline dictionary-based compress ion. In Proc. DCC, pages 296–305, 1999

    1999

  14. [22]

    Z. Li, J. Li, and H. Huo. Optimal in-place suffix sorting. In Proc. SPIRE, volume 11147 of LNCS, pages 268–284, 2018

    2018

  15. [23]

    Lohrey, S

    M. Lohrey, S. Maneth, and R. Mennicke. XML tree structure c ompression using repair. Inf. Syst. , 38(8):1150–1167, 2013. 16

    2013

  16. [24]

    Masaki and T

    T. Masaki and T. Kida. Online grammar transformation based on Re-Pair algorithm. In Proc. DCC, pages 349–358, 2016

    2016

  17. [25]

    Navarro and L

    G. Navarro and L. M. S. Russo. Re-Pair achieves high-order en tropy. In Proc. DCC, page 537, 2008

    2008

  18. [26]

    Ochoa and G

    C. Ochoa and G. Navarro. RePair and all irreducible grammars ar e upper bounded by high-order empirical entropy. IEEE Trans. Information Theory , 65(5):3160–3164, 2019

    2019

  19. [27]

    Sakai, T

    K. Sakai, T. Ohno, K. Goto, Y. Takabatake, T. I, and H. Sakam oto. RePair in compressed space and time. In Proc. DCC, pages 518–527, 2019

    2019

  20. [28]

    Sekine, H

    K. Sekine, H. Sasakawa, S. Yoshida, and T. Kida. Adaptive dictio nary sharing method for Re-Pair algorithm. In Proc. DCC, page 425, 2014

    2014

  21. [29]

    S. Simic. Jensen’s inequality and new entropy bounds. Appl. Math. Lett. , 22(8):1262–1265, 2009

    2009

  22. [30]

    Tabei, H

    Y. Tabei, H. Saigo, Y. Yamanishi, and S. J. Puglisi. Scalable partial least squares regression on grammar-compressed data matrices. In Proc. SIGKDD, pages 1875–1884, 2016

    2016

  23. [31]

    S. Vigna. Broadword implementation of rank/select queries. In Proc. WEA, volume 5038 of LNCS, pages 154–168, 2008

    2008

  24. [32]

    J. W. J. Williams. Algorithm 232 - heapsort. Communications of the ACM , 7(6):347–348, 1964

    1964

  25. [33]

    Yoshida and T

    S. Yoshida and T. Kida. Effective variable-length-to-fixed-leng th coding via a Re-Pair algorithm. In Proc. DCC, page 532, 2013

    2013

  26. [34]

    Ziv and A

    J. Ziv and A. Lempel. A universal algorithm for sequential data c ompression. IEEE Trans. Infor- mation Theory, 23(3):337–343, 1977. 17

    1977

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.