3 * New version of the difference engine
5 * Copyright © 2008 Guy Van den Broeck <guy@guyvdb.eu>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 * http://www.gnu.org/copyleft/gpl.html
23 * @ingroup DifferenceEngine
27 * This diff implementation is mainly lifted from the LCS algorithm of the Eclipse project which
28 * in turn is based on Myers' "An O(ND) difference algorithm and its variations"
29 * (http://citeseer.ist.psu.edu/myers86ond.html) with range compression (see Wu et al.'s
30 * "An O(NP) Sequence Comparison Algorithm").
32 * This implementation supports an upper bound on the excution time.
34 * Complexity: O((M + N)D) worst case time, O(M + N + D^2) expected time, O(M + N) space
36 * @author Guy Van den Broeck
37 * @ingroup DifferenceEngine
51 private $maxDifferences;
52 private $lcsLengthCorrectedForHeuristic = false;
58 public $heuristicUsed;
60 function __construct( $tooLong = 2000000, $powLimit = 1.45 ) {
61 $this->tooLong
= $tooLong;
62 $this->powLimit
= $powLimit;
65 public function diff( /*array*/ $from, /*array*/ $to ) {
66 // remember initial lengths
70 $this->heuristicUsed
= false;
73 $removed = $m > 0 ?
array_fill( 0, $m, true ) : array();
74 $added = $n > 0 ?
array_fill( 0, $n, true ) : array();
76 // reduce the complexity for the next step (intentionally done twice)
77 // remove common tokens at the start
79 while ( $i < $m && $i < $n && $from[$i] === $to[$i] ) {
80 $removed[$i] = $added[$i] = false;
81 unset( $from[$i], $to[$i] );
85 // remove common tokens at the end
87 while ( $i +
$j <= $m && $i +
$j <= $n && $from[$m - $j] === $to[$n - $j] ) {
88 $removed[$m - $j] = $added[$n - $j] = false;
89 unset( $from[$m - $j], $to[$n - $j] );
93 $this->from
= $newFromIndex = $this->to
= $newToIndex = array();
95 // remove tokens not in both sequences
97 foreach ( $from as $key ) {
98 $shared[$key] = false;
101 foreach ( $to as $index => &$el ) {
102 if ( array_key_exists( $el, $shared ) ) {
106 $newToIndex[] = $index;
109 foreach ( $from as $index => &$el ) {
110 if ( $shared[$el] ) {
113 $newFromIndex[] = $index;
117 unset( $shared, $from, $to );
119 $this->m
= count( $this->from
);
120 $this->n
= count( $this->to
);
122 $this->removed
= $this->m
> 0 ?
array_fill( 0, $this->m
, true ) : array();
123 $this->added
= $this->n
> 0 ?
array_fill( 0, $this->n
, true ) : array();
125 if ( $this->m
== 0 ||
$this->n
== 0 ) {
128 $this->maxDifferences
= ceil( ( $this->m +
$this->n
) / 2.0 );
129 if ( $this->m
* $this->n
> $this->tooLong
) {
130 // limit complexity to D^POW_LIMIT for long sequences
131 $this->maxDifferences
= floor( pow( $this->maxDifferences
, $this->powLimit
- 1.0 ) );
132 wfDebug( "Limiting max number of differences to $this->maxDifferences\n" );
136 * The common prefixes and suffixes are always part of some LCS, include
137 * them now to reduce our search space
139 $max = min( $this->m
, $this->n
);
140 for ( $forwardBound = 0; $forwardBound < $max
141 && $this->from
[$forwardBound] === $this->to
[$forwardBound];
143 $this->removed
[$forwardBound] = $this->added
[$forwardBound] = false;
146 $backBoundL1 = $this->m
- 1;
147 $backBoundL2 = $this->n
- 1;
149 while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
150 && $this->from
[$backBoundL1] === $this->to
[$backBoundL2] ) {
151 $this->removed
[$backBoundL1--] = $this->added
[$backBoundL2--] = false;
154 $temp = array_fill( 0, $this->m +
$this->n +
1, 0 );
155 $V = array( $temp, $temp );
156 $snake = array( 0, 0, 0 );
158 $this->length
= $forwardBound +
$this->m
- $backBoundL1 - 1
159 +
$this->lcs_rec( $forwardBound, $backBoundL1,
160 $forwardBound, $backBoundL2, $V, $snake );
166 $this->length +
= $i +
$j - 1;
168 foreach ( $this->removed
as $key => &$removed_elem ) {
169 if ( !$removed_elem ) {
170 $removed[$newFromIndex[$key]] = false;
173 foreach ( $this->added
as $key => &$added_elem ) {
174 if ( !$added_elem ) {
175 $added[$newToIndex[$key]] = false;
178 $this->removed
= $removed;
179 $this->added
= $added;
182 function diff_range( $from_lines, $to_lines ) {
183 // Diff and store locally
184 $this->diff( $from_lines, $to_lines );
185 unset( $from_lines, $to_lines );
189 while ( $xi < $this->m ||
$yi < $this->n
) {
191 while ( $xi < $this->m
&& $yi < $this->n
192 && !$this->removed
[$xi]
193 && !$this->added
[$yi] ) {
197 // Find deletes & adds.
199 while ( $xi < $this->m
&& $this->removed
[$xi] ) {
204 while ( $yi < $this->n
&& $this->added
[$yi] ) {
208 if ( $xi > $xstart ||
$yi > $ystart ) {
209 $ranges[] = new RangeDifference( $xstart, $xi,
216 private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
217 // check that both sequences are non-empty
218 if ( $bottoml1 > $topl1 ||
$bottoml2 > $topl2 ) {
222 $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
223 $topl2, $V, $snake );
225 // need to store these so we don't lose them when they're
226 // overwritten by the recursion
231 // the middle snake is part of the LCS, store it
232 for ( $i = 0; $i < $len; ++
$i ) {
233 $this->removed
[$startx +
$i] = $this->added
[$starty +
$i] = false;
238 +
$this->lcs_rec( $bottoml1, $startx - 1, $bottoml2,
239 $starty - 1, $V, $snake )
240 +
$this->lcs_rec( $startx +
$len, $topl1, $starty +
$len,
241 $topl2, $V, $snake );
242 } else if ( $d == 1 ) {
244 * In this case the sequences differ by exactly 1 line. We have
245 * already saved all the lines after the difference in the for loop
246 * above, now we need to save all the lines before the difference.
248 $max = min( $startx - $bottoml1, $starty - $bottoml2 );
249 for ( $i = 0; $i < $max; ++
$i ) {
250 $this->removed
[$bottoml1 +
$i] =
251 $this->added
[$bottoml2 +
$i] = false;
258 private function find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
259 $from = &$this->from
;
263 $snake0 = &$snake[0];
264 $snake1 = &$snake[1];
265 $snake2 = &$snake[2];
266 $bottoml1_min_1 = $bottoml1 -1;
267 $bottoml2_min_1 = $bottoml2 -1;
268 $N = $topl1 - $bottoml1_min_1;
269 $M = $topl2 - $bottoml2_min_1;
271 $maxabsx = $N +
$bottoml1;
272 $maxabsy = $M +
$bottoml2;
273 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
275 // value_to_add_forward: a 0 or 1 that we add to the start
276 // offset to make it odd/even
277 if ( ( $M & 1 ) == 1 ) {
278 $value_to_add_forward = 1;
280 $value_to_add_forward = 0;
283 if ( ( $N & 1 ) == 1 ) {
284 $value_to_add_backward = 1;
286 $value_to_add_backward = 0;
289 $start_forward = -$M;
291 $start_backward = -$N;
294 $limit_min_1 = $limit - 1;
295 $limit_plus_1 = $limit +
1;
297 $V0[$limit_plus_1] = 0;
298 $V1[$limit_min_1] = $N;
299 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
301 if ( ( $delta & 1 ) == 1 ) {
302 for ( $d = 0; $d <= $limit; ++
$d ) {
303 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
304 $end_diag = min( $end_forward, $d );
305 $value_to_add_forward = 1 - $value_to_add_forward;
307 // compute forward furthest reaching paths
308 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
309 if ( $k == -$d ||
( $k < $d
310 && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] ) ) {
311 $x = $V0[$limit_plus_1 +
$k];
313 $x = $V0[$limit_min_1 +
$k] +
1;
316 $absx = $snake0 = $x +
$bottoml1;
317 $absy = $snake1 = $x - $k +
$bottoml2;
319 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
323 $x = $absx -$bottoml1;
325 $snake2 = $absx -$snake0;
326 $V0[$limit +
$k] = $x;
327 if ( $k >= $delta - $d +
1 && $k <= $delta +
$d - 1
328 && $x >= $V1[$limit +
$k - $delta] ) {
332 // check to see if we can cut down the diagonal range
333 if ( $x >= $N && $end_forward > $k - 1 ) {
334 $end_forward = $k - 1;
335 } else if ( $absy - $bottoml2 >= $M ) {
336 $start_forward = $k +
1;
337 $value_to_add_forward = 0;
341 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
342 $end_diag = min( $end_backward, $d );
343 $value_to_add_backward = 1 - $value_to_add_backward;
345 // compute backward furthest reaching paths
346 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
348 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] ) ) {
349 $x = $V1[$limit_min_1 +
$k];
351 $x = $V1[$limit_plus_1 +
$k] - 1;
354 $y = $x - $k - $delta;
357 while ( $x > 0 && $y > 0
358 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1] ) {
363 $V1[$limit +
$k] = $x;
365 // check to see if we can cut down our diagonal range
367 $start_backward = $k +
1;
368 $value_to_add_backward = 0;
369 } else if ( $y <= 0 && $end_backward > $k - 1 ) {
370 $end_backward = $k - 1;
375 for ( $d = 0; $d <= $limit; ++
$d ) {
376 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
377 $end_diag = min( $end_forward, $d );
378 $value_to_add_forward = 1 - $value_to_add_forward;
380 // compute forward furthest reaching paths
381 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
383 ||
( $k < $d && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] ) ) {
384 $x = $V0[$limit_plus_1 +
$k];
386 $x = $V0[$limit_min_1 +
$k] +
1;
389 $absx = $snake0 = $x +
$bottoml1;
390 $absy = $snake1 = $x - $k +
$bottoml2;
392 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
396 $x = $absx -$bottoml1;
397 $snake2 = $absx -$snake0;
398 $V0[$limit +
$k] = $x;
400 // check to see if we can cut down the diagonal range
401 if ( $x >= $N && $end_forward > $k - 1 ) {
402 $end_forward = $k - 1;
403 } else if ( $absy -$bottoml2 >= $M ) {
404 $start_forward = $k +
1;
405 $value_to_add_forward = 0;
409 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
410 $end_diag = min( $end_backward, $d );
411 $value_to_add_backward = 1 - $value_to_add_backward;
413 // compute backward furthest reaching paths
414 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
416 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] ) ) {
417 $x = $V1[$limit_min_1 +
$k];
419 $x = $V1[$limit_plus_1 +
$k] - 1;
422 $y = $x - $k - $delta;
425 while ( $x > 0 && $y > 0
426 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1] ) {
431 $V1[$limit +
$k] = $x;
433 if ( $k >= -$delta - $d && $k <= $d - $delta
434 && $x <= $V0[$limit +
$k +
$delta] ) {
435 $snake0 = $bottoml1 +
$x;
436 $snake1 = $bottoml2 +
$y;
440 // check to see if we can cut down our diagonal range
442 $start_backward = $k +
1;
443 $value_to_add_backward = 0;
444 } else if ( $y <= 0 && $end_backward > $k - 1 ) {
445 $end_backward = $k - 1;
451 * computing the true LCS is too expensive, instead find the diagonal
452 * with the most progress and pretend a midle snake of length 0 occurs
456 $most_progress = self
::findMostProgress( $M, $N, $limit, $V );
458 $snake0 = $bottoml1 +
$most_progress[0];
459 $snake1 = $bottoml2 +
$most_progress[1];
461 wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
462 $this->heuristicUsed
= true;
464 * HACK: since we didn't really finish the LCS computation
465 * we don't really know the length of the SES. We don't do
466 * anything with the result anyway, unless it's <=1. We know
467 * for a fact SES > 1 so 5 is as good a number as any to
472 private static function findMostProgress( $M, $N, $limit, $V ) {
475 if ( ( $M & 1 ) == ( $limit & 1 ) ) {
476 $forward_start_diag = max( -$M, -$limit );
478 $forward_start_diag = max( 1 - $M, -$limit );
481 $forward_end_diag = min( $N, $limit );
483 if ( ( $N & 1 ) == ( $limit & 1 ) ) {
484 $backward_start_diag = max( -$N, -$limit );
486 $backward_start_diag = max( 1 - $N, -$limit );
489 $backward_end_diag = -min( $M, $limit );
491 $temp = array( 0, 0, 0 );
494 $max_progress = array_fill( 0, ceil( max( $forward_end_diag - $forward_start_diag,
495 $backward_end_diag - $backward_start_diag ) / 2 ), $temp );
496 $num_progress = 0; // the 1st entry is current, it is initialized
499 // first search the forward diagonals
500 for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k +
= 2 ) {
501 $x = $V[0][$limit +
$k];
503 if ( $x > $N ||
$y > $M ) {
508 if ( $progress > $max_progress[0][2] ) {
510 $max_progress[0][0] = $x;
511 $max_progress[0][1] = $y;
512 $max_progress[0][2] = $progress;
513 } else if ( $progress == $max_progress[0][2] ) {
515 $max_progress[$num_progress][0] = $x;
516 $max_progress[$num_progress][1] = $y;
517 $max_progress[$num_progress][2] = $progress;
521 $max_progress_forward = true; // initially the maximum
522 // progress is in the forward
525 // now search the backward diagonals
526 for ( $k = $backward_start_diag; $k <= $backward_end_diag; $k +
= 2 ) {
527 $x = $V[1][$limit +
$k];
528 $y = $x - $k - $delta;
529 if ( $x < 0 ||
$y < 0 ) {
533 $progress = $N - $x +
$M - $y;
534 if ( $progress > $max_progress[0][2] ) {
536 $max_progress_forward = false;
537 $max_progress[0][0] = $x;
538 $max_progress[0][1] = $y;
539 $max_progress[0][2] = $progress;
540 } else if ( $progress == $max_progress[0][2] && !$max_progress_forward ) {
542 $max_progress[$num_progress][0] = $x;
543 $max_progress[$num_progress][1] = $y;
544 $max_progress[$num_progress][2] = $progress;
548 // return the middle diagonal with maximal progress.
549 return $max_progress[floor( $num_progress / 2 )];
552 public function getLcsLength() {
553 if ( $this->heuristicUsed
&& !$this->lcsLengthCorrectedForHeuristic
) {
554 $this->lcsLengthCorrectedForHeuristic
= true;
555 $this->length
= $this->m
-array_sum( $this->added
);
557 return $this->length
;
563 * Alternative representation of a set of changes, by the index
564 * ranges that are changed.
566 * @ingroup DifferenceEngine
568 class RangeDifference
{
578 function __construct( $leftstart, $leftend, $rightstart, $rightend ) {
579 $this->leftstart
= $leftstart;
580 $this->leftend
= $leftend;
581 $this->leftlength
= $leftend - $leftstart;
582 $this->rightstart
= $rightstart;
583 $this->rightend
= $rightend;
584 $this->rightlength
= $rightend - $rightstart;