一种最优相似度的公共序列研究  

Research on a common sequence with optimal similarity

作　　者：武明超 崔晓兵 姚欣 邵咏慧 Wu Mingchao;Cui Xiaobing;Yao Xin;Shao Yonghui(School of Computer and Information Engineering,Henan Normal University,Xinxiang 453000,China;Chengdu University,Chengdu 610000,China)

机构地区：[1]河南师范大学计算机与信息工程学院,河南新乡453000 [2]成都大学,四川成都610000

出　　处：《无线互联科技》2019年第12期112-113,共2页Wireless Internet Technology

摘　　要：针对多条序列最长公共子序列的多解问题,为了能够求出若干条字符串序列,对它们共有的最大相似序列,在计算中按照相似度和长度进行打分,并且对输出的子序列进行排序,以便能够输出相似序列的位置并且达到最优的相似度。根据最优相似度确定字符串之间匹配的公共长度和重复率,用比重复率作为判别相似度的一个指标,在一个已知的字符串,通过和其他字符的比较,利用此种思想,可以找出插入在字符串中的空格位置,并能使相似度达到最优化。通过构建代数结构“格”,利用递归求解当前格与当前序列的公共格。再通过动态规划求出最长公共子序列的长度数组和状态数组,矩阵搜索求出所有有效的跳跃点,能有效避免重复搜索,大大提高时间效率。For the multi-solution problem of the longest common subsequence of multiple sequences,in order to be able to find several sequences of strings,the largest similar sequence they share is scored according to the similarity and length in the calculation,and the output is sub-The sequences are sorted so that the positions of similar sequences and the similarity of high matches can be output.Then use two strings to slide the number of matches between the comparison and the overlap rate of the two strings when sliding,thus defining the measure of similarity,by determining that one string is less than the other.An algorithm is designed to determine the position of the inserted space in the matrix of the string matching and to maximize the similarity index.Then,by constructing an algebraic structure“grid”,the common lattice of the current lattice and the current sequence is solved by recursion can effectively avoid repeated searches,greatly improving time efficiency.

关 键 词：最长公共子序列 近似算法 贪心算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]