基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

生物信息挖掘中LIS算法研究*

探讨了生物信息挖掘中ó模式子序列问题的一个特例,即最长递增子序列(LIS)问题。对于LIS问题,分别用LCS算法、动态规划、动态规划结合二分法进行求解,并分析了这三种算法的时间和空间复杂度,对其中两种算法进行了实现,验证了时间和空间复杂性理论分析的正确性,最后得出了一种高效的LIS算法。     

最长公共子序列问题的改进快速算法

现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<相似文献   

基于高效精确的最大公共子序列的视频片段匹配

为视频序列匹配提出一个高效精确的最大公共子序列（Efficient and Effective Longest Common Subsequence,EELCS）算法。首先,利用矢量量化（Vector Quantization,VQ）将多维最大公共子序列算法（Multi-dimensional LCS,MLCS）中元素对匹配过程中的实际距离的计算简化成比较操作,较原始的最大公共子序列匹配算法（Original LCS,OLCS）,该处理不仅可以继承MLCS的可应用到实际多维时序匹配问题中的优点,同时大大降低了匹配的复杂度;然后进一步区分待匹配序列中由于匹配子序列和未匹配子序列在时间轴上连续性而产生的差异;最后将该算法应用到视频片段的匹配中。实验结果表明,与具有代表性的基于时间规扭曲的最大公共子序列（Time-Warped LCS,T-WLCS）和连续最大公共子序列（Continuous LCS,CLCS）相比,该算法能较好地应用于视频序列的匹配。     

低复杂度序列高斯逼近MIMO检测算法

提出一种多入多出（MIMO）系统空间复用模式下的低复杂度序列高斯逼近（LC-SGA）算法。该算法把序列高斯逼近（SGA）算法在复数域进行路径搜索的问题近似为实数域的搜索问题,从而降低了计算复杂度。仿真结果表明,LC-SGA算法在相同搜索路径数的情况下,其误比特率（BER）性能与传统的SGA算法相当,且当搜索路径数较大时接近最大似然检测的性能。     

一种具有容错性的序列综合算法

线性递归序列的容错综合问题在流密码分析领域具有重要的理论分析与应用价值。利用伽罗华域上2个变元多项式??x,y?的齐次理想刻画齐次关键方程的解空间,通过齐次关键方程解决线性递归序列综合问题不但具有可行性,而且具有某些容错性质。为此,根据二元多项式齐次理想Gr?bner基算法,提出一种求解齐次关键方程的快速算法,并给出一个定理来论述算法实现序列综合的充分条件。通过实验仿真对该算法在不同的序列复杂度和误码率下的容错性能进行分析,结果表明,该算法的成功率与序列复杂度呈线性关系,在误码率为10–3的情况下,对于序列复杂度为65、序列长度为1 000的序列,成功率可达86.6%以上。     

基于多元时间序列的自适应贪婪高斯分段算法

现有多元时间序列分段算法中分段点的选择以及分段个数的确定往往需要分别独立完成,大大增加了算法的计算复杂度.为解决上述问题,提出一种基于多元时间序列的自适应贪婪高斯分段算法.该算法将多元时间序列各个分段所对应的数据解释为来自不同多元高斯分布的独立样本,进而将分段问题转化为协方差正则化的最大似然估计问题进行求解.为提高学习效率,采用贪婪搜寻方法使每个段的似然值最大化进而近似地找到最优分段点,并且在搜寻的过程中利用信息增益方法自适应地获取最优的分段个数,避免分段个数确定和分段点选择分别独立进行,从而减少计算的复杂度.基于多种领域的真实数据集实验结果表明,所提出方法的分段精度以及运行效率均优于传统方法,并且能够有效完成多元时间序列的异常检测任务.     

一般间隙近似无重叠模式匹配

具有间隙约束条件模式匹配问题是序列模式挖掘问题的基础与核心.无重叠模式匹配是其中的一种方法,当前研究是在间隙为正的精确模式匹配,为了进一步增加匹配的灵活性,本文探索了一般间隙近似无重叠模式匹配问题.本文提出一种有效的求解算法,该算法首先将问题转化为网树;然后为了有效地避免可行解丢失,提出近似监测机制以解决该问题;采用迭代搜索最左孩子策略的方式寻找无重叠出现;之后在网树上剪枝找到的无重叠出现,并迭代上述过程直至没有新的无重叠出现产生.最后本文理论分析了算法的空间复杂度和时间复杂度.大量实验结果验证了本文算法具有较好的求解质量及求解效率.     

周期为2n的二元序列k错2-adic复杂度算法

首先设计了一个计算周期为2^n的二元序列的2-adic复杂度综合算法．随后,以该算法为基础,给出了一个计算周期为2^n的二元序列的k错2-adic复杂度综合算法．使用这两个算法可以分别在n步内计算得到序列的2-adic复杂度上界以及k错2-adic复杂度上界．     

基于二分迭代SAX的时序相似性度量算法

时序降维是解决时间序列高维问题的关键技术。符号聚集近似表示(SAX表示法)作为一种时序降维技术,具有良好的维度约简能力与性能稳定的下界距离算法,但算法中分段数的选取需根据当前时序数据的特征而人为设定。针对这一问题,引入了滑动窗口算法与统计学方法,提出了基于二分迭代SAX的时序相似性度量算法。实验结果表明,该算法不仅解决了分段数设定困难的问题,而且降低了时序降维表示的复杂度,提高了SAX算法在多种时序数据上的分类准确性。     

An Efficient Systolic Algorithm for the Longest Common Subsequence Problem

A longest common subsequence (LCS) of two strings is a common subsequence of the two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, a fast linear systolic algorithm that improves on previous systolic algorithms for solving the LCS problem is presented. For two given strings of length m and n, where m n, the LLCS and an LCS can be found in m + 2n – 1 time steps. This algorithm achieves the tight lower bound of the time complexity under the situation where symbols are input sequentially to a linear array of n processors. The systolic algorithm can be modified to take only m + n steps on multicomputers by using the scatter operation.     

LCS approximation via embedding into locally non-repetitive strings

A classical measure of similarity between strings is the length of the longest common subsequence (LCS) between the two given strings. The search for efficient algorithms for finding the LCS has been going on for more than three decades. To date, all known algorithms may take quadratic time (shaved by logarithmic factors) to find large LCS. In this paper, the problem of approximating LCS is studied, while focusing on the hard inputs for this problem, namely, approximating LCS of near-linear size in strings over a relatively large alphabet (of size at least n^? for some constant ?>0, where n is the length of the string). We show that, any given string over a relatively large alphabet can be embedded into a locally non-repetitive string. This embedding has a negligible additive distortion for strings that are not too dissimilar in terms of the edit distance. We also show that LCS can be efficiently approximated in locally-non-repetitive strings. Our new method (the embedding together with the approximation algorithm) gives a strictly sub-quadratic time algorithm (i.e., of complexity O(n^2-?) for some constant ?) which can find common subsequences of linear (and near linear) size that cannot be detected efficiently by the existing tools.     

Parallel algorithms for the longest common subsequence problem

A subsequence of a given string is any string obtained by deleting none or some symbols from the given string. A longest common subsequence (LCS) of two strings is a common subsequence of both that is as long as any other common subsequences. The problem is to find the LCS of two given strings. The bound on the complexity of this problem under the decision tree model is known to be mn if the number of distinct symbols that can appear in strings is infinite, where m and n are the lengths of the two strings, respectively, and m⩽n. In this paper, we propose two parallel algorithms far this problem on the CREW-PRAM model. One takes O(log² m + log n) time with mn/log m processors, which is faster than all the existing algorithms on the same model. The other takes O(log² m log log m) time with mn/(log² m log log m) processors when log² m log log m > log n, or otherwise O(log n) time with mn/log n processors, which is optimal in the sense that the time×processors bound matches the complexity bound of the problem. Both algorithms exploit nice properties of the LCS problem that are discovered in this paper     

A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw.     

An improved algorithm for the longest common subsequence problem

The Longest Common Subsequence problem seeks a longest subsequence of every member of a given set of strings. It has applications, among others, in data compression, FPGA circuit minimization, and bioinformatics. The problem is NP-hard for more than two input strings, and the existing exact solutions are impractical for large input sizes. Therefore, several approximation and (meta) heuristic algorithms have been proposed which aim at finding good, but not necessarily optimal, solutions to the problem. In this paper, we propose a new algorithm based on the constructive beam search method. We have devised a novel heuristic, inspired by the probability theory, intended for domains where the input strings are assumed to be independent. Special data structures and dynamic programming methods are developed to reduce the time complexity of the algorithm. The proposed algorithm is compared with the state-of-the-art over several standard benchmarks including random and real biological sequences. Extensive experimental results show that the proposed algorithm outperforms the state-of-the-art by giving higher quality solutions with less computation time for most of the experimental cases.     

Approximate Matching of Run-Length Compressed Strings

We focus on the problem of approximate matching of strings that have been compressed using run-length encoding. Previous studies have concentrated on the problem of computing the longest common subsequence (LCS) between two strings of length m and n , compressed to m' and n' runs. We extend an existing algorithm for the LCS to the Levenshtein distance achieving O(m'n+n'm) complexity. Furthermore, we extend this algorithm to a weighted edit distance model, where the weights of the three basic edit operations can be chosen arbitrarily. This approach also gives an algorithm for approximate searching of a pattern of m letters (m' runs) in a text of n letters (n' runs) in O(mm'n') time. Then we propose improvements for a greedy algorithm for the LCS, and conjecture that the improved algorithm has O(m'n') expected case complexity. Experimental results are provided to support the conjecture.     

CIM algorithm for approximating three-dimensional polygonal curves

The polygonal approximation problem is a primary problem in computer graphics,pattern recognition,CAD/CAM,etc.In R^2,the cone intersection method(CIM) is one of the most efficient algorithms for approximating polygonal curves,With CIM Eu and Toussaint,by imposing an additional constraint and changing the given error criteria,resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion(PS-WMN)under L2 norm.In this paper,without any additional constraint and change of the error criteria,a CIM solution to the same problem with the line segment error criterion(LS-WMN)is presented,which is more frequently encountered than the PS-WMN is .Its time complexity is O(n^3),and the space complexity is O(n^2) .An approximation algorithm is also presented,which takes O(n^2) time and O(n) space.Results of some examples are given to illustrate the efficiency of these algorithms.     

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.     

A linear space algorithm for the LCS problem

Summary The LCS problem is to determine the longest common subsequence (LCS) of two strings. A new linear-space algorithm to solve the LCS problem is presented. The only other algorithm with linear-space complexity is by Hirschberg and has runtime complexity O(mn). Our algorithm, based on the divide and conquer technique, has runtime complexity O(n(m-p)), where p is the length of the LCS.