论文标题
所有距离的对数较大的删除代码
Logarithmically larger deletion codes of all distances
论文作者
论文摘要
两个二进制单词$ u，v \ in \ {0,1 \}^n $之间的删除距离是最小的$ k $，因此$ u $ and $ v $共享$ n-k $的常见子序列。如果每对$ c $中的每对不同单词的删除距离大于$ k $，则一套长度$ n $的二进制单词$ c $称为$ k $ demention代码。 1965年，Levenshtein发起了删除代码的研究，表明，对于$ k \ ge 1 $固定和$ n $，将$ k $ - demotion代码$ c \ subseteq \ subseteq \ {0,1 \}^n $最大尺寸的最大尺寸的$ \ leq o_k（2^n/n^k）$。我们通过证明存在至少$ω_k（2^n \ log n/n/n^{2k}）$的$ k $ deotion代码来对这些边界进行第一个渐近改进。我们的证明是灵感来自江式和瓦尔迪对古典吉尔伯特（Varshamov）边界的改进。我们还建立了几个相关的结果，这些结果涉及一对具有给定长度和删除距离的单词的最长常见子序列和最短的共同超股式。
The deletion distance between two binary words $u,v \in \{0,1\}^n$ is the smallest $k$ such that $u$ and $v$ share a common subsequence of length $n-k$. A set $C$ of binary words of length $n$ is called a $k$-deletion code if every pair of distinct words in $C$ has deletion distance greater than $k$. In 1965, Levenshtein initiated the study of deletion codes by showing that, for $k\ge 1$ fixed and $n$ going to infinity, a $k$-deletion code $C\subseteq \{0,1\}^n$ of maximum size satisfies $Ω_k(2^n/n^{2k}) \leq |C| \leq O_k( 2^n/n^k)$. We make the first asymptotic improvement to these bounds by showing that there exist $k$-deletion codes with size at least $Ω_k(2^n \log n/n^{2k})$. Our proof is inspired by Jiang and Vardy's improvement to the classical Gilbert--Varshamov bounds. We also establish several related results on the number of longest common subsequences and shortest common supersequences of a pair of words with given length and deletion distance.
