| 摘要: |
| 提出串的快速连续弱哈希(fast continuous weak Hash,简称FCWH),并研究它在理论和工程上的应用.首先提出FCWH 的概念,从代数结构角度统一规划该类哈希的构造框架;然后对哈希冲突概率进行理论分析和实验数据分析,推广并加强了Rabin 的相关工作;最后,通过推广串匹配的Karp-Rabin 算法,应用FCWH 解决顺序抽取公共子串问题(sequential extraction of common substrings,简称SECS),并据此设计快速同步协议X-Sync 来解决当今宽带网络和云计算环境下文档多版本内容的实时备份检索. |
| 关键词: 快速连续弱哈希(FCWH) 串匹配 顺序抽取公共子串(SECS) 快速同步(X-Sync) 有限群 有限环 有限域 |
| DOI：10.3724/SP.J.1001.2011.03867 |
| 分类号: |
| 基金项目: |
|
| Fast Continuous Weak Hashes in Strings and Its Applications |
|
XU Ze-Ming1,2, HOU Zi-Feng1,3
|
|
1.Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100190, China;2.Graduate University, The Chinese Academy of Sciences, Beijing 100049, China;3.Lenovo Corporate R&D, Beijing 100085, China
|
| 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. |
| Key words: fast continuous weak Hash (FCWH) string-matching sequential extraction of common substrings (SECS) express synchronization (X-Sync) finite group finite ring finite field |
