改进的LCS方法在测试脚本序列比对中的应用

在自动化测试中,需要对录制和回放过程中的请求序列进行解析和比对,帮助用户进行脚本的修正和完善。为了实现请求序列的比对,采用最长公共子序列(LCS)算法对录制和回放的序列进行比较,其核心思想是把序列对比转化成图论问题,通过二维矩阵寻路来找到最优的匹配方式。文中对算法的原理和实现做了详细描述,并对算法的性能进行测试和分析,最后将算法应用到软件脚本修改器中,验证算法在自动化测试实际应用中的效果。结果表明,LCS算法可以高效地对序列进行解析和比对,提高了自动化测试的效率。     

基于粒子视频的高密度人群主流运动检测

采用粒子视频流获得视频序列中的特征点运动轨迹,并对获得的运动轨迹进行提取,然后利用最长共同子序列LCS(Longest Common Subsequence)聚类轨迹,得到运动的主流方向。该算法可以有效检测实际场景中的主流运动方向。     

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

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

一种基于图的近重复视频子序列匹配算法

为了解决近重复视频检测中的效果和效率问题, 提出了一种基于图的近重复视频子序列匹配算法。将基于关键帧特征的相似性查询结果构建成匹配结果图, 进而将近重复视频检测转换成一个在匹配结果图中查找最长路径的问题。该算法有三个主要优势：a）它能在众多杂乱的匹配结果中找到最佳的匹配序列, 有效剔除了某些假“高相似度”匹配带来的噪声, 因而能在一定程度上弥补底层特征描述力的不足; b）由于它充分考虑和利用了视频序列的时序特性, 具有很高的近重复视频定位准确度; c）它能自动检测出匹配结果图中存在的多条离散路径, 从而能一次性检测出两段视频中可能存在多段近重复视频的情形。提出的算法不仅提高了检测的准确度, 而且提高了检测效率, 取得了良好的实践效果。     

一种新的二维碎片的轮廓匹配方法*

以往的轮廓匹配算法中所用的轮廓表示方法大多需要大量繁琐的计算,大大增加了算法的时间复杂度,为此提出一种新的轮廓特征表示方法,简化了此部分的计算。首先求出待匹配图像单像素宽的轮廓曲线上像素点的坐标序列,然后利用轮廓上各点和与其相差六个点的像素点之间的位置关系及行列坐标差的平方代数和对轮廓进行表示,得到两轮廓曲线的表示序列后;接着采用寻找两轮廓表示序列的最长公共子序列（LCS）的方法进行匹配,并在匹配过程中引入了“断点续配”的概念,有效提高了算法的容错性。实验证明所用的轮廓表示方法简单明了,计算量小,在提高算     

基于J2EE平台应用时序挖掘算法对纺织品出口风险预测的研究

贸易数据是按时间记录下的、不断更新中的海量数据。首先引入时间序列模式的概念,分析了时间序列的本质问题;其次改进了AprioriAll算法挖掘贸易序列数据库的有用序列模式;然后使用离散傅里叶变换子序列相似性查找的方法,将现有序列与挖掘到的感兴趣的序列模式进行子序列匹配,得到有用的知识;最后结合实际情况,合理搭建系统平台,将改进的算法应用在该平台之下得到满意的效果。     

基于傅立叶变换的一种时间序列相似搜索算法

该文提出了基于傅立叶变换的一种新的时间序列相似搜索算法。该算法利用高效的索引方法,达到快速的匹配,解决了多序列的子序列匹配问题。大量算例验证了该算法的通用性和有效性,它可以应用到求解各种时间序列相关的实际问题。     

基于图形表示的LCS问题

所谓的LCS（Longest Common Subsequence）问题,就是寻找生物序列的最长公共子序列。传统的算法都是基于字符串的比较。近几年不少学者给出了生物序列的图形表示,本文就利用DNA序列的一种二维图形表示采寻找最长公共子序列。     

求解最长循环公共子序列问题的两个算法

最长循环公共子序列（LCCS）是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列（LCS）。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在◢O（mn）◣时间复杂度下快速估算LCCS长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好。     

基于形状特征k-d树的多维时间序列相似搜索

多维时间序列是信息系统中一类重要的数据对象,相似搜索是其应用的一个核心.两个序列(子序列)相似度加以比较的常用方法是:将序列(子序列)转换成空间中的曲线,然后计算曲线间的欧几里德距离.这种方法的主要缺陷是它仅考虑了序列(子序列)间的整体距离关系,而不能体现它们自身的局部变化.针对此问题,提出了一种新的可应用于多维时间序列的快速相似搜索方法.该方法将序列(子序列)的局部变化特性与检索结构(k-d树)结合起来,使得在搜索k-d树的同时实现了序列(子序列)的局部变化匹配,从而极大地提高了查询效率和正确率.实验结果表明了算法的有效性.     

On the parameterized complexity of the repetition free longest common subsequence problem

Longest common subsequence is a widely used measure to compare strings, in particular in computational biology. Recently, several variants of the longest common subsequence have been introduced to tackle the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.     

A Coarse-Grained Parallel Algorithm for the All-Substrings Longest Common Subsequence Problem

Given two strings A and B of lengths n_a and n_b, respectively, the All-substrings Longest Common Subsequence (ALCS) problem obtains, for any substring B' of B, the length of the longest string that is a subsequence of both A and B'. The sequential algorithm for this problem takes O(n_a n_b) time and O(n_b) space. We present a parallel algorithm for the ALCS problem on the Coarse-Grained Multicomputer (BSP/CGM) model with p < √n_a processors, that takes O(n_a n_b/p) time, O(log p) communication rounds and O(n_b √n_a) space per processor. The proposed algorithm also solves the basic Longest Common Subsequence (LCS) problem that finds the longest string (and not only its length) that is a subsequence of both A and B. To our knowledge, this is the best BSP/CGM algorithm in the literature for the LCS and ALCS problems.     

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.     

基于FSA的DNA重复体频率统计算法

针对现有DNA重复体频率统计算法效率低、灵活性差等不足,基于字符串多模式匹配的有限状态自动机,构造DNA子序列比对自动机,利用KMP算法对自动机进行状态转移优化,由此提出一种高效的重复体频率统计算法。该算法通过对DNA数据库的线性扫描,得到每个DNA子序列在全局数据库中重叠与非重叠的重复体频率统计信息以及指定DNA序列集合的最长公共子序列信息。实验结果表明,该算法具有效率高、匹配精确、信息获取方式灵活、支持在线操作等优势。     

基于句子相似度的论文抄袭检测模型研究

提出一种基于句子相似度的论文抄袭检测模型。利用局部词频指纹算法对大规模文档进行快速检测,找出疑似抄袭文档。根据最长有序公共子序列算法计算句子间的相似度,并标注抄袭细节,给出抄袭依据。在标准中文数据集SOGOU-T上进行的实验表明,该模型具有较强的局部信息挖掘能力,在一定程度上克服了现有的论文抄袭检测算法精度不高的缺点。     

Multiscale video sequence matching for near-duplicate detection and retrieval

As one of key technologies in content-based near-duplicate detection and video retrieval, video sequence matching can be used to judge whether two videos exist duplicate or near-duplicate segments or not. Despite a lot of research efforts devoted in recent years, how to precisely and efficiently perform sequence matching among videos (which may be subject to complex audio-visual transformations) from a large-scale database still remains a pretty challenging task. To address this problem, this paper proposes a multiscale video sequence matching (MS-VSM) method, which can gradually detect and locate the similar segments between videos from coarse to fine scales. At the coarse scale, it makes use of the Maximum Weight Matching (MWM) algorithm to rapidly select several candidate reference videos from the database for a given query. Then for each candidate video, its most similar segment with respect to the given query is obtained at the middle scale by the Constrained Longest Ascending Matching Subsequence (CLAMS) algorithm, and then can be used to judge whether that candidate exists near-duplicate or not. If so, the precise locations of the near-duplicate segments in both query and reference videos are determined at the fine scale by using bi-directional scanning to check the matching similarity at the segments’ boundaries. As such, the MS-VSM method can achieve excellent near-duplicate detection accuracy and localization precision with a very high processing efficiency. Extensive experiments show that it outperforms several state-of-the-art methods remarkably on several benchmarks.

     

The set-set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which both of the input strings consists of sets of symbols which may be permuted.     

3字符最长公共弱递增子串的O（nloglogn）算法

最长公共子串(LCS)和最长递增子串(LIS)是两个非常经典的基础算法问题,并且在生物信息学中已有重要应用.2006年,Brodal等人提出了最长公共弱递增字串问题(LCWIS),并且给出了2字符字母表上线性时间算法和3字符字母表上O(nlogn)时间的算法.本文中,我们提出了一种新的在3字符字母表上寻找最长公共弱递增子串(LC-WIS)的算法.该算法利用了两个成熟的数据结构:约束堆(Bounded heap)和van Emde Boas树.我们算法的时间复杂度是O(nloglogn),空间复杂度为0(n),两者都是目前为止最优的.