Highlight the difference between two strings in PH

Question

What is the easiest way to highlight the difference between two strings in PHP?

I'm thinking along the lines of the Stack Overflow edit history page, where new text is in green and removed text is in red. If there are any pre-written functions or classes available, that would be ideal.

Answer 1

I came across this PHP diff class by Chris Boulton based on Python difflib which could be a good solution:

PHP Diff Lib

Answer 2

Here is a short function you can use to diff two arrays. It implements the LCS algorithm:

function computeDiff($from, $to)
{
    $diffValues = array();
    $diffMask = array();

    $dm = array();
    $n1 = count($from);
    $n2 = count($to);

    for ($j = -1; $j < $n2; $j++) $dm[-1][$j] = 0;
    for ($i = -1; $i < $n1; $i++) $dm[$i][-1] = 0;
    for ($i = 0; $i < $n1; $i++)
    {
        for ($j = 0; $j < $n2; $j++)
        {
            if ($from[$i] == $to[$j])
            {
                $ad = $dm[$i - 1][$j - 1];
                $dm[$i][$j] = $ad + 1;
            }
            else
            {
                $a1 = $dm[$i - 1][$j];
                $a2 = $dm[$i][$j - 1];
                $dm[$i][$j] = max($a1, $a2);
            }
        }
    }

    $i = $n1 - 1;
    $j = $n2 - 1;
    while (($i > -1) || ($j > -1))
    {
        if ($j > -1)
        {
            if ($dm[$i][$j - 1] == $dm[$i][$j])
            {
                $diffValues[] = $to[$j];
                $diffMask[] = 1;
                $j--;  
                continue;              
            }
        }
        if ($i > -1)
        {
            if ($dm[$i - 1][$j] == $dm[$i][$j])
            {
                $diffValues[] = $from[$i];
                $diffMask[] = -1;
                $i--;
                continue;              
            }
        }
        {
            $diffValues[] = $from[$i];
            $diffMask[] = 0;
            $i--;
            $j--;
        }
    }    

    $diffValues = array_reverse($diffValues);
    $diffMask = array_reverse($diffMask);

    return array('values' => $diffValues, 'mask' => $diffMask);
}

It generates two arrays:

• values array: a list of elements as they appear in the diff.
• mask array: contains numbers. 0: unchanged, -1: removed, 1: added.

If you populate an array with characters, it can be used to compute inline difference. Now just a single step to highlight the differences:

function diffline($line1, $line2)
{
    $diff = computeDiff(str_split($line1), str_split($line2));
    $diffval = $diff['values'];
    $diffmask = $diff['mask'];

    $n = count($diffval);
    $pmc = 0;
    $result = '';
    for ($i = 0; $i < $n; $i++)
    {
        $mc = $diffmask[$i];
        if ($mc != $pmc)
        {
            switch ($pmc)
            {
                case -1: $result .= '</del>'; break;
                case 1: $result .= '</ins>'; break;
            }
            switch ($mc)
            {
                case -1: $result .= '<del>'; break;
                case 1: $result .= '<ins>'; break;
            }
        }
        $result .= $diffval[$i];

        $pmc = $mc;
    }
    switch ($pmc)
    {
        case -1: $result .= '</del>'; break;
        case 1: $result .= '</ins>'; break;
    }

    return $result;
}

Eg.:

echo diffline('StackOverflow', 'ServerFault')

Will output:

S<del>tackO</del><ins>er</ins>ver<del>f</del><ins>Fau</ins>l<del>ow</del><ins>t</ins> 

StackOerverfFaulowt

Additional notes:

• The diff matrix requires (m+1)*(n+1) elements. So you can run into out of memory errors if you try to diff long sequences. In this case diff larger chunks (eg. lines) first, then diff their contents in a second pass.
• The algorithm can be improved if you trim the matching elements from the beginning and the end, then run the algorithm on the differing middle only. A latter (more bloated) version contains these modifications too.

Answer 3

There is also a PECL extension for xdiff:

• http://php.net/manual/en/book.xdiff.php
• http://pecl.php.net/package/xdiff

In particular:

• xdiff_string_diff — Make unified diff of two strings

Example from PHP Manual:

<?php
$old_article = file_get_contents('./old_article.txt');
$new_article = $_POST['article'];

$diff = xdiff_string_diff($old_article, $new_article, 1);
if (is_string($diff)) {
    echo "Differences between two articles:\n";
    echo $diff;
}

Answer 4

This is the best one I've found.

http://code.stephenmorley.org/php/diff-implementation/

Answer 5

I would recommend looking at these awesome functions from PHP core:

similar_text — Calculate the similarity between two strings

http://www.php.net/manual/en/function.similar-text.php

levenshtein — Calculate Levenshtein distance between two strings

http://www.php.net/manual/en/function.levenshtein.php

soundex — Calculate the soundex key of a string

http://www.php.net/manual/en/function.soundex.php

metaphone — Calculate the metaphone key of a string

http://www.php.net/manual/en/function.metaphone.php

Answer 6

If you want a robust library, Text_Diff (a PEAR package) looks to be pretty good. It has some pretty cool features.