一个生成unified diff的php程序

就是patch的那种格式了，也就是用diff -u old.file new.file生成的文件差别信息。这里只有对比两个字符串的，对比两个文件的稍微改改就行了。php可以用现成的xdiff_string_diff一类的外置函数来处理，效率会比较高。但有些虚拟服务提供商可能没有提供此功能，这种情况下可以考虑使用这个程序。应用patch可以用PhpPatcher；生成可视化文件差异可以用Text_Diff。

算法比较简单，就是一般的dynamic programming的LCS(longest common subsequence)。有很多可以优化的地方，比如开头和结尾相同的行去掉；用hash table把只在其中一个文件中出现的字符串去掉；字符串比较时先对比hash（估计php应该做了这方面的优化了吧）。当然，真的对速度有要求的话还是用上面说的xdiff的库比较好，那个实际是调用native library来完成的，纯php再优化也比不过了。

<?

function diff($a, $b, $context) {
    $lena = count($a);
    $lenb = count($b);
    $trace = array();
    $trace[-1] = array_fill(-1, $lenb + 1, +1);
    $lcs0 = array_fill(-1, $lenb + 1, 0);
    $lcs1[-1] = 0;

    foreach ($a as $x) {
        $t = array();
        $t[-1] = -1;
        for ($i = 0; $i < $lena; $i++) {
            if ($x == $b[$i]) {
                $lcs1[$i] = $lcs0[$i - 1] + 1; 
                $t[$i] = 0;
            } elseif ($lcs0[$i] > $lcs1[$i - 1]) {
                $lcs1[$i] = $lcs0[$i];
                $t[$i] = -1;
            } else {
                $lcs1[$i] = $lcs1[$i - 1];
                $t[$i] = +1;
            }
        }
        array_push($trace, $t);
        $t = $lcs1;
        $lcs1 = $lcs0;
        $lcs0 = $t;
    }

    $same = 0;
    $out = false;
    $ret = array();
    for ($i = $lena - 1, $j = $lenb - 1; $i != -1 || $j != -1; ) {
        if ($trace[$i][$j] == 0) {
            $same++;
            if ($out && $same > $context * 2) {
                $outbegina = $i + $same - $context;
                $outbeginb = $j + $same - $context;
                for ($k = $i + $same - 1; $k >= $outbegina; $k--) {
                    array_push($ret, array('cmd'=>' ', 'dat'=>$a[$k]));
                }
                array_push($ret, array('cmd'=>'@', 'dat'=>array($outbegina, 
                                                                $outenda - $outbegina + 1,
                                                                $outbeginb,
                                                                $outendb - $outbeginb + 1)));
                $out = false;
            }
            $i--;
            $j--;
        } else {
            if (!$out) {
                $same = min($same, $context);
                $out = true;
                $outenda = $i + $same;
                $outendb = $j + $same;
            }
            for ($k = $i + $same; $k > $i; $k--) {
                array_push($ret, array('cmd'=>' ', 'dat'=>$a[$k]));
            }
            $same = 0;
            if ($trace[$i][$j] == -1) {
                array_push($ret, array('cmd'=>'-', 'dat'=>$a[$i]));
                $i--;
            } else {
                array_push($ret, array('cmd'=>'+', 'dat'=>$b[$j]));
                $j--;
            }
        }
    }

    if ($out) {
        $outbegina = max(0, $same - $context);
        $outbeginb = max(0, $same - $context);
        for ($k = $same - 1; $k >= $outbegina; $k--) {
            array_push($ret, array('cmd'=>' ', 'dat'=>$a[$k]));
        }
        array_push($ret, array('cmd'=>'@', 'dat'=>array($outbegina, 
                                                        $outenda - $outbegina + 1,
                                                        $outbeginb,
                                                        $outendb - $outbeginb + 1)));
    }

    return array_reverse($ret);
}

function diff_string($a, $b, $context = 3) {
    $d = diff(explode("\n", $a), explode("\n", $b), $context);
    $ret = array();
    print_r($d);
    foreach ($d as $i) {
        if ($i["cmd"] == '@') {
            array_push($ret, sprintf('@@ -%d,%d +%d,%d @@', 
                                     $i["dat"][0], $i["dat"][1], 
                                     $i["dat"][2], $i["dat"][3]));
        } else {
            array_push($ret, $i["cmd"] . $i["dat"]);
        }
    }
    return implode("\n", $ret);
}


$a = array('c','0','1','2','a','b','e','2','c','d','e','f');
$b = array('0','1','2','b','f','1','c','d','e','f');
echo '<pre>';
print_r(diff_string(implode("\n",$a), implode("\n",$b), 1));
echo '</pre>';