一种带匹配路径约束的最长公共子序列长度算法

王前东*

doi:10.11999/JEIT170092

一种带匹配路径约束的最长公共子序列长度算法

doi: 10.11999/JEIT170092

王前东*¹

计量
- 文章访问数: 1047
- HTML全文浏览量: 118
- PDF下载量: 247
- 被引次数: 0
出版历程
- 收稿日期: 2017-01-23
- 修回日期: 2017-08-19
- 刊出日期: 2017-11-19

A Matching Path Constrained Longest Common Subsequence Length Algorithm

WANG Qiandong¹

摘要

摘要: 在带约束的最长公共子序列问题中提出一种特殊的新问题：假设有两序列Q和C, Q中指定的匹配位置序列I，计算两序列Q和C的最长公共子序列，且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题，该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型，其次推出该序列的性质，最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn), m, n, t分别为序列Q, C, I的长度。
- 最长公共子序列 /
- 匹配路径约束 /
- 带约束的最长公共子序列 /
- 带匹配路径约束的最长公共子序列
Abstract: A special new problem is proposed in the constrained longest common subsequence problem. Given sequences Q , C and the specific positions sequence I in Q, the matching path constrained longest common subsequence problem for Q and C with respect to I is to find a Longest Common Subsequence (LCS) of Q and C such that the positions I in Q are in matching path of this LCS. A matching path constrained longest common subsequence algorithm is proposed for this problem. Firstly, a new model is defined for matching path constrained longest common subsequence. Secondly, the property of the subsequence is given. Lastly, a common method with O(mnt) time and a fast method with O(mn) time are respectively analyzed, where n, m and t are lengths of Q, C, and I respectively.

HTML全文

参考文献(17)

WANG Haoxin, ZHONG Jingdong, and ZHANG Defu. A duplicate code checking algorithm for the programming experiment[C]. 2015 Second International Conference on Mathematics and Computers in Sciences and in Industry (MCSI), Sliema, 2015: 39-42. doi: 10.1109/MCSI.2015.12.

WANGGER R A and FISCHER M J. The string-to-string correction problem[J]. Journal of the Association for Computing Machinery, 1974, 21(1): 168-173.

赵建军, 陈滨, 杨利斌, 等. 一种基于字符串模型的轨迹相似度计算[J]. 科学技术与工程, 2013, 13(1): 80-84.

ZHAO Jianjun, CHEN Bin, YANG Libin, et al. Measure similarity between trajectories based on alphabetic string model[J]. Science Technology and Engineering, 2013, 13(1): 80-84.

TSAI Y T. The constrained longest common subsequence problem[J]. Information Processing Letters, 2003, 88(4): 173-176. doi: 10.1016/j.ipl.2003.07.001.

GOTTHILF Z, HTSAI YERMELIN D, and LEWENSTEIN M. Constrained LCS: Hardness and approximation[C]. Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching, Berlin, 2008: 255-262. doi: 10.1007/978-3-540-69068-9_24.

CHIN F, SANTIS A, FERRARA A, et al. A simple algorithm for the constrained sequence problems[J]. Information Processing Letters, 2004, 90(4): 175-179. doi: 10.1016/j.ipl. 2004.02.008.

ARSLAN A and EGECIOGLU O. Algorithms for the constrained longest common subsequence problems[J]. International Journal of Foundations of Computer Science, 2005, 16(6): 1099-1109. doi: 10.1142/S0129054105003674.

BECERRA D, SOTO W, NINO L, et al. An algorithm for constrained LCS[C]. IEEE/ACS International Conference on Computer Systems and Applications, Hammamet Tunisia, 2010: 1-7. doi: 10.1109/AICCSA.2010.5586937.

BONIZZONI P, VEDOVA G, DONDI R, et al. Variants of constrained longest common subsequence[J]. Information Processing Letters, 2010, 110(20): 877-881. doi: 10.1016/j.ipl. 2010.07.015.

业宁, 朱大铭, 张倩倩, 等. 带约束最长公共子序列快速算法[J]. 南京大学学报(自然科学版), 2009, 45(5): 576-584.

YE Ning, ZHU Daming, ZHANG Qianqian, et al. Fast algorithm of the longest common subsequence with constraints[J]. Journal of Nanjing Universitv, 2009, 45(5): 576-584.

TSENG C T, YANG C B, and ANN H Y. Efficient algorithms for the longest common subsequence problem with sequential substring constraints[J]. Journal of Complexity, 2013, 29(1): 44-52. doi: 10.1109/BIBE.2011.34.

魏龙翔, 何小海, 滕奇志, 等. 结合Hausdorff距离和最长公共子序列的轨迹分类[J]. 电子与信息学报, 2013, 35(4): 784-790. doi: 10.3724/SP.J.1146.2012.01078.

WEI Longxiang, HE Xiaohai, TENG Qizhi, et al. Trajectory classification based on Hausdorff distance and longest common subsequence[J]. Journal of Electronics Information Technology, 2013, 35(4): 784-790. doi: 10.3724/ SP.J.1146.2012.01078.

BEAL R, AFRIN T, FARHEEN A, et al. A new algorithm for the LCS problem with application in compressing genome resequencing data[C]. 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Washington, DC, 2015: 69-74. doi: 10.1109/BIBM.2015.7359657.

LIU Richen, GUO Hanqi, ZHANG Jiang, et al. Comparative visualization of vector field ensembles based on longest common subsequence[C]. 2016 IEEE Pacific Visualization Symposium (PacificVis), Taipei, 2016: 96-103. doi: 10.1109/ PACIFICVIS.2016.7465256.

施引文献

资源附件(0)

访问统计