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 execution 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];
144 $this->removed
[$forwardBound] = $this->added
[$forwardBound] = false;
147 $backBoundL1 = $this->m
- 1;
148 $backBoundL2 = $this->n
- 1;
150 while ( $backBoundL1 >= $forwardBound && $backBoundL2 >= $forwardBound
151 && $this->from
[$backBoundL1] === $this->to
[$backBoundL2]
153 $this->removed
[$backBoundL1--] = $this->added
[$backBoundL2--] = false;
156 $temp = array_fill( 0, $this->m +
$this->n +
1, 0 );
157 $V = array( $temp, $temp );
158 $snake = array( 0, 0, 0 );
160 $this->length
= $forwardBound +
$this->m
- $backBoundL1 - 1
174 $this->length +
= $i +
$j - 1;
176 foreach ( $this->removed
as $key => &$removed_elem ) {
177 if ( !$removed_elem ) {
178 $removed[$newFromIndex[$key]] = false;
181 foreach ( $this->added
as $key => &$added_elem ) {
182 if ( !$added_elem ) {
183 $added[$newToIndex[$key]] = false;
186 $this->removed
= $removed;
187 $this->added
= $added;
190 function diff_range( $from_lines, $to_lines ) {
191 // Diff and store locally
192 $this->diff( $from_lines, $to_lines );
193 unset( $from_lines, $to_lines );
197 while ( $xi < $this->m ||
$yi < $this->n
) {
199 while ( $xi < $this->m
&& $yi < $this->n
200 && !$this->removed
[$xi]
201 && !$this->added
[$yi]
206 // Find deletes & adds.
208 while ( $xi < $this->m
&& $this->removed
[$xi] ) {
213 while ( $yi < $this->n
&& $this->added
[$yi] ) {
217 if ( $xi > $xstart ||
$yi > $ystart ) {
218 $ranges[] = new RangeDifference( $xstart, $xi, $ystart, $yi );
225 private function lcs_rec( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
226 // check that both sequences are non-empty
227 if ( $bottoml1 > $topl1 ||
$bottoml2 > $topl2 ) {
231 $d = $this->find_middle_snake( $bottoml1, $topl1, $bottoml2,
232 $topl2, $V, $snake );
234 // need to store these so we don't lose them when they're
235 // overwritten by the recursion
240 // the middle snake is part of the LCS, store it
241 for ( $i = 0; $i < $len; ++
$i ) {
242 $this->removed
[$startx +
$i] = $this->added
[$starty +
$i] = false;
247 +
$this->lcs_rec( $bottoml1, $startx - 1, $bottoml2,
248 $starty - 1, $V, $snake )
249 +
$this->lcs_rec( $startx +
$len, $topl1, $starty +
$len,
250 $topl2, $V, $snake );
251 } elseif ( $d == 1 ) {
253 * In this case the sequences differ by exactly 1 line. We have
254 * already saved all the lines after the difference in the for loop
255 * above, now we need to save all the lines before the difference.
257 $max = min( $startx - $bottoml1, $starty - $bottoml2 );
258 for ( $i = 0; $i < $max; ++
$i ) {
259 $this->removed
[$bottoml1 +
$i] =
260 $this->added
[$bottoml2 +
$i] = false;
269 private function find_middle_snake( $bottoml1, $topl1, $bottoml2, $topl2, &$V, &$snake ) {
270 $from = &$this->from
;
274 $snake0 = &$snake[0];
275 $snake1 = &$snake[1];
276 $snake2 = &$snake[2];
277 $bottoml1_min_1 = $bottoml1 - 1;
278 $bottoml2_min_1 = $bottoml2 - 1;
279 $N = $topl1 - $bottoml1_min_1;
280 $M = $topl2 - $bottoml2_min_1;
282 $maxabsx = $N +
$bottoml1;
283 $maxabsy = $M +
$bottoml2;
284 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
286 // value_to_add_forward: a 0 or 1 that we add to the start
287 // offset to make it odd/even
288 if ( ( $M & 1 ) == 1 ) {
289 $value_to_add_forward = 1;
291 $value_to_add_forward = 0;
294 if ( ( $N & 1 ) == 1 ) {
295 $value_to_add_backward = 1;
297 $value_to_add_backward = 0;
300 $start_forward = -$M;
302 $start_backward = -$N;
305 $limit_min_1 = $limit - 1;
306 $limit_plus_1 = $limit +
1;
308 $V0[$limit_plus_1] = 0;
309 $V1[$limit_min_1] = $N;
310 $limit = min( $this->maxDifferences
, ceil( ( $N +
$M ) / 2 ) );
312 if ( ( $delta & 1 ) == 1 ) {
313 for ( $d = 0; $d <= $limit; ++
$d ) {
314 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
315 $end_diag = min( $end_forward, $d );
316 $value_to_add_forward = 1 - $value_to_add_forward;
318 // compute forward furthest reaching paths
319 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
320 if ( $k == -$d ||
( $k < $d
321 && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] )
323 $x = $V0[$limit_plus_1 +
$k];
325 $x = $V0[$limit_min_1 +
$k] +
1;
328 $absx = $snake0 = $x +
$bottoml1;
329 $absy = $snake1 = $x - $k +
$bottoml2;
331 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
335 $x = $absx - $bottoml1;
337 $snake2 = $absx - $snake0;
338 $V0[$limit +
$k] = $x;
339 if ( $k >= $delta - $d +
1 && $k <= $delta +
$d - 1
340 && $x >= $V1[$limit +
$k - $delta]
345 // check to see if we can cut down the diagonal range
346 if ( $x >= $N && $end_forward > $k - 1 ) {
347 $end_forward = $k - 1;
348 } elseif ( $absy - $bottoml2 >= $M ) {
349 $start_forward = $k +
1;
350 $value_to_add_forward = 0;
354 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
355 $end_diag = min( $end_backward, $d );
356 $value_to_add_backward = 1 - $value_to_add_backward;
358 // compute backward furthest reaching paths
359 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
361 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] )
363 $x = $V1[$limit_min_1 +
$k];
365 $x = $V1[$limit_plus_1 +
$k] - 1;
368 $y = $x - $k - $delta;
371 while ( $x > 0 && $y > 0
372 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]
378 $V1[$limit +
$k] = $x;
380 // check to see if we can cut down our diagonal range
382 $start_backward = $k +
1;
383 $value_to_add_backward = 0;
384 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
385 $end_backward = $k - 1;
390 for ( $d = 0; $d <= $limit; ++
$d ) {
391 $start_diag = max( $value_to_add_forward +
$start_forward, -$d );
392 $end_diag = min( $end_forward, $d );
393 $value_to_add_forward = 1 - $value_to_add_forward;
395 // compute forward furthest reaching paths
396 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
398 ||
( $k < $d && $V0[$limit_min_1 +
$k] < $V0[$limit_plus_1 +
$k] )
400 $x = $V0[$limit_plus_1 +
$k];
402 $x = $V0[$limit_min_1 +
$k] +
1;
405 $absx = $snake0 = $x +
$bottoml1;
406 $absy = $snake1 = $x - $k +
$bottoml2;
408 while ( $absx < $maxabsx && $absy < $maxabsy && $from[$absx] === $to[$absy] ) {
412 $x = $absx - $bottoml1;
413 $snake2 = $absx - $snake0;
414 $V0[$limit +
$k] = $x;
416 // check to see if we can cut down the diagonal range
417 if ( $x >= $N && $end_forward > $k - 1 ) {
418 $end_forward = $k - 1;
419 } elseif ( $absy - $bottoml2 >= $M ) {
420 $start_forward = $k +
1;
421 $value_to_add_forward = 0;
425 $start_diag = max( $value_to_add_backward +
$start_backward, -$d );
426 $end_diag = min( $end_backward, $d );
427 $value_to_add_backward = 1 - $value_to_add_backward;
429 // compute backward furthest reaching paths
430 for ( $k = $start_diag; $k <= $end_diag; $k +
= 2 ) {
432 ||
( $k != -$d && $V1[$limit_min_1 +
$k] < $V1[$limit_plus_1 +
$k] )
434 $x = $V1[$limit_min_1 +
$k];
436 $x = $V1[$limit_plus_1 +
$k] - 1;
439 $y = $x - $k - $delta;
442 while ( $x > 0 && $y > 0
443 && $from[$x +
$bottoml1_min_1] === $to[$y +
$bottoml2_min_1]
449 $V1[$limit +
$k] = $x;
451 if ( $k >= -$delta - $d && $k <= $d - $delta
452 && $x <= $V0[$limit +
$k +
$delta]
454 $snake0 = $bottoml1 +
$x;
455 $snake1 = $bottoml2 +
$y;
460 // check to see if we can cut down our diagonal range
462 $start_backward = $k +
1;
463 $value_to_add_backward = 0;
464 } elseif ( $y <= 0 && $end_backward > $k - 1 ) {
465 $end_backward = $k - 1;
471 * computing the true LCS is too expensive, instead find the diagonal
472 * with the most progress and pretend a midle snake of length 0 occurs
476 $most_progress = self
::findMostProgress( $M, $N, $limit, $V );
478 $snake0 = $bottoml1 +
$most_progress[0];
479 $snake1 = $bottoml2 +
$most_progress[1];
481 wfDebug( "Computing the LCS is too expensive. Using a heuristic.\n" );
482 $this->heuristicUsed
= true;
485 * HACK: since we didn't really finish the LCS computation
486 * we don't really know the length of the SES. We don't do
487 * anything with the result anyway, unless it's <=1. We know
488 * for a fact SES > 1 so 5 is as good a number as any to
493 private static function findMostProgress( $M, $N, $limit, $V ) {
496 if ( ( $M & 1 ) == ( $limit & 1 ) ) {
497 $forward_start_diag = max( -$M, -$limit );
499 $forward_start_diag = max( 1 - $M, -$limit );
502 $forward_end_diag = min( $N, $limit );
504 if ( ( $N & 1 ) == ( $limit & 1 ) ) {
505 $backward_start_diag = max( -$N, -$limit );
507 $backward_start_diag = max( 1 - $N, -$limit );
510 $backward_end_diag = -min( $M, $limit );
512 $temp = array( 0, 0, 0 );
514 $max_progress = array_fill( 0, ceil( max( $forward_end_diag - $forward_start_diag,
515 $backward_end_diag - $backward_start_diag ) / 2 ), $temp );
516 $num_progress = 0; // the 1st entry is current, it is initialized
519 // first search the forward diagonals
520 for ( $k = $forward_start_diag; $k <= $forward_end_diag; $k +
= 2 ) {
521 $x = $V[0][$limit +
$k];
523 if ( $x > $N ||
$y > $M ) {
528 if ( $progress > $max_progress[0][2] ) {
530 $max_progress[0][0] = $x;
531 $max_progress[0][1] = $y;
532 $max_progress[0][2] = $progress;
533 } elseif ( $progress == $max_progress[0][2] ) {
535 $max_progress[$num_progress][0] = $x;
536 $max_progress[$num_progress][1] = $y;
537 $max_progress[$num_progress][2] = $progress;
541 $max_progress_forward = true; // initially the maximum
542 // progress is in the forward
545 // now search the backward diagonals
546 for ( $k = $backward_start_diag; $k <= $backward_end_diag; $k +
= 2 ) {
547 $x = $V[1][$limit +
$k];
548 $y = $x - $k - $delta;
549 if ( $x < 0 ||
$y < 0 ) {
553 $progress = $N - $x +
$M - $y;
554 if ( $progress > $max_progress[0][2] ) {
556 $max_progress_forward = false;
557 $max_progress[0][0] = $x;
558 $max_progress[0][1] = $y;
559 $max_progress[0][2] = $progress;
560 } elseif ( $progress == $max_progress[0][2] && !$max_progress_forward ) {
562 $max_progress[$num_progress][0] = $x;
563 $max_progress[$num_progress][1] = $y;
564 $max_progress[$num_progress][2] = $progress;
568 // return the middle diagonal with maximal progress.
569 return $max_progress[(int)floor( $num_progress / 2 )];
575 public function getLcsLength() {
576 if ( $this->heuristicUsed
&& !$this->lcsLengthCorrectedForHeuristic
) {
577 $this->lcsLengthCorrectedForHeuristic
= true;
578 $this->length
= $this->m
- array_sum( $this->added
);
581 return $this->length
;
587 * Alternative representation of a set of changes, by the index
588 * ranges that are changed.
590 * @ingroup DifferenceEngine
592 class RangeDifference
{
612 function __construct( $leftstart, $leftend, $rightstart, $rightend ) {
613 $this->leftstart
= $leftstart;
614 $this->leftend
= $leftend;
615 $this->leftlength
= $leftend - $leftstart;
616 $this->rightstart
= $rightstart;
617 $this->rightend
= $rightend;
618 $this->rightlength
= $rightend - $rightstart;