理解Paul Heckel的Diff算法有困难

Question

我一直在看Paul Heckel's Diff Algorithm，我似乎没有完全理解它。在

我复制了Python代码中显示的步骤1-5，但是我无法使用算法的最后一步来显示差异。如果有人能解释Python的最后一步，我会很感激的。在

另外，我不完全理解为什么您需要引用第4步和第5步中的表行，所以对它的解释也会很神奇！在

非常感谢

以下是我当前的代码：

def find_diff(current_file_as_list, different_file_as_list):

N = current_file_as_list
O = different_file_as_list

table = {}

OA = []
NA = []
for i in O:
    OA.append(i)
for i in N:
    NA.append(i)

# First pass
i = 0

for line in N:
    if not line in table:
        table[line] = {}
        table[line]["NC"] = 1
    else:
        if table[line]["NC"] == 1:
            table[line]["NC"] = 2
        else:
            table[line]["NC"] = "many"
    NA[i] = table[line]
    i += 1

# second pass
j = 0

for line in O:
    if not line in table:
        table[line] = {}
        table[line]["OC"] = 1
    else:
        if not "OC" in table[line]:
            table[line]["OC"] = 1
        elif table[line]["OC"] == 1:
            table[line]["OC"] = 2
        else:
            table[line]["OC"] = "many"
    table[line]["OLNO"] = j  # Gets overwritten with multiple occurrences.
    # Check to see if this is the intended implementation.
    # Maybe only relevant for "OC" == "NC" == 1
    OA[j] = table[line]
    j += 1

# third pass
i = 0

for i in range(0, len(NA)):
    # Check if they appear in both files
    if "OC" in NA[i] and "NC" in NA[i]:
        # Check if they appear exactly once
        if NA[i]["OC"] == NA[i]["NC"] == 1:
            olno = NA[i]["OLNO"]
            NA[i], OA[olno] = olno, i
    i += 1

# fourth pass
# ascending
for i in range(0, len(NA)):
    for j in range(0 , len(OA)):
        if NA[i] == OA[j] and i + 1 < len(NA) and j + 1 < len(OA) and NA[i + 1] == OA[j + 1]:
            OA[j + 1] = table[O[i + 1]]
            NA[i + 1] = table[N[j + 1]]

# fifth pass
# descending
for i in range(len(NA) - 1, 0, -1):
    for j in range(len(OA) - 1, 0, -1):
        if NA[i] == OA[j] and i - 1 > 0 and j - 1 > 0 and NA[i - 1] == OA[j - 1]:
            OA[j - 1] = table[O[i - 1]]
            NA[i - 1] = table[N[j - 1]]

# final step implementation should go here but I'm not sure how to approach it but this is my current attempt (which I am certain is wrong):
k = 0

array = []

for i in range(0, len(NA)):

    if isinstance(NA[i], int):
        array.append("= " + str(N[i]))
        k = NA[i] + 1
    elif isinstance(NA[i], dict):
        array.append("+ " + N[i])

    for j in range(k, len(OA)):
        k = j + 1
        print("j - " + str(j))
        if not isinstance(OA[j], int):
            array.append("- " + O[j])
        else:
            break

您可以传递任意两个字符串或字符串列表作为函数的输入，例如find_diff（“hello”，“hell”）

Answer 1

我不知道你在哪里找到这个解释和代码，但它有几个错误。Wikipedia中用于数据比较的一个页面是a reference to Paul's paper，这对理解算法非常有帮助。在

首先，据我所知，你最后一步的实现是正确的（假设前面的步骤是正确的）。在

让我们从一个语法/语言问题开始：也许我遗漏了一些东西，但是我不明白为什么您（以及您链接到的代码）在第三个过程中递增自递增索引i。在

关于表项的计数器：在链接的代码中有一个带注释的问题-为什么我们需要2值？答案是-我们没有！在论文中，Heckel明确地写道，计数器只应该有0、1和many。您可以看到，我们从不使用或查询计数器的2值。我猜测这个错误来自于用一种比Heckel在编写算法时所想的更灵活的语言来实现算法，因为查询特定表项是否存在计数器等同于查询计数器的值是否为0。在

最后也是最重要的一点是，这一实施中的第四和第五关是错误的。在这里，我相信论文中通行证的措辞可能会令人困惑，不管是谁写的链接代码都弄错了。你的第二个问题已经揭示了这一点。第四个过程按升序排列在NA上，对于每个值指向OA中的位置（这意味着在讨论的实现中它属于int类型），我们检查两个数组中下一个位置的值是否指向同一个表条目。如果他们这样做，我们将用彼此的位置替换这些指针（用ints覆盖指针。所以你的第二个问题是关于点的-我们在这里根本不使用表入口指针）。这样，我们就有了我们在第三个过程中发现的唯一的线，作为锚来找到紧随其后的未添加线，它们是它们的“块”的一部分，但在文件中不是唯一的。同样的情况发生在第五遍，但向后，所以在未更改的唯一行之前的相同行也将被归类为未更改的行。在

下面是我描述的第四和第五关：

# fourth pass
# ascending
for i in range(0, len(NA) - 1):
    if isinstance(NA[i], int) and (NA[i] + 1) < len(OA) and NA[i + 1] == OA[NA[i] + 1]:
        NA[i + 1] = NA[i] + 1
        OA[NA[i] + 1] = i + 1

# fifth pass
# descending
for i in range(len(NA) - 1, 0, -1):
    if isinstance(NA[i], int) and (NA[i] - 1) >= 0 and NA[i - 1] == OA[NA[i] - 1]:
        NA[i - 1] = NA[i] - 1
        OA[NA[i] - 1] = i - 1