| [ Index ] |
|
Code source de SPIP 1.8.3 |
1 <?php 2 3 /***************************************************************************\ 4 * SPIP, Systeme de publication pour l'internet * 5 * * 6 * Copyright (c) 2001-2005 * 7 * Arnaud Martin, Antoine Pitrou, Philippe Riviere, Emmanuel Saint-James * 8 * * 9 * Ce programme est un logiciel libre distribue sous licence GNU/GPL. * 10 * Pour plus de details voir le fichier COPYING.txt ou l'aide en ligne. * 11 \***************************************************************************/ 12 13 14 // Ce fichier ne sera execute qu'une fois 15 if (defined("_ECRIRE_INC_DIFF")) return; 16 define("_ECRIRE_INC_DIFF", "1"); 17 18 19 // 20 // LCS (Longest Common Subsequence) en deux versions 21 // (ref: http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE208.HTM) 22 23 // Version ultra-simplifiee : chaque chaine est une permutation de l'autre 24 // et on passe en parametre un des deux tableaux de correspondances 25 function lcs_opt($s) { 26 $n = count($s); 27 if (!$n) return array(); 28 $paths = array(); 29 $paths_ymin = array(); 30 $max_len = 0; 31 32 // Insertion des points 33 asort($s); 34 foreach ($s as $y => $c) { 35 for ($len = $max_len; $len > 0; $len--) { 36 if ($paths_ymin[$len] < $y) { 37 $paths_ymin[$len + 1] = $y; 38 $paths[$len + 1] = $paths[$len]; 39 $paths[$len + 1][$y] = $c; 40 break; 41 } 42 } 43 if ($len == 0) { 44 $paths_ymin[1] = $y; 45 $paths[1] = array($y => $c); 46 } 47 if ($len + 1 > $max_len) $max_len = $len + 1; 48 } 49 return $paths[$max_len]; 50 } 51 52 // Version normale : les deux chaines n'ont pas ete traitees au prealable 53 // par la fonction d'appariement 54 function lcs($s, $t) { 55 $n = count($s); 56 $p = count($t); 57 if (!$n || !$p) return array(0 => array(), 1 => array()); 58 $paths = array(); 59 $paths_ymin = array(); 60 $max_len = 0; 61 $s_pos = $t_pos = array(); 62 63 // Insertion des points 64 foreach ($t as $y => $c) $t_pos[trim($c)][] = $y; 65 66 foreach ($s as $x => $c) { 67 $c = trim($c); 68 if (!$t_pos[$c]) continue; 69 krsort($t_pos[$c]); 70 foreach ($t_pos[$c] as $y) { 71 for ($len = $max_len; $len > 0; $len--) { 72 if ($paths_ymin[$len] < $y) { 73 $paths_ymin[$len + 1] = $y; 74 // On construit le resultat sous forme de chaine d'abord, 75 // car les tableaux de PHP sont dispendieux en taille memoire 76 $paths[$len + 1] = $paths[$len]." $x,$y"; 77 break; 78 } 79 } 80 if ($len + 1 > $max_len) $max_len = $len + 1; 81 if ($len == 0) { 82 $paths_ymin[1] = $y; 83 $paths[1] = "$x,$y"; 84 } 85 } 86 } 87 if ($paths[$max_len]) { 88 $path = explode(" ", $paths[$max_len]); 89 $u = $v = array(); 90 foreach ($path as $p) { 91 list($x, $y) = explode(",", $p); 92 $u[$x] = $y; 93 $v[$y] = $x; 94 } 95 return array($u, $v); 96 } 97 return array(0 => array(), 1 => array()); 98 } 99 100 101 function test_lcs($a, $b) { 102 $s = explode(" ", $a); 103 $t = explode(" ", $b); 104 105 $t0 = explode(" ", microtime()); 106 list($r1, $r2) = lcs($s, $t); 107 $t1 = explode(" ", microtime()); 108 $dt = $t1[0] + $t1[1] - $t0[0] - $t0[1]; 109 echo join(" ", $r1)."<br />"; 110 echo join(" ", $r2)."<p>"; 111 echo "<div style='font-weight: bold; color: red;'>$dt s.</div>"; 112 } 113 114 function test_lcs_opt($s) { 115 $s = preg_split(',\s+,', $s); 116 117 $t0 = explode(" ", microtime()); 118 $t = lcs_opt($s); 119 $t1 = explode(" ", microtime()); 120 $dt = $t1[0] + $t1[1] - $t0[0] - $t0[1]; 121 echo join(" ", $s)."<br />"; 122 echo join(" ", $t)."<p>"; 123 echo "<div style='font-weight: bold; color: red;'>$dt s.</div>"; 124 } 125 126 127 // 128 // Generation de diff a plusieurs etages 129 // 130 131 class Diff { 132 var $diff; 133 var $fuzzy; 134 135 function Diff($diff) { 136 $this->diff = $diff; 137 $this->fuzzy = true; 138 } 139 140 function comparer($new, $old) { 141 $paras = $this->diff->segmenter($new); 142 $paras_old = $this->diff->segmenter($old); 143 if ($this->diff->fuzzy()) { 144 list($trans_rev, $trans) = apparier_paras($paras_old, $paras); 145 $lcs = lcs_opt($trans); 146 $lcs_rev = array_flip($lcs); 147 } 148 else { 149 list($trans_rev, $trans) = lcs($paras_old, $paras); 150 $lcs = $trans; 151 $lcs_rev = $trans_rev; 152 } 153 154 reset($paras_old); 155 reset($paras); 156 reset($lcs); 157 unset($i_old); 158 $fin_old = false; 159 foreach ($paras as $i => $p) { 160 if (!isset($trans[$i])) { 161 // Paragraphe ajoute 162 $this->diff->ajouter($p); 163 continue; 164 } 165 $j = $trans[$i]; 166 if (!isset($lcs[$i])) { 167 // Paragraphe deplace 168 $this->diff->deplacer($p, $paras_old[$j]); 169 continue; 170 } 171 if (!$fin_old) { 172 // Paragraphes supprimes jusqu'au paragraphe courant 173 if (!isset($i_old)) { 174 list($i_old, $p_old) = each($paras_old); 175 if (!$p_old) $fin_old = true; 176 } 177 while (!$fin_old && $i_old < $j) { 178 if (!isset($trans_rev[$i_old])) { 179 $this->diff->supprimer($p_old); 180 } 181 unset($i_old); 182 list($i_old, $p_old) = each($paras_old); 183 if (!$p_old) $fin_old = true; 184 } 185 } 186 // Paragraphe n'ayant pas change de place 187 $this->diff->comparer($p, $paras_old[$j]); 188 } 189 // Paragraphes supprimes a la fin du texte 190 if (!$fin_old) { 191 if (!isset($i_old)) { 192 list($i_old, $p_old) = each($paras_old); 193 if (!strlen($p_old)) $fin_old = true; 194 } 195 while (!$fin_old) { 196 if (!isset($trans_rev[$i_old])) { 197 $this->diff->supprimer($p_old); 198 } 199 list($i_old, $p_old) = each($paras_old); 200 if (!$p_old) $fin_old = true; 201 } 202 } 203 if (isset($i_old)) { 204 if (!isset($trans_rev[$i_old])) { 205 $this->diff->supprimer($p_old); 206 } 207 } 208 return $this->diff->resultat(); 209 } 210 } 211 212 class DiffTexte { 213 var $r; 214 215 function DiffTexte() { 216 $this->r = ""; 217 } 218 219 function _diff($p, $p_old) { 220 $diff = new Diff(new DiffPara); 221 return $diff->comparer($p, $p_old); 222 } 223 224 function fuzzy() { 225 return true; 226 } 227 function segmenter($texte) { 228 return separer_paras($texte); 229 } 230 231 // NB : rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies" 232 function ajouter($p) { 233 $p = trim($p); 234 $this->r .= "\n\n\n<div class=\"diff-para-ajoute\" title=\""._T('diff_para_ajoute')."\">".$p."</div rem=\"diff-\">"; 235 } 236 function supprimer($p_old) { 237 $p_old = trim($p_old); 238 $this->r .= "\n\n\n<div class=\"diff-para-supprime\" title=\""._T('diff_para_supprime')."\">".$p_old."</div rem=\"diff-\">"; 239 } 240 function deplacer($p, $p_old) { 241 $this->r .= "\n\n\n<div class=\"diff-para-deplace\" title=\""._T('diff_para_deplace')."\">"; 242 $this->r .= trim($this->_diff($p, $p_old)); 243 $this->r .= "</div rem=\"diff-\">"; 244 } 245 function comparer($p, $p_old) { 246 $this->r .= "\n\n\n".$this->_diff($p, $p_old); 247 } 248 249 function resultat() { 250 return $this->r; 251 } 252 } 253 254 class DiffPara { 255 var $r; 256 257 function DiffPara() { 258 $this->r = ""; 259 } 260 261 function _diff($p, $p_old) { 262 $diff = new Diff(new DiffPhrase); 263 return $diff->comparer($p, $p_old); 264 } 265 266 function fuzzy() { 267 return true; 268 } 269 function segmenter($texte) { 270 $paras = array(); 271 $texte = trim($texte); 272 while (preg_match('/[\.!\?]+\s*/u', $texte, $regs)) { 273 $p = strpos($texte, $regs[0]) + strlen($regs[0]); 274 $paras[] = substr($texte, 0, $p); 275 $texte = substr($texte, $p); 276 } 277 if ($texte) $paras[] = $texte; 278 return $paras; 279 } 280 281 function ajouter($p) { 282 $this->r .= "<span class=\"diff-ajoute\" title=\""._T('diff_texte_ajoute')."\">".$p."</span rem=\"diff-\">"; 283 } 284 function supprimer($p_old) { 285 $this->r .= "<span class=\"diff-supprime\" title=\""._T('diff_texte_supprime')."\">".$p_old."</span rem=\"diff-\">"; 286 } 287 function deplacer($p, $p_old) { 288 $this->r .= "<span class=\"diff-deplace\" title=\""._T('diff_texte_deplace')."\">".$this->_diff($p, $p_old)."</span rem=\"diff-\">"; 289 } 290 function comparer($p, $p_old) { 291 $this->r .= $this->_diff($p, $p_old); 292 } 293 294 function resultat() { 295 return $this->r; 296 } 297 } 298 299 class DiffPhrase { 300 var $r; 301 302 function DiffPhrase() { 303 $this->r = ""; 304 } 305 306 function fuzzy() { 307 return false; 308 } 309 function segmenter($texte) { 310 $paras = array(); 311 if (test_pcre_unicode()) { 312 $punct = '([[:punct:]]|'.plage_punct_unicode().')'; 313 $mode = 'u'; 314 } 315 else { 316 // Plages de poncutation pour preg_match bugge (ha ha) 317 $punct = '([^\w\s\x80-\xFF]|'.plage_punct_unicode().')'; 318 $mode = ''; 319 } 320 $preg = '/('.$punct.'+)(\s+|$)|(\s+)('.$punct.'*)/'.$mode; 321 while (preg_match($preg, $texte, $regs)) { 322 $p = strpos($texte, $regs[0]); 323 $l = strlen($regs[0]); 324 $punct = $regs[1] ? $regs[1] : $regs[6]; 325 $milieu = ""; 326 if ($punct) { 327 // Attacher les raccourcis fermants au mot precedent 328 if (preg_match(',^[\]}]+$,', $punct)) { 329 $avant = substr($texte, 0, $p) . $regs[5] . $punct; 330 $texte = $regs[4] . substr($texte, $p + $l); 331 } 332 // Attacher les raccourcis ouvrants au mot suivant 333 else if ($regs[5] && preg_match(',^[\[{]+$,', $punct)) { 334 $avant = substr($texte, 0, $p) . $regs[5]; 335 $texte = $punct . substr($texte, $p + $l); 336 } 337 // Les autres signes de ponctuation sont des mots a part entiere 338 else { 339 $avant = substr($texte, 0, $p); 340 $milieu = $regs[0]; 341 $texte = substr($texte, $p + $l); 342 } 343 } 344 else { 345 $avant = substr($texte, 0, $p + $l); 346 $texte = substr($texte, $p + $l); 347 } 348 if ($avant) $paras[] = $avant; 349 if ($milieu) $paras[] = $milieu; 350 } 351 if ($texte) $paras[] = $texte; 352 return $paras; 353 } 354 355 function ajouter($p) { 356 $this->r .= "<span class=\"diff-ajoute\" title=\""._T('diff_texte_ajoute')."\">".$p."</span rem=\"diff-\"> "; 357 } 358 function supprimer($p_old) { 359 $this->r .= "<span class=\"diff-supprime\" title=\""._T('diff_texte_supprime')."\">".$p_old."</span rem=\"diff-\"> "; 360 } 361 function comparer($p, $p_old) { 362 $this->r .= $p; 363 } 364 365 function resultat() { 366 return $this->r; 367 } 368 } 369 370 371 function preparer_diff($texte) { 372 include_spip("charsets.php"); 373 374 $charset = lire_meta('charset'); 375 if ($charset == 'utf-8') 376 return unicode_to_utf_8(html2unicode($texte)); 377 return unicode_to_utf_8(html2unicode(charset2unicode($texte, $charset, true))); 378 } 379 380 function afficher_diff($texte) { 381 $charset = lire_meta('charset'); 382 if ($charset == 'utf-8') return $texte; 383 return charset2unicode($texte, 'utf-8'); 384 } 385 386 387 ?>
titre
Description
Corps
titre
Description
Corps
titre
Description
Corps
titre
Corps
| Généré le : Thu Feb 22 22:27:47 2007 | par Balluche grâce à PHPXref 0.7 |