difflib - Calcolare le differenze tra sequenze

Scopo Libreria di strumenti per calcolare e lavorare con differenze tra sequenze, specialmente di righe nei file di testo
Versione Python 2.1

La classe SequenceMatcher confronta due sequenze qualsiasi di valori, fintanto che i valori siano divisibili. Usa un algoritmo recursivo per identificare i blocchi più lunghi contigui corrispondenti dalle sequenze, eliminando valori "spazzatura". La classe Differ lavora sulle sequenze di righe di testo e produce una codifica delta in forma leggibile dall'uomo, incluse le differenze all'interno delle singole righe. La classe HtmlDiff produce risultati analoghi, formattati come una tabella HTML

Dati per il test

Gli esempi di seguito faranno tutti uso di questi comuni dati per il test nel modulo difflib_data:

text1 = """Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
mauris eget magna consequat convallis. Nam sed sem vitae odio
pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
enim. Donec quis lectus a justo imperdiet tempus."""
text1_lines = text1.splitlines()

text2 = """Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
imperdiet tempus. Suspendisse eu lectus. In nunc. """
text2_lines = text2.splitlines()

Esempio di Differ

Con la classe Differ, riprodurre un risultato simile allo strumento da riga comandi diff è semplice:

import difflib
from difflib_data import *

d = difflib.Differ()
diff = d.compare(text1_lines, text2_lines)
print '\n'.join(list(diff))

Il risultato include i valori originali in entrata da entrambe le liste, inclusi i valori comuni, e dati di marcatura per indicare quali cambiamenti sono stati effettuati. Le righe potrebbero essere prefissate con il simbolo - per indicare che sono nella prima sequenza, ma non nella seconda. Le righe prefissate con il segno + sono nella seconda sequenza, ma non nella prima. Se una riga ha una modifica incrementale tra le versioni, si usa una riga aggiuntiva prefissata con ? per indicare dove ci sono cambiamenti all'interno della riga. Se una riga non è cambiata, viene stampata con uno spazio aggiuntivo a sinistra, per allinearla alle altre righe che potrabbero iniziare con altri marcatori. L'inizio di entrambi i segmenti di testo è uguale.

1:   Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer

La seconda riga è stata cambiata per includere una virgola nel testo modificato. Entrambe le versioni della riga sono stampate, con una informazione aggiuntiva nella riga 4, che mostra la colonna dove il testo è stato modificato, incluso il fatto che il carattere , è stato aggiunto.

2: - eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
3: + eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
4: ?                                                         +
5:

Le righe da 6 a 9 mostrano dove è stato rimosso uno spazio supplementare.

6: - tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
7: ?                                                             -
8:
9: + tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec

Successivamente è stato fatta una modifica più complessa, sostituendo diverse parole in una frase.

10: - mauris eget magna consequat convallis. Nam sed sem vitae odio
11: ?                                              - --
12:
13: + mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
14: ?                                            +++ +++++   +
15:

L'ultima frase nel paragrafo è stata modificata in modo significativo, quindi la differenza viene rappresentata semplicemente eliminando la vecchia versione ed aggiungendo la nuova (righe 20-23)

16:   pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
17:   metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
18:   urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
19:   suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
20: - adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
21: - enim. Donec quis lectus a justo imperdiet tempus.
22: + adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
23: + imperdiet tempus. Suspendisse eu lectus. In nunc.

La funzione ndiff() fornisce essenzialmente lo stesso risultato. Il processo è specificamente modellato per lavorare con dati di testo, eliminando il "rumore" dai dati in entrata.

import difflib
from difflib_data import *

diff = difflib.ndiff(text1_lines, text2_lines)
print '\n'.join(list(diff))
$ python difflib_ndiff.py
  Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
- eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
+ eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
?                                                         +

- tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
?                                                             -

+ tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
- mauris eget magna consequat convallis. Nam sed sem vitae odio
?                                             ------

+ mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
?                                            +++        +++++++++

  pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
- adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
- enim. Donec quis lectus a justo imperdiet tempus.
+ adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
+ imperdiet tempus. Suspendisse eu lectus. In nunc.

Altri formati di Diff

Mentre la classe Differ mosta l'intero input, diff unificata include solo le righe modificate ed un poco di contesto. Nella versione 2.3, è stata aggiunta la funzione unified_diff() per produrre questo tipo di risultato

import difflib
from difflib_data import *

diff = difflib.unified_diff(text1_lines, text2_lines, lineterm='')
print '\n'.join(list(diff))

Il risultato dovrebbe essere familiare agli utilizzatori di svn od altri strumenti di controllo di versione

$ python difflib_unified.py
---
+++
@@ -1,10 +1,10 @@
 Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
-eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
-tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
-mauris eget magna consequat convallis. Nam sed sem vitae odio
+eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
+tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
+mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
 pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
 metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
 urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
 suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
-adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
-enim. Donec quis lectus a justo imperdiet tempus.
+adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
+imperdiet tempus. Suspendisse eu lectus. In nunc.

L'uso di context_diff() produce un risultato simile

$ python difflib_context.py
***
---
***************
*** 1,10 ****
  Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
! eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitor
! tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec
! mauris eget magna consequat convallis. Nam sed sem vitae odio
  pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
! adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristique
! enim. Donec quis lectus a justo imperdiet tempus.
--- 1,10 ----
  Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
! eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
! tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
! mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
  pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
  metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
  urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
  suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
! adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
! imperdiet tempus. Suspendisse eu lectus. In nunc.

Risultato in HTML

HtmlDiff (nuovo in Python 2.4) genera un risultato in formato HTML con le stesse informazioni della classe Diff. Questo esempio usa make_table(), ma il metodo make_file() produce come risultato un file HTML pienamente formato.

import difflib
from difflib_data import *

d = difflib.HtmlDiff()
print d.make_table(text1_lines, text2_lines)
$ python difflib_html.py

      
f1Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integerf1Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Integer
n2eu lacus accumsan arcu fermentum euismod. Donec pulvinar porttitorn2eu lacus accumsan arcu fermentum euismod. Donec pulvinar, porttitor
3tellus. Aliquam venenatis. Donec facilisis pharetra tortor.  In nec3tellus. Aliquam venenatis. Donec facilisis pharetra tortor. In nec
4mauris eget magna consequat convallis. Nam sed sem vitae odio4mauris eget magna consequat convallis. Nam cras vitae mi vitae odio
5pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu5pellentesque interdum. Sed consequat viverra nisl. Suspendisse arcu
6metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris6metus, blandit quis, rhoncus ac, pharetra eget, velit. Mauris
7urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,7urna. Morbi nonummy molestie orci. Praesent nisi elit, fringilla ac,
8suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta8suscipit non, tristique vel, mauris. Curabitur vel lorem id nisl porta
t9adipiscing. Suspendisse eu lectus. In nunc. Duis vulputate tristiquet9adipiscing. Duis vulputate tristique enim. Donec quis lectus a justo
10enim. Donec quis lectus a justo imperdiet tempus.10imperdiet tempus. Suspendisse eu lectus. In nunc. 

Dati da buttare

Tutte le funzioni che producono sequenze di diff accettano parametri per indicare quali righe dovrebbero essere ignorate, e quali caratteri all'interno di una riga dovrebbero essere ignorati. Si può quindi fare in modo che vengano ignorate modifiche tra due versioni di file che riguardano caratteri di marcatura o spazi, ad esempio.

from difflib import SequenceMatcher

A = " abcd"
B = "abcd abcd"

print 'A = "%s"' % A
print 'B = "%s"' % B

s = SequenceMatcher(None, A, B)
i, j, k = s.find_longest_match(0, 5, 0, 9)
print 'isjunk=None     :', (i, j, k), '"%s"' % A[i:i+k], '"%s"' % B[j:j+k]

s = SequenceMatcher(lambda x: x==" ", A, B)
i, j, k = s.find_longest_match(0, 5, 0, 9)
print 'isjunk=(x==" ") :', (i, j, k), '"%s"' % A[i:i+k], '"%s"' % B[j:j+k]

Il comportamento predefinito di Differ è di non ignorare alcuna riga o carattere esplicitamente, ma di contare sulla capacità di SequenceMatcher di identificare "rumore". Il comportamento predefinito di ndiff è di ignorare spazi e caratteri di tabulazione

$ python difflib_junk.py
A = " abcd"
B = "abcd abcd"
isjunk=None     : (0, 4, 5) " abcd" " abcd"
isjunk=(x==" ") : (1, 0, 4) "abcd" "abcd"

SequenceMatcher

SequenceMatcher, che implementa l'algoritmo di comparazione, può essere usato con sequenze di qualsiasi tipo di oggetto fintanto che lo stesso sia divisibile. Ad esempio due liste di interi possono essere confrontate, ed usando get_opcodes() può essere stampato un insieme di istruzioni per convertire la lista originale in una nuova.

import difflib
from difflib_data import *

s1 = [ 1, 2, 3, 5, 6, 4 ]
s2 = [ 2, 3, 5, 4, 6, 1 ]

matcher = difflib.SequenceMatcher(None, s1, s2)
for tag, i1, i2, j1, j2 in matcher.get_opcodes():
    print ("%7s s1[%d:%d] (%s) s2[%d:%d] (%s)" %
           (tag, i1, i2, s1[i1:i2], j1, j2, s2[j1:j2]))
$ python difflib_seq.py
 delete s1[0:1] ([1]) s2[0:0] ([])
  equal s1[1:4] ([2, 3, 5]) s2[0:3] ([2, 3, 5])
 insert s1[4:4] ([]) s2[3:4] ([4])
  equal s1[4:5] ([6]) s2[4:5] ([6])
replace s1[5:6] ([4]) s2[5:6] ([1])

Si può usare SequenceMatcher con le proprie classi, così come con i tipi built-in.

Vedere anche:

difflib
La documentazione standard della libreria per questo modulo
Pattern Matching: The Gestalt Approach
Discussione su di un algoritmo simile di John W. Ratcliff e D. E. Metzener pubblicato nel Dr. Dobb's Journal del luglio 1988 (in inglese).
Strumenti di elaborazione del testo