Simple text diff function

Question

I've put together this extremely simple text diff function a while ago:

function diff($old, $new) {
    $old = trim($old);
    $new = trim($new);

    if($old == $new) {
        return $new;
    }

    $old    = explode(" ", $old);
    $new    = explode(" ", $new);           
    $result = "";       
    $length = max(count($old), count($new));

    for($i = 0; $i < $length; $i++) {
        if(!isset($new[$i])) {
            $result .= "<del>{$old[$i]}</del>";
            continue;
        }

        if(!isset($old[$i])) {
            $result .= "<ins>{$new[$i]}</ins> ";
            continue;
        }           

        if($old[$i] != $new[$i]) {
            $result .= "<del>{$old[$i]}</del><ins>{$new[$i]}</ins> ";
            continue;
        }

        $result .= "{$new[$i]} ";
    }

    $result = str_replace(array("</ins> <ins>", "</del> <del>"), " ", $result);     

    return trim($result);   
}

$string1 = "Hello World!! Please review my diff function. Be gentle.";
$string2 = "Hello world! Please critique my diff function. Be extra vigilant.";

echo diff($string1, $string2);
// Hello <del>World!!</del><ins>world!</ins> Please <del>review</del><ins>critique</ins> my diff function. Be <del>gentle.</del><ins>extra vigilant.</ins>

The html output is:

Hello World!!world! Please reviewcritique my diff function. Be gentle.extra vigilant.

The purpose of the function wasn't something important, as I can't even remember why I built it (found in my sandbox directory, which is full of little experiments). Is it any good? I've always used PEAR Text_Diff for text diffs, but if I'm not doing anything inherently wrong in my simple function, I'd love to use it instead.

Any suggestions on an easy way to move html out of the function?

Answer 1

It looks fine. A few notes:

1, Use max instead of

$length = count($old) > count($new) ? count($old) : count($new);

2, Consider testing with newlines, tabs and maybe other whitespace characters.

3, http://en.wikipedia.org/wiki/Longest_common_subsequence could be useful if you want a better algorithm.

4, For removing HTML out of the function create a class which does it and delegate the calls to it. For example:

public interface Decorator {

    public function delete($input);

    public function insert($input);

    public function removeUnnecessaryMarkers($input);
}

public class HtmlDecorator {
    public function delete($input) {
        return "<del>{$input}</del>";
    }
    public function insert($input) {
        return "<ins>{$input}</ins>";
    }
    public function removeUnnecessaryMarkers($input) {
        return str_replace(array("</ins> <ins>", "</del> <del>"), " ", $input); 
    }
}

...
if(!isset($new[$i])) {
    $result .= $decorator->delete($old[$i]);
    continue;
}
...

(I haven't tested that this is a valid PHP syntax or not. Feel free to fix it.)

Answer 2

Would have posted this as a comment, but have only just signed up to add this input so not got that privalige yet! Have you had a look at the google-diff-match-patch library? There might be some good algorithmic ideas you could take away from that? There's no php example, but they've got a few other language options in there.

Answer 3

It looks like the program can only handle replacements, up to the ends. Like if you gave it

A B C D E
A C D E

it would say B was replaced by C, C by D, D by E, and E deleted. That's four changes, instead of just the one change of deleting B.

There's another way, where you can work out the details. It is to have two indices, i and j. When old[i] == new[j], both i and j are incremented. Otherwise you go into a diagonal search comparing elements like this:

i+1, j+0
i+0, j+1

i+2, j+0
i+1, j+1
i+0, j+2

i+3, j+0
i+2, j+1
i+1, j+2
i+0, j+3

until you get a match. Then you know how many elements in between were inserted or deleted.