串的快速连续弱哈希及其应用
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


Fast Continuous Weak Hashes in Strings and Its Applications
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    提出串的快速连续弱哈希(fast continuous weak Hash,简称FCWH),并研究它在理论和工程上的应用.首先提出FCWH 的概念,从代数结构角度统一规划该类哈希的构造框架;然后对哈希冲突概率进行理论分析和实验数据分析,推广并加强了Rabin 的相关工作;最后,通过推广串匹配的Karp-Rabin 算法,应用FCWH 解决顺序抽取公共子串问题(sequential extraction of common substrings,简称SECS),并据此设计快速同步协议X-Sync 来解决当今宽带网络和云计算环境下文档多版本内容的实时备份检索.

    Abstract:

    In this paper, the fast continuous weak Hash (FCWH) in strings is proposed and its theoretic and practical applications are investigated. First, FCWH is conceptualized and a uniform construction framework for FCWH is formulized from an algebraic viewpoint. Secondly, the theoretical and experimental collision probabilities of FCWH are analyzed, and the related work by Michael O. Rabin is generalized and strengthened. Finally, by generalizing the Karp-Rabin algorithm for string-matching problem, FCWH is applied to solve the problem of sequential extraction of common substrings (SECS), and, based on SECS, the express synchronization (X-Sync) protocol is designed to address the issue of real-time backup and the retrieval of multiple versions of a given document in the current environment of broadband communication network and cloud computing.

    参考文献
    相似文献
    引证文献
引用本文

徐泽明,侯紫峰.串的快速连续弱哈希及其应用.软件学报,2011,22(3):353-365

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-01-31
  • 最后修改日期:2010-04-28
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号