Трудность понимания алгоритма Диффа Пола Хеккеля
Я смотрел на алгоритм Диффа Пола Хеккеля и, похоже, не совсем понял его.
Я скопировал шаги 1-5, как показано в коде Python, но не могу показать различия, используя последний шаг алгоритма. Я был бы признателен, если бы кто-то объяснил последний шаг вместе с кодом 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("привет", "ад")
2 ответа
Я не уверен, где вы нашли это объяснение и код, но в нем есть несколько ошибок. Одной из страниц Википедии для сравнения данных была ссылка на статью Пола, которая оказалась наиболее полезной для понимания алгоритма.
Во-первых, насколько я понимаю, ваша реализация последнего шага верна (при условии, что предыдущие шаги были выполнены правильно).
Давайте начнем с синтаксической / языковой проблемы: возможно, я что-то упускаю, но я не понимаю, почему вы (и код, на который вы ссылались) увеличиваете самоинкрементный индекс i в третьем проходе.
Что касается счетчиков записей таблицы: в связанном коде есть закомментированный вопрос - зачем вообще нужно значение 2? Ответ - мы не делаем! В самой статье Геккель явно пишет, что единственными значениями, которые должны иметь счетчики, являются 0, 1 и многие. Вы можете видеть, что мы никогда не используем и не запрашиваем счетчики для значения 2. Я дико догадываюсь, что эта ошибка происходит из-за реализации алгоритма на языке, более гибком, чем те, которые Геккель имел в виду при написании алгоритма, поскольку запрос о наличии счетчика для конкретной записи таблицы является синонимом запроса, если счетчик значение равно 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
Я искал решение той же проблемы. В итоге я реализовал алгоритм Хеккеля на Python с нуля. Вот реализация первых 5 шагов алгоритма Хеккеля и реализация 6-го шага (извлечение представления различий) .
Вы также можете использовать пакет mdiff в своей программе для обнаружения разницы текста с перемещением блока с помощью алгоритма Хеккеля:
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']
Также в пакете есть простое приложение с графическим интерфейсом , которое позволяет визуализировать и тестировать алгоритм.