学位论文 > 优秀研究生学位论文题录展示

基于字符信息量法则的串匹配算法研究

作　者: 李国华
导　师: 昝红英
学　校: 郑州大学
专　业: 计算机系统结构
关键词: 字符特征字符信息量字符信息量法则字符串匹配模式串匹配
分类号: TP391.1
类　型: 硕士论文
年　份: 2012年
下　载: 37次
引　用: 0次
阅　读: 论文下载

内容摘要

字符串匹配问题是文本信息处理领域中的一门非常重要的课题。随着网络和信息技术高速发展,极度膨胀的信息量,使得对信息处理的性能和效率要求越来越高,在某种程度上,字符串匹配的效率甚至成为了人们准确获取自己所需信息的瓶颈。在科学领域(比如计算机科学、生物学、人口统计学、金融等)、自然界和社会生活中(比如单词频率、数字中首数字出现的频率等)很多的现象,被证实内在的很多特性都符合幂律分布的规律。幂律分布利用统计规律揭示了许多表面上看起来丝毫没有关联的事物之间的关系,而这种关系或称之为不平衡性。事实上,不平衡性的分布特点可以从另外一个角度帮助大家研究和理解事物本质。Zipf定律、Heaps定律、Benford定律等便是研究长尾分布的几种重要定律。本文以Zipf定律、Heaps定律、Benford定律为参照,首先研究英文单词词表中不同字符所蕴含的内在特性,并提出字符表征单词个数,即字符的信息量的概念,验证表明字符倒序排名与其信息量的分布也符合幂律分布,并据此提出字符信息量的法则。更进一步的,本文通过字符的信息量的不平衡性特点用于指导字符串匹配算法问题的研究。并经过实验得出,基于字符信息量的法则可以很快的加速字符串匹配的过程,提高字符串匹配算法的性能,结合字符信息量的法则,本文提出了基于字符信息量法则的字符串匹配算法的三个变种算法：SMCI-no-sort算法、SMCI-partial-sort、SMCI-all-sort算法。实验表明字符信息量的法则在字符串匹配问题上,可以加速模式串在文本串中的跳跃过程,从而提高字符串匹配的速度。具体来说,本文具有创新的研究成果主要体现在以下几点：1,定义了用字符来表征单词的概念和字符蕴含的信息量概念,通过实证,得到字符的排名倒数与字符蕴含的信息量同样符合幂律分布,进而提出字符信息量法则(Character’s Law).2,提出SMCI-no-sort算法；该算法思想是完全基于字符的倒排索引结构进行字符串的查找,通过字符分布的不平衡性,加速字符查找过程。该算法预处理过程只需建立倒排索引结构,而不涉及子串的排序操作,所以预处理时间消耗很低。3,提出SMCI-all-sort算法；该算法与SMCI-no-sort算法对应,在预处理阶段通过对所有列表进行排序,在搜索时,根据完全有序的列表,只需要进行二元搜索。4,提出SMCI-partial-sort算法；该算法充分利用了字符分布的不平衡性和不同字符所表征单词的信息量不同,选择部分列表进行排序,从而提升预处理阶段的性能和搜索阶段的效率。

全文目录

摘要  4-6
Abstract  6-10
图表目录  10-12
1 引言  12-15
  1.1 研究背景及意义  12-13
    1.1.1 研究背景及意义  12-13
    1.1.2 研究内容  13
  1.2 论文组织安排  13-15
2 字符串匹配相关研究  15-20
3 语言统计学定律  20-25
  3.1 Zipf定律  21-22
  3.2 Heaps定律  22-23
  3.3 Benford定律  23-25
4 字符信息量(Character's Law)法则  25-29
  4.1 字符信息量定义  25
  4.2 字符特征的统计规律  25-27
  4.3 字符信息量法则  27-29
5 基于字符信息量法则的串匹配算法  29-50
  5.1 搜索查询中的字符信息量法则  29-30
  5.2 基于信息量法则的串匹配算法  30-38
    5.2.1 SMCI-no-sort算法  31-32
    5.2.2 SMCI-all-sort  32-34
    5.2.3 SMCI-partial-sort算法  34-38
  5.3 SMCI算法示例  38-41
  5.4 实验及结果分析  41-50
6 总结与展望  50-51
参考文献  51-54
个人简历在学期间发表的学术论文及研究成果  54-55
致谢  55

基于字符信息量法则的串匹配算法研究

内容摘要

全文目录

相似论文