摘要: 1．本文的创新点
随着网络和生物信息学的发展，对于串匹配技术提出了许多新的需求。尤其是在信息安全领域，此如何能够及时、准确、安全地在庞大的实时网络信息流中获得特定的信息成为研究的热点和重点，其中的挑战性问题就是针对大规模模式串的字符串匹配算法，其执行效率成为整个应用场景中性能瓶颈。通过对经典多模式串匹配算法的分析，基于对这类算法的特征分析，提出一种的新的并行多模式串匹配算法。主要的创新点有：
· 提出基于模式串分解的并行算法，其主要思想是先把模式串集合分解成多个子集，然后和对每个子集选择不同的经典串匹配算法，最好通过设计的调度算法把若干子集的匹配映射到并行多核体系结构上。论文证明了该最优分解和映射问题是NP-Hard问题，并设计了一种启发式算法以最小化并行程序的执行时间。
· 对最优分解的集合小于处理器核的个数情况，设计了一个动态规划算法求解最优分解，该算法的时间复杂度是O(qr²)，空间复杂度是O(qr)，其中r 是模式串的个数，q是处理器核的个数。
· 对最优分解的集合大于处理器核的个数情况，设计了另一个动态规划算法求解最优分级，算法的时间复杂度是O(r²)，空间复杂度是O(r)。
· 针对分解的集合与处理器核之间映射问题，设计了贪婪算法调度任务以获得负载平衡，该算法的时间复杂度是O(llogq+llogl)，空间复杂度是O(l)。 2．实现方法
· 结合作者以前的工作基础，利用分析总结出的经典多模式串匹配算法（AC、WM、SBOM）的特征，确定基于模式串划分算法的理论基础。
· 把并行多模式串匹配算法分解为两个组合子问题：模式串划分和匹配任务调度，证明该为题是NP-Hard问题。进一步设计启发式算法，根据划分最优集合的大小确定最优问题求解区间。
·  设计两类动态规划算法和一个贪婪算法，并证明算法的正确性。
·  基于以前实现的一种针对大规模模式串的快速匹配算法COM，实现上述的并行算法，在4核处理器进行了实验，性能提高约2倍。 3．结论及未来待解决的问题
本文提出了一种基于模式串集合分解的并行多模式串匹配算法，并在多核上得以实现。本研究工作的一个重要启示是合理利用现有的经典模式串匹配算法的特点，对其进行适当的组合以获得更好的性能。由于寻找最优组合是NP Hard问题，本文提出了一种多项式复杂度的启发式算法求最优解。 4．实用价值或应用前景
对于大规模的模式串，使用传统的多串匹配算法可以解决，但是在数量超过5000 的时候，它们的性能下降的都很显著，这已经不能满足实时的数据处理的需求。本文提出的并行算法是解决该问题潜在途径之一。