论文摘要
随着互联网的发展和普及，海量信息的处理和新的应用需求，对于串匹配这个计算机领域中一个基本的而又是重要的问题，提出了新的挑战。串匹配问题在Internet网络信息搜索、信息过滤、生物信息学、网络入侵检测、网络远程教育、电子商务等领域具有广泛的应用。关于串匹配的问题很早就有相关的研究，提出了许多单模式匹配算法和多模式匹配算法。人们逐渐发现在实际应用中根据实际需要进行串匹配的研究具有重要的应用价值。因此，研究高效、快速的字符串匹配算法具有重要的理论价值和实际意义。应该说，本文所提出的连续厂位匹配规则是从精确串匹配规则中演变和发展而来的。这种演变思想的来源是，作者通过查阅医学领域以及计算机领域中关于免疫学、人工免疫系统和免疫算法的相关资料，从中了解到免疫系统已经应用到计算机领域来解决许多难题，并得到了满意的效果。但在这其中将免疫系统中的连续r位匹配规则应用到字符串匹配这个问题上的先例并不多。然而，作者却发现该免疫匹配规则有很多良好特性，如果能够将其应用到我们所讨论的串匹配问题上，那么将会得到比较好的效果。例如，其分布性、并行性的特点，如果应用到串匹配的问题上，那么当数据量剧增的时候，运行时间急剧下降的问题将会得到解决。在人类的免疫系统中，抗体的种类大概有106个，然而到目前为止，人们所发现的病毒性抗原的种类大概有1016个，那么我们的肌体为什么能够在如此庞大的病毒性抗原面前还能安然无恙呢?这里面，抗原与抗体的不完全匹配起着非常重要的作用。连续r位匹配规则正是从免疫系统中抗原与抗体不完全匹配性引出的，所以应用其特点来解决串匹配问题也是值得研究的。作者正是基于以上的一些想法，开始了本论文的撰写工作。首先，本文简单的介绍了一下免疫学的一些基本知识以及免疫匹配规则，给出了本文所应用的生物学基础。其次，通过对KMP算法的分析，向其中引入了连续r位匹配规则因子，这样就可以通过预先控制匹配阈值r的大小来满足我们所需要的模式串与文本串相匹配的程度，从而得到我们满意的答案。最后，作者通过实际搭建机群的经验，给出了搭建Cluster机群环境的详细步骤，并且在该系统下运行了并行串匹配程序。通过实验结果分析，达到了预先设计的效果。在本文的总结部分作者提出了一些有待解决的问题，例如，如何再进一步的改善并行机群的通讯时间问题，以及通过与医学领域专家合作，设计出类似于免疫系统能够同一时间应对来自外界不同种的病毒性抗原的侵扰，而每个问题又可以并行来执行。这些都值得我们在今后的工作中进行研究。