/
doc.go
156 lines (137 loc) · 11.8 KB
/
doc.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// package lcs contains code to find longest-common-subsequences
// (and diffs)
package lcs
/*
Compute longest-common-subsequences of two slices A, B using
algorithms from Myers' paper. A longest-common-subsequence
(LCS from now on) of A and B is a maximal set of lexically increasing
pairs of subscripts (x,y) with A[x]==B[y]. There may be many LCS, but
they all have the same length. An LCS determines a sequence of edits
that changes A into B.
The key concept is the edit graph of A and B.
If A has length N and B has length M, then the edit graph has
vertices v[i][j] for 0 <= i <= N, 0 <= j <= M. There is a
horizontal edge from v[i][j] to v[i+1][j] whenever both are in
the graph, and a vertical edge from v[i][j] to f[i][j+1] similarly.
When A[i] == B[j] there is a diagonal edge from v[i][j] to v[i+1][j+1].
A path between in the graph between (0,0) and (N,M) determines a sequence
of edits converting A into B: each horizontal edge corresponds to removing
an element of A, and each vertical edge corresponds to inserting an
element of B.
A vertex (x,y) is on (forward) diagonal k if x-y=k. A path in the graph
is of length D if it has D non-diagonal edges. The algorithms generate
forward paths (in which at least one of x,y increases at each edge),
or backward paths (in which at least one of x,y decreases at each edge),
or a combination. (Note that the orientation is the traditional mathematical one,
with the origin in the lower-left corner.)
Here is the edit graph for A:"aabbaa", B:"aacaba". (I know the diagonals look weird.)
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
b | | | ___/‾‾‾ | ___/‾‾‾ | | |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
c | | | | | | |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a a b b a a
The algorithm labels a vertex (x,y) with D,k if it is on diagonal k and at
the end of a maximal path of length D. (Because x-y=k it suffices to remember
only the x coordinate of the vertex.)
The forward algorithm: Find the longest diagonal starting at (0,0) and
label its end with D=0,k=0. From that vertex take a vertical step and
then follow the longest diagonal (up and to the right), and label that vertex
with D=1,k=-1. From the D=0,k=0 point take a horizontal step and the follow
the longest diagonal (up and to the right) and label that vertex
D=1,k=1. In the same way, having labelled all the D vertices,
from a vertex labelled D,k find two vertices
tentatively labelled D+1,k-1 and D+1,k+1. There may be two on the same
diagonal, in which case take the one with the larger x.
Eventually the path gets to (N,M), and the diagonals on it are the LCS.
Here is the edit graph with the ends of D-paths labelled. (So, for instance,
0/2,2 indicates that x=2,y=2 is labelled with 0, as it should be, since the first
step is to go up the longest diagonal from (0,0).)
A:"aabbaa", B:"aacaba"
⊙ ------- ⊙ ------- ⊙ -------(3/3,6)------- ⊙ -------(3/5,6)-------(4/6,6)
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ -------(2/3,5)------- ⊙ ------- ⊙ ------- ⊙
b | | | ___/‾‾‾ | ___/‾‾‾ | | |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ -------(3/5,4)------- ⊙
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ -------(1/2,3)-------(2/3,3)------- ⊙ ------- ⊙ ------- ⊙
c | | | | | | |
⊙ ------- ⊙ -------(0/2,2)-------(1/3,2)-------(2/4,2)-------(3/5,2)-------(4/6,2)
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a | ___/‾‾‾ | ___/‾‾‾ | | | ___/‾‾‾ | ___/‾‾‾ |
⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙ ------- ⊙
a a b b a a
The 4-path is reconstructed starting at (4/6,6), horizontal to (3/5,6), diagonal to (3,4), vertical
to (2/3,3), horizontal to (1/2,3), vertical to (0/2,2), and diagonal to (0,0). As expected,
there are 4 non-diagonal steps, and the diagonals form an LCS.
There is a symmetric backward algorithm, which gives (backwards labels are prefixed with a colon):
A:"aabbaa", B:"aacaba"
⊙ -------- ⊙ -------- ⊙ -------- ⊙ -------- ⊙ -------- ⊙ -------- ⊙
a | ____/‾‾‾ | ____/‾‾‾ | | | ____/‾‾‾ | ____/‾‾‾ |
⊙ -------- ⊙ -------- ⊙ -------- ⊙ -------- ⊙ --------(:0/5,5)-------- ⊙
b | | | ____/‾‾‾ | ____/‾‾‾ | | |
⊙ -------- ⊙ -------- ⊙ --------(:1/3,4)-------- ⊙ -------- ⊙ -------- ⊙
a | ____/‾‾‾ | ____/‾‾‾ | | | ____/‾‾‾ | ____/‾‾‾ |
(:3/0,3)--------(:2/1,3)-------- ⊙ --------(:2/3,3)--------(:1/4,3)-------- ⊙ -------- ⊙
c | | | | | | |
⊙ -------- ⊙ -------- ⊙ --------(:3/3,2)--------(:2/4,2)-------- ⊙ -------- ⊙
a | ____/‾‾‾ | ____/‾‾‾ | | | ____/‾‾‾ | ____/‾‾‾ |
(:3/0,1)-------- ⊙ -------- ⊙ -------- ⊙ --------(:3/4,1)-------- ⊙ -------- ⊙
a | ____/‾‾‾ | ____/‾‾‾ | | | ____/‾‾‾ | ____/‾‾‾ |
(:4/0,0)-------- ⊙ -------- ⊙ -------- ⊙ --------(:4/4,0)-------- ⊙ -------- ⊙
a a b b a a
Neither of these is ideal for use in an editor, where it is undesirable to send very long diffs to the
front end. It's tricky to decide exactly what 'very long diffs' means, as "replace A by B" is very short.
We want to control how big D can be, by stopping when it gets too large. The forward algorithm then
privileges common prefixes, and the backward algorithm privileges common suffixes. Either is an undesirable
asymmetry.
Fortunately there is a two-sided algorithm, implied by results in Myers' paper. Here's what the labels in
the edit graph look like.
A:"aabbaa", B:"aacaba"
⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙
a | ____/‾‾‾‾ | ____/‾‾‾‾ | | | ____/‾‾‾‾ | ____/‾‾‾‾ |
⊙ --------- ⊙ --------- ⊙ --------- (2/3,5) --------- ⊙ --------- (:0/5,5)--------- ⊙
b | | | ____/‾‾‾‾ | ____/‾‾‾‾ | | |
⊙ --------- ⊙ --------- ⊙ --------- (:1/3,4)--------- ⊙ --------- ⊙ --------- ⊙
a | ____/‾‾‾‾ | ____/‾‾‾‾ | | | ____/‾‾‾‾ | ____/‾‾‾‾ |
⊙ --------- (:2/1,3)--------- (1/2,3) ---------(2:2/3,3)--------- (:1/4,3)--------- ⊙ --------- ⊙
c | | | | | | |
⊙ --------- ⊙ --------- (0/2,2) --------- (1/3,2) ---------(2:2/4,2)--------- ⊙ --------- ⊙
a | ____/‾‾‾‾ | ____/‾‾‾‾ | | | ____/‾‾‾‾ | ____/‾‾‾‾ |
⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙
a | ____/‾‾‾‾ | ____/‾‾‾‾ | | | ____/‾‾‾‾ | ____/‾‾‾‾ |
⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙ --------- ⊙
a a b b a a
The algorithm stopped when it saw the backwards 2-path ending at (1,3) and the forwards 2-path ending at (3,5). The criterion
is a backwards path ending at (u,v) and a forward path ending at (x,y), where u <= x and the two points are on the same
diagonal. (Here the edgegraph has a diagonal, but the criterion is x-y=u-v.) Myers proves there is a forward
2-path from (0,0) to (1,3), and that together with the backwards 2-path ending at (1,3) gives the expected 4-path.
Unfortunately the forward path has to be constructed by another run of the forward algorithm; it can't be found from the
computed labels. That is the worst case. Had the code noticed (x,y)=(u,v)=(3,3) the whole path could be reconstructed
from the edgegraph. The implementation looks for a number of special cases to try to avoid computing an extra forward path.
If the two-sided algorithm has stop early (because D has become too large) it will have found a forward LCS and a
backwards LCS. Ideally these go with disjoint prefixes and suffixes of A and B, but disjointness may fail and the two
computed LCS may conflict. (An easy example is where A is a suffix of B, and shares a short prefix. The backwards LCS
is all of A, and the forward LCS is a prefix of A.) The algorithm combines the two
to form a best-effort LCS. In the worst case the forward partial LCS may have to
be recomputed.
*/
/* Eugene Myers paper is titled
"An O(ND) Difference Algorithm and Its Variations"
and can be found at
http://www.xmailserver.org/diff2.pdf
(There is a generic implementation of the algorithm the repository with git hash
b9ad7e4ade3a686d608e44475390ad428e60e7fc)
*/