柔性字符串匹配

第1章导言

1.1本书的目的和侧重点

1.2概况

1.3基本概念

1.3.1位并行和位运算

1.3.2带标记的有根树和trie

1.3.3自动机

1.3.4复杂度表示法

第2章字符串匹配

2.1基本概念

2.2基于前缀搜索的方法

2.2.1Knuth-Morris-Pratt算法的思想

2.2.2Shift-And/Shift-Or算法

2.3基于后缀搜索的方法

2.3.1Boyer-Moore算法的思想

2.3.2Horspool算法

2.4基于子串搜索的方法

2.4.1BDM算法的思想

2.4.2BNDM算法

2.4.3BOM算法

2.5实验图

2.6其他算法和参考文献

第3章多字符串匹配

3.1基本概念

3.2基于前缀搜索的方法

3.2.1MultipleShift-And算法

3.2.2基本的Aho-Corasick算法

3.2.3高级的Aho-Corasick算法

3.3基于后缀搜索的方法

3.3.1Commentz-Walter算法的思想

3.3.2SetHorspool算法

3.3.3Wu-Manber算法

3.4基于子串搜索的方法

3.4.1MultipleBNDM算法

3.4.2SBDM算法的思想

3.4.3SBOM算法

3.5实验图

3.6其他算法和文献

第4章扩展字符串匹配

4.1基本概念

4.2字符组

4.2.1模式串中的字符组

4.2.2文本中的字符组

4.3限长空位

4.3.1Shift-And算法扩展

4.3.2BNDM算法扩展76

4.4可选字符

4.5通配符和重复字符

4.5.1Shift-And算法扩展

4.5.2BNDM算法扩展

4.6多模式串搜索

4.7其他算法和参考文献

第5章正则表达式匹配

5.1基本概念

5.2构造NFA

5.2.1Thompson自动机

5.2.2Glushkov自动机

5.3搜索正则表达式的经典方法

5.3.1Thompson的NFA模拟

5.3.2使用确定自动机

5.3.3混合方法

5.4位并行算法

5.4.1位并行Thompson

5.4.2位并行Glushkov

5.5过滤方法

5.5.1多字符串匹配方法

5.5.2Gnu的基于必要因子的启发式方法

5.5.3基于BNDM的方法

5.6实验结果

5.7其他算法与参考资料

5.8构造解析树

第6章近似匹配

6.1基本概念

6.2动态规划算法

6.2.1编辑距离的计算

6.2.2在文本中搜索

6.2.3平均情况下的改进

6.2.4其他基于动态规划的算法

6.3基于自动机的算法

6.4位并行算法

6.4.1并行化NFA

6.4.2并行化动态规划矩阵

6.5文本快速过滤算法

6.5.1k+1分片算法

6.5.2近似BNDM算法

6.5.3其他过滤算法

6.6多模式串近似搜索

6.6.1仅允许一个错误的散列算法

6.6.2多模式串的k+1分片算法

6.6.3重叠自动机算法

6.7扩展字符串和正则表达式的近似搜索

6.7.1基于动态规划的方法

6.7.2Four-Russians方法

6.7.3位并行方法

6.8实验图

6.9其他算法和参考文献

第7章总结

7.1软件资源

7.1.1GnuGrep

7.1.2Wu和Manber的Agrep

7.1.3Navarro的Nrgrep

7.1.4Mehldau和Myers的Anrep

7.1.5计算生物学方面的资料

7.2其他书籍

7.2.1串匹配方面

7.2.2计算生物学方面

7.3其他资源

7.3.1期刊

7.3.2会议

7.3.3在线资源

7.4相关主题

7.4.1索引

7.4.2压缩文本中的搜索

7.4.3重复和循环

7.4.4二维和多维的模式匹配

7.4.5树模式匹配

7.4.6序列比较

7.4.7特异子串检测

参考文献

索引