python - 查找列表之间最小差异的算法

Question

我一直在尝试理解使用的算法here比较两个列表，在此 commit 中实现.据我了解，其目的是找到最少的更改来创建 dst来自 src .这些更改稍后被列为 patch 的序列。命令。我不是python开发者，学习了generators了解流程以及递归是如何完成的。但是，现在我无法理解 _split_by_common_seq 生成的输出。方法。我输入了几个不同的列表，输出如下所示。你能帮我理解为什么在这些情况下输出是这样的吗？

在引用案例中，

src [0, 1, 2, 3]
dst [1, 2, 4, 5]
[[(0, 1), None], [(3, 4), (2, 4)]]

我看不出它与 picture 有什么关系在文档中。为什么(3,4)和 (2,4)在右侧？它是标准算法吗？

测试用例

src [1, 2, 3]
dst [1, 2, 3, 4, 5, 6, 7, 8]
[[None, None], [None, (3, 8)]]   

src [1, 2, 3, 4, 5]
dst [1, 2, 3, 4, 5, 6, 7, 8]
[[None, None], [None, (5, 8)]]

src [4, 5]
dst [1, 2, 3, 4, 5, 6, 7, 8]
[[None, (0, 3)], [None, (5, 8)]]

src [0, 1, 2, 3]
dst [1, 2, 4, 5]
[[(0, 1), None], [(3, 4), (2, 4)]]

src [0, 1, 2, 3]
dst [1, 2, 3, 4, 5]
[[(0, 1), None], [None, (3, 5)]]

src [0, 1, 3]
dst [1, 2, 4, 5]
[[(0, 1), None], [(2, 3), (1, 4)]] 

为了将来引用，这里是代码(取自上述存储库):

import itertools

def _longest_common_subseq(src, dst):
    """Returns pair of ranges of longest common subsequence for the `src`
and `dst` lists.

>>> src = [1, 2, 3, 4]
>>> dst = [0, 1, 2, 3, 5]
>>> # The longest common subsequence for these lists is [1, 2, 3]
... # which is located at (0, 3) index range for src list and (1, 4) for
... # dst one. Tuple of these ranges we should get back.
... assert ((0, 3), (1, 4)) == _longest_common_subseq(src, dst)
"""
    lsrc, ldst = len(src), len(dst)
    drange = list(range(ldst))
    matrix = [[0] * ldst for _ in range(lsrc)]
    z = 0 # length of the longest subsequence
    range_src, range_dst = None, None
    for i, j in itertools.product(range(lsrc), drange):
        if src[i] == dst[j]:
            if i == 0 or j == 0:
                matrix[i][j] = 1
            else:
                matrix[i][j] = matrix[i-1][j-1] + 1
            if matrix[i][j] > z:
                z = matrix[i][j]
            if matrix[i][j] == z:
                range_src = (i-z+1, i+1)
                range_dst = (j-z+1, j+1)
        else:
            matrix[i][j] = 0
    return range_src, range_dst

def split_by_common_seq(src, dst, bx=(0, -1), by=(0, -1)):
    """Recursively splits the `dst` list onto two parts: left and right.
The left part contains differences on left from common subsequence,
same as the right part by for other side.

To easily understand the process let's take two lists: [0, 1, 2, 3] as
`src` and [1, 2, 4, 5] for `dst`. If we've tried to generate the binary tree
where nodes are common subsequence for both lists, leaves on the left
side are subsequence for `src` list and leaves on the right one for `dst`,
our tree would looks like::

[1, 2]
/ \
[0] []
/ \
[3] [4, 5]

This function generate the similar structure as flat tree, but without
nodes with common subsequences - since we're don't need them - only with
left and right leaves::

[]
/ \
[0] []
/ \
[3] [4, 5]

The `bx` is the absolute range for currently processed subsequence of
`src` list. The `by` means the same, but for the `dst` list.
"""
    # Prevent useless comparisons in future
    bx = bx if bx[0] != bx[1] else None
    by = by if by[0] != by[1] else None

    if not src:
        return [None, by]
    elif not dst:
        return [bx, None]

    # note that these ranges are relative for processed sublists
    x, y = _longest_common_subseq(src, dst)

    if x is None or y is None: # no more any common subsequence
        return [bx, by]

    return [split_by_common_seq(src[:x[0]], dst[:y[0]],
                                 (bx[0], bx[0] + x[0]),
                                 (by[0], by[0] + y[0])),
            split_by_common_seq(src[x[1]:], dst[y[1]:],
                                 (bx[0] + x[1], bx[0] + len(src)),
                                 (bx[0] + y[1], bx[0] + len(dst)))]

Answer 1

这是一个可爱的算法，但我不认为它是一个“已知”的算法。这是一种比较列表的聪明方法，可能不是有人第一次想到它，但我以前从未见过。

基本上，输出告诉您src 中看起来不同的范围。和 dst .

该函数总是返回一个包含 2 个列表的列表。第一个列表引用 src 中的元素和 dst位于 src 之间的最长公共(public)子序列的左侧和 dst ;第二个是指最长公共(public)子序列右侧的元素。这些列表中的每一个都包含一对元组。元组表示列表中的一个范围 - (x, y)表示执行 lst[x:y] 会得到的元素.从这对元组中，第一个元组是从 src 开始的范围。 ，第二个元组的范围是 dst .

在每一步，算法都会计算 src 的范围。和 dst位于最长公共(public)子序列的左侧和 src 之间的最长公共(public)子序列的右侧和 dst .

让我们看一下您的第一个示例以澄清问题:

src [0, 1, 2, 3]
dst [1, 2, 4, 5]

src之间的最长公共(public)子序列和 dst是 [1, 2] .在 src , 范围 (0, 1)定义紧邻 [1, 2] 左侧的元素;在 dst ，该范围为空，因为在 [1, 2] 之前没有任何内容.因此，第一个列表将是 [(0, 1), None] .
[1, 2] 的右侧, 在 src ，我们有 (3, 4) 范围内的元素，并在 dst我们有 4 和 5，它们由范围 (2, 4) 表示.所以第二个列表将是 [(3, 4), (2, 4)] .

你去吧:

[[(0, 1), None], [(3, 4), (2, 4)]]

这与评论中的树有什么关系？

树中的叶子使用不同的符号:而不是描述范围的元组，而是显示该范围内的实际元素。事实上，[0]是 (0, 1) 范围内的唯一元素在 src .这同样适用于其余部分。

一旦你得到这个，你发布的其他例子应该很容易理解。但请注意，如果有多个公共(public)子序列，输出可能会变得更复杂:算法以非递增顺序查找每个公共(public)子序列；因为每次调用都会返回一个包含 2 个元素的列表，这意味着在这种情况下您将获得嵌套列表。考虑:

src = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
dst = [46, 1, 2, 3, 4, 5, 99, 98, 97, 5, 6, 7, 30, 31, 32, 11, 12, 956]

这输出:

[[(0, 1), (0, 1)], [[[None, (6, 10)], [(8, 11), (12, 15)]], [(13, 14), (17, 18)]]]

第二个列表是嵌套的，因为存在不止一个递归级别(您之前的示例立即落入基本情况)。

前面显示的解释递归地适用于每个列表:[[(0, 1), (0, 1)], [[[None, (6, 10)], [(8, 11), (12, 15)]], [(13, 14), (17, 18)]]] 中的第二个列表显示最长公共(public)子序列右侧列表中的差异。

最长的公共(public)子序列是[1, 2, 3, 4, 5] . [1, 2, 3, 4, 5] 的左侧，两个列表的第一个元素不同(范围相等且易于检查)。

现在，该过程递归地应用。对于右侧，有一个新的递归调用，src和 dst变得:

src = [6, 7, 8, 9, 10, 11, 12, 13]
dst = [99, 98, 97, 5, 6, 7, 30, 31, 32, 11, 12, 956]

    # LCS = [6, 7]; Call on the left
        src = []
        dst = [99, 98, 97, 5]
    # LCS = [6, 7]; Call on the right
        src = [8, 9, 10, 11, 12, 13]
        dst = [30, 31, 32, 11, 12, 956]
        # LCS = [11, 12]; Call on the left
            src = [8, 9, 10]
            dst = [30, 31, 32]
        # LCS = [11, 12]; Call on the right
            src = [13]
            dst = [956]

最长的公共(public)子序列是[6, 7] .然后你将有另一个递归调用
在左侧，为 src = []和 dst = [99, 98, 97, 5] ，现在没有最长的公共(public)子序列了，这边的递归就停止了(照着图就行了)。

每个嵌套列表递归地表示调用过程的子列表上的差异，但请注意，索引始终引用原始列表中的位置(由于 bx 和 by 的参数传递方式 - 注意他们总是从一开始就积累)。

这里的关键是您将获得与递归深度成线性比例的嵌套列表，事实上，您实际上可以通过查看嵌套级别来判断原始列表中存在多少公共(public)子序列。