串的快速连续弱哈希及其应用

摘要

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