有人可以解释这个 "Longest Common Subsequence" 算法吗？

Question

Longest Common Subsequence (LCS)问题是：给定两个序列A和B，找到在A和B中都找到的最长子序列.例如，给定 A = "peterparker" 和 B = "spiderman"，最长公共子序列是 "pera".

谁能解释这个 Longest Common Subsequence 算法？

def longestCommonSubsequence(A: List, B: List) -> int:
    # n = len(A)
    # m = len(B)
    
    indeces_A = collections.defaultdict(list)
    
    # O(n)
    for i, a in enumerate(A):
        indeces_A[a].append(i)
    
    # O(n)
    for indeces_a in indeces_A.values():
        indeces_a.reverse()
    
    # O(m)
    indeces_A_filtered = []
    for b in B:
        indeces_A_filtered.extend(indeces_A[b])
    
    # The length of indeces_A_filtered is at most n*m, but in practice it's more like O(m) or O(n) as far as I can tell.
    iAs = []
    # O(m log m) in practice as far as I can tell.
    for iA in indeces_A_filtered:
        j = bisect.bisect_left(iAs, iA)
        if j == len(iAs):
            iAs.append(iA)
        else:
            iAs[j] = iA
    return len(iAs)

所写的算法找到 longest common subsequence 的长度，但可以修改为完全找到 longest common subsequence。

我在 leetcode link 上寻找等效问题的最快 python 解决方案时发现了这个算法。该算法是该问题最快的 python 解决方案（40 毫秒），而且它似乎还具有 O(m log m) 时间复杂度，这比大多数其他解决方案的 O(m*n) 时间复杂度要好得多。

我不完全理解它为什么有效，并尝试遍历 Longest Common Subsequence 问题的已知算法以找到其他提及它的方法，但找不到类似的东西。我能找到的最接近的东西是 Hunt–Szymanski algorithm link 据说在实践中也有 O(m log m)，但似乎不是相同的算法。

我的理解是：

indeces_a 是相反的，因此在 iAs for 循环中，保留较小的索引（这在进行下面的演练时更为明显。）
据我所知，iAs for 循环找到 indeces_A_filtered 的 longest increasing subsequence。

谢谢！

这是算法的演练，例如 A = "peterparker" 和 B = "spiderman"

     01234567890
A = "peterparker"
B = "spiderman"

indeces_A = {'p':[0,5], 'e':[1,3,9], 't':[2], 'r':[4,7,10], 'a':[6], 'k':[8]}

# after reverse
indeces_A = {'p':[5,0], 'e':[9,3,1], 't':[2], 'r':[10,7,4], 'a':[6], 'k':[8]}

#                     -p-  --e--  ---r--  a
indeces_A_filtered = [5,0, 9,3,1, 10,7,4, 6]

# the `iAs` loop

iA = 5
j = 0
iAs = [5]

iA = 0
j = 0
iAs = [0]

iA = 9
j = 1
iAs = [0,9]

iA = 3
j = 1
iAs = [0,3]

iA = 1
j = 1
iAs = [0,1]

iA = 10
j = 2
iAs = [0,1,10]

iA = 7
j = 2
iAs = [0,1,7]

iA = 4
j = 2
iAs = [0,1,4]

iA = 6
j = 3
iAs = [0,1,4,6] # corresponds to indices of A that spell out "pera", the LCS

return len(iAs) # 4, the length of the LCS

Answer 1

这里缺少的是“耐心排序”，它与最长递增子序列 (LIS) 的联系有点微妙，但众所周知。代码中的最后一个循环是使用“贪心策略”进行耐心排序的基本实现。通常，它不是，而是直接计算 LIS，而是计算 LIS 的长度。

一个足够简单的正确性证明，其中包括可靠地计算 LIS 所需的草图（不仅仅是它的长度），可以在

的早期作为引理 1 找到

"Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem" David Aldous and Persi Diaconis

Answer 2

了解LIS算法

def lenLIS(self, nums):
    lis = []
    for num in nums:
        i = bisect.bisect_left(lis, num)
        if i == len(lis):
            lis.append(num) # Append
        else:
            lis[i] = num # Overwrite
    return len(lis)

上面的算法给了我们nums的最长递增子序列（LIS）的长度，但不一定给我们nums的LIS。要理解为什么上面的算法是正确的，以及如何修改它以获得 nums 的 LIS，请继续阅读。

我举例说明

示例 1

（摘自 Tim Peters 链接的 https://www.stat.berkeley.edu/~aldous/Papers/me86.pdf）：

nums = [7,2,8,1,3,4,10,6,9,5]
lenLIS(nums) == 5

算法告诉我们nums的LIS的长度是5，但是我们如何得到nums的LIS。

我们表示 lis 的历史如下（下面解释）：

7
2, 8
1, 3, 4, 10
          6, 9
          5

我们呈现 lis 历史的方式很有意义。首先，想象一个空的 table 行和列。我们最初排在第一行。在 for num in nums: 循环的每次迭代中，我们要么 Append Overwrite 取决于 num 的值和 lis 的值：

Append：我们在 table 中通过在下一列中写入附加值 (num) 来表示这一点，即在第 i 列当前行。附加值始终大于当前行中的所有值。
Overwrite：如果lis[i]已经等于num，我们不对table做任何事情。否则，我们通过向下移动到下一行并在新行的第 i 列写入新值 (num) 来在 table 中表示它。新值始终小于列中的所有其他值。

观察：

table可以稀疏
值按从左到右、从上到下的顺序插入。因此，每当我们在 table 中向上或向左移动时，我们都会移动到 nums.
当我们越过一行时，值会增加。因此，向左移动会使我们得到一个较小的值。
假设 (r, i) 有一个值 v，但 (r, i-1) 没有。这只能作为覆盖的结果发生。考虑 Overwrite 之前 lis 的状态。有一个值 v 必须放在 lis 中，我们将这个位置计算为 i = bisect_left(lis, v)。 i 将被计算为 s.t。 lis[i-1] < v < lis[i]。从 v at (r, i)，我们可以通过向左移动一次（到空的 (r, i-1)）然后再向上移动一个矿石到达 table 中的 lis[i-1]次，直到我们遇到一个值。该值将是 lis[i-1].
将 2. 和 3. 放在一起，我们已经证明在 table 中，我们总是可以向左移动一次然后向上移动零次或多次以达到较小的值。将此运动的一个应用表示为 prev。此外，1. 告诉我们执行 prev 时遇到的较小值是在 nums 中较早出现的值。

我们使用4.从table得到LIS(nums)。从 table 最右边的值之一开始，然后重复执行 prev 以反向遇到 LIS(nums) 的其他值。

在示例中执行此过程，我们从 9 开始。应用 prev 一次，我们得到 6。第二次，我们得到 4，然后是 3，然后是 1。事实上 [1,3,4,6,9] 是 nums 的 LIS 之一。

示例 2：

nums = [2,7,10,14,25,5,6,5,10,20,1,22,4,12,7,11,9,25]
lenLIS(nums)

lis的历史：

2, 7, 10, 14, 25
   5,  6  10, 20
1                22
   4          12
       7      11
           9     25

所以 lenLIS(nums) == 6 是 len(LIS(nums)。让我们找到 LIS(nums):

同样，从 table 最右边的值之一开始：22。应用 prev 一次，我们得到 20。第二次，我们得到 10，然后是 6，然后是 5，然后是 2。所以 [2,5,6,10,20,22] 是 nums 的 LIS。

我们可以从其他最右边的值开始：25。应用 prev 一次，我们得到 11。第二次，我们得到 10，然后是 6，然后是 5，然后是 2。所以 [2,5,6,10,11,25] 是 nums 的另一个有效 LIS。

此解释与 https://www.stat.berkeley.edu/~aldous/Papers/me86.pdf 中的解释类似，但我发现自己更容易理解，只是想分享它以防对其他人有用。

有人可以解释这个 "Longest Common Subsequence" 算法吗？

Can someone explain this "Longest Common Subsequence" algorithm?

python

algorithm

diff

string-algorithm

subsequence

了解LIS算法

示例 1

观察：

示例 2：