4.4 difflib -- Aiuti per calcolare le differenze

Nuovo nella versione 2.1.

class SequenceMatcher
Questa è una classe flessibile, per la comparazione delle coppie di sequenze di qualsiasi tipo, a condizione che gli elementi di sequenza siano chiavi valide per una tabella di hash (NdT: "hashables"). L'algoritmo fondamentale è più vecchio, e un poco più sofisticato, di quello pubblicato alla fine degli anni '80 da Ratcliff e Obershelp col nome iperbolico di ``gestalt pattern matching''. L'idea è quella di trovare la più lunga sotto sequenza corrispondente, che non contenga elementi ``spazzatura'' (l'algoritmo di Ratcliff e Obershelp non si occupa della spazzatura). La stessa idea viene poi applicata ricorsivamente alle parti della sequenza che si trovano a sinistra e a destra della sotto sequenza in corrispondenza. Questo non produce la minima alterazione sulle sequenze, ma tende a produrre corrispondenze che ``appaiono giuste'' agli osservatori umani.

Timing (NdT: Complessità temporale): L'algoritmo base di Ratcliff-Obershelp ha complessità temporale cubica nel caso peggiore, ma normalmente quadratica. SequenceMatcher è quadratica nel peggiore dei casi, ed ha una prevedibilità di comportamento che dipende in modo piuttosto complicato sul numero degli elementi che si trovano in comune tra le due sequenza; il caso migliore è lineare.

class Differ
Questa è una classe per confrontare sequenze di linee di testo, e generare delle differenze o variazioni leggibili da un umano. Differ usa SequenceMatcher sia per confrontare le sequenze di linee, sia per confrontare le sequenze di caratteri all'interno di linee simili (near-matching).

Ogni riga di variazioni di Differ inizia con un codice di due lettere:

Codice  Significato 
'- ' linea unica nella sequenza 1
'+ ' linea unica nella sequenza 2
' ' linea comune ad entrambe le sequenze
'? ' linea non presente in nessuna delle sequenze in input

Le linee che iniziano con `' tentano di guidare l'occhio alle differenze tra le linee e, dove non presenti, in entrambe le sequenze di input. Queste linee possono confondere se la sequenza contiene dei caratteri di tabulazione.

context_diff( a, b[, fromfile[, tofile [, fromfiledate[, tofiledate[, n [, lineterm]]]]]])
Confronta a e b (liste di stringhe); restituisce la variazione (un generatore che genera le righe variate) nel formato contestuale di diff.

Il formato contestuale di diff è un modo compatto di mostrare solo le linee che sono state modificate, più poche linee di contesto. I cambiamenti vengono mostrati in uno stile prima/dopo. Il numero di linee di contesto viene indicato da n, il cui valore predefinito è tre.

In modo predefinito, le linee di controllo di diff (quelle con *** o ---) vengono create con un carattere di fine riga nella loro parte finale. Questo è utile in modo tale che gli input creati da file.readlines() risultino in diff utilizzabili in file.writelines(), dato che entrambi gli input e gli output terminano con dei caratteri di fine riga.

Per gli input che non terminano con un carattere di fine riga, impostate l'argomento lineterm al valore "", così che l'output sia uniformemente privo del fine riga.

Il formato contestuale di diff normalmente ha un header (NdT: intestazione) che inizia con i nomi dei file e la data di modifica. Ognuno di questi può venire specificato utilizzando delle stringhe per fromfile, tofile, fromfiledate e tofiledate. Le date di modifica vengono normalmente espresse nel formato restituito da time.ctime(). Se non specificato, il valore predefinito delle stringhe corrisponde a spazi bianchi.

Tools/scripts/diff.py è un front-end da linea di comando a questa funzione.

Nuovo nella versione 2.3.

get_close_matches( word, possibilities[, n[, cutoff]])
Restituisce una lista delle migliori corrispondenze ``abbastanza buone''. word è una sequenza per cui vengono richieste corrispondenze ravvicinate (NdT: close matches), e possibilities è una lista di sequenze su cui vengono ricercate le corrispondenze word (tipicamente una lista di stringhe).

L'argomento facoltativo n (valore predefinito 3) è il massimo numeri di corrispondenze ravvicinate da restituire; n dev'essere maggiore di 0.

L'argomento facoltativo cutoff (valore predefinito 0.6) è un numero in virgola mobile nell'intervallo [0,1]. Le possibilità che non raggiungono un punteggio di somiglianza con word almeno equivalente a questo valore vengono ignorate.

Le migliori (non più di n) corrispondenze tra le possibilità vengono restituite in una lista, ordinate in base al punteggio di similitudine, le più simili per prime.

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

ndiff( a, b[, linejunk[, charjunk]])
Confronta a e b (liste di stringhe); restituisce la variazione nello stile Differ (un generatore che restituisce le righe variate).

Le chiavi facoltative linejunk e charjunk sono per le funzioni filtro (oppure None):

linejunk: Una funzione che accetta una singola stringa argomento, e che restituisce vero se la stringa è spazzatura, falso se non lo è. Il valore predefinito è None, a partire da Python 2.3. Prima di allora, il valore predefinito era la funzione a livello di modulo IS_LINE_JUNK(), che filtra le linee senza caratteri visibili, ad eccezione di un singolo carattere cancelletto ("#"). A partire da Python 2.3, la sottostante classe SequenceMatcher effettua un'analisi dinamica delle linee che sono così frequenti da costituire rumore, e questo generalmente lavora meglio del sistema adottato precedentemente alla versione 2.3.

charjunk: Una funzione che accetta un carattere (una stringa di lunghezza uno), e restituisce vero se il carattere è spazzatura falso altrimenti. Il valore predefinito è la funzione a livello di modulo IS_CHARACTER_JUNK(), che filtra tutti i caratteri di spaziatura (uno spazio o un tab; nota: è una cattiva idea includere i fine riga tra questi!)

Tools/scripts/ndiff.py è un front-end da linea di comando a questa funzione.

>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
...              'ore\ntree\nemu\n'.splitlines(1))
>>> print ''.join(diff),
- one
?  ^
+ ore
?  ^
- two
- three
?  -
+ tree
+ emu

restore( sequence, which)
Restituisce una delle due sequenze che hanno generato una variazione.

Fornendo una sequence prodotta da Differ.compare() o ndiff(), estrae le linee originate da file 1 o 2 (parametro which), rimuovendo i prefissi delle linee.

Esempio:

>>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
...              'ore\ntree\nemu\n'.splitlines(1))
>>> diff = list(diff) # materializza in una lista la variazione generata   
>>> print ''.join(restore(diff, 1)),
one
two
three
>>> print ''.join(restore(diff, 2)),
ore
tree
emu

unified_diff( a, b[, fromfile[, tofile [, fromfiledate[, tofiledate[, n [, lineterm]]]]]])
Confronta a e b (liste di stringhe); restituisce una variazione (un generatore che genera le righe variate) nel formato unificato di diff.

I diff unificati sono un modo compatto per mostrare solo le linee che sono cambiate, più alcune righe di contesto. I cambiamenti vengono mostrati in uno stile inline (invece che in blocchi separati prima/dopo). Il numero di righe di contesto viene indicato da n, il cui valore predefinito è tre.

In modo predefinito, le righe di controllo di diff (quelle con ---, +++ o @@)) vengono create con un fine riga nella loro parte finale. Questo è utile perché gli input creati da file.readlines() risultino in diff utilizzabili per file.writelines(), dato che sia l'input che l'output terminano con un fine riga.

Per input che non sono terminati da una newline, impostate l'argomento lineterm a "" così che l'output sia uniformemente privo del fine riga.

Il formato diff contestuale normalmente ha una intestazione indicante i nomi dei file e la data di modifica. Questi possono essere specificati utilizzando stringhe per fromfile, tofile, fromfiledate e tofiledate. La data di modifica viene normalmente espressa nel formato restituito da time.ctime(). Se non specificato, il valore delle stringhe corrisponde a spazi bianchi.

Tools/scripts/diff.py è un front-end da riga di comando per questa funzione.

Nuovo nella versione 2.3.

IS_LINE_JUNK( line)
Restituisce vero per le righe che possono venire ignorate. La riga line può venire ignorata se è vuota o contiene un singolo "#", altrimenti non può venire ignorata. Utilizzata come valore predefinito per il parametro linejunk in ndiff() prima di Python 2.3.

IS_CHARACTER_JUNK( ch)
Restituisce vero per i caratteri che possono venire ignorati. Il carattere ch può venire ignorato se ch è uno spazio o un tab, altrimenti non è ignorabile. Utilizzato come valore predefinito per il parametro charjunk in ndiff().

Vedete anche:

Pattern Matching: The Gestalt Approach
Discussione di un algoritmo di similitudine, di John W. Ratcliff e D. E. Metzener. Pubblicato su Dr. Dobb's Journal nel luglio del 1988.



Subsections
Vedete Circa questo documento... per informazioni su modifiche e suggerimenti.