3
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.)

\$\endgroup\$
1
  • \$\begingroup\$ Thanks! Don't worry if the syntax is valid, you've given me a lot to work with. I'll edit the answer if I find any syntax mistakes. \$\endgroup\$ – yannis Nov 29 '11 at 10:30
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Yep, testing it with larger texts definitely show its weaknesses. I found the script in my sandbox of tricks, it's possible that it's a quick script I've built for a very specific purpose. I'll definitely try the indices as a quick hack. Searching for diff engines I've found this excellent fine granularity engine (demo here) so I'll probably throw away my script and use it instead... There are some open issues but overall its great. \$\endgroup\$ – yannis Nov 30 '11 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.