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

摘要：

针对多条序列最长公共子序列的多解问题,为了能够求出若干条字符串序列,对它们共有的最大相似序列,在计算中按照相似度和长度进行打分,并且对输出的子序列进行排序,以便能够输出相似序列的位置并且达到最优的相似度.根据最优相似度确定字符串之间匹配的公共长度和重复率,用比重复率作为判别相似度的一个指标,在一个已知的字符串,通过和其他字符的比较,利用此种思想,可以找出插入在字符串中的空格位置,并能使相似度达到最优化.通过构建代数结构"格",利用递归求解当前格与当前序列的公共格.再通过动态规划求出最长公共子序列的长度数组和状态数组,矩阵搜索求出所有有效的跳跃点,能有效避免重复搜索,大大提高时间效率.

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

所属期刊栏目：16

在线出版日期：2019-08-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：112-113