随着互联网的飞速发展,网络上的信息量呈现出爆炸式的增长,如何从大量信息中迅速有效地提取出所需信息成为一项重要的研究课题。高效的模式匹配算法能迅速检索出用户需要的重要信息。模式匹配问题是个古老而又经典的问题,模式P的相邻字符之间出现可变长度的通配符使的该问题更加复杂。带有通配符和长度约束的模式匹配问题PMWL (Pattern Matching with Wildcards and Length constraints)不仅具有重要的理论研究价值,而且在生物信息学、网络安全和信息检索中具有重要的实际应用价值。本文对带有可变长度通配符的模式匹配问题展开研究,主要研究内容有三个方面：(1)基于关键字符定位的模式匹配算法研究；(2)提出了一种文本分割算法,并与后缀树相结合,提高模式匹配算法的时间和空间效率；(3)对PMWL问题中匹配解的完备性问题进行研究,提出了一种新颖的数据结构CluTree,以及基于CluTree的检索算法,能进一步提高匹配解的完备性和时间效率。主要研究内容和创新如下：(1)基于关键字符定位的模式匹配算法研究；对于含有通配符和长度限制的模式匹配问题,模式中相邻字符间包含通配符使匹配问题更加复杂。当文本T的长度比较大,字符分布非常复杂时,目前的算法定位误差比较大。由于现有算法没有考虑待检索文本T分布的特点,没有考虑到模式P中子模式及各字符的不同作用,在一些不可能匹配的地方进行检索,消耗了检索时间,降低了检索效率。本文根据模式P中各字符在文本T中出现的差异及在模式P中的分布,提出一种模式P中字符重要性的评价机制,先计算出模式P的频率函数fr(PJ)和自频率函数fp(Pj),根据以上的计算结果找出模式P的KWp(k)函数,由KWP(k)函数找出了模式P的关键字符Pk。关键字符作为定位字符,然后借鉴SAIL的匹配思路,改进扫描表格的方式。当表格成功构建后,算法将得到一个匹配解。文本T扫描完毕后,算法返回所有的匹配解。(2)提出了一种文本分割算法,并与后缀树相结合,提高模式匹配算法的时间和空间效率；对大文本进行分而治之的模式匹配策略,有效地解决了大规模串匹配的性能瓶颈。如何进行正确的分割是该问题的核心部分。本文设计分割算法,从T中找出可以分割,且不影响匹配结果的点。借鉴SAIL的forward过程的思想,利用局部约束确定解的空间,排除所有不满足条件的位置。在具体实现过程中,算法逐个扫描初始分割点附近的点,若发现某个点与周围的点不可能构成一个匹配解时结束循环,返回当前扫描的位置,并将作为正确的分割位置。分割算法对大文本的检索效率有了很大提高。基于分割算法模式匹配算法能加快检索速度,因此也很好的提高了检索的时间。将分割算法与后缀树相结合的多后缀树检索算法能较大提高后缀树算法的空间效率。设计的算法可用于生物信息学领域中,进行DNA序列的匹配和蛋白质序列的识别,可以提高模式匹配的效率。(3)基于CluTree的PMWL问题匹配算法由于通配符的出现,PMWL问题中的检索将更加复杂,在不含通配符的简单模式匹配SPM (simple pattern matching)中不会有解的争议,一个待匹配文本中对于任意给定模式的解是确定的。而在PMWL问题中,一个匹配位置可能作为模式中子模式出现,也可能作为通配符的位置出现,这种匹配位置的多样性导致匹配结果的不确定性,更为复杂的是可能有多个侯选匹配串的位置相互嵌套,如何选择正确的匹配位置以确定最优解一直是个待解决的难题。多个嵌套模式中选定最优匹配位置,目前的算法在处理嵌套区域的纠缠态模式的匹配问题,都采用左优先的left-most策略。当模式比较复杂,这种相互嵌套纠缠的区域是最复杂的匹配区域,简单的左优先无法解决这类问题,必然会丢失匹配串。提出了一种基于CluTree结构的检索算法RBCT,对这样的嵌套区域建立一个多根的红黑树群CluTree,在模式的匹配过程中根据CluTree中各节点的共享度、相关度及混合信息熵来选择匹配的路径,并且运用动态剪枝技术来保证树群CluTree的动态更新和共享节点资源的释放,RBCT算法对CluTree中的节点进行遍历,最终得到优化的解。