第一篇近似串匹配基础 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