Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
PHP Diff Algorithm
Author Message
PaulButler

Posted: Thu May 17, 2007 5:56 pm   Post subject: PHP Diff Algorithm

I wrote a simple diff algorithm in PHP. The functions are described in the comments; basically the "diff" function works directly on an array and the htmlDiff function is a wrapper that takes two normal strings and returns HTML markup representing the difference.

I assume that the "largest common substring" algorithm is the one I used, but I did not have any code or description to base it on so I had to figure most of it out myself. Considering diff algorithms are fairly useful and fun but challenging to code, I am surprised that there is so little information on them on the web.

 php:         May be used and distributed under the zlib/libpng license.                 This code is intended for learning purposes; it was written with short         code taking priority over performance. It could be used in a practical         application, but there are a few ways it could be optimized.                 Given two arrays, the function diff will return an array of the changes.         I won't describe the format of the array, but it will be obvious         if you use print_r() on the result of a diff on some test data.                 htmlDiff is a wrapper for the diff command, it takes two strings and         returns the differences in HTML. The tags used are and ,         which can easily be styled with CSS.  */ function diff(\$old, \$new){         foreach(\$old as \$oindex => \$ovalue){                 \$nkeys = array_keys(\$new, \$ovalue);                 foreach(\$nkeys as \$nindex){                         \$matrix[\$oindex][\$nindex] = isset(\$matrix[\$oindex - 1][\$nindex - 1]) ?                                 \$matrix[\$oindex - 1][\$nindex - 1] + 1 : 1;                         if(\$matrix[\$oindex][\$nindex] > \$maxlen){                                 \$maxlen = \$matrix[\$oindex][\$nindex];                                 \$omax = \$oindex + 1 - \$maxlen;                                 \$nmax = \$nindex + 1 - \$maxlen;                         }                 }                }         if(\$maxlen == 0) return array(array('d'=>\$old, 'i'=>\$new));         return array_merge(                 diff(array_slice(\$old, 0, \$omax), array_slice(\$new, 0, \$nmax)),                 array_slice(\$new, \$nmax, \$maxlen),                 diff(array_slice(\$old, \$omax + \$maxlen), array_slice(\$new, \$nmax + \$maxlen))); } function htmlDiff(\$old, \$new){         \$diff = diff(explode(' ', \$old), explode(' ', \$new));         foreach(\$diff as \$k){                 if(is_array(\$k))                         \$ret .= (!empty(\$k['d'])?"".implode(' ',\$k['d'])." ":'').                                 (!empty(\$k['i'])?"".implode(' ',\$k['i'])." ":'');                 else \$ret .= \$k . ' ';         }         return \$ret; } ?>

Somsakjohn

Posted: Wed Jun 08, 2016 6:33 am   Post subject: RE:PHP Diff Algorithm

I was very impressed that I had a message on it. Size and promised to use it.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 2 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: