4

我一直在研究Paul Heckel 的 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（“你好”，“地狱”）

4

1 回答 1

5

我不确定你在哪里找到这个解释和代码，但它有几个错误。用于数据比较参考的 Wikipedia 页面之一是对 Paul 论文的参考，该论文被证明对理解算法最有帮助。

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

让我们从语法/语言问题开始：也许我遗漏了一些东西，但我不明白为什么您（以及您链接到的代码）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
于 2017-03-20T16:31:20.653 回答