o(np)のdiffアルゴリズムを作りました。
元ネタはこの辺。
An O(NP) sequence comparison algorithm

なんで車輪の再発明したかというと、既存のライブラリだと挙動がわからない上に、使い勝手がいまいちだからです。
自分で全部書けば、自由自在（ぉ
とりあえずリファクタリングの余地は多々ある感じですが。

一般的な意味でのdiffと違うところと言えば、追加／削除のみしか考えておらず、「置換」がありません。
けど、アルゴリズム上「置換」に当たる場合は「追加→削除」または「削除→追加」のいずれかの順番でSESの中に現れるので、その場合を「置換」と処理すればよいかと思います。

使い方とかは暇があったら書く。

このあたりを参考にさせてもらいました。日本語の解説ではこれが一番わかりがよく正確だと思います。
diff(1)

PLAIN TEXT
CODE:
  1. <?php
  2. class DiffModel{
  3.     private $flip = false;
  4.     private $arr1 = null;
  5.     private $arr2 = null;
  6.     private $size1 = null;
  7.     private $size2 = null;
  8.     private $ses = null;
  9.  
  10.     private $patharr=null;
  11.     const SAME=0;
  12.     const ADD=1;
  13.     const DEL=2;
  14.  
  15.     public function __construct($article1="", $article2=""){
  16.         if(is_array($article1) and is_array($article2)){
  17.             $this->setArray($article1, $article2);
  18.         }else{
  19.             $this->setArticles($article1, $article2);
  20.         }
  21.     }
  22.  
  23.     public function setArticles($article1, $article2){
  24.         if(strlen($article1)> strlen($article2)){
  25.             $this->arr1 = empty($article1) ? array() : mb_str_split($article1);
  26.             $this->arr2 = empty($article2) ? array() : mb_str_split($article2);
  27.  
  28.             $this->size1 = count($this->arr1);
  29.             $this->size2 = count($this->arr2);
  30.             $this->flip = true;
  31.         }else{
  32.             $this->arr1 = empty($article2) ? array() : mb_str_split($article2);
  33.             $this->arr2 = empty($article1) ? array() : mb_str_split($article1);
  34.  
  35.             $this->size1 = count($this->arr1);
  36.             $this->size2 = count($this->arr2);
  37.             $this->flip = false;
  38.         }
  39.     }
  40.  
  41.     public function setArray($arr1, $arr2){
  42.         if(count($arr1)> count($arr2)){
  43.             $this->arr1 = $arr1;
  44.             $this->arr2 = $arr2;
  45.  
  46.             $this->size1 = count($this->arr1);
  47.             $this->size2 = count($this->arr2);
  48.             $this->flip = true;
  49.         }else{
  50.             $this->arr1 = $arr2;
  51.             $this->arr2 = $arr1;
  52.  
  53.             $this->size1 = count($this->arr1);
  54.             $this->size2 = count($this->arr2);
  55.             $this->flip = false;
  56.         }
  57.  
  58.     }
  59.  
  60.     public function diff(){
  61.  
  62.         $offset = $this->size2 + 1;
  63.  
  64.         $this->patharr = array();
  65.  
  66.         $fp = array_fill(0, $this->size1 + $this->size2 + 3, -1);
  67.         $delta = $this->size1 - $this->size2;
  68.  
  69.         $p=0;
  70.         for(; $fp[$delta + $offset] <$this->size1; $p++){
  71.             for($k = -$p; $k <$delta; $k++){
  72.                 $fp[$k + $offset] = $this->snake($k, $offset, $fp);
  73.             }
  74.  
  75.             for($k = $delta + $p; $k>= $delta; $k--){
  76.                 $fp[$k + $offset] = $this->snake($k, $offset, $fp);
  77.             }
  78.  
  79.         }
  80.  
  81.         return $delta + 2*($p - 1);
  82.     }
  83.  
  84.     public function getDiff(){
  85.         $ind = $this->size2 + $this->size1*($this->size2+1);
  86.         $item = array(-1, $this->size2, $this->size1);
  87.         $this->ses = array();
  88.         do{
  89.             switch($this->patharr[$ind][0]){
  90.             case (self::ADD):
  91.                 if($item[0] != $this->patharr[$ind][0]){
  92.                     $this->ses[] = array($this->flip ? self::ADD : self::DEL, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1]);
  93.                 }else{
  94.                     $this->ses[count($this->ses)-1][1] = $this->patharr[$ind][1];
  95.                     $this->ses[count($this->ses)-1][2] += $item[1] - $this->patharr[$ind][1];
  96.                 }
  97.                 //echo sprintf("add %3d-%3d %s\n", $this->patharr[$ind][1], $item[1], mb_substr($this->article2, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1], "utf-8"));
  98.                 break;
  99.             case (self::DEL):
  100.                 if($item[0] != $this->patharr[$ind][0]){
  101.                     $this->ses[] = array($this->flip ? self::DEL : self::ADD, $this->patharr[$ind][2], $item[2] - $this->patharr[$ind][2]);
  102.                 }else{
  103.                     $this->ses[count($this->ses)-1][1] = $this->patharr[$ind][2];
  104.                     $this->ses[count($this->ses)-1][2] += $item[2] - $this->patharr[$ind][2];
  105.                 }
  106.                 //echo sprintf("del %3d-%3d %s\n", $this->patharr[$ind][2], $item[2], mb_substr($this->article1, $this->patharr[$ind][2], $item[2] - $this->patharr[$ind][2], "utf-8"));
  107.                 break;
  108.             case (self::SAME):
  109.                 if($item[0] != $this->patharr[$ind][0]){
  110.                     $this->ses[] = array(self::SAME, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1]);
  111.                 }else{
  112.                     $this->ses[count($this->ses)-1][1] = $this->patharr[$ind][1];
  113.                     $this->ses[count($this->ses)-1][2] += $item[1] - $this->patharr[$ind][1];
  114.                 }
  115.                 //echo sprintf("sam %3d-%3d %s\n", $this->patharr[$ind][1], $item[1], mb_substr($this->article2, $this->patharr[$ind][1], $item[1] - $this->patharr[$ind][1], "utf-8"));
  116.                 break;
  117.             }
  118.  
  119.             $item = $this->patharr[$ind];
  120.             $ind = $this->patharr[$ind][1] + $this->patharr[$ind][2]*($this->size2+1);
  121.  
  122.         }while($ind> 0);
  123.  
  124.         $this->ses = array_reverse($this->ses);
  125.         return $this->ses;
  126.  
  127.     }
  128.  
  129.     private function snake($k, $offset, &$fp){
  130.         $y=0;
  131.         if($fp[$k-1 + $offset] + 1> $fp[$k+1+$offset]){
  132.             $y = $fp[$k-1 + $offset] + 1;
  133.             //$this->patharr[($y-$k) + $y*($this->size2+1)] = array($y-$k,$y-1);
  134.             $this->patharr[($y-$k) + $y*($this->size2+1)] = array(self::DEL, $y-$k,$y-1);
  135.         }else{
  136.             $y = $fp[$k+1 + $offset];
  137.             $this->patharr[($y-$k) + $y*($this->size2+1)] = array(self::ADD, $y-$k-1, $y);
  138.         }
  139.  
  140.         $x = $y-$k;
  141.         $sx = $x;
  142.         $sy = $y;
  143.  
  144.         while($x <$this->size2 and $y <$this->size1 and $this->arr2[$x] == $this->arr1[$y]){
  145.             $x++;
  146.             $y++;
  147.         }
  148.  
  149.         if(!($x == $sx and $y == $sy) )$this->patharr[$x+$y*($this->size2+1)] = array(self::SAME, $sx,$sy);
  150.  
  151.         return $y;
  152.     }
  153.  
  154. }
  155. ?>