《近似串匹配关键技术及实用算法》PDF下载

  • 购买积分:9 如何计算积分?
  • 作  者:孙德才,王晓霞著
  • 出 版 社:沈阳:东北大学出版社
  • 出版年份:2014
  • ISBN:9787551706032
  • 页数:191 页
图书介绍:随着因特网的发展和普及,信息已实现了全球的共享与交互,从信息的采集、传播和使用都变得非常便利。但巨大的信息量使得个人的接受能力严重超载,因此如何从这巨大的信息中迅速、准确地获取所需要的信息,一直是计算机科学研究中的基本问题。近似匹配是允许有一定误差的串匹配技术,它能从大文本库中快速地找出与查询相近的字符串。近似串匹配技术近似串匹配技术在众多领域都有广泛的应用,如生物信息学、文本检索、信号处理和模式识别等。本书主要介绍了近似串匹配的相关知识,主要包括近似串匹配的概念、分类和发展历程,过滤算法的基础知识和研究现状等,并详细地介绍了作者在索引结构和匹配算法等方面所做的研究工作和相关实验结果。最后对近似串匹配技术的下一步的研究方向进行了预期。

第一篇近似串匹配基础 3

第1章 绪论 3

1.1 研究意义 3

1.2 研究背景 4

1.3 本书结构及主要工作 5

第2章 近似串匹配技术概述 8

2.1 近似串匹配基础 8

2.2 近似串匹配的常用索引结构及研究现状 11

2.3 近似串匹配过滤算法 15

2.4 本章小结 20

第二篇近似串匹配索引技术 23

第3章 中文倒排索引及精确字符串匹配 23

3.1 引 言 23

3.2 中文编码 23

3.3 中文倒排索引 24

3.4 一种中文Bigram二级哈希索引及精确字符串匹配 29

3.5 实验分析 33

3.6 本章小结 37

第4章 倒排索引建立方法及优化技术 38

4.1 引 言 38

4.2 基于预测内存分配的倒排索引 39

4.3 实验分析 41

4.4 本章小结 43

第5章 索引压缩技术 44

5.1 引 言 44

5.2 索引压缩技术基础 44

5.3 中文索引分组压缩方法及实验分析 47

5.4 基于混合编码的q-gram索引压缩方法及实验分析 55

5.5 本章小结 66

第6章 支持多种子近似串匹配的单索引结构 68

6.1 引 言 68

6.2 任意连续种子地址集合计算 69

6.3 索引时空分析 73

6.4 实验分析 74

6.5 本章小结 78

第三篇近似串匹配过滤算法 81

第7章 基于q-gram命中特征的近似串全局匹配算法 81

7.1 引 言 81

7.2 q-gram命中特征提取 82

7.3 基于q-gram命中特征的近似串全局匹配算法 86

7.4 QHF算法的退化 91

7.5 QHF算法的时间复杂度和空间需求分析 92

7.6 实验结果与分析 93

7.7 本章小结 99

第8章 基于尾匹配q-gram的近似串全局匹配算法 101

8.1 引 言 101

8.2 新过滤特征提取 101

8.3 基于尾匹配q-gram的过滤算法 104

8.4 TMQ算法的时间复杂度和空间需求分析 108

8.5 实验分析 109

8.6 本章小结 112

第9章 基于对角线特征的近似串局部匹配算法 113

9.1 引 言 113

9.2 对角线特征提取 114

9.3 基于对角线特征的近似串局部匹配算法 116

9.4 LAADF算法的退化 121

9.5 LAADF算法的时间复杂度和空间需求分析 121

9.6 实验结果与分析 123

9.7 本章小结 128

第10章 基于二次过滤的近似串局部匹配算法 129

10.1 引 言 129

10.2 二次过滤特征提取 130

10.3 基于二次过滤的近似串局部匹配算法 134

10.4 TSF算法的退化 139

10.5 TSF算法的时间复杂度和空间需求分析 139

10.6 实验结果与分析 142

10.7 本章小结 147

第11章 基于连续匹配块的近似串局部匹配算法 148

11.1 引 言 148

11.2 连续匹配块特征提取 148

11.3 基于连续匹配块的近似串局部匹配算法 151

11.4 QFLA算法的退化和失效 156

11.5 QFLA算法的时间复杂度和空间需求分析 157

11.6 实验结果与分析 159

11.7 本章小结 166

总结及展望 167

一、工作总结 167

二、研究展望 170

参考文献 172