Scholarlink

The worst-case additive sensitivity of a string repetitiveness measure c is defined to be the largest difference between c(w) and \(c(w')\) , where w is a string of length n and \(w'\) is a string that can be obtained by performing a single-character edit operation on w. We present \(O(\sqrt{n})\) upper bounds for the worst-case additive sensitivity of the smallest string attractor size \(\gamma \) and the smallest bidirectional scheme size \( b \) , which match the known lower bounds \(\varOmega (\sqrt{n})\) for \(\gamma \) and \( b \)  [Akagi et al. 2023]. Further, we present matching upper and lower bounds for the worst-case additive sensitivity of the Lempel-Ziv family - \(\varTheta (n^{\frac{2}{3}})\)  for LZSS and LZ-End, and \(\varTheta (n)\) for LZ78.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tight Additive Sensitivity on LZ-Style Compressors and String Attractors

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Yuto Fujie,
  • Hiroki Shibata,
  • Yuto Nakashima,
  • Shunsuke Inenaga

摘要

The worst-case additive sensitivity of a string repetitiveness measure c is defined to be the largest difference between c(w) and \(c(w')\) , where w is a string of length n and \(w'\) is a string that can be obtained by performing a single-character edit operation on w. We present \(O(\sqrt{n})\) upper bounds for the worst-case additive sensitivity of the smallest string attractor size \(\gamma \) and the smallest bidirectional scheme size \( b \) , which match the known lower bounds \(\varOmega (\sqrt{n})\) for \(\gamma \) and \( b \)  [Akagi et al. 2023]. Further, we present matching upper and lower bounds for the worst-case additive sensitivity of the Lempel-Ziv family - \(\varTheta (n^{\frac{2}{3}})\)  for LZSS and LZ-End, and \(\varTheta (n)\) for LZ78.