带有换位操作的近似串匹配算法及其并行实现

摘要

该文的主要研究内容与贡献是：对带有换位操作的近似串匹配问题进行了讨论,提出了一个基于过滤思想的快速的串行算法.理论分析表明,在误差率α（α=k/m）比较小的情况下,该串行算法的时间性能较好,其平均时间复杂度为0（kn+m）,其中,n和m分别是文本串和模式串的长度,k是近似匹配允许的最大误差数.该文还给出了上述串行过滤算法在PRAM模型和分布式存储模型上的并行化,并行化的算法使用p个处理器,平均时间复杂度为0（kn/p+km）.我们还在分布式存储的并行计算机曙光-2000上实现了我们的并行化算法,实验结果表明,并行化算法在分布式存储的并行计算机系统上的并行性能良好.

目录

文摘

英文文摘

第一章近似串匹配问题和近似串匹配算法

1.1近似串匹配问题的研究背景和研究意义

1.2近似串匹配问题描述

1.3近似串匹配问题的相关概念

1.4一般近似串匹配问题的串行算法

1.4.1最平凡的动态规划算法

1.4.2 Ukkonen的动态规划算法

第二章带有换位操作的近似串匹配问题的过滤算法

2.1概述

2.2问题描述

2.3带有换位操作的近似串匹配问题的动态规划算法

2.4带有换位操作的近似串匹配问题的过滤算法

2.4.1算法的基本原理

2.4.2算法描述

2.4.3算法分析

2.5实验结果与分析

2.5.1实验中的几个问题

2.5.2实验结果及分析

2.6小结

第三章并行计算机系统与并行算法

3.1并行计算机系统

3.1.1并行计算机系统的发展

3.1.2并行计算机系统的分类

3.2并行算法

3.2.1并行算法的定义及基本设计技巧

3.2.2并行算法的评价

第四章带有换位操作的近似串匹配过滤算法的并行化及其实现

4.1带有换位操作的近似串匹配过滤算法的并行化设计

4.1.1带有换位操作的近似串匹匹配过滤算法在PRAM模型上的并行化

4.1.2带有换位操作的近似串匹配问题基于分布式存储模型的并行化过滤第法

4.2带有换位操作的近似串匹配问题的并行化过滤算法在曙光-2000上的实现

4.2.1超级并行计算机系统曙光-2000介绍

4.2.2编程环境简介

4.2.3并行化过滤算法在曙光-2000上的实现

4.3小结

第五章结束语

5.1总结

5.2 进一步的工作

参考文献

致谢