查找两个字符串之间的最佳匹配字符数(类似于字符串对齐,但在某些方面并非如此)

find the optimal matching number of characters between two strings (something like string alignment but not in some ways)(查找两个字符串之间的最佳匹配字符数(类似于字符串对齐,但在某些方面并非如此))

本文介绍了查找两个字符串之间的最佳匹配字符数(类似于字符串对齐,但在某些方面并非如此)的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正尝试用Python来做这件事。 我有两个序列:

序列1:‘A B C D E’

序列2:‘A R C B E’

假设我要"计算"seq1和seq2中的字符数 但是在下面的方法中,假设我从序列1中的A到序列2中的A画一条线,同样连接C--C和E--E,但是如果我连接B-B,这条连接线将跨越连接C-C的线,所以。 我想要计算B-B或C--C,而不是两者,因为它们的线交叉,并找出我可以在两个字符串之间建立的此类连接的总数。

有没有办法做到这一点?我确信我要做的事情有一个名字,但我不知道,这使得在网上搜索可能的方法也很困难。

感谢您的帮助。

推荐答案

听起来像longest common subsequence问题。Levenshtein距离的动态规划算法的简化版本解决了这个问题。

互联网上有许多Python implementations of LCS。维基百科提供的伪代码对于翻译成Python来说也是微不足道的。

这篇关于查找两个字符串之间的最佳匹配字符数(类似于字符串对齐,但在某些方面并非如此)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:查找两个字符串之间的最佳匹配字符数(类似于字符串对齐,但在某些方面并非如此)

基础教程推荐