 算法在字典与源文件间寻找匹配)
Zstandard contrib 中的编辑距离匹配器用 Myers O(ND) 算法在字典与源文件间寻找匹配【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo本篇聚焦 MongoDB 仓库内第三方 Zstandard 库的 contrib 实验组件——Edit Distance Match Findersrc/third_party/zstandard/zstd/contrib/match_finders/。它借鉴文件 diff 领域的编辑距离思想以 Myers O(ND) 算法在字典dictionary与源文件之间寻找最优/近最优匹配序列。读完后你将理解这一匹配器从动机、核心算法到启发式加速的完整设计以及作者最终将其留在 contrib 而非主线的原因。背景动机面向 patch 压缩 的匹配器该组件的 README 与头文件注释README.md、zstd_edist.h完整阐述了研究动机目标场景是软件包补丁patching最常见的例子是用新版本更新一个现有软件包。此时新旧版本之间的差异通常极小新文件的大部分内容与旧文件相同。技术表述两个文件之间的编辑距离将一个字节序列转换为另一个所需的最少修改次数相对于文件大小是很小的。核心算法来自 Eugene W. Myers 的经典论文An O(ND) Difference Algorithm and its VariationsAlgorithmica Vol. 1, 1986, pp. 251-266。这正是git diff等现代 diff 工具所采用的算法。启发式来源作者补充的加速启发式借鉴了 GNU diff、bsdiff、Xdelta 等文本/二进制 diff 实现。Zstandard 压缩本质上依赖在当前窗口/字典内找到可回溯匹配的序列sequence。这个实验把字典 vs 源文件这一对固定关系当作两个待 diff 的序列来求解属于一种离线、全局式的匹配发现方式与 zstd 主压缩器逐块滑动的匹配策略形成鲜明对比。对外 API 与 ZSTD_Sequence 语义组件仅暴露一个函数定义在 zstd_edist.hsize_t ZSTD_eDist_genSequences(ZSTD_Sequence* sequences, const void* dict, size_t dictSize, const void* src, size_t srcSize, int useHeuristics);参数与返回值语义参数含义dict/dictSize字典字节缓冲区对应旧版本/参考序列src/srcSize待压缩源文件缓冲区useHeuristics是否启用启发式。启用时得到近最优编辑脚本但速度大幅提升关闭时追求最优解可能极慢sequences输出缓冲区写入ZSTD_Sequence数组返回值找到的序列数量每个输出序列携带offset、litLength、matchLength三个字段——这正是 zstd 序列产生器如ZSTD_registerSequenceProducer外部匹配器接口所需的格式意味着该匹配器的产物可以直接喂给 zstd 的序列压缩路径。核心算法双向 Myers 对角线搜索 中间相遇实现主体是 zstd_edist.c 中的ZSTD_eDist_diagL81-L323。关键结构与常量如下L29-L75/* Just a sential for the entries of the diagonal matrix */ #define ZSTD_EDIST_DIAG_MAX (S32)(1 30) /* How large should a snake be to be considered a big snake. */ #define ZSTD_EDIST_SNAKE_THRESH 20 /* After how many iterations should we start to use the heuristic * based on big snakes */ #define ZSTD_EDIST_SNAKE_ITER_THRESH 200 /* After how many iterations should be just give up and take * the best available edit script for this round */ #define ZSTD_EDIST_EXPENSIVE_THRESH 1024 typedef struct { U32 dictIdx; U32 srcIdx; U32 matchLength; } ZSTD_eDist_match;算法工作流程双缓冲对角线ZSTD_eDist_state持有forwardDiag与backwardDiag两条S32数组。从 API 入口ZSTD_eDist_genSequencesL529-L558可以看到两块缓冲在一次连续分配中完成nbDiags dictSize srcSize 3随后偏移srcSize 1各自指向有效区这是典型的 Myers 算法对角线索引 ±srcSize 平移手法保证索引不越界。前向/后向交替推进主循环每轮先把前向对角线的[forwardMin, forwardMax]向外扩一格并更新forwardDiag[diag]存字典侧最大进度snake 展开即沿对角线连续比较dict[dictIdx] src[srcIdx]再对后向对角线做镜像操作。中间相遇判定odd变量依据(forwardMid - backwardMid) 1决定本轮由哪一侧检测相遇——当同一diag上backwardDiag[diag] forwardDiag[diag]时两条路径已接上取(dictIdx, srcIdx)为分割点通过ZSTD_eDist_partition回传dictMid/srcMid以及两半各自的useHeuristics标志递归终止。分治递归ZSTD_eDist_compareL334-L388先在低端和高端做廉价的首尾扫描——首尾逐字节相等直接记录长度为 1 的匹配并收缩区间剩余区间若两端相触则整段是插入/删除对压缩而言无匹配价值否则调用ZSTD_eDist_diag求中点再对上下两半递归。源码注释明确指出与多数 diff 算法不同这里只关心匹配matches不记录差异。值得注意的是每发现一个字节相等就调用ZSTD_eDist_insertMatch写入一条matchLength 1的记录最终匹配由后处理阶段合并得到见下文这是为了与 Myers 算法的逐字节语义保持一致。两道加速启发式当useHeuristics打开时主循环在常规相遇判定之后还有两级逃生通道L195-L321源码注释直言其效果是将总耗时从数分钟降到数秒代价是编辑脚本可能不再最优Big snake 启发式iterations 200且本轮出现过长度超过 20 的 snake 时触发前向侧遍历所有对角线用打分v (dictIdx - dictLow) * 2 - diagDiag衡量进度收益只有当v 12 * (iterations |diagDiag|)才视为值得分割命中后在分割点附近继续向后前向确认 20 字节连续相等即锁定中点并让上半部分继续用启发式highUseHeuristics 1。后向侧做完全镜像的处理打分v (dictHigh - dictIdx) * 2 diagDiag。直观含义如果某条对角线已经跑得比迭代代价多得多说明两侧在此处高度相似可以放心地提前切开不必等到严格相遇。太贵启发式iterations 1024时触发直接在前向/后向对角线集合中各选最靠里的点分别最大化/最小化dictIdx srcIdx比较哪一侧距离边界更近就从哪一侧切开。这是对 Myers 最坏情形两个序列差异巨大、D 很大的兜底保证分治递归能够持续推进而不会卡死在单轮超长迭代里。匹配合并与序列转换找到全部字节级匹配后还有两步后处理1) 合并连续匹配——ZSTD_eDist_combineMatchesL401-L438先用qsortZSTD_eDist_matchComp按srcIdx排序源码注释说明合并步骤依赖有序性同时承认qsort并非瓶颈未做优化线性扫描把首尾相接的匹配prev.srcIdx prev.matchLength cur.srcIdx且prev.dictIdx prev.matchLength cur.dictIdx合并为长匹配丢弃短于MINMATCH的匹配。MINMATCH由 zstd_internal.h 定义为 3即小于 3 字节的匹配对 zstd 编码没有意义zstd 序列中短匹配由字面量编码覆盖。2) 转换为 ZSTD_Sequence——ZSTD_eDist_convertMatchesToSequencesL440-L460核心换算逻辑U32 const litLength !i ? match.srcIdx : match.srcIdx - (matches[i - 1].srcIdx matches[i - 1].matchLength); U32 const offset (match.srcIdx dictSize) - match.dictIdx;litLength当前匹配起点与上一匹配终点之间的字面量长度首个匹配则为绝对起点偏移offset把字典视为接在源文件之前的虚拟窗口后源匹配位置回溯到字典匹配位置的距离——这正是 zstd 字典压缩中字典匹配的偏移表示方式。内存开销与测试辅助工具从ZSTD_eDist_genSequences的实现可以看到整体内存模型对角线缓冲2 * (dictSize srcSize 3) * sizeof(S32)即 O(dictSize srcSize)匹配缓冲srcSize * sizeof(ZSTD_eDist_match)最多每字节一条合并阶段临时再分配一份匹配缓冲。这也解释了为何它只适合字典与源文件都较小或规模可控的场景——内存与时间都线性依赖两个序列的总长。文件尾部还保留了几个静态辅助函数L462-L523从源码结构看属于实验/验证用途ZSTD_eDist_hamingDist等长序列的汉明距离ZSTD_eDist_levenshteinDist朴素递归版 Levenshtein 距离注释明确警告只用于快速测试不要跑 GB 级文件无记忆化指数级复杂度ZSTD_eDist_validateMatches断言校验每条合并后的匹配——索引不越界、且memcmp(dict dictIdx, src srcIdx, matchLength) 0即每条匹配在字典侧和源侧必须逐字节真实相等。实验结论为何停留在 contribREADME与头文件注释一致给出了作者的实验性结论这也是理解该组件定位的关键对目标场景大型相似文件失败仅用该匹配器时耗时约为 zstd 压缩级别 19 的5~10 倍而压缩结果通常反而大 2~3 倍唯一稳定胜出的场景用与源文件非常相似的同样小的字典压缩 10 KB的小文件时其压缩率可超过 zstd-19根本短板zstd-19 的核心优势之一是重叠匹配overlapping matches——一个匹配区域可以与前一匹配部分重叠从而表达更紧凑的序列而编辑距离匹配器基于无重叠的最小编辑脚本天然找不到任何重叠匹配作者因此将其保留在contrib目录作为将来若重新变得有趣时再探索的实验性代码。对读者的实用启示如果确有版本补丁/相似大文件类需求zstd 主线方案是配合ZSTD_compress_usingCDict/ 前缀prefix字典或外部序列产生器 API而非直接采用本组件本组件的价值更多在于其将 Myers 分治 snake 启发式落地到匹配发现问题上的参考实现。小结contrib/match_finders是一个自洽的小型算法实验室以 Myers O(ND) 双向对角线搜索为骨架用 big-snake 与太贵两级启发式控制最坏代价再用排序合并 MINMATCH 过滤 偏移换算把编辑脚本翻译成可直接喂给 zstd 的ZSTD_Sequence流。它完整展示了diff 算法思想 × 压缩匹配发现这一交叉方向的设计与取舍并诚实地记录了负向结论——这使其成为研究 zstd 匹配策略极限时一份少见的、有源码佐证的第一手材料。【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
