Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
Abstract
A k-substring edit in a sequence first deletes a substring of length at most k, and then inserts a sequence of length at most k at the same position. A code that can correct a k-substring edit is called a k-substring edit code. In this paper, we develop a new localization method and use it to construct a q-ary k-substring edit correcting code with log n+8loglog n+o(loglog n) bits of redundancy for any fixed q≥2 and k≥1, where n is the code length. For the binary alphabet, this improves upon the redundancy log n+16kloglog n+o(loglog n) obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy log n+Oq,k(1), which is optimal up to an additive constant. As corollaries, for all fixed q≥2 and 1≤ t≤ T, we obtain q-ary (≤ t)-burst-deletion correcting codes and (t,T)-localized deletion correcting codes with redundancies log n+Oq,t(1) and log n+Oq,T(1), respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For (≤ t)-burst-deletion correction with t≥2, such redundancy had previously been achieved only for q=t=2 by Levenshtein in 1967.
Related
- Polynomially larger deletion codes by linear hashing of substring counts
- Order-Optimal Systematic Permutation Codes for Correcting t Deletions
- Four New Single-Error-Correcting Binary Codes
- On Optimal Encodings and Systematicity in Function-Correcting Codes
- Optimal single-track Gray codes from Gray-ordered necklaces
BibTeX
@misc{ye2026substring,
title = {{Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes}},
author = {Zuo Ye and Gennian Ge},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05696},
eprint = {2610.05696},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05696},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
AU - Zuo Ye
AU - Gennian Ge
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05696
UR - https://arxiv.org/abs/2610.05696
AB - A k-substring edit in a sequence first deletes a substring of length at most k, and then inserts a sequence of length at most k at the same position. A code that can correct a k-substring edit is called a k-substring edit code. In this paper, we develop a new localization method and use it to construct a q-ary k-substring edit correcting code with log n+8loglog n+o(loglog n) bits of redundancy for any fixed q≥2 and k≥1, where n is the code length. For the binary alphabet, this improves upon the redundancy log n+16kloglog n+o(loglog n) obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy log n+O_q,k(1), which is optimal up to an additive constant. As corollaries, for all fixed q≥2 and 1≤ t≤ T, we obtain q-ary (≤ t)-burst-deletion correcting codes and (t,T)-localized deletion correcting codes with redundancies log n+O_q,t(1) and log n+O_q,T(1), respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For (≤ t)-burst-deletion correction with t≥2, such redundancy had previously been achieved only for q=t=2 by Levenshtein in 1967.
ER -