摘要
Rabin指纹算法计算效率高、随机性好,可将数据更改对连续指纹序列的影响限制在局部范围内,广泛应用于重复数据检测领域。分析了Rabin指纹在有限域GF(2n)上的运算原理,得出滑动窗口移动时定长字符序列的数字指纹快速计算公式。用伪代码描述了Rabin指纹算法在重复数据检测中的应用,并用VC++语言进行了算法实现,在普通计算机上提取Word文档、程序源代码和BMP图像等三类文件作为测试数据集,测试结果表明算法是有效的。
Rabin fingerprint algorithm is widely used in the field of duplicate data detection with high computational efficiency and good randomness.When data changes affecting the continuous fingerprint sequence,the algorithm can limit the impact to lo cal area.After analyzing the Rabin fingerprint principle on galois field GF(2n),a fingerprint fast calculation formula for fixedlength character sequence is derived in the process of slide window moving.The application of Rabin fingerprint algorithm in du plicate data detection fields is described by pseudo code,and implemented by VC++ programing language.Experiment uses a da ta set that including three types of files(Word documents,source code,and BMP images) extraced from some ordinary computer,and the result shows that the algorithm is effective.
出处
《电脑知识与技术》
2013年第7X期4918-4920,4932,共4页
Computer Knowledge and Technology
基金
广东远程开放教育科研基金项目(YJ1333)
韶关市创新资金项目(201210)
韶关学院科研项目(201202)
关键词
存储系统
重复数据检测
Rabin指纹
基于内容分块
有限域
storage system
duplicated data detection
rabin fingerprint
content defined chunking
galois field
