{"id":"51c41418-d196-4126-98b9-f8ef83a126be","arxiv_id":"2509.03265","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Run-length encoded dictionary matching can be solved in O((runs in patterns + runs in text) log log(pattern length) + occurrences) expected time and O(runs in patterns) space.","lead":"The authors give the first near-linear-time algorithm for finding every dictionary pattern inside a run-length encoded text without decompressing either input. The method is optimal within a log-log factor, and the new compressed automaton and reporting index are reusable tools for repetitive data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Automaton transitions use exact run-length matching, so text runs longer than the pattern's corresponding run cause missed occurrences; a simple counterexample breaks Theorem 1.","rationale":"The reader identified Lemma 3 (the compact-trie transformation) as the weakest assumption, but the more load-bearing problem is in the query algorithm's transition rule. Section 5 Step 2 and Section 6 Step 2 match text runs to trie edges by exact run label α^y, with no provision for text runs longer than the pattern's corresponding run. This causes the automaton state to fall back to the root whenever the current text run is longer than the matching edge, losing the longest-suffix invariant. The counterexample P={a^3 b}, S=a^4 b is minimal and directly falsifies the claimed correctness of Lemma 7 and Theorem 1. The paper's own treatment of single-run patterns (Section 5, 'Dealing with Single Run Patterns') shows that occurrences ending inside a text run are meant to be supported, but the main automaton does not support the analogous partial-run matches needed to maintain state for multi-run patterns. The correctness proof in Section 5 only considers the case where the longest suffix su is formed by appending the entire run α^y to a previous state; it omits the case where su is a strict prefix of the text run (e.g., a^3 inside a^4). The full algorithm's predecessor structure is on Zv (first-run length of nodes), not on the edge run length y, so it cannot recover the missing transition. This is a concrete, reproducible flaw rather than a gap in a case analysis. I recommend REJECT because the central claim is not established by the described algorithm; a corrected transition rule may be possible, but the manuscript as written is incorrect.","tokens_in":17003,"tokens_out":31147,"duration_ms":270276,"concrete_test":"Trace the Section 6 algorithm on the RLE inputs P = {(a,3),(b,1)} and S = {(a,4),(b,1)}. After processing the run (a,4), the predecessor lookup DG[a^4] is queried from the root group; since the root has no outgoing edge labeled a^4, the state stays root. The subsequent run (b,1) also stays at root, so no occurrence is reported. The actual occurrence at position 1 is missed. A minimal implementation that follows the paper's Step 2 literally will confirm this; if the implementation instead queries a predecessor on the run length z ≤ y and transitions to the longest such edge, the counterexample is resolved.","verdict_should_be":"REJECT","load_bearing_attack":"The central query algorithm in Section 5 (Step 2) and Section 6 (Step 2) only follows an edge when the text run label α^y matches an edge label exactly. It never takes the longest edge label α^z with z ≤ y. Consider P = {a^3 b} (RLE: (a,3)(b,1)) and S = a^4 b (RLE: (a,4)(b,1)). The true occurrence is at starting position 1. Process run a^4: Step 1 uses i_v = -1 (state is root), and Step 2 finds no edge labeled a^4 from root, so the state remains root. Process run b^1: again the state is root, i_v = -1, and no occurrence is reported. The invariant 'sv is the longest suffix of S′' is violated after the first run, because the longest suffix of a^4 that is a prefix of a pattern is a^3, but the state is root. The correctness proof in Section 5 fails exactly in the case where the suffix is a proper prefix of the text run (sw = ε, su ≠ ε), which the proof does not handle. This is not a matter of a terse case analysis; the described transition rule is incorrect for any text run longer than the corresponding pattern run, including the first run of a pattern. The truncate-match reporting in Step 1 cannot compensate because it relies on the state's i_v, which is lost when the state is wrong.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies compressed dictionary matching for run-length encoded (RLE) strings, aiming to report all occurrences of a pattern set P in a text S without decompressing either string. It proposes an algorithm based on a run-length encoded trie (TRLE) that simulates the Aho-Corasick automaton one run at a time, together with a new \"truncate match reporting\" data structure. The main claimed result, Theorem 1, is an O((m̄+n̄) log log m + occ) expected-time and O(m̄)-space algorithm, with a deterministic variant in Theorem 2. The paper also develops compressed sorting of RLE strings and a reduction to colored ancestor threshold reporting.","tokens_in":17275,"tokens_out":16107,"duration_ms":149652,"significance":"If correct, the result would be the first non-trivial algorithm for compressed dictionary matching on run-length encoded strings, and the proposed TRLE representation and truncate match reporting techniques could be of independent interest. The paper demonstrates technical sophistication in combining known data structures (perfect hashing, y-fast tries, path minima, level ancestors, first color ancestor) into a compressed AC automaton. However, the central query transition is incorrect: it does not handle text runs that are longer than the corresponding pattern run, a case that arises in ordinary string matching. Since the counterexample below invalidates the main theorems, the claimed results are not established.","major_comments":[{"comment":"The transition rule only follows an edge when the current text run label α^y exactly equals an edge label in the dictionary D_v (or in the group dictionary D_G). In ordinary run-length matching, a pattern run α^x should be allowed to match a text run α^y when x ≤ y, with the occurrence ending inside the text run. Consider P = {a^3 b} and S = a^4 b. The occurrence at position 1 is reported by the uncompressed Aho-Corasick algorithm, but the proposed algorithm processes run a^4 from the root: since a^4 is not an edge label from the root, the state remains the root; then run b^1 is processed, again with no edge, and no occurrence is reported. The correctness proof's induction fails exactly when the longest suffix of S'α^y is a proper prefix of α^y, because the proof writes the suffix as s_{u'} α^y, which is impossible when the suffix ends inside the run. The truncate match reporting step cannot compensate because it queries with i_v, which is already wrong when the state is root. This counterexample also invalidates Theorem 2, since the deterministic algorithm uses the same transition rule.","section":"Section 5, Step 2 (and Section 6, Step 2)"},{"comment":"The same issue appears in the full algorithm. The correctness proof again assumes that the longest suffix of S'α^y decomposes as s_{u'} α^y, requiring the suffix to include the full text run α^y. When the text run is longer than every available pattern run prefix, the correct automaton state should be a node whose string is a proper prefix of α^y (e.g., a^3 when processing a^4), but the algorithm never considers such a node because it only takes edges labeled exactly α^y. Consequently, the invariant that s_v is the longest suffix of S' is violated after the first run of the counterexample, and the induction step in the proof of Section 6 breaks for the same reason as in Section 5.","section":"Section 6, Step 2 and correctness proof"}],"minor_comments":[{"comment":"The paper defines Z_v as the length of the first run of s_v, but never defines Z_v for the root node, whose string is the empty string. The query 'if D_G[α^y] has a predecessor u to Z_v' requires a value for the root; if the intended convention is Z_root = 0, it should be stated explicitly.","section":"Section 6, Step 2"},{"comment":"The notation n and m is used inconsistently: the abstract uses m and n for the total uncompressed lengths and \\bar{m}, \\bar{n} for the number of runs, but Lemma 7 states 'consisting of m and n runs' while also referring to 'a string S of length n'. This overloading makes the time bounds ambiguous and should be corrected throughout.","section":"Abstract and Section 5, Lemma 7"},{"comment":"The transformation from the compact trie of run-pair strings to the compact trie of uncompressed strings is described only for two adjacent children in the loop. The case of three or more children sharing the same first run character is not fully spelled out; a more detailed case analysis or a worked example would improve clarity, since Corollary 1 and Lemma 4 depend on this transformation.","section":"Section 3, Lemma 3"},{"comment":"References [33] and [34] appear to be the same paper (both are listed as 'Approximating LZ77 via small-space multiple-pattern matching' by Fischer et al. in ESA 2015); one duplicate should be removed.","section":"References"}],"recommendation":"reject","confidential_remarks":"The correctness counterexample in the major comments is decisive: the main algorithm misses the occurrence of a^3 b in a^4 b, which is a standard instance of the problem. This is not a presentation issue but a fundamental flaw in the transition rule, and it invalidates both Theorem 1 and Theorem 2. The reader's report missed this issue; the skeptic's example is valid. I therefore recommend rejection. If the authors can repair the transition to handle partial-run matching (e.g., by taking the longest edge label α^z with z ≤ y and tracking leftover run material), the paper might be re-submitted with a corrected algorithm, but that would require substantial new machinery."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a nice toolbox—RLE sorting, truncate match reporting, grouped failure links—but the main algorithm as written is incorrect. The transition rule in both Section 5 and Section 6 only follows an edge when the text run length equals the edge label length. It has no case for a text run longer than the matching edge, and the correctness proof assumes the matched suffix ends exactly at the end of the current text run.\n\nCounterexample: P = {a^3b}, S = a^4b. The occurrence at position 1 is missed. After processing run a^4 from root, the algorithm finds no edge labeled a^4 and stays at root; processing b^1 then has iv = -1. The correct state after a^4 is a^3, the longest suffix of a^4 that is a prefix of a pattern. The proof's line \"either sw = epsilon or alpha^y in D_p(w)\" fails because the suffix here is a proper prefix of the text run, so its last run has length 3, not 4. This is not a presentation gap; it is load-bearing.\n\nWhat is genuinely good: the compressed sorting of RLE strings, the reduction of truncate match reporting to colored ancestor threshold reporting, and the grouping of nodes by first-run length with predecessor search are all interesting ideas. The deterministic alphabet reduction is also a nice contribution. The proofs for the supporting lemmas are mostly careful. Lemma 3 is terse and the root case in Section 6 is underdefined, but those are minor next to the transition problem.\n\nMy guess is the flaw can be repaired by reworking Step 2 to find the longest edge label alpha^z with z <= y and then continuing within the same run (possibly via failure links), but that needs new machinery and a fresh analysis. As written, Theorem 1 is false. I would not accept this version. I would still send it out rather than desk-reject, because the problem is natural and the techniques are substantial; a referee might help determine whether the fix is feasible within the stated bounds.","headline":"Nice techniques, but the central transition rule misses occurrences when text runs are longer than pattern edges; the main theorem is false as written.","tokens_in":17798,"tokens_out":9575,"would_cite":false,"duration_ms":90904,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that dictionary matching on run-length encoded strings can report all pattern occurrences in time near-linear in the number of runs, using space proportional to the patterns' runs.","keywords":["dictionary matching","run-length encoding","Aho-Corasick automaton","compressed pattern matching","compact trie","truncate match reporting","colored ancestor threshold reporting","predecessor search"],"falsifier":"Build a pattern set where several children of one trie node share the same first run character and a shorter child edge has a nonempty continuation, run the paper's transformation, and compare the resulting compact trie with the trie built directly from the uncompressed strings; any mismatch in node depths, edge labels, or child order falsifies the central claim. A looser empirical falsifier is a timing test on inputs with very long runs: if the algorithm's total time ever scales with the uncompressed length rather than with $\\overline{m}+\\overline{n}$ plus occurrences, the claimed bound fails.","tokens_in":16830,"feed_emoji":"🔍","tokens_out":9729,"duration_ms":80197,"temperature":0.7,"pith_summary":"Dictionary matching asks for every occurrence of any pattern from a set in a text. When both patterns and text contain long runs of identical characters, run-length encoding makes the input much smaller than the uncompressed strings, and the question is whether matching can be solved in time tied to that compressed size. The paper answers yes: from the run-length encodings alone, all occurrences can be reported in $O((\\overline{m}+\\overline{n})\\log\\log m+\\mathrm{occ})$ expected time and $O(\\overline{m})$ space, where $\\overline{m}$ and $\\overline{n}$ are the run counts of the patterns and text and $\\mathrm{occ}$ is the number of matches. This is the first non-trivial algorithm for compressed dictionary matching on run-length encoded strings, and since reading the input is unavoidable the time bound is optimal within a $\\log\\log m$ factor. The construction compresses the classic Aho-Corasick automaton so that the text is processed one run at a time, with a new truncate-match reporting data structure handling occurrences that end inside a run.","feed_headline":"RLE dictionary search now near-linear in number of runs","feed_subtitle":"First non-trivial algorithm matches all dictionary patterns in near-linear time without decompressing.","key_machinery":"The load-bearing object is the run-length encoded trie $T_{\\mathrm{RLE}}$, the trie over the pattern set in which every maximal run $\\alpha^x$ is compressed to a single edge label. The paper simulates the Aho-Corasick automaton on this trie by redefining failure links to skip to the longest suffix with at least one fewer run, grouping nodes that share a suffix except for the length of their first run, and giving each group a predecessor dictionary keyed by first-run length. Occurrences ending inside the current run of the text are delegated to the truncate match reporting problem, which the paper reduces to colored ancestor threshold reporting: given a node, a color, and a weight threshold, report all ancestors carrying that color with weight at most the threshold. The whole construction depends on a new reduction that sorts run-length encoded strings by sorting their run-pair encodings and then converts the compact trie of run-pair strings into the compact trie of the original strings in linear time.","core_discovery":"The central claim is Theorem 1: given the run-length encoding of a pattern set $\\mathcal{P}$ (with $\\overline{m}$ runs) and a text $S$ (with $\\overline{n}$ runs), dictionary matching can be solved in $O((\\overline{m}+\\overline{n})\\log\\log m+\\mathrm{occ})$ expected time and $O(\\overline{m})$ space. The paper achieves this by building the run-length encoded trie $T_{\\mathrm{RLE}}$ of the patterns, in which each run $\\alpha^x$ is one edge label, and simulating the Aho-Corasick automaton directly on this compressed trie. Failure links are redefined to point to suffixes with strictly fewer runs, nodes that differ only by the length of their first run are grouped and navigated with predecessor search, and occurrences ending inside the current text run are reported through the new truncate match reporting problem, reduced to colored ancestor threshold reporting on the compact trie of reversed truncated patterns. A deterministic counterpart (Theorem 2) reaches $O((\\overline{m}+\\overline{n})\\log\\log(\\overline{m}+\\overline{n})+\\mathrm{occ})$ time and $O(\\overline{n}+\\overline{m})$ space after reducing the alphabet by sorting the runs of both patterns and text.","pith_inferences":["Editorial extension: grouping RLE-trie nodes by suffix-and-first-run-length is a reusable compression idea that could be applied to other automaton-based string problems, such as multiple-pattern longest common prefix queries or streaming matching on highly repetitive text.","Editorial extension: the truncate match reporting primitive isolates the partial-run boundary where ordinary automaton states cannot represent the overlap, so it may transfer to matching with wildcards, gaps, or approximate matches inside a run.","Editorial extension: a natural empirical check is whether the $\\log\\log m$ predecessor term or the compact-trie transformation dominates in practice on highly repetitive corpora; the theory predicts both should scale with run counts, not uncompressed lengths."],"forward_implications":["Dictionary matching on run-length encoded text and patterns can be solved in time near-linear in the number of runs, so inputs with very long repeated-character runs no longer require work proportional to the uncompressed length.","The classic Aho-Corasick automaton can be simulated in $O(\\overline{m})$ space without materializing every pattern prefix, by grouping automaton states and using predecessor search.","Occurrences ending inside the last processed run are handled by the new truncate-match structure, which reduces that task to colored ancestor threshold reporting on a compact trie.","A deterministic variant achieves nearly the same bounds in worst-case time, at the cost of an alphabet-reduction sorting step that uses $O(\\overline{n})$ additional space.","Since any correct algorithm must read its input, the randomized time bound is optimal up to the $\\log\\log m$ factor."],"supporting_citations":[{"why":"The classic Aho-Corasick automaton that the paper compresses; its failure and output links define the matching behavior being simulated.","marker":"[1]"},{"why":"Supplies the expected-time string sorting used to sort the run-length encoded pattern set before compact-trie construction.","marker":"[14]"},{"why":"Supplies perfect hashing, giving the constant-time membership queries used in the dictionaries of the compressed trie.","marker":"[35]"},{"why":"Supplies the y-fast trie predecessor structure used to navigate grouped nodes and to support deterministic queries.","marker":"[48]"},{"why":"Supplies the deterministic linear-space integer sorting used in the deterministic toolbox.","marker":"[38]"},{"why":"Supplies the first color ancestor data structure used as the base for colored ancestor threshold reporting.","marker":"[44]"},{"why":"Supplies deterministic perfect hashing, enabling the deterministic predecessor structure used in Theorem 2.","marker":"[46]"},{"why":"Supplies the level-ancestor queries used inside the induced color trees of the colored ancestor threshold reporting structure.","marker":"[20]"}],"fun_headline_variants":["First near-linear RLE dictionary match","RLE dictionary search: near-linear at last","Near-linear dictionary matching on runs","Run-length encoded search hits near-linear","Compressed dictionary search now near-linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the linear-time transformation that turns the compact trie over run-pair encoded strings into the compact trie over the original strings. That transformation must correctly handle every configuration of children sharing the same first run character, especially a shorter child edge whose label continues; if a case is missed, the compressed preprocessing and the final time bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["First near-linear RLE dictionary match","RLE dictionary search: near-linear at last","Near-linear dictionary matching on runs","Run-length encoded search hits near-linear","Compressed dictionary search now near-linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000845,"raw_usage":{"total_tokens":3739,"prompt_tokens":1063,"completion_tokens":2676,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":679,"completion_tokens_details":{"reasoning_tokens":2614}},"tokens_in":679,"tokens_out":2676,"duration_ms":18375,"temperature":1.0,"reasoning_tokens":2614,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:35:16.226936+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a pattern set where several children of one trie node share the same first run character and a shorter child edge has a nonempty continuation, run the paper's transformation, and compare the resulting compact trie with the trie built directly from the uncompressed strings; any mismatch in node depths, edge labels, or child order falsifies the central claim. A looser empirical falsifier is a timing test on inputs with very long runs: if the algorithm's total time ever scales with the uncompressed length rather than with $\\overline{m}+\\overline{n}$ plus occurrences, the claimed bound fails.","supporting_citations":[{"cited_title":"Aho and Margaret J","cited_arxiv_id":null,"evidence_quote":"The classic Aho-Corasick automaton that the paper compresses; its failure and output links define the matching behavior being simulated."},{"cited_title":"A new efficient radix sort","cited_arxiv_id":null,"evidence_quote":"Supplies the expected-time string sorting used to sort the run-length encoded pattern set before compact-trie construction."},{"cited_title":"Fredman, J´ anos Koml´ os, and Endre Szemer´ edi","cited_arxiv_id":null,"evidence_quote":"Supplies perfect hashing, giving the constant-time membership queries used in the dictionaries of the compressed trie."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the y-fast trie predecessor structure used to navigate grouped nodes and to support deterministic queries."},{"cited_title":"Deterministic sorting in o( nloglogn) time and linear space","cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic linear-space integer sorting used in the deterministic toolbox."},{"cited_title":"Muthukrishnan and Martin M¨ uller","cited_arxiv_id":null,"evidence_quote":"Supplies the first color ancestor data structure used as the base for colored ancestor threshold reporting."},{"cited_title":"Constructing efficient dictionaries in close to sorting time","cited_arxiv_id":null,"evidence_quote":"Supplies deterministic perfect hashing, enabling the deterministic predecessor structure used in Theorem 2."},{"cited_title":"Finding level-ancestors in trees","cited_arxiv_id":null,"evidence_quote":"Supplies the level-ancestor queries used inside the induced color trees of the colored ancestor threshold reporting structure."}],"review_version":2}