论文标题
编码单个编辑的序列重建
Coding for Sequence Reconstruction for Single Edits
论文作者
论文摘要
Levenshtein在2001年引入的序列重建问题考虑了一种通信方案，其中发件人从某些代码簿中传输代码字，并且接收器获得了代码字的多个嘈杂的读数。公共设置假定代码簿是整个空间，问题是确定重建传输代码字所需的不同读数的最小数量。 在现代存储设备的动机上，我们研究了问题的变体，其中噪声读取$ n $的数量是固定的。具体来说，我们设计了重建代码，该代码从$ n $ distions嘈杂的读取中重建代码字。我们专注于引入单个编辑错误（即单个替换，插入或删除）及其变体的频道，并针对所有$ n $的值设计重建代码。特别是，对于单个编辑的情况，我们表明，随着噪声读取的数量增加，可以优雅地减少所需的冗余钻头数量，从$ \ log n+o（1）$（1）$（1）$（1）$ \ log \ log \ log \ log n+o（1）$，然后再到$ o（1）$，其中$ n $表示编码的长度。我们还表明，某些重建代码的冗余在最佳之内。
The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads $N$ is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from $N$ distinct noisy reads. We focus on channels that introduce single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of $N$. In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant bits required can be gracefully reduced from $\log n+O(1)$ to $\log \log n+O(1)$, and then to $O(1)$, where $n$ denotes the length of a codeword. We also show that the redundancy of certain reconstruction codes is within one bit of optimality.
