有没有什么算法可以解决每个字符具有不同权重的最长公共子序列问题？ [英] Is there any algorithm to address the longest common subsequence problem with different weights for each character?

问题描述

我正在寻找一种算法来解决具有以下条件的两个字符串的LCS问题：

每个字符串都由英文字符组成，每个字符都有一个权重。例如：

序列1(S1)：带权重的ABBCD[1，2，4，1，3]

序列2(S2)："tbdc"，权重为[7，5，1，2]

假设MW(s, S)被定义为字符串S中的子序列s相对于相关权重的最大权重。最重的公共子序列(HCS)定义为：

hcs=argmin(mw(s，s1)，mw(s，s2))

算法输出应为字符串中的HCS索引和权重。在本例中，索引将为：

i_s1=[2，4]-->MW("BD"，"ABBCD")=7

i_s2=[1，2]-->mw("bd"，"tbdc")=6

因此HCS = "BD", and weight = min(MW(s, S1), MW(s, S2)) = 6.

推荐答案

您需要生成的表将包含此内容。

for each position in sequence 1
    for each position in sequence 2
        for each extreme pair of (weight1, weight2)
            (last_position1, last_position2)

其中，极值对是指不可能找到序列1中的权重和序列2中的权重都是>=且至少一个是>的点的子序列。

可能有多个极端对，其中一个序列高于另一个序列。

规则是，在(i, -1)或(-1, j)位置，唯一的极端对是权重为0的空集。在任何其他情况下，我们合并(i-1, j)和(i, j-1)的极值对。然后如果seq1[i] = seq2[j]，则添加您转到(i-1, j-1)的选项，然后在相应的子序列中包括i和j。(因此，将weight1[i]和weight2[j]添加到权重中，然后进行合并。)

对于该合并，您可以按权重1升序排序，即前面两个点的所有极值，然后丢弃其权重2小于或等于序列中先前发布的最佳权重2的所有极值。

当你到达终点时，你可以找到min最高的极值对，这就是你的答案。然后，您可以遍历数据结构以查找有问题的子序列。

这篇关于有没有什么算法可以解决每个字符具有不同权重的最长公共子序列问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！