Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
复制标题
同步字符串：小字母表上的高效确定性构造
DOI：
10.1137/1.9781611975482.132
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wu, Ke
中科院分区：
文献类型：
--
作者：
Cheng, Kuan;Haeupler, Bernhard;Li, Xin;Shahrasbi, Amirbehshad;Wu, Ke
最近Haeupler和Shahrasbi [1]在研究用于纠正插入和删除错误的码（insdel码）时引入了同步串。同步字符串是字符串中符号索引的编码，并且与适当的解码算法一起，它可以将插入和删除错误转换为标准符号擦除和损坏。这将构造insdel码的问题简化为构造标准纠错码的问题，这更容易理解。除此之外，同步字符串在其他应用中也很有用，例如同步序列和交互式编码方案。对于所有这样的应用，同步串都希望在尽可能小的字母表上，因为较大的字母表大小对应于添加的更多冗余信息。Haeupler和Shahrasbi [1]表明，对于任何参数ε> 0，任意长度的同步串存在于其大小仅取决于ε的字母表上。具体地说，[1]得到了O（ε−4）的字母表大小，这留下了一个悬而未决的问题，即这样的字母表的最小大小在Ω（ε−1）和O（ε−4）之间。在这项工作中，我们通过提供改进的Ω（ε−3/2）下界和O（ε−2）上界来部分弥合这一差距。此外，我们还提供了快速显式构造的同步字符串在小alphabets.Further，沿着线以前的工作类似的组合对象，我们研究了极值问题的最小可能的字母表的大小，同步字符串可以存在一些常数ε< 1。我们证明了在长度为4的字母表上可以构造ε-同步串，而在二进制字母表上不存在这样的串。这将极端问题减少到是否在三进制字母表上存在同步字符串。
Synchronization strings are recently introduced by Haeupler and Shahrasbi [1] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm it can transform insertion and deletion errors into standard symbol erasures and corruptions. This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood. Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes. For all such applications, synchronization strings are desired to be over alphabets that are as small as possible, since a larger alphabet size corresponds to more redundant information added.Haeupler and Shahrasbi [1] showed that for any parameterε> 0, synchronization strings of arbitrary length exist over an alphabet whose size depends only onε. Specifically, [1] obtained an alphabet size ofO(ε−4), which left an open question on where the minimal size of such alphabets lies between Ω(ε−1) andO(ε−4). In this work, we partially bridge this gap by providing an improved lower bound of Ω (ε−3/2), and an improved upper bound ofO(ε−2). We also provide fast explicit constructions of synchronization strings over small alphabets.Further, along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constantε< 1. We show that one can construct ε-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.