提出可逆字符串分解方法，高效压缩并揭示结构规律
Flashback: A Reversible Bilateral Run-Peeling Decomposition of Strings
- 从首尾交替剥离最长字符段，生成双向令牌对
- 仅需1+[r/2]个令牌，达到理论最低上限
- 适合研究字符串压缩与形式语言的学者
我们提出Flashback，一种可逆字符串分解方法，通过反复剥离带哨兵的输入字符串的首尾最大字符段，将每对记录为一个双向令牌。分解与重构均在O(n)时间和空间内完成。核心成果是运行配对定理：字符串的第一个运行段与最后一个配对，第二个与倒数第二配对，依此类推。这使得具有r个最大运行段的字符串恰好产生1+[r/2]个令牌，并达到任何合法双向剥皮方案的下限。由此定理可推出若干结构性质：不可再剥的核最多含两个符号；回文串当且仅当其运行长度编码对称且运行数为奇数；分解结果可被显式有限状态机刻画；改变任一运行长度仅重写一个内容令牌。
原文摘要 · Abstract (English)
We introduce Flashback, a reversible string decomposition that repeatedly peels the maximal leading and trailing character runs from a sentinel-wrapped input, recording each pair as one bilateral token. Decomposition and reconstruction both run in O(n) time and space. Our central result is a run-pairing theorem: Flashback is equivalent to pairing the first run of the string with the last, the second with the second-to-last, and so on. This gives an exact token count of 1+[r/2] for a string with r maximal runs, and matches a lower bound that holds for any admissible bilateral run-peeling scheme. From the run-pairing theorem the main structural properties follow as corollaries: the irreducible peeling kernel uses at most two symbols; palindromes are precisely the strings whose run-length encoding is symmetric with an odd number of runs; the image of the decomposition admits an explicit finite-state characterisation; and changing one run length rewrites exactly one content token.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。