1 // Copyright 2017, The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE.md file.
5 // Package diff implements an algorithm for producing edit-scripts.
6 // The edit-script is a sequence of operations needed to transform one list
7 // of symbols into another (or vice-versa). The edits allowed are insertions,
8 // deletions, and modifications. The summation of all edits is called the
9 // Levenshtein distance as this problem is well-known in computer science.
11 // This package prioritizes performance over accuracy. That is, the run time
12 // is more important than obtaining a minimal Levenshtein distance.
15 // EditType represents a single operation within an edit-script.
19 // Identity indicates that a symbol pair is identical in both list X and Y.
20 Identity EditType = iota
21 // UniqueX indicates that a symbol only exists in X and not Y.
23 // UniqueY indicates that a symbol only exists in Y and not X.
25 // Modified indicates that a symbol pair is a modification of each other.
29 // EditScript represents the series of differences between two lists.
30 type EditScript []EditType
32 // String returns a human-readable string representing the edit-script where
33 // Identity, UniqueX, UniqueY, and Modified are represented by the
34 // '.', 'X', 'Y', and 'M' characters, respectively.
35 func (es EditScript) String() string {
36 b := make([]byte, len(es))
37 for i, e := range es {
48 panic("invalid edit-type")
54 // stats returns a histogram of the number of each type of edit operation.
55 func (es EditScript) stats() (s struct{ NI, NX, NY, NM int }) {
56 for _, e := range es {
67 panic("invalid edit-type")
73 // Dist is the Levenshtein distance and is guaranteed to be 0 if and only if
74 // lists X and Y are equal.
75 func (es EditScript) Dist() int { return len(es) - es.stats().NI }
77 // LenX is the length of the X list.
78 func (es EditScript) LenX() int { return len(es) - es.stats().NY }
80 // LenY is the length of the Y list.
81 func (es EditScript) LenY() int { return len(es) - es.stats().NX }
83 // EqualFunc reports whether the symbols at indexes ix and iy are equal.
84 // When called by Difference, the index is guaranteed to be within nx and ny.
85 type EqualFunc func(ix int, iy int) Result
87 // Result is the result of comparison.
88 // NSame is the number of sub-elements that are equal.
89 // NDiff is the number of sub-elements that are not equal.
90 type Result struct{ NSame, NDiff int }
92 // Equal indicates whether the symbols are equal. Two symbols are equal
93 // if and only if NDiff == 0. If Equal, then they are also Similar.
94 func (r Result) Equal() bool { return r.NDiff == 0 }
96 // Similar indicates whether two symbols are similar and may be represented
97 // by using the Modified type. As a special case, we consider binary comparisons
98 // (i.e., those that return Result{1, 0} or Result{0, 1}) to be similar.
100 // The exact ratio of NSame to NDiff to determine similarity may change.
101 func (r Result) Similar() bool {
102 // Use NSame+1 to offset NSame so that binary comparisons are similar.
103 return r.NSame+1 >= r.NDiff
106 // Difference reports whether two lists of lengths nx and ny are equal
107 // given the definition of equality provided as f.
109 // This function returns an edit-script, which is a sequence of operations
110 // needed to convert one list into the other. The following invariants for
111 // the edit-script are maintained:
112 // • eq == (es.Dist()==0)
116 // This algorithm is not guaranteed to be an optimal solution (i.e., one that
117 // produces an edit-script with a minimal Levenshtein distance). This algorithm
118 // favors performance over optimality. The exact output is not guaranteed to
119 // be stable and may change over time.
120 func Difference(nx, ny int, f EqualFunc) (es EditScript) {
121 // This algorithm is based on traversing what is known as an "edit-graph".
122 // See Figure 1 from "An O(ND) Difference Algorithm and Its Variations"
123 // by Eugene W. Myers. Since D can be as large as N itself, this is
124 // effectively O(N^2). Unlike the algorithm from that paper, we are not
125 // interested in the optimal path, but at least some "decent" path.
127 // For example, let X and Y be lists of symbols:
128 // X = [A B C A B B A]
131 // The edit-graph can be drawn as the following:
134 // C │_|_|\|_|_|_|_│ 0
135 // B │_|\|_|_|\|\|_│ 1
136 // A │\|_|_|\|_|_|\│ 2
137 // B │_|\|_|_|\|\|_│ 3
138 // A │\|_|_|\|_|_|\│ 4
139 // C │ | |\| | | | │ 5
143 // List X is written along the horizontal axis, while list Y is written
144 // along the vertical axis. At any point on this grid, if the symbol in
145 // list X matches the corresponding symbol in list Y, then a '\' is drawn.
146 // The goal of any minimal edit-script algorithm is to find a path from the
147 // top-left corner to the bottom-right corner, while traveling through the
148 // fewest horizontal or vertical edges.
149 // A horizontal edge is equivalent to inserting a symbol from list X.
150 // A vertical edge is equivalent to inserting a symbol from list Y.
151 // A diagonal edge is equivalent to a matching symbol between both X and Y.
154 // • 0 ≤ fwdPath.X ≤ (fwdFrontier.X, revFrontier.X) ≤ revPath.X ≤ nx
155 // • 0 ≤ fwdPath.Y ≤ (fwdFrontier.Y, revFrontier.Y) ≤ revPath.Y ≤ ny
158 // • fwdFrontier.X < revFrontier.X
159 // • fwdFrontier.Y < revFrontier.Y
160 // Unless, it is time for the algorithm to terminate.
161 fwdPath := path{+1, point{0, 0}, make(EditScript, 0, (nx+ny)/2)}
162 revPath := path{-1, point{nx, ny}, make(EditScript, 0)}
163 fwdFrontier := fwdPath.point // Forward search frontier
164 revFrontier := revPath.point // Reverse search frontier
166 // Search budget bounds the cost of searching for better paths.
167 // The longest sequence of non-matching symbols that can be tolerated is
168 // approximately the square-root of the search budget.
169 searchBudget := 4 * (nx + ny) // O(n)
171 // The algorithm below is a greedy, meet-in-the-middle algorithm for
172 // computing sub-optimal edit-scripts between two lists.
174 // The algorithm is approximately as follows:
175 // • Searching for differences switches back-and-forth between
176 // a search that starts at the beginning (the top-left corner), and
177 // a search that starts at the end (the bottom-right corner). The goal of
178 // the search is connect with the search from the opposite corner.
179 // • As we search, we build a path in a greedy manner, where the first
180 // match seen is added to the path (this is sub-optimal, but provides a
181 // decent result in practice). When matches are found, we try the next pair
182 // of symbols in the lists and follow all matches as far as possible.
183 // • When searching for matches, we search along a diagonal going through
184 // through the "frontier" point. If no matches are found, we advance the
185 // frontier towards the opposite corner.
186 // • This algorithm terminates when either the X coordinates or the
187 // Y coordinates of the forward and reverse frontier points ever intersect.
189 // This algorithm is correct even if searching only in the forward direction
190 // or in the reverse direction. We do both because it is commonly observed
191 // that two lists commonly differ because elements were added to the front
192 // or end of the other list.
194 // Running the tests with the "debug" build tag prints a visualization of
195 // the algorithm running in real-time. This is educational for understanding
196 // how the algorithm works. See debug_enable.go.
197 f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es)
199 // Forward search from the beginning.
200 if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 {
203 for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ {
204 // Search in a diagonal pattern for a match.
206 p := point{fwdFrontier.X + z, fwdFrontier.Y - z}
208 case p.X >= revPath.X || p.Y < fwdPath.Y:
209 stop1 = true // Hit top-right corner
210 case p.Y >= revPath.Y || p.X < fwdPath.X:
211 stop2 = true // Hit bottom-left corner
212 case f(p.X, p.Y).Equal():
213 // Match found, so connect the path to this point.
214 fwdPath.connect(p, f)
215 fwdPath.append(Identity)
216 // Follow sequence of matches as far as possible.
217 for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y {
218 if !f(fwdPath.X, fwdPath.Y).Equal() {
221 fwdPath.append(Identity)
223 fwdFrontier = fwdPath.point
224 stop1, stop2 = true, true
226 searchBudget-- // Match not found
230 // Advance the frontier towards reverse point.
231 if revPath.X-fwdFrontier.X >= revPath.Y-fwdFrontier.Y {
237 // Reverse search from the end.
238 if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 {
241 for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ {
242 // Search in a diagonal pattern for a match.
244 p := point{revFrontier.X - z, revFrontier.Y + z}
246 case fwdPath.X >= p.X || revPath.Y < p.Y:
247 stop1 = true // Hit bottom-left corner
248 case fwdPath.Y >= p.Y || revPath.X < p.X:
249 stop2 = true // Hit top-right corner
250 case f(p.X-1, p.Y-1).Equal():
251 // Match found, so connect the path to this point.
252 revPath.connect(p, f)
253 revPath.append(Identity)
254 // Follow sequence of matches as far as possible.
255 for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y {
256 if !f(revPath.X-1, revPath.Y-1).Equal() {
259 revPath.append(Identity)
261 revFrontier = revPath.point
262 stop1, stop2 = true, true
264 searchBudget-- // Match not found
268 // Advance the frontier towards forward point.
269 if revFrontier.X-fwdPath.X >= revFrontier.Y-fwdPath.Y {
276 // Join the forward and reverse paths and then append the reverse path.
277 fwdPath.connect(revPath.point, f)
278 for i := len(revPath.es) - 1; i >= 0; i-- {
280 revPath.es = revPath.es[:i]
288 dir int // +1 if forward, -1 if reverse
289 point // Leading point of the EditScript path
293 // connect appends any necessary Identity, Modified, UniqueX, or UniqueY types
294 // to the edit-script to connect p.point to dst.
295 func (p *path) connect(dst point, f EqualFunc) {
297 // Connect in forward direction.
298 for dst.X > p.X && dst.Y > p.Y {
299 switch r := f(p.X, p.Y); {
304 case dst.X-p.X >= dst.Y-p.Y:
317 // Connect in reverse direction.
318 for p.X > dst.X && p.Y > dst.Y {
319 switch r := f(p.X-1, p.Y-1); {
324 case p.Y-dst.Y >= p.X-dst.X:
339 func (p *path) append(t EditType) {
340 p.es = append(p.es, t)
342 case Identity, Modified:
352 type point struct{ X, Y int }
354 func (p *point) add(dx, dy int) { p.X += dx; p.Y += dy }
356 // zigzag maps a consecutive sequence of integers to a zig-zag sequence.
357 // [0 1 2 3 4 5 ...] => [0 -1 +1 -2 +2 ...]
358 func zigzag(x int) int {