网树——一种新型数据结构及其应用

本书围绕网树结构这一新型数据结构进行介绍，该结构是一种多树根、多双亲的拓展树结构。本书应用该结构解决了若干模式匹配（串匹配）、序列模式挖掘、图论等科学前沿问题，并对模式匹配和序列模式挖掘研究发展进行了简要回顾。 本书主要内容包括：网树结构与树结构的区别与联系；对具有间隙约束模式匹配问题进行概述，在此基础上，采用网树结构及其变形结构对几种模式匹配问题进行求解；对关联规则挖掘和序列模式挖掘进行简要回顾，在此基础上，采用网树结构及其变形结构对无特殊条件和无重叠条件的间隙约束序列模式挖掘进行求解；采用网树结构对图中具有长度约束的路径数和优选不相交路径问题进行求解。 本书可作为高等院校计算机科学与技术及其相关专业研究生和高年级本科生教材，也可用作拓展青少年信息学奥林匹克竞赛活动训练的辅助读本，还可供对数据结构课程或数据挖掘、模式识别等相关研究方向感兴趣的研究人员和工程技术人员阅读参考。

第1章 网树结构
第2章 网树求解几种间隙约束模式匹配问题
2.1 间隙约束模式匹配
2.1.1 按照匹配的类型进行划分
2.1.2 按照出现的约束类型进行划分
2.1.3 按照间隙的类型进行划分
2.1.4 本节小结
2.2 无特殊条件下准确模式匹配问题
2.2.1 问题定义及分析
2.2.2 求解算法
2.2.3 实验结果及分析
2.2.4 本节小结
2.3 无特殊条件下近似模式匹配问题
2.3.1 问题定义及分析
2.3.2 单根网树及求解算法
2.3.3 实验结果及分析
2.3.4 本节小结
2.4 无特殊条件下一般间隙准确模式匹配问题
2.4.1 问题定义及分析
2.4.2 求解算法
2.4.3 实验结果及分析
2.4.4 本节小结
2.5 一次性条件下模式匹配问题
2.5.1 问题定义及分析
2.5.2 求解算法
2.5.3 实验结果及分析
2.5.4 本节小结
2.6 无重叠条件下模式匹配问题
2.6.1 问题定义及计算复杂度分析
2.6.2 求解算法
2.6.3 实验结果及分析
2.6.4 本节小结
第3章 网树求解几种间隙约束的序列模式挖掘问题
3.1 关联规则挖掘问题
3.1.1 问题定义及分析
3.1.2 求解算法
3.1.3 存在的问题
3.1.4 本节小结
3.2 序列模式挖掘问题
3.2.1 问题定义及分析
3.2.2 求解算法
3.2.3 与关联规则挖掘的区别
3.2.4 存在的问题
3.2.5 本节小结
3.3 无特殊条件下序列模式挖掘问题
3.3.1 问题定义及分析
3.3.2 求解算法
3.3.3 实验结果及分析
3.3.4 本节小结
3.4 无重叠条件下序列模式挖掘问题
3.4.1 问题定义及分析
3.4.2 求解算法
3.4.3 实验结果及分析
3.4.4 本节小结
第4章 网树求解几种图问题
4.1 具有长度约束的路径数问题
4.1.1 求解算法及复杂度分析
4.1.2 网树求解最长路径问题
4.1.3 实验结果及分析
4.1.4 本节小结
4.2 具有长度约束的优选不相交路径问题
4.2.1 求解算法及复杂度分析
4.2.2 实验结果及分析
4.2.3 本节小结
第5章 网树研究总结与展望
5.1 网树研究总结
5.2 网树研究展望
5.2.1 模式匹配的展望研究
5.2.2 序列模式挖掘的展望研究
5.2.3 其他问题的展望研究
参考文献