基于动态字典的增量更新算法

作者：陈志龙; 倪桂强; 姜劲松; 罗健欣; 严英姿

来源：解放军理工大学学报(自然科学版), 2015, 16(05): 426-432.

• 动态字典
• 增量更新
• 差异压缩

为减少软件更新中增量包的大小,提出了基于动态字典的增量更新算法DICDIFF。该算法使用后缀排序方法预处理新老版本文件,将预处理的结果以后缀数组和名次数组的形式存储为字典目录,基于该字典目录能够快速查找字典数据集与待编码数据之间的相同数据段。随着编码进度的推进,动态扩展字典数据集能够使用更多已知数据段用于构造待编码数据。通过选取多款软件的新旧版本作为实验样本,DICDIFF在平均情况下能够节省68.9%的网络流量,高于现有其他增量更新算法。实验结果表明,该算法能够进一步减少增量更新过程中的网络流量。

• 单位
  解放军理工大学; 中国人民解放军南京陆军指挥学院