| 摘要 | 第1-5页 |
| ABSTRACT | 第5-7页 |
| 目录 | 第7-12页 |
| 第一章 引言 | 第12-17页 |
| ·串匹配技术研究的目的和意义 | 第12-15页 |
| ·串匹配技术的广泛应用 | 第12-13页 |
| ·串匹配技术面临的新挑战 | 第13-15页 |
| ·本文的研究内容与安排 | 第15-17页 |
| 第二章 串匹配算法的研究现状 | 第17-30页 |
| ·串匹配的定义 | 第17-18页 |
| ·精确串匹配算法的研究现状 | 第18-25页 |
| ·基于前缀的算法[KMP，AC] | 第18-20页 |
| ·基于后缀的算法[BM，Horspool，Wu-Manber] | 第20-21页 |
| ·基于因子的算法[BDM，BOM] | 第21-22页 |
| ·位并行算法[Shift-AND，Shift-OR，BNDM] | 第22-23页 |
| ·近年来的进展 | 第23-24页 |
| ·精确串匹配算法的时间复杂度下界 | 第24-25页 |
| ·动态串匹配算法的研究现状 | 第25-30页 |
| 第三章 串匹配算法性能分析 | 第30-38页 |
| ·串匹配算法的性能瓶颈 | 第30-31页 |
| ·影响串匹配算法性能的因素 | 第31-32页 |
| ·从算法角度改进的可能性 | 第32-35页 |
| ·从空间角度改进的可能性 | 第35-38页 |
| 第四章 基于存储压缩的串匹配算法 | 第38-57页 |
| ·算法的主要思想 | 第38-39页 |
| ·双数组Trie结构 | 第39页 |
| ·算法的设计和实现 | 第39-44页 |
| ·构造剪枝的Suffix Trie | 第40-41页 |
| ·构造双数组Trie | 第41-43页 |
| ·搜索过程 | 第43-44页 |
| ·空间复杂度分析 | 第44-46页 |
| ·实验 | 第46-52页 |
| ·实验环境和数据 | 第46-47页 |
| ·匹配速度比较 | 第47-49页 |
| ·存储空间比较 | 第49-50页 |
| ·平均跳跃距离比较 | 第50-51页 |
| ·二级cache miss次数比较 | 第51-52页 |
| ·本章小结 | 第52-57页 |
| 第五章 串匹配算法的内存布局优化 | 第57-63页 |
| ·问题的提出 | 第57页 |
| ·问题的形式化 | 第57-58页 |
| ·问题的求解 | 第58-60页 |
| ·内存布局优化的过程 | 第60页 |
| ·实验 | 第60-61页 |
| ·实验环境和数据 | 第60-61页 |
| ·实验结果及分析 | 第61页 |
| ·本章小结 | 第61-63页 |
| 第六章 动态串匹配算法 | 第63-72页 |
| ·经典算法在动态匹配上的局限性 | 第63页 |
| ·经典算法在动态匹配上的扩展 | 第63-67页 |
| ·可增删关键词的Advanced AC算法 | 第63-65页 |
| ·可增删关键词的Wu-Manber算法 | 第65页 |
| ·可增删关键词的SBOM算法 | 第65-67页 |
| ·实验 | 第67-72页 |
| ·实验环境和数据 | 第67页 |
| ·批量增加关键词时间代价比较 | 第67-68页 |
| ·匹配速度比较 | 第68-72页 |
| 第七章 通用串匹配算法库 | 第72-75页 |
| ·通用串匹配算法库的框架 | 第72-73页 |
| ·通用串匹配算法库的API接口 | 第73页 |
| ·通用串匹配算法库的功能特点 | 第73-75页 |
| 第八章 总结与展望 | 第75-77页 |
| 参考文献 | 第77-81页 |
| 致谢 | 第81-82页 |
| 作者简历 | 第82页 |