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