Разностный алгоритм Майерса был предложен Юджином Майерсом в статье, опубликованной в 1986 году, вы можете просмотреть в конце статьи.Ссылка 1..
мы часто используемgit diff
diff
Есть много результатов diff, например, вы можете удалить всю строку, а затем добавить еще одну целую строку. Вы можете удалить персонажа, чтобы добавить персонажа ......
Неудивительно, что это число является экспоненциальным
Так какой диф "лучше"
Подробнее см. в разделе «Ссылки».ссылка 2, который не будет повторяться здесь
Резюме примерно некоторых условий:
- Минимальные изменения
Редактировать график
Нитьa = 'ABCABBA' b = 'CBABAC'
Изменить затем выглядеть, как показано на следующем рис.
Длина a записывается как N, где N = 7, а длина b записывается как M, где M = 6.
Каждой точке может соответствовать координата (x, y)
Теперь, начиная с точки (0, 0), строкаa, двигаясь вправо, т.е. увеличивая значение x, эквивалентно изменению отaУдаление символа от (0, 0) до (1, 0) означает удаление символа «A». Двигаясь вниз, то есть увеличивая значение y, это эквивалентно переходу отbДобавление персонажа к (1, 0) до (1, 1) означает введение символа «C» в это время, переместив предыдущие два шага, мы получаем отредактированную строку как «CBCABBA»
В дополнение к движению вправо и вниз, мы также можем двигаться по диагонали, например, к точке (2, 0), поскольку третий символ a — это «C», а первый символ b — «C», а это означает, что есть одни и те же персонажи могут быть зарезервированы, ни добавлены, ни удалены. Обратите внимание, что перемещение по диагонали не требует затрат, потому что перемещение по ней не меняет строку.
Список и объяснение некоторых существительных
Trace
«Точки совпадения» диагональных ребер пути, состоящего из последовательности длины L
Shortest Edit Script(SES)
Самый короткий скрипт редактирования. Содержит всего две команды: удалить и добавить
От (0, 0) до (N, M) скрипт удаляет N - L символов, добавляет M - L символов
Таким образом, для каждой трассы существует соответствующий сценарий редактирования D = N + M - 2L.
Longest Common Subsequence(LCS)
Тогда задача LCS/SES эквивалентна поиску пути с наименьшей стоимостью от (0, 0) до )(N, M) в этом графе редактирования весов.
О чем вы подумали? bfs, dijkstra или dp... ?
Жадный алгоритм O((M+N)D)
Задача поиска кратчайшего сценария редактирования сводится кПроблема нахождения пути от (0, 0) до (n, m) с наименьшим количеством горизонтальных и вертикальных сторон
Список и объяснение некоторых существительных
snake
серпантин
Змея представляет собой линию, состоящую из горизонтального (вертикального) хода, за которым следует как можно больше диагональных ходов.
Например: двигайтесь от (0, 1) к (0, 2) по диагональной линии, пока (2, 4), (0, 1) - (0, 2) - (2, 4) образуют змейку
Темно-синяя линия, как на фиг.
diagonal k
Косая черта k, k (косая черта) линия
Определите k = x - Y, K, состоящие из одной той же точки по прямой линии, они взаимно параллельные наклонные линии
d-path
Две леммы и доказательства
Лемма 1. Конец D-пути должен лежать на k-м склоне, где k ∈ {-D, -D + 2, ... D-2, D}
Доказательство по индукции:
0-путь (включая максимум косые черты, иначе 0 точек) должен быть на косой черте 0
Если предположить, что конечная точка D-пути находится в точке k, k ∈ {-D, -D + 2, ... D-2, D}, то (D+1)-путь, состоящий из предыдущих D -путь, считается заканчивающимся на k линии, то после перемещения на один шаг по горизонтали (вертикали) конечная точка должна находиться на линии k+1, k-1, и даже если за ней следует косая черта, она все еще находится на линии k+1, k-1.
Таким образом, (D+1)-путь должен заканчиваться косой чертой {-D ± 1, (-D + 2) ± 1 ... D ± 1} = { -D - 1, -D + 1, ... D - 1, D + 1}, значит, доказано.
Эта лемма утверждает, чтоКогда D нечетно, все D-пути попадают на нечетные k строк, а когда D четно, все D-пути попадают на четные k строк.
Лемма 2. Самая дальняя точка 0-пути есть (x, x), где x ∈ min(z - 1 || az ≠ bz или z > M или z > N). Самая дальняя точка D-пути находится на линии k, которую можно разложить на (D-1)-путь на линии k-1, за которым следует боковое ребро, затем гипотенуза настолько длинной, насколько это возможно, и на k+ (D-1)-пути на 1-й линии, за которой следует вертикальное ребро, за которым следует гипотенуза настолько длинной, насколько это возможно
Докажи, посмотри на бумагу
Эта лемма содержит жадный принцип:D-путь можно получить, жадно расширив самую дальнюю точку (D-1)-пути.
Это отвечает условиям качественного diff 1,3, совпадения как можно большего количества одинаковых символов, такой ситуации не будет
Например
k = -1
Его также можно сдвинуть вниз на k=0, то есть (2, 2) можно сдвинуть вниз до (2, 3)
Поскольку (4, 5) дальше, чем (2, 3) на линии k = -1, мы выбираем k = -2
k = 1
Его можно сдвинуть вправо от k = 0, то есть (2, 2) сдвинется вправо к (3, 2) через косую черту к (5, 4)
Его также можно сдвинуть вниз на k = 2, то есть (3, 1) перемещается вниз к (3, 2) по диагональной линии к (5, 4)
Мы выберем начальную точку с большим значением X, потому что удаление является приоритетом, поэтому выберите K = 2
k = 3, может перемещаться вправо только от k = 2, т. е. (3, 1) перемещается вправо к (4, 1) через косую черту к (5, 2)
Простая реализация
Поддельный код
Некоторые примечания:
- Массив V содержит самые дальние точки D-пути, V[-D], V[-D+2]...V[D-2], V[D]
- Значение, хранящееся в v[k], представляет собой значение координаты абсцисс x самой дальней точки на линии k, поскольку y можно вычислить как x - k
- v[1] = 0, установите начальную точку как (0, -1), которая используется для поиска самой дальней точки достижения 0-пути
js: попробуйте вставить прямо в консоль Chrome?
function myers(stra, strb) {
let n = stra.length
let m = strb.length
let v = {
'1': 0
}
let vs = {
'0': { '1': 0 }
}
let d
loop:
for (d = 0; d <= n + m; d++) {
let tmp = {}
for (let k = -d; k <= d; k += 2) {
let down = k == -d || k != d && v[k + 1] > v[k - 1]
let kPrev = down ? k + 1 : k - 1
let xStart = v[kPrev]
let yStart = xStart - kPrev
let xMid = down ? xStart : xStart + 1
let yMid = xMid - k
let xEnd = xMid
let yEnd = yMid
while(xEnd < n && yEnd < m && stra[xEnd] === strb[yEnd]) {
xEnd++
yEnd++
}
v[k] = xEnd
tmp[k] = xEnd
if (xEnd == n && yEnd == m) {
vs[d] = tmp
let snakes = solution(vs, n, m, d)
printRes(snakes, stra, strb)
break loop
}
}
vs[d] = tmp
}
}
function solution(vs, n, m, d) {
let snakes = []
let p = { x: n, y: m }
for (; d > 0; d--) {
let v = vs[d]
let vPrev = vs[d-1]
let k = p.x - p.y
let xEnd = v[k]
let yEnd = xEnd - k
let down = k == -d || k != d && vPrev[k + 1] > vPrev[k - 1]
let kPrev = down ? k + 1 : k - 1
let xStart = vPrev[kPrev]
let yStart = xStart - kPrev
let xMid = down ? xStart : xStart + 1
let yMid = xMid - k
snakes.unshift([xStart, xMid, xEnd])
p.x = xStart
p.y = yStart
}
return snakes
}
function printRes(snakes, stra, strb) {
let grayColor = 'color: gray'
let redColor = 'color: red'
let greenColor = 'color: green'
let consoleStr = ''
let args = []
let yOffset = 0
snakes.forEach((snake, index) => {
let s = snake[0]
let m = snake[1]
let e = snake[2]
let large = s
if (index === 0 && s !== 0) {
for (let j = 0; j < s; j++) {
consoleStr += `%c${stra[j]}`
args.push(grayColor)
yOffset++
}
}
// 删除
if (m - s == 1) {
consoleStr += `%c${stra[s]}`
args.push(redColor)
large = m
// 添加
} else {
consoleStr += `%c${strb[yOffset]}`
args.push(greenColor)
yOffset++
}
// 不变
for (let i = 0; i < e - large; i++) {
consoleStr += `%c${stra[large+i]}`
args.push(grayColor)
yOffset++
}
})
console.log(consoleStr, ...args)
}
let s1 = 'ABCABBA'
let s2 = 'CBABAC'
myers(s1, s2)
Временная сложность: ожидается O(M+N+D^2), в худшем случае O((M+N)D)
Лично я хотел бы объяснить, что наихудший случай возникает, когда две строки a и b почти равны, и вероятность появления очень мала.
Космическая сложность: O(D^2)
оптимизация
Оптимизация пространственной сложности O(D) приведена в статье, и я напишу ее позже. Заинтересованные друзья могут проверить в ссылке
Ссылаться на
[1] http://xmailserver.org/diff2.pdf
[2] http://cjting.me/misc/how-git-generate-diff/
[3] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
[4] https://www.codeproject.com/articles/42279/investigating-myers-diff-algorithm-part-of