难以理解Paul Heckel的Diff算法

Question

我一直在研究 Paul Heckel的差异算法，但似乎还没有完全理解。

我复制了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")。

- Tuffail

Answer 1

我不确定你在哪里找到这个解释和代码，但它有几个错误。数据比较维基百科页面的参考文献之一是Paul's paper的参考文献，这对理解算法非常有帮助。

首先，就我所见，如果前面的步骤正确完成，最后一步的实现是正确的。

让我们从语法/语言问题开始：也许我漏掉了什么，但我不明白为什么你（以及你链接的代码）在第三次遍历中增加自增索引i。

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

最后，也是最重要的，此实现中的第四和第五遍是错误的。我认为论文中的过程措辞可能会让人感到困惑，并且编写链接代码的人弄错了。你的第二个问题已经揭示了它。第四次遍历是对NA进行升序排列，并对每个值指向OA中的一个位置（这意味着在所讨论的实现中，它是int类型）的位置进行检查，我们检查两个数组中下一个位置的值是否指向相同的表条目。如果它们这样做，我们用彼此的位置替换这些指针（用int覆盖指针）。因此，你的第二个问题很到位 - 我们根本不使用表条目指针。这样，我们就有了我们在第三遍发现的独特行作为锚点，以找到紧随其后但在文件中不是唯一的“块”中的未更改行。第五遍也是这样，但是向后，因此在未更改的唯一行之前相同的行也将被分类为未更改行。

以下是我描述的第四和第五遍：

# 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

- et_l

---

谢谢您。您的解释非常详细。我期待着看到更新后的代码。关于第三步中的语法/语言问题，我之前使用了类似链接的字典来保留对当前元素的引用，但在实现过程中后来切换到了列表，并且如您所述，i 的定义和增量是错误的。 - Tuffail

已添加代码，请告知是否有任何不清晰或令人困惑之处。 - et_l

如果这个回答是您正在寻找的 - 请将其接受为正确答案（在左侧答案分数下方点击勾号标志）。 - et_l

嗨@et_l，这正是我想要实现的。谢谢你的帮助！我已经接受了这个答案。 - Tuffail

Answer 2

我一直在寻找相同问题的解决方案。最终我从头开始用Python实现了Heckel算法。这里是Heckel算法前五步的实现和第6步（提取差异表示）的实现。

您还可以在程序中使用mdiff包，使用Heckel算法检测文本差异和块移动。

from mdiff import HeckelSequenceMatcher

a = ['line1', 'line2', 'line3', 'line4', 'line5']
b = ['line1', 'line3', 'line2', 'line4', 'line6']
sm = HeckelSequenceMatcher(a, b)
opcodes = sm.get_opcodes()

for tag, i1, i2, j1, j2 in opcodes:
    print('{:7}   a[{}:{}] --> b[{}:{}] {!r:>8} --> {!r}'.format(tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]))

equal     a[0:1] --> b[0:1]  ['line1'] --> ['line1']
move      a[1:2] --> b[2:2]  ['line2'] --> []
equal     a[2:3] --> b[1:2]  ['line3'] --> ['line3']
moved     a[1:1] --> b[2:3]         [] --> ['line2']
equal     a[3:4] --> b[3:4]  ['line4'] --> ['line4']
replace   a[4:5] --> b[4:5]  ['line5'] --> ['line6']

还有一个简单的GUI应用程序在软件包中，可以可视化和测试算法。

- Mateusz Matelski