Subversion Repositories Sites.tela-botanica.org

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
4 david 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
?>