郭嘉祥、陈鑫等NeurIPS 2025：基于Levenshtein距离深度嵌入的高效4-元编辑错误纠错码
针对DNA存储等新兴存储技术中出现的插入、删除与替换（编辑）类信道错误，现有纠错码在短码长场景下的码率较低，限制了分段纠错策略的整体效率。
近日，天津国家应用数学中心郭嘉祥、陈鑫等开发了一种“基于Levenshtein距离深度嵌入的高效4-元编辑错误纠错码：DoDo-Code”，大幅提高了短码长场景下的编辑错误纠错码码率。相关成果被机器学习顶级会议NeurIPS 2025接收，文章题目是：DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel。
作者首先改进了前期工作，采用了一系列深度学习技术来构建Levenshtein距离的嵌入空间。该方法的核心是通过截断泊松负对数似然（truncated PNLL）损失训练孪生神经网络（Siamese Neural Network）模型（如图1所示）。通过该模型，原始序列被映射为嵌入向量，其向量之间的平方欧氏距离可有效近似序列间的Levenshtein距离。此外，通过使用一个最终的批量归一化（Batch Normalization）层，这些嵌入向量的集合在统计上近似服从多元正态分布。
进一步，作者利用嵌入向量分布能够保持原始序列距离特性的优势，提出了一种超越传统组合编码设计的新范式。该方法以深度Levenshtein嵌入空间为低复杂度代理空间，通过其向量的概率密度来估计原始序列的邻居密度。在此基础上，作者设计了一种贪心搜索算法来构建码本（如图2所示）：在每次迭代中，选择概率密度最低的嵌入向量所对应的序列作为码字，并将其及邻近的Levenshtein球从候选集中移除。通过此迭代过程，最终得到符合有界距离解码器要求的高密度码本。
最后，作者利用深度嵌入空间距离计算复杂度低，且其欧氏距离度量与成熟的近邻搜索算法高度兼容的优势，提出了一种基于K-d树的快速纠错算法（如图3所示）。该算法在嵌入空间中将对损坏序列的纠错转化为高效的近邻查询操作，从而将解码的平均计算复杂度降低为与码字长度同阶的O(n)。
对深度嵌入空间的可视化分析（如图4所示）表明：这项研究提出的搜索策略倾向于优先选择分布边缘低密度区域的嵌入向量作为码字。与此同时，可视化结果也表明传统VT码的设计存在优化空间，其码本之外仍存在大量与任何码字距离均大于2的“孤立序列”，未能实现对整个序列空间的完全覆盖。
而在与现有最优的组合编码方案进行比较时（如图5所示），DoDo-Code在短码长场景下的码率优势十分显著。此外，其码率曲线与理想冗余log 3n + log log n的理论曲线高度重合，表明DoDo-Code的码率性能可能已达到了近似最优的水平。
作者介绍
郭嘉祥、陈鑫，天津大学应用数学中心副教授、天津大学合成生物技术全国重点实验室成员。
