一种基于后缀数组的近似模式匹配的过滤算法

为了提高在海量的信息中进行多重复模式查找算法的效率,提出了算法Epattern_searcher.该算法运用过滤算法的思想而设计,同时又采用能节省空间占用的后缀数组来实现,从而提高了算法的运行速度.针对英文小说中高频词的查找问题,对算法进行了实验测试,得到此算法的时间复杂度为O(d+g)/(g)· n2· |σ|-q的实验结果.     

一种Byte查找第K个元素的算法研究

查找第K个元素的问题在计算机查找技术中占有十分重要的地位，这个问题的最直接解法是先将序列排序，从而能得到第K个元素，最少需O(nlogn)次比较，即时间复杂度为O(nlogn)．比较好的方法是采用分治策略解决该同题，但其最坏时间复杂度为O(n^2)，平均时间复杂度为O(2n)．本文提出一种Byte解决第K个元素问题的算法，该算法的平均时间复杂度为O(n n／255)，优于以前对该问题的求解方法，而且该算法可以适用于由整数、浮点数、无符号整型数、双精度数和字符型数构成的超大数集．     

一种快速单模式准确匹配算法

引入连续跳跃查找文本的思想,提出了一种新的单模式精确匹配算法,其最优条件下的时间复杂度为O[n/(m 1)],新算法的平均时间复杂度分析表明其具有优越的查找性能,对比实验结果显示,新算法的性能优于目前所见的同类算法,特别是在模式较短的情况下,优势更为明显,这一特点非常适合于自然语言文本的检索。     

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

拉格朗日插值多项式的一种并行算法

提出在机群系统并行环境下的构造拉格朗日插值多项式的一种并行算法.该算法以n个节点(x0,y0),(x1,y1),…,(xn-1,yn-1)的拉格朗日插值多项式公式为基础.当处理机数量为n2时,它的时间复杂度为3log(n) O(1);当处理机数量为p2(p相似文献   

数据结构中排序方法的研究

排序是数据处理领域中最常用的一种运算。排序的目的之一是方便查找。对于一个顺序存储的线性表,若不经过排序而查找,则时间复杂度为O（n）,若在排序的基础上进行二分查找,则时间复杂度可提高到O（logn）,效果是相当显著的。     

Loewner矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×n阶Loewner矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn) O(n2)。     

Loewner型方程组极小范数最小二乘解的快速算法

通过构造特殊分块矩阵及其三角分解给出了求秩为n 的m×n阶Loewner型矩阵为系数阵的线性方程组极小范数最小二乘解的快速算法, 该算法的计算复杂度为O(mn)+O(n²), 而一般方法的计算复杂度为O(mn²)+O(n³) .     

Cauchy型矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×n Cauchy型矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn) O(n2).     

快速Gabor滤波器在指纹纹理分析中的应用

为了提高指纹识别速度,在分析了Gabor滤波器实部特征的基础上简化了求二维卷积的运算,从而改进了Gabor滤波器算法,实验表明该改进算法使运算的复杂度由O(n2)降至O(n).