search

sisong / HDiffPatch

a C\C++ library and command-line tools for Diff & Patch between binary files or directories(folder); cross-platform; runs fast; create small delta/differential; support large files and limit memory requires when diff & patch.
Other
1.52k stars 280 forks source link

后缀数组构建算法 #384

Closed xiayuxixi closed 3 months ago

xiayuxixi commented 3 months ago

作者你好，想请问一下在HDiffPatch算法中，你对于旧文件的后缀数组构建用的哪一个算法哦？然后你对于相同的数据间的压缩逻辑是怎样的呀?

sisong commented 3 months ago

创建old数据的后缀数组用的是libdivsufsort；然后用new数据到old中去查询最长匹配，如果匹配成功，就用覆盖线[old位置,new位置,匹配长度]来表示，从而"压缩"了数据。

xiayuxixi commented 3 months ago

相当于就是用libdivsufsort构建一个旧文件的后缀数组的字典，然后新文件去进行匹配。那个最长匹配就是指的字典中二进制文件新旧相同的部分吗，每找到一个匹配就压缩一次，是这个逻辑吗？那那个最长匹配有没有字节的限制哦

sisong commented 3 months ago

是的，一次匹配就是一次可能的节省，代码里称为覆盖线。
覆盖线有最小长度限制，逻辑上没有最长限制。 但需要注意，覆盖线根据情况可能被延长（更好压缩）、分裂（可以控制patch时的最大变量类型）、合并（需要存储的数据更少）处理。

xiayuxixi commented 3 months ago

好滴，明白啦，学习差分算法的话，作者有没有推荐的资料呀

---原始邮件--- 发件人: @.> 发送时间: 2024年5月29日(周三) 晚上6:38 收件人: @.>; 抄送: @.**@.>; 主题: Re: [sisong/HDiffPatch] 后缀数组构建算法 (Issue #384)

是的，一次匹配就是一次可能的节省，代码里称为覆盖线。 覆盖线有最小长度限制，逻辑上没有最长限制。 但需要注意，覆盖线根据情况可能被延长（更好压缩）、分裂（可以控制patch时的最大变量类型）、合并（需要存储的数据更少）处理。

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.Message ID: @.***>

sisong commented 3 months ago

这得看你的目的，和你当前已经掌握的知识。
我也没有什么具体的资料，都是自己摸索或知道一个思路后然后按照自己的想法做一个自己的版本。