分布式存储的并行串匹配算法的设计与分析

并行串匹配算法的研究大都集中在PRAM(parallel random access machine)模型上,其他更为实际的模型上的并行串匹配算法的研究相对要薄弱得多.该文采用将最优串行算法并行化的技术,利用模式串的周期性质,巧妙地将改进的KMP(Knuth-Morris-Pratt)算法并行化,提出了一个简便、高效且具有良好可扩放性的分布式串匹配算法,其计算复杂度为O(n/p+m),通信复杂度为O(ulogp相似文献   

无向图的边极大匹配并行算法及其应用*

在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.     

矩阵条件数及高斯算法平滑分析的进一步研究

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n³).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ²≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og₂(n)+3log₂(1/σ)+log₂log₂n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og₂n+3log₂(1/σ)+4√2+log₂n+log₂(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n²)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og₂n+3log₂(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.     

基于组合策略的单模式串精确匹配算法

以仅使用后缀有限自动机的RF算法作为参照对象,对采用组合策略的LDM、ILDM1、ILDM2等算法时间复杂度进行了比较研究。实验表明,LDM和ILDM1算法的时间复杂度要差于RF算法,即组合策略是失效的。实验还发现,ILDM2算法中把模式前缀长度R是否超过模式长度m的1/ 2作为正向有限自动机暂停匹配的条件,对于中小字母表的模式串的匹配也不是最佳策略。     

双向选择排序算法

为丰富O(n²)阶排序算法的种类,以更好地服务于教学科研和日常应用,提出了一种新的排序算法-双向选择排序算法.通过数学方法分析得知:该算法的时间复杂度为O(n²),空间复杂度为O(1).通过实验对比得知:在相同条件下,该算法的运行时间平均为冒泡排序的27%、简单选择排序的62%、直接插入排序的88%.     

一种基于拓扑势的网络社区发现方法

从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n^3/γ)～O(n²),n为网络节点数,m为边数,2<γ<3为一个常数.     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

网格多处理机的一种改进的子网分配算法

子网分配问题是指识别并分配一个空闲的、满足指定大小要求的节点机.首先,提出了网格结构中一种新的具有O(N²_a·1og₂N_a)时间复杂度的空闲子网搜索算法,它优于现有的O(N³_a)时间复杂度的搜索算法.然后,用该算法对基于保留因子的最佳匹配类子网分配算法——RF(reservation factor)算法进行了改进,得到了     

串匹配算法中的自动机紧缩存储技术

自动机是串匹配算法中常用的数据结构,对自动机实现紧缩存储可以节省算法空间。总结常用自动机紧缩存储方法,分析其原理、时间效率、空间效率和优缺点,给出各种方法与数据稀疏性之间的关系。运用紧缩存储方法实现基本AC算法,对随机数据和真实数据的实验结果证明该算法有效。     

高性能正则表达式匹配算法评估

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%~89.9%;在匹配效率方面,与mDFA相比,XFA的匹配时间增加了38.9%~174.6%;XFA在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8倍时,mDFA的存储空间增长了64倍,而XFA的存储空间仅增加了16倍,匹配时间仅增加了61.3%。     

On building minimal automaton for subset matching queries

We address the problem of building an index for a set D of n strings, where each string location is a subset of some finite integer alphabet of size σ, so that we can answer efficiently if a given simple query string (where each string location is a single symbol) p occurs in the set. That is, we need to efficiently find a string d∈D such that p[i]∈d[i] for every i. We show how to build such index in O(nlogσ/Δ(σ)log(n)) average time, where Δ is the average size of the subsets. Our methods have applications e.g. in computational biology (haplotype inference) and music information retrieval.     

Approximate string matching with suffix automata

Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.     

自动机算法在文本不精确匹配中的应用

论文从实用的角度,着重研究了有限自动机算法在文本的不精确匹配中的应用,提出了一种用于中文精确匹配的自动机的构建思想,两种用于中文同音字匹配的自动机的构建思想,以及利用自动机的原理去除无用字符对文本匹配的干扰的方法。编程实现了上述三种自动机算法并对其作了测试,给出了三种算法各自的性能测试数据。     

网络入侵检测系统模式匹配算法研究

模式匹配算法是网络入侵检测中的关键所在,它直接影响到网络入侵检测系统的实时检测性能.引入4种模式匹配算法,分析其工作原理,通过实验对上述4种算法进行了性能测试.根据实验结果,得出了不同算法的应用范围,为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考.     

Efficient parameterized string matching

In parameterized string matching the pattern P matches a substring t of the text T if there exist a bijective mapping from the symbols of P to the symbols of t. We give simple and practical algorithms for finding all such pattern occurrences in sublinear time on average. The algorithms work for a single and multiple patterns.     

On Boyer-Moore automata

The notion of Boyer-Moore automaton was introduced by Knuth, Morris, and Pratt in their historical paper on fast pattern matching. It leads to an algorithm that requires more preprocessing but is more efficient than the original Boyer-Moore's algorithm. We formalize the notion of Boyer-Moore automaton and we give an efficient building algorithm. Also, bounds on the number of states are presented, and the concept of potential of a transition is introduced to improve the worst-and average-case behavior of these machines. We show that looking at the rightmost unknown character, as suggested by Knuthet al., is not necessarily optimal.R. A. Baeza-Yates gratefully acknowledges the support of Grant C-11001 from Fundación Andes, and C. Choffrut gratefully acknowledges the support of the PRC Mathématiques et Informatique.     

一种入侵检测系统的模式匹配算法*

提出了一种基于后缀树自动机的模式匹配算法,匹配中应用后缀启发机制进行启发跳跃,忽略不必要的比较。实验表明,该方法与传统模式匹配方法相比能有效地加快模式匹配的速度,提高入侵检测效率。