Ndiï¬€ un approccio naturale al confronto di documenti XML

Universita degli Studi di BolognaFacolta di Scienze Matematiche Fisiche e Naturali

Corso di Laurea Specialistica in

Informatica

Ndiffun approccio naturale

al confronto di documenti XML

Tesi di Laurea di: Relatore: Chiar.mo Prof.

MICHELE SCHIRINZI FABIO VITALI

Correlatore: Dott.

ANGELO DI IORIO

Parole chiave: Diff, Change-Tracking, Ricerca dei cambiamenti, XML

21 Marzo 2007

III SessioneAnno Accademico 2005–2006

Indice

Introduzione 1

1 Algoritmi di diff tra documenti XML 71.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Analogie tra Diff e LCS . . . . . . . . . . . . . . . . . . . . . . 91.3 Algoritmi esistenti . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3.1 XyDiff . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.3.2 DeltaXML . . . . . . . . . . . . . . . . . . . . . . . . . 151.3.3 MMDiff e XMDiff . . . . . . . . . . . . . . . . . . . . . 151.3.4 XMLdiff . . . . . . . . . . . . . . . . . . . . . . . . . . 161.3.5 GNUdiff . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2 Approccio naturale al diff 192.1 Percezione del confronto . . . . . . . . . . . . . . . . . . . . . 192.2 Diff e soluzioni possibili . . . . . . . . . . . . . . . . . . . . . 202.3 Metrica della naturalezza . . . . . . . . . . . . . . . . . . . . . 242.4 Confronto dei risultati . . . . . . . . . . . . . . . . . . . . . . 25

3 Ndiff 273.1 Intuizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 L’algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3 Parsing dei documenti XML . . . . . . . . . . . . . . . . . . . 34

3.3.1 Visita top-down . . . . . . . . . . . . . . . . . . . . . . 353.3.2 Visita bottom-up . . . . . . . . . . . . . . . . . . . . . 37

3.4 Partizionamento . . . . . . . . . . . . . . . . . . . . . . . . . . 393.5 Ricerca aggiornamenti . . . . . . . . . . . . . . . . . . . . . . 483.6 Ricerca spostamenti . . . . . . . . . . . . . . . . . . . . . . . . 503.7 Ricerca spostamenti-aggiornamenti . . . . . . . . . . . . . . . 513.8 Propagazione bottom-up . . . . . . . . . . . . . . . . . . . . . 523.9 Rappresentazione del risultato . . . . . . . . . . . . . . . . . . 55

i

INDICE

4 Napply:Motore di ricostruzione 594.1 Sintassi del delta . . . . . . . . . . . . . . . . . . . . . . . . . 594.2 Applicazione del delta . . . . . . . . . . . . . . . . . . . . . . 64

4.2.1 Inserimento di un nodo . . . . . . . . . . . . . . . . . . 654.2.2 Inserimento di un albero . . . . . . . . . . . . . . . . . 684.2.3 Cancellazione di un nodo . . . . . . . . . . . . . . . . . 694.2.4 Cancellazione di un albero . . . . . . . . . . . . . . . . 694.2.5 Aggiornamento di un nodo . . . . . . . . . . . . . . . . 70

4.3 Trasformazione da Vn a Vn+1 . . . . . . . . . . . . . . . . . . . 70

5 Nmerge:Motore di markup dei cambiamenti 735.1 Markup delle differenze . . . . . . . . . . . . . . . . . . . . . . 735.2 Inserimento del markup relativo alle differenze . . . . . . . . . 76

5.2.1 Inserimento di un nodo . . . . . . . . . . . . . . . . . . 775.2.2 Inserimento di un albero . . . . . . . . . . . . . . . . . 795.2.3 Cancellazione di un nodo . . . . . . . . . . . . . . . . . 805.2.4 Cancellazione di un albero . . . . . . . . . . . . . . . . 815.2.5 Aggiornamento di un nodo . . . . . . . . . . . . . . . . 81

6 Un’applicazione di Ndiff: LIBRA 856.1 Contesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856.2 LIBRA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7 Conclusioni 917.1 Espansione future . . . . . . . . . . . . . . . . . . . . . . . . . 91

Bibliografia e riferimenti 93

ii

Elenco delle figure

1.1 Esempio di matrice per il calcolo della LCS tra due sequenze . 12

1.2 Tabella riassuntiva degli algoritmi esaminati . . . . . . . . . . 18

2.1 Ambiguita nel confronto . . . . . . . . . . . . . . . . . . . . . 21

2.2 Valutazione di parti aggiornate . . . . . . . . . . . . . . . . . 22

2.3 Valutazione di parti spostate . . . . . . . . . . . . . . . . . . . 23

2.4 Confronto tra Ndiff e altri algoritmi . . . . . . . . . . . . . . . 26

2.5 Confronto tra Ndiff e altri algoritmi sulla media della dimen-sione dei delta rilevati . . . . . . . . . . . . . . . . . . . . . . 26

3.1 Modo di procedere di Ndiff . . . . . . . . . . . . . . . . . . . . 28

3.2 Relazione di associazione tra i nodi dei documenti confrontati 30

3.3 Schema del calcolo del diff tra due documenti . . . . . . . . . 33

3.4 Vettore dei puntatori calcolato con una previsita sinistra suun semplice documento . . . . . . . . . . . . . . . . . . . . . . 36

3.5 Esempio di calcolo dei valori HashTree . . . . . . . . . . . . . 38

3.6 Esempio di calcolo della LCCS. . . . . . . . . . . . . . . . . . 41

3.7 Schema di chiamata della funzione findLCCS . . . . . . . . . . 43

3.8 Schema di calcolo della MSC in modo ingenuo . . . . . . . . . 44

3.9 Schema di calcolo della MSC in modo efficiente . . . . . . . . 46

3.10 Grafico delle aree di ricerca degli aggiornamenti. . . . . . . . . 49

3.11 Grafico tridimensionale della funzione che calcola la somiglian-za di nodi di testo. . . . . . . . . . . . . . . . . . . . . . . . . 50

3.12 Grafico delle aree di ricerca degli spostamenti . . . . . . . . . 51

3.13 Diagramma di decisione durante la propagazione del matchingBottom-up. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.14 Schema di propagazione del matching bottom-up . . . . . . . 54

3.15 Interpretazione di < sugli alberi relativi ai documenti XMLconfrontati. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1 Schema di applicazione del delta. . . . . . . . . . . . . . . . . 59

iii

4.2 Un’esecuzione di operazione insert di un nodo. . . . . . . . . . 664.3 Processo di adozione dei nodi . . . . . . . . . . . . . . . . . . 674.4 Esecuzione dell’operazione di inserimento di un albero. . . . . 684.5 Un’esecuzione di operazione delete di un nodo. . . . . . . . . . 694.6 Esecuzione di operazione di cancellazione di un albero. . . . . 704.7 Trasformazione del documento Vn in Vn+1 attraverso l’appli-

cazione del delta. . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.1 Applicazione delle informazioni di markup alla versione Vn perottenere Vn→n+1 . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.2 Un’esecuzione di operazione insert di un nodo. I nuovi figlidel nodo inserito vengono marcati come downgraded . . . . . . 78

5.3 Un’esecuzione di operazione insert di un albero. . . . . . . . . 795.4 Un’esecuzione di operazione delete di un nodo. . . . . . . . . . 805.5 Un’esecuzione di operazione delete di un albero. . . . . . . . . 815.6 Aggiornamento di un nodo di testo. . . . . . . . . . . . . . . . 82

6.1 Esempio di testo a fronte. . . . . . . . . . . . . . . . . . . . . 886.2 Funzionamento di LIBRA . . . . . . . . . . . . . . . . . . . . 89

Introduzione

Il presente lavoro illustra un algoritmo per rilevare ed esprimere i cambia-

menti tra diverse versioni di uno stesso documento XML. Questi algoritmi

vengono chiamati di diff e trovano applicazione in tutti quei sistemi che

hanno la necessita di mantenere e tracciare lo sviluppo di un documento.

Infatti l’importanza di tracciare e mantenere la storia di un documento e

fondamentale nel momento in cui vogliamo capire come si e arrivati alla sua

versione definitiva. In [Vitali et al,95] e [Vitali,99] si mettono in evidenza

alcuni importanti vantaggi di questi sistemi:

• Revisione storica: L’evoluzione nel tempo e una caratteristica intrin-

seca di alcuni sistemi, per cui e strettamente necessario tenere traccia

delle versioni, basti pensare al diritto, in cui e necessario applicare le

leggi in base al loro contenuto nel momento in cui e avvenuto l’evento

(nonostante possono essere state modificate, soprattutto vista la len-

tezza delle procedure legali) o ai prodotti software di cui si pubblicano

diverse release, mentre si lavora a nuove versioni del software stesso.

In alcuni ambienti come l’ingegneria del software, d’altra parte, e ne-

cessaria un’analisi del processo produttivo per controllare la qualita e

la crescita del prodotto, per cui il versionamento diventa ulteriormente

necessario.

• Sicurezza e produzione esplorativa: La possibilita di ‘congelare’

e recuperare gli stadi intermedi del proprio lavoro, se da un lato per-

mette di sentirsi piu sicuri, dall’altro favorisce anche l’esplorazione e

1

INTRODUZIONE

gli esperimenti, data la possibilita di tornare indietro sui propri passi e

ripetere le prove in una direzione diversa.

• Collaborazione distribuita: se piu autori collaborano alla produ-

zione di un documento in un ambiente che supporta la gestione delle

versioni (per cui ogni autore crea una nuova versione dopo ogni sessio-

ne di editing), e possibile in qualunque momento evidenziare l’apporto

dato da ognuno e le differenze tra i diversi contributi. Inoltre un mec-

canismo di merging, ossia fusione tra le diverse versioni, permette di

convergere ad un unico risultato finale, che e appunto lo scopo ultimo

della produzione collaborativa.

• Collaborazione parallela e asincrona: se supportati da un sistema

di versionamento, tutti gli autori possono modificare un documento

indipendentemente e nello stesso momento, creando diverse varianti

che convergeranno nello stato finale. Poiche ogni sessione di editing

crea una versione indipendente, non c’e nessun rischio di sovrascrittura

e cancellazione del contributo di altri autori e non e necessario nessun

meccanismo di locking alle risorse.

• Pluralismo: chiunque puo creare la propria versione personale del do-

cumento, aggiungendo suggerimenti, modifiche, pareri contrari o nuovi

collegamenti, poiche la fase di editing non coinvolge la risorsa originale

ma ne crea una nuova e ben identificata.

• Forme emergenti di collaborazione[Maioli et al,94]: poiche ogni

utente puo creare la propria versione personale di un documento, egli

puo, in una seconda fase, far visionare la propria variante agli autori

ufficiali, che valuteranno la possibilita di accorpare tale versione alla

storia ufficiale del documento.

• Efficienza e scalabilita: Sono automaticamente risolti problemi di ef-

ficienza e di scalabilita nella produzione distribuita in termini di numero

2

INTRODUZIONE

e distribuzione degli autori, dei documenti e dei server interessati. In-

fatti non risultano piu necessarie strategie di locking, accesso controlla-

to alle risorse, replicazione di oggetti, sincronizzazione o serializzazione

delle operazioni.

Un sistema di questo tipo puo essere realizzato salvando interamente il docu-

mento in diversi istanti di tempo nell’arco del suo sviluppo: una versione sara

stabilita dall’attimo in cui l’utente decide di salvare il documento. Questo

modo di creare versionamento e molto semplice ma presenta notevoli svan-

taggi. Pensiamo alla stesura di un documento molto grande in cui le varie

versioni si discostano per poche frasi. Procedendo in questo modo abbiamo

un notevole spreco di memoria. Intuitivamente sarebbe molto meglio salva-

re solo i cambiamenti avvenuti tra versioni successive che ragionevolmente

avranno una dimensione minore della versione intera. Adottando quest’ul-

timo procedimento, abbiamo un documento iniziale(la prima stesura) e una

lista di documenti delta che descrivono i cambiamenti tra la versione n e la

versione n+1. I documenti delta conterranno solo i cambiamenti tra le ver-

sioni e forniranno un metodo semplice per esaminare e confrontare le varie

versioni.

Una buona gestione del versionamento dipende dal modo con cui andiamo a

rilevare le differenze tra versioni successive. Possiamo usare due approcci:

• Realizzare editor capaci di memorizzare le operazioni che l’utente com-

pie nel momento in cui scrive il documento;

• Realizzare algoritmi capaci di confrontare due versioni successive e

trovare i cambiamenti tra queste.

Procedendo nel secondo modo, andiamo a ‘supporre’ quali possano essere

state le operazioni compiute dall’utente nel passare da una versione alla suc-

cessiva. Intuitivamente la soluzione ad un problema di questo tipo non e

unica, infatti possiamo avere un’insieme di documenti delta, tutti corretti,

che sono possibili interpretazioni dei cambiamenti avvenuti. Diventa quindi

3

INTRODUZIONE

necessario definire delle metriche su cui valutare e quantificare la bonta del

risultato. La metrica piu usata si basa sul dare un peso alle diverse ope-

razioni rilevate e promuovere l’algoritmo che ottiene il risultato con il peso

minimo. Il nostro approccio invece considerera il risultato dal punto di vi-

sta della naturalezza, definibile come la capacita dell’algoritmo di rilevare le

modifiche seguendo una concezione di confronto propria della natura umana.

Vedremo che spesso il delta minimo(con peso minore) coincidera con quello

piu ‘naturale’.

Per completare la contestualizzazione del nostro lavoro definiamo la for-

ma in cui sono scritti i documenti da confrontare. L’algoritmo realizzato si

occupa di trovare le differenze tra documenti strutturati ed in particolare

documenti XML (eXtensible Markup Language).

XML e un linguaggio di markup descrittivo che permette di definire la strut-

tura che descrive un contesto informativo all’interno del contesto stesso, pre-

cisando l’articolazione di un documento attraverso l’uso di marcatori inseriti

al suo interno. XML viene utilizzato spesso nella rappresentazione di do-

cumenti testuali, anche di carattere letterario o genericamente umanistico,

diffondendosi quindi in un settore nel quale la rappresentazione digitale delle

informazioni costituisce in larga misura un elemento di novita. In secondo

luogo, la versatilita di XML nel generare definizioni di diverse tipologie di

documento, produce la convinzione diffusa che tale linguaggio possa costitui-

re una sorta di strumento ‘neutro’ con il quale rappresentare la conoscenza

contenuta nelle diverse fonti informative. Esso risulta essere abbastanza ge-

nerale da poter essere utilizzato nei piu disparati contesti: dalla definizione

della struttura di documenti allo scambio di informazioni tra sistemi diversi,

dalla rappresentazione di immagini alla definizione di formati di dati. Questo

aspetto ha contribuito a rendere il ricorso agli strumenti informatici sempre

piu omogeneo anche in contesti molto diversi tra loro.

4

INTRODUZIONE

Ndiff e un algoritmo capace di confrontare ed esprimere le differenze tra

due documenti XML, cercando di derivare un ‘delta naturale’. Dalla dif-

fusione di XML e dall’importanza dei sistemi di versionamento si evince il

numero di applicazioni che potrebbero usare algoritmi di questo tipo. Ndiff

non e il nostro primo lavoro in questo campo, in particolare Ndiff e il ri-

sultato derivato dalla nostra precedente esperienza nella realizzazione di un

algoritmo di diff [Schirinzi,04] all’interno del motore di versionamento nel

progetto IsaWiki[ISA]. Abbiamo migliorato il nostro precedente lavoro ren-

dendo modulare l’esecuzione dell’algoritmo, definendo il concetto di ‘fase’ e

rendendo queste indipendenti una dall’altra. Per ogni fase abbiamo esplici-

tato dei parametri che permettono di selezionare un particolare tipo di delta

dallo spazio delle soluzioni possibili, dove i parametri sono associabili a con-

cezioni intuitive di confronto, sulle quali basiamo il concetto di ‘naturalezza

del risultato’. Inoltre abbiamo inserito una nuova fase che permette l’indi-

viduazione di altri tipi di modifiche, migliorando la propagazione bottom-up

del matching(cap.3.8). La rappresentazione del delta e stata completamente

ristrutturata eliminando informazioni di markup superflue e ottimizzando l’e-

spressione dei cambiamenti a livello di aggiornamento di nodi testuali e nodi

elemento. Di conseguenza abbiamo modificato sia il motore di ricostruzione

dei documenti, chiamandolo Napply, che il motore di ‘applicazione con mar-

kup’, chiamandolo Nmerge. A livello implementativo, abbiamo aggiornato il

vecchio codice PHP adattandolo alla versione 5 di PHP(con supporto per le

nuove specifiche DOM) ed inserendo le classi relative alle nuove funzionalita

sviluppate.

La motivazione che ha portato a riprendere e migliorare il nostro lavoro e

stata la richiesta da parte del servizio informatico del Senato della Repubbli-

ca, di un algoritmo di diff capace di interpretare al meglio le differenze tra

documenti XML rappresentanti dei DDL(Disegni di Legge), dove, reputato

interessante il nostro primo lavoro, hanno chiesto informazioni e degli esempi

di applicazione dell’algoritmo. Abbiamo realizzato a tale scopo un’interfaccia

grafica per Ndiff, soprannominata LIBRA(cap.6) che permette di testare e

5

INTRODUZIONE

visualizzare i risultati sui DDL.

Di seguito, dopo l’analisi della letteratura scientifica sul diff di documenti

XML contenuta nel primo capitolo, seguira nel capitolo successivo una de-

scrizione dell’approccio utilizzato da Ndiff. Nel terzo capitolo descriveremo

formalmente l’algoritmo; nel quarto e nel quinto capitolo troviamo rispetti-

vamente i due modi in cui si puo utilizzare il delta prodotto da Ndiff, cioe

la riapplicazione alla versione n per ottenere la versione n+1 e la creazione

di un documento strutturato uguale al documento Vn, in cui sono riportate

le modifiche effettuate tra le due versioni. Infine nel sesto capitolo vedremo

l’applicazione di Ndiff al caso reale dei Disegni di Legge del Senato.

6

Capitolo 1

Algoritmi di diff tra documentiXML

In questo capitolo forniamo dei criteri di valutazione sugli algoritmi di diff

e presentiamo un’importante analogia tra il problema del diff e il proble-

ma della LCS. Di seguito elenchiamo una rassegna di lavori che sono stati

realizzati in questo campo. Confronteremo gli algoritmi basandoci sulla loro

descrizione formale ed in particolare considereremo il tempo di calcolo, la

memoria necessaria e la qualita del risultato di ogni soluzione.

1.1 Introduzione

Presentiamo prima di tutto le due principali aree che un algoritmo di diff

deve affrontare: la ricerca dei cambiamenti e la loro rappresentazione. Inoltre

definiamo alcuni criteri di valutazione della bonta di un algoritmo in queste

aree.

• Ricerca dei cambiamenti: Questo problema presenta in ingresso

due documenti e deve restituire un documento delta che rappresenti i

cambiamenti fra i due documenti in input. Gli aspetti importanti in

questa fase sono i seguenti:

– Correttezza: Un algoritmo di diff e considerato corretto se resti-

tuisce un delta sufficiente a trasformare la vecchia versione di un

7

ALGORITMI DI DIFF TRA DOCUMENTI XML

documento XML nella nuova versione. In altre parole, un diff e

corretto se permette la ricostruzione del documento senza perdita

di dati. Deve quindi individuare tutte le modifiche avvenute tra

le due versioni.

– Minimizzazione: In alcune applicazioni, l’obbiettivo principale

del diff e ottenere un delta con dimensione minima. La minimiz-

zazione del delta e un obbiettivo importante se pensiamo a sistemi

in cui bisogna memorizzare notevoli quantita di documenti.

– Semantica: Un algoritmo di diff e considerato semanticamente

corretto se il delta ottenuto si riferisce effettivamente a quello che

e successo fra i due documenti XML in input.

– Velocita e complessita: Un altro fattore di valutazione di un

algoritmo diff e il tempo di esecuzione e la memoria occupata nel

calcolo del risultato. Per esempio alcuni algoritmi esprimono un

delta in tempo e spazio quadratico.

– Ricerca degli spostamenti: La capacita di trovare gli sposta-

menti di parti del documento e un ulteriore parametro di valuta-

zione per un algoritmo di diff.

• Rappresentazione dei cambiamenti: L’importanza della rappre-

sentazione del risultato di un algoritmo di Diff dipende dalle applica-

zioni in cui verra usato:

– Nei sistemi di versionamento[Shu yao et al,01], la rappresen-

tazione del delta deve permettere un buon risparmio di memoria

e un’efficiente ricostruzione delle versioni del documento.

– Nei sistemi di visualizzazione dei cambiamenti, la rappre-

sentazione del delta deve essere chiara e facilmente analizzabile.

8

1.2 Analogie tra Diff e LCS

Ci sono due possibili interpretazioni per la ricerca e l’espressione del delta:

il modello Kuo-Chung Tai’s[Kuo-Chung,79] e quello di Selkow’s[Selkow,77].

In [Kuo-Chung,79] la cancellazione di un nodo implica che i figli di questo

vengono adottati dal padre. Per esempio:

<capitolo><sezione>

<paragrafo>Cancellami

</paragrafo></sezione>

</capitolo>

Se cancelliamo il nodo <sezione> abbiamo

<capitolo><paragrafo>

Cancellami</paragrafo>

</capitolo>

mentre in [Selkow,77] ogni nodo e un’entita rappresentante l’intero sotto-

albero radicato in esso, quindi la cancellazione di un nodo in questo mo-

dello porta alla rimozione di tutto il sotto-albero radicato. Nell’esempio

precedente:

<capitolo> </capitolo>

Nel diff fra documenti XML di solito si preferisce trattare il secondo ap-

proccio, in quanto piu vicino alla logica di definizione di XML. Questo puo

non essere una buona soluzione se trattiamo per esempio documenti XML

con content model misto, in particolare documenti che si riferiscono a testi

letterali, dove ha piu senso usare il primo approccio.


In questa sezione presentiamo un’importante analogia tra il problema del diff

e il problema di trovare la LCS(Longest Common Subsequence) tra due se-

quenze. Il problema di trovare le differenze fra due documenti e riconducibile

a trovare il numero minimo di operazioni per trasformare una stringa x in una

9

stringa y [A. Apostolico et al,97][V.I.Levenshtein,66][R. A. Wagner et al,74].

Inserimenti e cancellazioni corrispondono a inserire e cancellare un simbolo

in una stringa. Per avere il minimo delta per trasformare la stringa x nella

stringa y dobbiamo trovare la ‘Longest Common Subsequence’ fra x e y.

Definiamo sottosequenza di una certa sequenza la sequenza originale con l’e-

sclusione di alcuni elementi(eventualmente nessuno). Formalmente, data una

sequenza X=<x1,x2,x3,...,xm>, una sequenza Z=<z1,z2,z3,...,zk> viene detta

sottosequenza di X se esiste una sequenza, strettamente crescente, <i1,i2,

..., ik> di indici di X tale che per tutti gli indici j=1,2,...,k, vale xij=zj.

Per esempio, Z=<B,C,D,B> e una sottosequenza di X = <A,B,C,B,D,A,B>,

dove la corrispondente sequenza di indici risulta <2,3,5,7>.

Date due sequenze X e Y, diciamo che una sequenza Z e una sottosequenza

comune di X e Y se Z e una sottosequenza di entrambe le sequenze X e Y.

Per esempio, se X=<A,B,C,B,D,A,B> e Y=<B,D,C,A,B,A> la sequenza

<B,C,A> e una sottosequenza comune di X e Y. La sequenza <B,C,A> non

e la piu lunga sottosequenza comune di X e Y, dato che e lunga 3 e la se-

quenza <B,C,B,A>, che e comune a X e Y, ha lunghezza 4. La sequenza

<B,C,B,A> e una LCS di X e Y, come pure la sequenza <B,D,A,B>: non

esiste alcuna sottosequenza comune di lunghezza maggiore o uguale a 5.

Nel problema della piu lunga sottosequenza comune sono date due

sequenze X=<x1,x2,x3,...,xm> e Y=<y1,y2,y3,...,yn> e si vuole determinare

la sottosequenza comune di X e Y di lunghezza massima.

Un metodo di soluzione ingenuo per il problema della LCS consiste nell’enu-

merare tutte le sottosequenze di X e nel controllare che ogni sottosequenza

sia anche sottosequenza di Y. Durante ogni fase del procedimento risoluti-

vo bisogna mantenere l’informazione sulla piu lunga sottosequenza trovata

fino a quel punto. Dato che ogni sottosequenza di X corrisponde a un sot-

toinsieme <1,2,...,m> di indici di X, la soluzione ingenua richiede un tempo

esponenziale, rendendola impraticabile per sequenze lunghe. Illustreremo di

seguito un algoritmo per risolvere il problema in un tempo quadratico.

Per illustrare la soluzione facciamo riferimento alla seguente procedura:

10


1: procedure lengthLCS(var X,Y )

2: begin

3: m := lenght(X)

4: n := lenght(Y)

5: for i := 1 to m do

6: c[i,0] := 0

7: for j := 1 to n do

8: c[0,j] := 0

9: for i := 1 to m do

10: for j := 1 to n do

11: if Xi == Yj then

12: begin

13: c[i,j] := c[i-1,j-1]+1

14: b[i,j] := ↖15: end

16: else

17: if c[i− 1, j] ≥ c[i, j − 1] then

18: begin

19: c[i,j] := c[i-1,j]

20: b[i,j] := ↑21: end

22: else

23: begin

24: c[i,j] := c[i,j-1]

25: b[i,j] := ←26: end

27: return b,c

28: end

11

Figura 1.1: Esempio di matrice per il calcolo della LCS tra due sequenze

La procedura lenghtLCS ha come parametri di ingresso le due sequenze

X=<x1,x2,x3,...,xm> e Y=<y1,y2,y3,...,yn>, i valori c[i,j] sono memorizza-

ti in una tabella c[0..m,0..n] e gli elementi della tabella sono calcolati se-

guendo l’ordine delle righe. La procedura utilizza anche una seconda tabella

b[1..m,1..n] per semplificare la costruzione di una soluzione ottima. L’idea in-

tuitiva e che il generico elemento b[i,j] ‘punta’ alla posizione della tabella che

corrisponde alla scelta della soluzione ottima del sottoproblema nel calcolo

di c[i,j]. La procedura restituisce le due tabelle b e c; il valore dell’elemento

c[m,n] e la lunghezza di una LCS di X e Y. Per chiarire il funzionamento

dell’algoritmo consideriamo il seguente esempio:

Supponiamo di voler calcolare la sequenza massima fra le due sequenze

X=<A,B,C,B,D,A,B> e Y=<B,D,C,A,B,A>. Dopo la chiamata della pro-

cedura lenghtLCS abbiamo le due tabelle b e c rappresentate insieme in

fig.1.1 dove in grigio si vede la scelta del percorso che determina una LCS

per le sequenze trattate. La tabella b restituita dalla procedura lenghtLCS

12

puo essere utilizzata per costruire direttamente una LCS per le sequenze

X=<A,B,C,B,D,A,B> e Y=<B,D,C,A,B,A>. L’idea e piuttosto semplice.

Consideriamo l’elemento b[m,n] e poi percorriamo la tabella nel senso indica-

to dai puntatori. Quando il valore dell’elemento b[i,j] e uguale a↖, significa

che xi = yj appartiene alla LCS. Utilizzando questa strategia gli elementi

della LCS vengono scanditi in ordine inverso. La seguente procedura ricor-

siva stampa una LCS di X e Y nel giusto ordine. La chiamata iniziale della

procedura e PrintLCS(b,X,lenght[X],lenght[Y]).

1: procedure printLCS(var b, X, i, j)

2: begin

3: if (i 6= 0)and(j 6= 0) then

4: begin

5: if (b[i, j] ==↖ then

6: begin

7: printLCS(b,X,i-1,j-1)

8: print Xi

9: end

10: else

11: if b[i, j] ==↑ then

12: printLCS(b,X,i-1,j)

13: elseprintLCS(b,X,i,j-1)

14: end

15: end

Per l’esempio, la procedura stampera la sequenza <B,C,B,A>. E importante

notare che la funzione lenghtLCS impiega un tempo O(m×n), e una dimen-

sione di memoria dell’ordine di 2×m×n per memorizzare le tabelle ‘b’ e ‘c’.

Quindi anche se la funzione printLCS esegue in O(m+n), questa soluzione

ha una complessita totale di O(m×n).

Ci sono varie migliorie per risolvere il problema della LCS, in [Hirschberg,75]

viene proposta una soluzione per portare lo spazio usato dall’algoritmo a

13


lineare. Nel 1986 E.W.Myyers descrive un algoritmo[Eugene W. Myers.,86]

capace di calcolare una LCS in O(n×D), dove D e il numero di differenze fra

le stringhe in input, usato nel famoso GNU diff[GNU diff] programma per la

comparazione di file.

1.3 Algoritmi esistenti

In questa sezione riportiamo le informazioni relative ad un gruppo di lavori

che rappresentano le soluzioni migliori in questo campo. In particolare for-

niscono un set abbastanza ampio di tipologie di approcci che possono essere

usati per affrontare il problema. Gli altri lavori si basano principalmente sulle

stesse idee. Nella definizione delle complessita dei vari algoritmi ci riferiremo

con N alla somma del numero di nodi dei due documenti da confrontare e

con D al numero di differenze tra i documenti.

1.3.1 XyDiff

XyDiff[G.Cobena et al] e un algoritmo che ha come punto di forza la velocita

di calcolo. Questo e stato implementato come supporto nella gestione del-

la memorizzazione di diverse versioni dei documenti all’interno del progetto

XyLemme[XyLemme], dove era richiesto di memorizzare giornalmente una

quantita enorme di documenti. Diventava quindi fondamentale la velocita di

calcolo.

L’idea dell’algoritmo e di ‘segnare’ ogni nodo dei documenti XML da con-

frontare, con un valore hash rappresentante tutto il sotto-albero radicato. Di

seguito i nodi vengono inseriti in una coda con priorita che e data dal pe-

so dell’albero radicato. Il peso di un albero viene calcolato in tempo lineare

attraverso una funzione ω(x) e risulta proporzionale al testo contenuto. L’in-

serimento dei nodi nella coda con priorita, permette di ridurre il numero di

confronti successivi tra i due documenti. Quando due nodi vengono uguaglia-

ti, si cerca di eguagliare iterativamente i loro genitori. L’algoritmo supporta

le operazioni di inserimento, cancellazione, aggiornamento e spostamento ed

14


e in grado di eseguire comparazioni di documenti con dimensioni fino a 10

Mb. Inoltre prevede la possibilita di attivare alcune opzioni, come il non

considerare gli ‘spazi bianchi’. Il primo rilascio dell’algoritmo e stato fatto

in C++, successivamente e stato fatto un porting dell’algoritmo in java con

il nome jXyDiff. XyDiff esegue in tempo O(n×log(n)) e spazio O(n).

1.3.2 DeltaXML

DeltaXML[DeltaXML] e un tool commerciale creato da deltaXML.com, ca-

pace di confrontare, unire e sincronizzare diverse versioni di un documento

XML. I documenti in input devono essere ben formati e devono avere lo stesso

elemento radice, mentre la conoscenza del DTD relativa al documento non e

richiesta. Il delta trovato e descritto solo in termini di inserimenti, cancella-

zioni e aggiornamenti. Gli spostamenti non sono rilevati, perche porterebbero

l’algoritmo ad avere una complessita maggiore. Nel caso in cui un nodo e

spostato tra le due versioni, DeltaXML assume che il nodo sia stato cancella-

to dalla vecchia posizione e inserito in quella nuova. DeltaXML non produce

un documento delta contenente solo le differenze tra i documenti confrontati,

ma un documento XML con una struttura[Robin La Fontaine,2001] simile al

documento originale, in modo tale da poter essere comprensibile e utilizzabile

per una consultazione visiva o come input per ulteriori processi. DeltaXML

usa un algoritmo di matching tra alberi che come affermano gli autori esegue

in tempo e spazio lineari.

1.3.3 MMDiff e XMDiff

Sudarshan S. Chawathe[Chawathe,99] ha presentato un algoritmo capace di

calcolare il delta minimo tra due documenti XML. Intuitivamente l’algorit-

mo costruisce una matrice come quella descritta in fig.1.1, variando pero le

condizioni di inserimento delle frecce ↖, in seguito trova una LCS sfruttan-

do la matrice. MMDiff esegue in tempo O(n2) con spazio O(n2), in XMDiff

15

viene ridotto lo spazio usato a O(n). Entrambi gli algoritmi non rilevano

operazioni di spostamento.

1.3.4 XMLdiff

XMLdiff[XMLDiff] e stato sviluppato da Logilab; attualmente viene incluso

nella distribuzione Debian GNU/Linux come principale tool per il confron-

to di documenti XML. Questo tool utilizza un formato interno(Xupdate)

per rappresentare i cambiamenti tra le varie versioni. Un esempio di delta

prodotto e il seguente:

[rename, /root[1]/sub[1]/node[2]/b[1], node][move−after,/root[1]/sub[1]/node[2]/node[1],/root[1]/sub[1]/node[1]][insert−after, /root[1]/sub2[1]/node[1], <node/> ][rename,/root[1]/sub2[1]/node[3], b][move−first,/root[1]/sub2[1]/b[1], /root[1]/sub2[1]/node[2]][remove, /root[1]/sub[1]/node[3]]

Il principale svantaggio di questo tool risiede nella codifica del delta in quan-

to e in una forma difficile da comprendere. XMLdiff offre due modalita per

il confronto. La prima(Fast match) realizzata per documenti molto grandi,

basata su concetti espressi in [Chawathe,96]: l’algoritmo opera attraverso la

ricerca di una LCS con l’algoritmo di Myers([Eugene W. Myers.,86]) e quindi

il tempo di computazione diventa O(ND). La seconda modalita si basa su

concetti espressi in [Kaizhong et al,89] e [Kaizhong,90], dove vengono cercate

le operazioni di inserimento e cancellazione in base al modello di Kuo-Chung

Tai’s[Kuo-Chung,79] illustrato precedentemente. Piu precisamente, viene mi-

gliorato l’algoritmo di Zhang Shasha aggiungendo un’operazione denominata

swap, che realizza uno scambio tra un nodo ed i suoi vicini[Barnard et al,95].

Questa seconda modalita calcola in tempo quadratico.

1.3.5 GNUdiff

GNUdiff[GNU diff] e il famoso tool diff presente nei sistemi linux. GNUdiff

effettua un confronto fra due file o tra elenchi di file, riportando le differenze

riscontrate. Il confronto tra i file e basato sulle linee, quindi GNUdiff non

16

sfrutta i vantaggi forniti da una rappresentazione strutturata dei documenti.

I parametri di GNUdiff permettono all’utente di scegliere di ignorare gli spazi

bianchi, le linee vuote, il case-sensitive e una moltitudine di altre opzioni.

Nel formato del delta di default, ciascun gruppo di modifiche e preceduto da

un linea di informazioni riportante i numeri di linea di inizio e fine del gruppo

per ciascuno dei due files (vecchio e nuovo) e dal tipo di modifica necessaria

per riallinearli (c = change, a=append, d=delete). Di seguito ciascuna riga di

output e preceduta dal simbolo < se la linea deve essere eliminata dal vecchio

file, e dal simbolo > se la linea deve essere aggiunta al nuovo file. Il tool e

basato sull’algoritmo D-Band[Eugene W. Myers.,86]. Questo algoritmo non

e capace di rilevare gli spostamenti. Per effettuare confronti di file XML con

questo approccio, e necessario formattare i documenti XML in modo che le

linee assumano significato. Un esempio di confronto tra il documento:

<?xml version="1.0"?><a>

<c/>



<c/>

</a>

e il documento:


<c/><c/>

</a>

dove l’interpretazione del delta prodotto diviene:


<c/>

− − 

<c/>

17

Figura 1.2: Tabella riassuntiva degli algoritmi esaminati

</a>

Da questo esempio si puo vedere come GNUdiff non prenda in considerazione

la struttura associata al documento.

1.4 Conclusioni

Riportiamo in fig.1.2 una tabella riassuntiva delle caratteristiche dei diversi

lavori che si occupano dell’argomento. Dall’analisi di questi lavori, emerge

l’idea di segnare i sotto-alberi dei documenti da confrontare attraverso valori

hash che ne faciliteranno il confronto. Molti algoritmi usano come soluzione

ridurre il problema a quello della LCS attraverso una serializzazione degli

alberi relativi ai documenti XML da trattare. In questo lavoro noi abbia-

mo implementato un algoritmo basandoci principalmente sulle stesse idee,

ma dando una rilevanza maggiore a cio che noi definiamo naturalezza del

risultato, definibile come la capacita dell’algoritmo di rilevare le modifiche

seguendo una concezione di confronto propria della natura umana.

18

Capitolo 2

Approccio naturale al diff

In questo capitolo cercheremo di affrontare e formalizzare la percezione uma-

na di confronto per ricavare un procedimento che sara alla base di Ndiff.

2.1 Percezione del confronto

Vogliamo ora formalizzare la percezione umana di confronto nel momento in

cui ci troviamo davanti al problema di cercare le differenze tra due documenti

simili.

Dovendo effettuare il confronto manualmente, cercheremo prima di tutto le

parti invariate tra i due documenti e le useremo come base per le osserva-

zioni successive. Valuteremo una parte del documento come aggiornata, se

e simile nei due documenti e si trova nella stessa posizione, dove per stessa

posizione intendiamo l’essere tra due parti ritenute uguali(fig.2.2). Invece

valuteremo una parte come spostata se uguale ma in posizione diversa nei

due documenti(fig.2.3). Comunque potrebbe non essere sempre possibile fa-

re una distinzione netta fra i vari tipi di modifica. Supponiamo di dare due

documenti da confrontare a persone diverse e di chiedergli di evidenziarne

le differenze. Probabilmente le differenze trovate dalle due persone saranno

simili, a patto che non vi siano casi ambigui. Infatti nel momento in cui ab-

biamo delle differenze che possono essere valutate in modo diverso, subentra

la scelta soggettiva della persona, che la portera a scegliere la tipologia di

19

APPROCCIO NATURALE AL DIFF

differenza che giudica piu opportuna. Un esempio di ambiguita si vede in

fig.2.1 dove una parte del documento A puo essere considerata come sposta-

ta o aggiornata dalle relative parti del documento B. Schematizzando queste

osservazioni vengono fuori tre nozioni:

• localita: Due parti di due documenti hanno la stessa localita se si

trovano tra parti riconosciute uguali.

• somiglianza: Due parti si assomigliano se il testo e simile.

• distanza: la distanza tra una parte A del documento A e una parte

B del documento B e definibile come il numero di parti trovate uguali

che intercorrono tra la parte A e la parte B. Se due elementi hanno la

stessa localita allora la loro distanza e 0.

Attraverso questi tre concetti possiamo definire un procedimento naturale

del confronto. In ogni caso non e possibile eliminare quel tipo di ambiguita

illustrata precedentemente, ma si puo scegliere la soluzione desiderata attra-

verso dei valori che esprimono valutazioni sui tre concetti esposti.

Ndiff si basa sul procedimento descritto precedentemente, cercando di inter-

pretare al meglio le differenze tra i due documenti. Le ambiguita vengono

risolte attraverso parametri passati all’algoritmo.

2.2 Diff e soluzioni possibili

Di solito la soluzione al problema del diff non e unica. Esistono infatti un

insieme di delta tutti corretti che rappresentano possibili interpretazioni delle

differenze avvenute. Inoltre le ambiguita sulle tipologie di modifica porta-

no questo insieme ad essere piu o meno vasto. Molti lavori scelgono una

di queste soluzioni in base ai risultati che vogliono ottenere, per esempio la

minimalita del delta. Il nostro scopo e scegliere tra queste soluzioni, quella

che si avvicina di piu alla nostra intuizione di confronto, tenendo conto che

confrontiamo documenti testuali. Nel momento in cui si presentano delle

20


Figura 2.1: Ambiguita nel confronto

21


Figura 2.2: Valutazione di parti aggiornate

22


Figura 2.3: Valutazione di parti spostate

23


ambiguita, vogliamo poter scegliere la soluzione voluta attraverso dei para-

metri che esprimano delle concezioni vicine al nostro modo di pensare. Il

procedimento descritto precedentemente e gia un modo per scegliere un sot-

toinsieme delle soluzioni possibili. Di seguito mostriamo quali possono essere

possibili parametri che ci portano a scremare ulteriormente questo sottoin-

sieme fino ad arrivare alla soluzione voluta. Una possibile parametrizzazione

e la seguente:

• Per valutare gli aggiornamenti fissiamo una soglia che stabilisce il va-

lore di somiglianza oltre il quale una parte viene considerata come

aggiornata.

• Per valutare gli spostamenti fissiamo una distanza oltre la quale una

parte non viene piu valutata come spostata.

• Per valutare parti spostate e aggiornate fissiamo una coppia di valori

sulla somiglianza e sulla distanza che ci serviranno come criterio di

scelta.

Questi parametri si avvicinano all’intuizione umana di confronto e permet-

tono di scegliere una particolare soluzione tra quelle possibili. Questo ci

permette in caso di ambiguita di scegliere la soluzione che si avvicina di piu

a quella voluta, a quella che noi ci aspettiamo dal diff cioe alla soluzione che

ci sembra piu naturale.

2.3 Metrica della naturalezza

Definire una metrica della naturalezza in base alle nozioni esposte prima,

diventa abbastanza complesso a causa dell’ambiguita di fondo che puo esserci

tra un tipo di riconoscimento e un altro. Noi abbiamo definito ‘naturalezza

del risultato’ la capacita dell’algoritmo di trovare le modifiche che troverebbe

un lettore umano, e la giustifichiamo attraverso il procedimento seguito nel

calcolo del delta. Per valutare i risultati in quest’ottica abbiamo eseguito una

24

2.4 Confronto dei risultati

serie di test su vari documenti, confrontando i risultati ottenuti con quelli che

ci aspettavamo. Nella maggior parte dei casi le differenze rilevate ricalcavano

le nostre attese, in altri casi, dove si presentavano delle ambiguita, siamo

riusciti a scegliere la soluzione voluta attraverso la variazione dei parametri

descritti precedentemente.

2.4 Confronto dei risultati

Abbiamo confrontato sul piano della naturalezza diversi algoritmi. I risultati

migliori si sono ottenuti con Ndiff, anche se ci rendiamo conto che questa

valutazione puo apparire soggettiva. Comunque il fatto stesso che Ndiff ci

permetta di esprimere dei parametri vicini alla nostra concezione di confron-

to, che altri lavori non fanno, evidenzia la qualita dell’algoritmo in termini

di naturalezza. Per fornire un approccio piu sperimentale abbiamo valutato

i diversi algoritmi sul piano della dimensione del delta trovato. L’insieme dei

documenti utilizzati per il test e composto da documenti che ci sono stati

inviati dal Senato che rappresentano DDL(quindi casi reali) e da documenti

scaricati casualmente da internet dove sono state apportate modifiche di va-

rio tipo. Nei grafici in fig.2.4 e fig.2.5 sono riportati i risultati dei test, dove

l’asse delle y rappresenta la dimensione del delta trovato. Ndiff e nettamente

migliore di XYdiff in termini di dimensione del risultato, e sembra essere

bilanciato anche rispetto agli altri algoritmi testati. Questo ci fa supporre

che esista una relazione tra naturalezza del risultato e dimensione del delta

rilevato.

25


Figura 2.4: Confronto tra Ndiff e altri algoritmi

Figura 2.5: Confronto tra Ndiff e altri algoritmi sulla media della dimensionedei delta rilevati

26

Capitolo 3

Ndiff

In questo capitolo descriveremo l’algoritmo Ndiff. Prima di tutto diamo

l’intuizione su cui si basa e di seguito scendiamo in un aspetto piu tecnico

descrivendo le varie fasi che lo compongono. Dal modo di procedere e dai

parametri esplicitati nelle varie fasi dell’algoritmo vedremo come venga fuo-

ri un aspetto ‘naturale’ del risultato, fornendo un delta che si avvicina alla

nostra interpretazione di confronto. L’unica condizione necessaria per l’ap-

plicazione di Ndiff stabilisce che i documenti da confrontare devono avere lo

stesso nodo radice. Non esistono altri vincoli, ne sul DTD dei documenti ne

su attributi ID definiti nel documento. Infatti la comparazione effettuata da

Ndiff si basa sulla struttura dei documenti XML senza appoggiarsi ad altre

informazioni.

3.1 Intuizione

L’intuizione su cui si basa Ndiff e procedere nella rilevazione delle modifi-

che attraverso i concetti di naturalezza descritti nel capitolo precedente. La

tipologia di associazioni vista tra le ‘parti’ dei documenti XML puo essere in-

terpretata come associazione tra nodi e sotto-alberi dei relativi alberi DOM.

Le nozioni di localita, somiglianza e distanza rimangono invariate e valgono

allo stesso modo se consideriamo invece delle ‘parti’, i relativi sotto-alberi

che le compongono. La fig.3.1 mostra un esempio di confronto effettuato da

27

NDIFF

Figura 3.1: Modo di procedere di Ndiff

28

3.1 Intuizione

Ndiff. L’idea di base e trovare i sottoinsiemi piu ‘grandi’ di nodi comuni tra

i due alberi e considerarli ‘non modificati’, per poi identificare come ‘aggior-

nati’ i nodi (o insiemi di nodi) che differiscono di poco e si trovano circa

nella stessa posizione (principi di somiglianza e localita), ed infine identifi-

care come ‘mossi’ i nodi uguali ma in posizioni molto diverse nel documento

(principio di distanza). Il nostro scopo e mettere in relazione i nodi dei due

documenti seguendo il procedimento ‘naturale’ di confronto. La relazione

di associazione si basera sulla posizione di ogni nodo data da una previsi-

ta sinistra dell’albero DOM. Di seguito ci riferiremo alla versione ‘originale’

con Vn e a quella modificata con Vn+1. Un esempio di associazione di nodi

tra due alberi e dato in fig.3.2, dove si vedono gli alberi confrontati e una

rappresentazione grafica dell’associazione. Nel grafico l’asse X rappresenta la

numerazione dei nodi del documento Vn e l’asse Y la numerazione dei nodi

del documento Vn+1 e i punti sul grafico rappresentano l’associazione tra i

nodi dei documenti. Come si intuisce dal grafico, un sotto-albero di Vn messo

in corrispondenza con un sotto-albero di Vn+1 e rappresentato da un’associa-

zione di punti continua derivata dal modo di numerare i nodi.

Come visto nel capito 1.2, il problema di trovare le differenze tra due do-

cumenti e analogo a trovarne le parti comuni, tutto cio che non e uguale tra

Vn e Vn+1 deve essere stato necessariamente aggiornato, inserito o cancellato.

Una rappresentazione del problema in termini matematici e la seguente:

Supponiamo di avere una funzione biiettiva b = Φ(a) che associa i no-

di del documento Vn ai nodi del documento Vn+1 secondo una LCS tra i

due documenti. Definiamo NVn l’insieme dei nodi di Vn e rispettivamente

NVn+1 l’insieme dei nodi di Vn+1. Ora prendiamo l’intervallo definito come

C = NVn − dominio(Φ) e I = NVn+1 − codominio(Φ) abbiamo che gli insiemi

C e I sono rispettivamente i nodi cancellati e inseriti nel passare da Vn a

Vn+1. Quindi avendo Vn e gli insiemi C ed I vale Vn+1=Vn-C+I, e simmetri-

camente Vn=Vn+1+C-I. Se consideriamo la fig.3.2, vediamo che gli insiemi C

e I corrispondono rispettivamente ai punti dell’asse X e dell’asse Y che non

fanno parte della relazione di associazione.

29

NDIFF

Figura 3.2: Relazione di associazione tra i nodi dei documenti confrontati

30

3.2 L’algoritmo

Una prima approssimazione delle differenze tra due versioni, o due docu-

menti, puo essere ottenuta calcolando i nodi inseriti(l’insieme I ) e cancel-

lati(l’insieme C ), ossia le parti non comuni tra i documenti. Possiamo di

seguito raffinare il risultato, andando ad esaminare ulteriormente gli insiemi

I e C per individuare nodi che possono essere considerati aggiornati o mossi

in base ai concetti espressi nel capitolo precedente.

Per raffinare il delta, prendiamo spunto da come un essere umano interprete-

rebbe un aggiornamento o uno spostamento o una combinazione di questi. E’

normale intuizione considerare una parte come ‘spostata’ se appare in punti

diversi del documento rispetto alla parte maggiore del documento stesso; per

esempio, se prendiamo un documento composto da 10 paragrafi e spostiamo

il primo paragrafo dall’inizio alla fine del documento, difficilmente qualcuno

ci dira che i paragrafi mossi sono stati gli altri 9 rispetto al primo. Questa

considerazione ci fornira un metodo per stabilire cosa e stato mosso fra due

documenti, basandoci sulla parte comune piu grande di entrambi.

Prendiamo ora due versioni di un documento che differiscono per l’aggior-

namento di una ‘parte’. Un lettore nel confrontare le due versioni potrebbe

pensare che queste ‘parti’ sono aggiornate, in quanto sono nella stessa posi-

zione e molto simili. Algoritmicamente se definiamo come ‘stessa posizione’

l’essere tra due parti uguali fra le due versioni, e definiamo una funzione che

misuri il grado di somiglianza tra due parti abbiamo un modo per rilevare

gli aggiornamenti.

Per rilevare invece combinazioni di spostamenti ed aggiornamenti possiamo

usare la combinazione dei due procedimenti visti prima. Questo e il mo-

do di procedere di Ndiff, cercando di esprimere l’interpretazione naturale di

confronto tra i due documenti.

3.2 L’algoritmo

L’algoritmo e una concatenazione di passi che lo rendono estremamente mo-

dulare. Partendo dai due documenti Vn e Vn+1 in input, costruiamo due

31

NDIFF

strutture dati particolari(Vtree) che forniscono metodi di accesso in tempo

costante ai nodi del documento ed altre informazioni aggiuntive. A que-

sto punto avviamo un processo incrementale che cerca di mettere in re-

lazione i nodi dei due documenti. I punti che compongono la relazione

< sono le triple (ia, ib, t), dove ia e l’indice del nodo nell’albero del do-

cumento Vn, ib e l’indice del nodo nell’albero del documento Vn+1 e t ∈{E, M, U}(E=uguale,M=mosso,U=aggiornato) rappresenta il tipo di asso-

ciazione tra i due nodi. Quindi < mette in relazione i nodi di Vn con i nodi di

Vn+1, e t rappresenta il tipo di associazione. Ovviamente < deve soddisfare

l’ipotesi ∀i, |{n|(i, j, t) ∈ <}| ≤ 1. Cioe un nodo di Vn puo essere associato

al piu a un nodo di Vn+1 ed un solo tipo di associazione t. Un esempio di

relazione e illustrato in fig. 3.2.

Il procedimento descritto puo essere visto come una concatenazione di varie

fasi, ognuna delle quali prende in input i due ‘Vtree’ e la relazione < di as-

sociazione dei nodi e da in output < arricchita da nuovi punti(fig. 3.3). Le

fasi dell’algoritmo sono:

1. Parsing dei documenti XML: In questa fase creiamo sui documenti

XML delle strutture dati particolarmente adatte ad essere confrontate;

chiameremo queste strutture Vtree.

2. Partizionamento: In questa fase andiamo a creare la prima appros-

simazione della relazione di associazione dei nodi. In particolare inse-

riremo in < i nodi che risulteranno uguali tra i due documenti.

3. Ricerca aggiornamenti: Andiamo a rilevare i nodi che possono es-

sere considerati come aggiornati, basandoci sui concetti di ‘localita’ e

‘somiglianza’.

4. Ricerca spostamenti: Andiamo a cercare i nodi uguali che non ap-

partengono ad <. I nodi trovati uguali saranno necessariamente degli

spostamenti, altrimenti sarabbero stati inseriti in < dalla fase di ‘par-

32

3.2 L’algoritmo

Figura 3.3: Schema del calcolo del diff tra due documenti

33

NDIFF

tizionamento’. Nel valutare un nodo come spostato faremo riferimento

al concetto di ‘distanza’.

5. Ricerca di spostamenti-aggiornamenti: Andiamo a cercare i nodi

che sono in parti diverse fra i documenti e risultano simili. In que-

sta fase faremo riferimento ai concetti di ‘somiglianza’ e ‘distanza’. Le

associazioni prodotte non sono uguali all’insieme delle associazioni ri-

levate dalle due fasi precedenti, in quanto ogni nodo dovra soddisfare

contemporaneamente le due condizioni precedenti.

6. Propagazione bottom-up: Andiamo a propagare il match ai nodi di

livello superiore, partendo dai nodi riconosciuti uguali o aggiornati.

7. Rappresentazione del risultato: In quest’ultimo passo andremo ad

esaminare < per costruire il documento delta che esprime i cambiamenti

trovati.

Notiamo che l’ordine delle fasi e rilevante in quanto cambiera la relazione <sulla quale operera la fase successiva. Inoltre possiamo aggiungere o togliere

delle fasi in modo da rilevare o no alcuni tipi di modifica sui documenti. I con-

cetti che useremo per discriminare aggiornamenti o spostamenti saranno dei

parametri che l’algoritmo prende in input e che permetteranno di selezionare

una particolare soluzione dall’insieme dei delta possibili.

3.3 Parsing dei documenti XML

Il parsing dei documenti XML avviene attraverso un parser di tipo DOM (Do-

cument Object Model). La creazione dell’albero DOM verra seguita da una

fase di post-parsing in cui verranno aggiunte informazioni che faciliteranno

la comparazione dei documenti. La struttura dati ottenuta e stata chiamata

Vtree e verra usata nelle varie fasi di confronto. I Vtree ci permetteranno

di identificare i nodi di un documento attraverso dei numeri corrispondenti

34


agli indici di un vettore e di confrontare rapidamente i documenti. Per ogni

nodo dell’albero vengono inserite informazioni relative a:

• Un valore hash che rappresenta l’intero sottoalbero radicato nel nodo,

HashTree.

• Un valore hash che rappresenta il nodo piu eventuali attributi, Hash-

Node.

• La posizione del nodo padre in una previsita sinistra dell’albero DOM

del documento XML, PosFather.

• Il numero dei nodi totali presenti nel sottoalbero, NumChild.

Inoltre verra fornito un metodo di accesso in tempo costante ai nodi dell’al-

bero, sfruttando un array di puntatori il cui indice corrisponde all’ordine di

una previsita sinistra dell’albero DOM. Quindi il primo elemento del vettore

sara un puntatore alla radice, l’ultimo un puntatore alla foglia piu a destra

dell’albero(fig.3.4). Facciamo vedere che partendo dall’albero DOM, riuscia-

mo a calcolare queste informazioni aggiuntive in tempo lineare sul numero di

nodi. In pratica si tratta di eseguire due visite sull’albero DOM, valorizzan-

do degli attributi di tipo ‘ereditato’ o ‘sintetizzato’. Ricordiamo che il valore

di attributi sintetizzati e determinabile dagli attributi dei nodi figlio, men-

tre gli attributi ereditati sono valorizzati utilizzando informazioni relative ad

attributi del nodo padre.

3.3.1 Visita top-down

La visita top-down ci permette di aggiungere per ogni nodo le informazioni

relative a:

• Creazione vettore dei puntatori: Inseriamo nel vettore i puntatori

relativi ad ogni nodo dell’albero. L’indice del vettore ci permettera di

accedere al nodo in tempo costante.

35

NDIFF

Figura 3.4: Vettore dei puntatori calcolato con una previsita sinistra su unsemplice documento

36

• Posizione del padre: Per ogni nodo memorizziamo l’indice sul vettore

dei puntatori del nodo padre(PosFather).

Propieta 3.1 (proprieta della numerazione dei nodi). Se definiamo y=p(x)

la funzione di numerazione dei nodi, dove x e il nodo e y la posizione che gli

viene associata. Valgono:

• Posizione del padre: p(father) < p(child), l’indice associato a un

nodo padre e minore dell’indice associato ai suoi figli. Cioe nella

numerazione il nodo padre viene prima dei suoi figli.

• Posizione dei nodi figlio: La posizione dei nodi appartenenti al sot-

toalbero del nodo X vanno da p(X)+1 a p(X)+nc dove nc rappresenta

la cardinalita(numeri di nodi) del sottoalbero radicato in X.

3.3.2 Visita bottom-up

La visita bottom-up verra eseguita sfruttando il vettore dei puntatori creato

precedentemente. Faremo una scansione del vettore partendo dall’ultimo

elemento fino al secondo. Durante la visita bottom-up andiamo a calcolare

le informazioni relative a:

• HashTree: Questo valore rappresenta l’intero sottoalbero radicato nel

nodo. Se due nodi hanno lo stesso valore HashTree hanno necessaria-

mente lo stesso sotto-albero. Il calcolo avviene aggiungendo il valo-

re HashTree del nodo visitato a quello del padre, ricalcolando l’hash

della nuova stringa ottenuta. HashTreefather = Υ(HashTreefather +

HashTreechild), dove Υ e la funzione che viene usata per calcolare il

valore hash. Un esempio di calcolo e dato in fig.3.5 dove i passi della

procedura sono disegnati da sinistra a destra, dall’alto in basso. Alla

fine del calcolo il nodo 19 contiene un valore hash che rappresenta il

contenuto dell’intero sotto-albero.

• HashNode: Questo valore viene calcolato utilizzando il nome del nodo

e il nome dei suoi eventuali attributi con rispettivi valori. Questo valore

37

NDIFF

Figura 3.5: Esempio di calcolo dei valori HashTree

puo essere calcolato anche durante la visita top-down in quanto dipende

solo da informazioni contenute nel nodo stesso, da cui segue che per i

nodi foglia il valore HashNode e uguale a HashTree.

• NumChild: Rappresenta il numero totale di nodi del sottoalbero ra-

dicato nel nodo. Il calcolo avviene facendo sommare un ‘+1’ al nodo

padre del nodo visitato. Il procedimento e simile al calcolo di HashTree.

Propieta 3.2 (proprieta del valore HashTree). Se il valore di HashTree del

nodo puntato da V [i] e uguale a quello puntato da V [j] allora V [i + k] =

V [j + k] con k=1..N, dove N e il numero di nodi radicati nel sottoalbero

associato al nodo puntato da V [i] o V [j].

38

3.4 Partizionamento

3.4 Partizionamento

La prima fase si occupa di trovare le parti maggiori di documento comuni

rimaste invariate tra le due versioni. In questo momento non abbiamo nes-

suna informazione relativa ad associazione di nodi(< e vuota). Questa fase

puo essere eseguita trovando una LCS tra i valori HashTree dei nodi nei due

documenti, considerando come ordine gli indici del vettore di puntatori. Du-

rante il calcolo della LCS possiamo sfruttare le proprieta 3.1 e 3.2 per evitare

confronti inutili.

La LCS trovata sara la prima approssimazione del risultato, in particolare

verranno aggiunti nella relazione < le coppie di nodi che risultano uguali tra

i due documenti. Per trovare una LCS tra le due sequenze definite preceden-

temente possiamo usare due approcci. Quello classico, piu veloce che esegue

in tempo O(N*D), definito da Myers[Eugene W. Myers.,86], che e un’otti-

mizzazione in termini di tempo e spazio dell’algoritmo illustrato nel capitolo

1.2. Noi useremo un nuovo approccio che esegue in tempo maggiore ma trova

un risultato che puo essere considerato piu ‘naturale’.

Definiamo MSC la massima sottosequenza continua comune tra due sequen-

ze. Per esempio la MSC tra:

S1=<OREVEINVEOD> e S2=<OTRETVEINVTEOTD>

SMSC=< V EINV >

Infatti SMSC e la sottosequenza comune continua piu lunga tra S1 e S2 consi-

derando tutte le sottosequenze possibili. Ora definiamo LCCS(Longest Com-

mon Continuous Subsequence), come l’insieme delle MSC piu lunghe tra S1

e S2, che non si intersecano. Spesso la LCCS e una soluzione particolare

della LCS dove sono state prese le MSC maggiori. Per chiarire il perche della

nostra scelta facciamo un semplice esempio; consideriamo le sequenze:

S1=< FORZALECCE >

S2=< FIOIRIZIAILIEICICIEIFORZALECC >

la LCS assocerebbe la prima ‘F’ di S1, con la prima F di S2, la prima O di S1

con la prima di S2, e cosı via fino ad associare l’intera stringa ‘FORZALEC-

39

NDIFF

CE’ che e propio la LCS. Quindi intuitivamente, se consideriamo la soluzione

della LCS come un diff avremo: ‘FIOIRIZIAILIEICICIEIFORZALECC’ do-

ve sono stati sottolineati i caratteri che risulterebbero inseriti. Una soluzione

ottima, ma non intuitiva, se pensiamo per esempio che le lettere possano esse-

re parole di una frase. Vediamo ora la LCCS, che in questo caso coincide con

l’unica MSC presente tra S1 e S2, che e quindi SLCCS=< FORZALECC >,

se pensiamo anche in questo caso il risultato come un’associazione tra i carat-

teri, avremo un diff del tipo ‘FIOIRIZIAILIEICICIEIFORZALECC’, molto

piu intuitivo.

Descriviamo di seguito un algoritmo capace di trovare una LCCS fra una

sequenza S1 e una sequenza S2. La qualita della soluzione converge con la

‘somiglianza’ delle sequenze in input.

L’idea dell’algoritmo e di considerare che una LCCS per due sequenze X e Y,

sia composta appunto dalla concatenazione di MSC calcolate su parti diverse

delle sequenze originali, senza intersezione e prese nel giusto ordine.

Per illustrare l’algoritmo supponiamo di voler calcolare la LCCS tra

X=<A,B,F,H,F,G,T,R,K,W,E,S,D> e

Y=<A,B,U,H,U,G,T,R,K,M,E,S,D>. Prendiamo la MSC fra X e Y che e

uguale a Z=<G,T,R,K> e supponiamo che Z faccia parte della LCCS, a

questo punto dividiamo le sequenze X e Y attraverso Z, abbiamo che da

X otteniamo le due sequenze Xs=<A,B,F,H,F> e Xd=<W,E,S,D> mentre

da Y abbiamo Ys=<A,B,U,H,U> e Yd=<M,E,S,D>. Nei passi successivi

riapplichiamo lo stesso procedimento su X=Xs e Y=Ys, successivamente su

X=Xd,Y=Yd. Un esempio di calcolo della LCCS per le stringhe X e Y e dato

in fig.3.6, dove le linee tratteggiate rappresentano il calcolo delle MSC per

le rispettive sequenze X e Y, mentre nel rettangolo tratteggiato in basso si

puo vedere che la LCCS per X e Y e ottenuta come concatenazione ordinata

delle MSC calcolate ad ogni passo. Da notare che l’ordine di divisione delle

sequenze e importante in quanto rispettera alla fine l’ordine di concatena-

zione per ottenere la LCCS. Una possibile implementazione dell’algoritmo

descritto e la seguente:

40

3.4 Partizionamento

Figura 3.6: Esempio di calcolo della LCCS.

41

NDIFF

1: procedure findLCCS(var A, B, Ia, Ib)

2: begin

3: Ea, Eb ← MAX-SUB(A, B, Ia, Ib)

4: LCCS ← LCCS + Ea

5: if (Ia.first ≤ Ea.first− 1)and(Ib.first ≤ Eb.first− 1) then

6: begin

7: I la ← [Ia.first,Ea.first− 1]

8: I lb ← [Ib.first,Eb.first− 1]

9: findLCCS(I la,I

lb)

10: end

11: if (Ea.last + 1 ≤ Ia.last)and(Eb.last + 1 ≤ Ib.last) then

12: begin

13: Ira ← [Ea.last + 1,Ia.last]

14: Irb ← [Eb.last + 1,Ib.last]

15: findLCCS(Ira ,I

rb )

16: end

17: end

Dove con la notazione [i,j] si intende la sotto-sequenza di S dall’elemento i

all’elemento j. Per esempio nella sequenza <A,B,G,F,T,Y,S,F>, la notazio-

ne [2,4] corrisponde alla sotto-sequenza <B,G,F> e [5,5] alla sotto-sequenza

<T>.

Prendiamo I=[i,j] e indichiamo con I.first l’estremo sinistro dell’intervallo I e

con I.last l’estremo destro; per esempio se I=[3,7], allora I.first=3 e I.last=7.

Un esempio dello schema di chiamata della funzione e dato in fig.3.7, dove le

linee continue delimitano gli intervalli di chiamata della funzione sulla sequen-

za A e sulla sequenza B, mentre le linee trattegiate delimitano gli intervalli di

ritorno, cioe gli intervalli trovati uguali fra le sequenze. Quindi nella prima

chiamata esaminiamo tutti e due gli intervalli di A e di B, nella seconda la

parte sinistra rimasta ‘fuori’ da A e B e nella terza la parte destra. Dallo

schema di computazione si nota che una chiamata ricorsiva viene provocata

42

3.4 Partizionamento

Figura 3.7: Schema di chiamata della funzione findLCCS

dal fatto che gli intervalli di input non sono uguali, ma neanche completa-

mente diversi. Piu precisamente per ogni differenza fra le due sequenze ci

sara una nuova chiamata, intendendo come differenza non un elemento ma

una parte di sequenza.

Questo modo di procedere fara un numero di chiamate proporzionale alle

differenze fra le due sequenze, e quindi particolarmente adatto a trattare

sequenze simili.

Un altro limite alla complessita di questa funzione e dettato dal modo con cui

viene calcolata la funzione MAX-SUB, che si occupa di trovare la sequenza

continua piu lunga fra due sequenze. Un modo ingenuo per implementarla

potrebbe essere quello di scandire tutte e due le sequenze e una volta trova-

ti degli elementi uguali, contare gli elementi successivi uguali, mantenendo

sempre l’intervallo e la dimensione della MSC migliore.

Questo modo di procedere richiede N*M*l confronti, dove N e M sono la

lunghezza delle sequenze trattate, e l la media degli li(fig.3.8 ). Con que-

sta soluzione abbiamo una complessita totale di O(N*M*l*D) dove D sono

il numero di ‘differenze fra le sequenze esaminate’. E’ quindi necessario mi-

gliorare il modo di trovare una MSC e lo si puo fare basandosi sulle seguenti

43

NDIFF

Figura 3.8: Schema di calcolo della MSC in modo ingenuo

44

3.4 Partizionamento

considerazioni:

• Confrontare solo le sequenze che iniziano allo stesso modo:

(con lo stesso prefisso), cioe attraverso una funzione possiamo suddivi-

dere gli elementi delle sequenze in classi e confrontare elementi solo se

appartenenti alla stessa classe.

• Sfruttiamo informazioni relative alla struttura dell’albero: Le

sequenze trattate sono serializzazioni di alberi XML attraverso la proce-

dura descritta precedentemente, quindi se S1[i]=S2[j] allora S1[i+k]=S2[j+k]

con k=1..N, dove N e il numero di nodi radicati nel sottoalbero associato

all’i-esima posizione della sequenza S1(proprieta 3.2).

Con queste considerazioni possiamo scrivere una procedura che riesce a tro-

vare una MSC in tempo medio lineare sugli elementi della sequenza. Dalla

fig.3.9 si vede che la complessita del calcolo della MSC diventa O((N) ∗ C ∗N/l), dove N e il numero di elementi di una sequenza(pref. la piu corta),

l e la media degli ‘li’ e C rappresenta la cardinalita media delle classi in

cui vengono catalogati gli elementi. Considerando una buona suddivisione la

cardinalita media C puo essere considerata come una costante, inoltre se le

sequenze sono simili allora l si avvicinera al valore di N e di conseguenza il

rapporto N/l tende a 1. Osserviamo che nel caso ottimo, in cui le sequenze

sono uguali, il tempo di confronto diventa O(1). Lo pseudo-codice relati-

vo all’algoritmo descritto per trovare la MSC, sfruttando le ottimizzazioni

diventa:

1: procedure MAX-SUB(var A, B, Ia, Ib)

2: var max:=0;

3: begin

4: for i := Ia.first to Ia.last do

5: begin

6: idc ← getIdClass(i,DOCa)

7: Cb ← getClass(idc, DOCb)

45

NDIFF

Figura 3.9: Schema di calcolo della MSC in modo efficiente

46

3.4 Partizionamento

8: for j := 0 to |Cb| do

9: begin

10: explorer ← 0

11: while A[i + explorer] == B[j + explorer] do

12: begin

13: explorer := explorer + (numero di nodi nel sottoalbero i)

14: if explorer > max then

15: begin

16: max := explorer

17: Ea ¡- [i,i+explorer]

18: Eb ¡- [j,j+explorer]

19: end

20: i := i+1

21: end

22: end

23: end

24: return Ea, Eb

25: end

MAX-SUB ha un tempo medio di esecuzione lineare se la suddivisione degli

elementi fra le classi di appartenenza e buona. Piu precisamente minore sara

il numero medio di elementi per classe maggiore sara la velocita dell’algorit-

mo, in quanto il secondo ciclo for(riga 8) avra meno casi da esaminare. La

riga 13 ci permette di sfruttare la proprieta 3.2.

I punti di forza nel trovare una LCCS con questo approccio sono:

• Numero delle differenze: findLCCS e parametrico rispetto al nu-

mero di differenze.

• Sequenze uguali: Esegue in tempo costante O(1) se le sequenze da

confrontare sono uguali.

• Cardinalita del vocabolario della sequenza: Se gli elementi di

47

NDIFF

una sequenza sono tutti diversi, o abbastanza(come possono essere le

parole di un testo) findLCCS esegue in tempo medio lineare.

Concludiamo dicendo che l’output della fase di ‘Partizionamento’ sara ap-

punto un insieme di terne del tipo (ia, ib, E), che verranno inserite in <.

Questo risultato e appunto il ‘mapping’ dei nodi uguali tra le due versioni

del documento e sara l’input, insieme ai documenti da confrontare, delle fasi

successive.

3.5 Ricerca aggiornamenti

In questo fase andiamo a cercare fra le due versioni, i nodi che possono essere

considerati come aggiornamenti. Per fare questo ci baseremo su due concetti:

• Localita: Consideriamo parti di documento che si trovano tra due

parti considerate uguali nelle due versioni.

• Somiglianza: Definiamo una funzione che ci calcolera l’indice di so-

miglianza di due nodi. Restituira un valore percentuale pari a 100 se i

nodi sono uguali, 0 se sono completamente diversi.

Il concetto di ‘localita’ puo essere spiegato semplicemente considerando che

probabilmente, una parte aggiornata si trova tra due parti di documento

uguali. Per chiarezza consideriamo la fig. 3.10 che rappresenta un possibile

output di < dopo la fase di partizionamento. Andremo a confrontare i no-

di che appartengono ai quadrati illustrati in figura, se questi saranno simili

per un valore maggiore di una certa soglia, verranno considerati aggiornati e

verranno inclusi nella relazione < come triple del tipo(ia,ib,U).

La somiglianza dei nodi viene data dalla funzione:

f(T1, T2) = 50 ∗ (MAX( length(TC)length(T1)

, length(TC)length(T2)

) + MIN( length(TC)length(T1)

, length(TC)length(T2)

))

dove length(x) restituisce la lunghezza della stringa x, e TC e la LCCS(o

48

3.5 Ricerca aggiornamenti

Figura 3.10: Grafico delle aree di ricerca degli aggiornamenti.

49

NDIFF

Figura 3.11: Grafico tridimensionale della funzione che calcola la somiglianzadi nodi di testo.

LCS) tra T1 e T2. La funzione f(T1, T2) assume valori tra 0 e 100 in quanto

i rapporti length(TC)length(T1)

e length(TC)length(T2)

assumono valori in [0,1] perche sicuramente

length(TC) < length(T1) e length(TC) < length(T2). In fig.3.11 vediamo un

esempio dell’andamento di f con length(TC) fissato a 50 e 0 < length(T1) <

100,0 < length(T2) < 100. La funzione si comporta bene, in quanto all’avvi-

cinarsi di length(T1) e length(T2) a length(TC) il valore f(T1, T2) cresce, in

particolare se length(T1) = length(T2) = length(TC)⇒ f(T1, T2) = 100.

3.6 Ricerca spostamenti

In questa fase andiamo a confrontare i nodi del documento non appartenenti

ad <, che quindi non hanno ancora trovato nessuna corrispondenza. Il con-

fronto avviene in modo incrociato, cioe tra parti di documento con ‘localita’

diversa; non confrontiamo parti con la stessa ‘localita’, in quanto se fossero

presenti nodi uguali, avrebbero fatto parte della LCCS(o LCS) trovata nella

fase di ‘partizionamento’. Un esempio delle aree di ricerca degli spostamenti

e dato dai quadrati evidenziati in fig.3.12, dove i punti cerchiati sull’asse X

e Y sono i nodi che non hanno ancora trovato nessuna corrispondenza. Nel

confronto utilizziamo il concetto di distanza per ridurre l’eventuale spazio di

50

3.7 Ricerca spostamenti-aggiornamenti

Figura 3.12: Grafico delle aree di ricerca degli spostamenti

ricerca degli spostamenti. Fissando una valore per la distanza, discriminiamo

il limite dopo il quale un nodo non viene piu considerato spostato. Pensiamo

ad esempio a un paragrafo che appare nella versione Vn nel primo capitolo,

e nella versione Vn+1 nell’ultimo capitolo, potremmo non volerlo considerare

come uno spostamento.

3.7 Ricerca spostamenti-aggiornamenti

Per rilevare i nodi spostati e aggiornati ci basiamo sulle nozioni di distanza

e somiglianza. In particolare fissiamo una coppia di valori (s, d), dove s rap-

presenta la soglia oltre la quale un nodo viene considerato aggiornato e d lo

spazio di ricerca degli spostamenti. Due nodi N1 e N2 verranno considerati

spostati/aggiornati se la loro distanza e minore di d e f(N1, N2) ≥ s, dove

f e la funzione descritta in 3.5. Nonostante questa fase sia un incrocio delle

51

NDIFF

due fasi precedenti, i risultati prodotti sono diversi. Comunque, procedendo

in questo modo corriamo il rischio di associare della parti in modo scorret-

to, occorre quindi un accurato ‘dosaggio’ dei valori d e s, in quanto gia la

condizione di spostato/aggiornato risulta troppo generica.

3.8 Propagazione bottom-up

Fino ad ora abbiamo confrontato i nodi in base al valore HashTree, quin-

di effettivamente non abbiamo confrontato nodi ma sotto-alberi dell’albero

DOM. In fondo, in base alla nostra numerazione dei nodi, un sotto-albero e

un insieme di punti continui in Vn messo in corrispondenza con un insieme

di punti di Vn+1. Quindi il mapping tra i punti contenuti in < puo essere piu

correttamente visto come un mapping di sotto-alberi. Ora partendo dalle ra-

dici di questa foresta di sotto-alberi risaliamo in modo ricorsivo i nodi, fino ad

arrivare alla radice del documento, per cercare singoli nodi rimasti uguali. E’

infatti possibile che due nodi abbiamo HashTree diversi, pur non essendo stati

modificati. Questo perche il valore HashTree di ogni nodo dipende dall’in-

tero sotto-albero radicato(le modifiche al sotto-albero sono quindi propagate

verso l’alto). L’algoritmo riconosce questi casi e considera uguali anche due

nodi con HashTree inizialmente diversi. Questo ci permettera di raffinare

il risultato del delta, eliminando le operazioni di inserimento/cancellazione

di singoli nodi posti ai livelli inferiori dell’albero. La fig.3.13 rappresenta

lo schema decisionale per il riconoscimento di questi nodi. Ragionando per

induzione sul percorso fino alla radice, possiamo avere 3 casi:

• Il nome del nodo Ni ∈ Vn e diverso dal nome del nodo Nj ∈ Vn+1

• Il nome del nodo Ni ∈ Vn e uguale al nome del nodo Nj ∈ Vn+1, ma gli

attributi sono diversi.

• Il nome del nodo Ni ∈ Vn e uguale al nome del nodo Nj ∈ Vn+1, ma

FNi6= FNj

, dove FNi={l’insieme dei sotto-alberi riconosciuti uguali

52

3.8 Propagazione bottom-up

Figura 3.13: Diagramma di decisione durante la propagazione del matchingBottom-up.

o simili tra i discendenti di Ni} e FNj={l’insieme dei sotto-alberi ri-

conosciuti uguali o simili tra i discendenti di Nj }. Per esempio se

consideriamo il nodo ‘D’ in fig.3.14, abbiamo che nel documento n,

FD={E,F}, mentre nel documento n+1 FD={E,F,G}. I nodi contenu-

ti negli insiemi Fx devono necessariamente appartenere alla relazione

<.

Nel primo caso, in cui il nome del nodo e diverso, arrestiamo il procedimento

ricorsivo in quanto i nodi non possono essere considerati uguali. Nel secondo

caso possiamo eguagliare i due nodi a patto di considerare Nj come aggior-

namento di Ni e quindi inserire un ‘minidelta’ sugli attributi dei nodi che

descrive le differenze rilevate e le operazioni necessarie per renderli uguali.

53

NDIFF

Figura 3.14: Schema di propagazione del matching bottom-up

Per chiarire il terzo punto facciamo riferimento alla fig. 3.14, dove sono rap-

presentate le associazioni definite in <. Vogliamo vedere se il nodo ‘D’ puo

essere considerato uguale tra i due documenti. Non basta che il nodo abbia lo

stesso nome e gli stessi attributi, deve valere anche che sia lo stesso ‘contesto’

per i sotto-alberi rilevati uguali o simili(appartenenti a <) al di sotto di lui.

Questo perche, se compariamo i due nodi senza che valga questa condizione,

non riusciremo a trovare i cambiamenti di contesto dei suoi sotto-alberi. In

questo caso particolare possiamo eguagliare ‘D’ solo se consideriamo il nodo

o il sottoalbero radicato in ‘G’ come uno spostamento. Infatti il ‘contesto’

del nodo ‘G’ e cambiato. Prima era figlio del nodo ‘B’, ma ora si ritrova a un

livello piu basso, figlio di ‘D’, e quindi e corretta la supposizione che questo

sia stato spostato. Da questo modo di procedere segue che la radice dei do-

cumenti verra sempre riconosciuta, in quanto e stato supposto che questa sia

uguale tra i due documenti e per costruzione tutti i sotto-alberi presenti in

< sono suoi discendenti. Il risultato di questa fase sara un raffinamento del

delta, evitando cosı di cancellare e reinserire singoli nodi a livello intermedio

dell’albero.

54

3.9 Rappresentazione del risultato

Figura 3.15: Interpretazione di < sugli alberi relativi ai documenti XMLconfrontati.


In quest’ultima fase andiamo a trasformare le informazioni raccolte nelle fasi

precedenti e contenute in < nell’equivalente documento XML che rappresenta

i cambiamenti fra i documenti confrontati. In fig.3.15 vediamo un’esempio

di interpretazione delle informazioni contenute in <: in alto e illustrato il

documento originale, in basso il documento modificato e le frecce rappresen-

tano le associazioni tra i nodi e i sotto-alberi dei due documenti. Il formato

del delta di Ndiff segue il modello [Kuo-Chung,79] descritto nel capitolo 1.1.

Attualmente il delta viene espresso attraverso 6 tipi di operazione:

• insertTree: Si riferisce all’operazione di inserimento di un sotto-albero.

55

NDIFF

• insertNode: Indica l’operazione di inserimento di un singolo nodo.

• deleteTree: Indica la cancellazione di un intero sotto-albero.

• deleteNode: Si riferisce alla cancellazione di un singolo nodo.

• updateElement: Indica l’operazione di aggiornamento di un nodo ele-

mento. L’aggiornamento viene specificato attraverso delle sub-operazioni

che esprimono l’inserimento, la modifica o cancellazione di attributi del

nodo.

• updateText: Indica l’aggiornamento di un nodo a contenuto testua-

le. L’aggiornamento viene specificato attraverso un insieme di sub-

operazioni che esprimono l’inserimento e la cancellazione di sotto-stringhe

del nodo.

L’operazione di spostamento non e definita esplicitamente, ma viene rap-

presentata da una coppia di operazioni insertTree e deleteTree legate da un

attributo il cui valore ne specifichera il legame.

Per ottenere il delta esaminiamo per ogni nodo di Vn le relative informazioni

contenute in <. I casi possibili sono:

• Il nodo appartiene a < ed e associato come ‘uguale’. In questo caso

non occorre inserire operazioni nel delta in quanto il nodo e presente

sia in Vn che in Vn+1 e soddisfa tutte le condizioni dettate dalle fasi

precedenti.

• Il nodo appartiene a < ed e associato come ‘aggiornato’. In questo

caso dobbiamo calcolare un ‘minidelta’ che renda uguali i due nodi

associati. Se i nodi sono a contenuto testuale calcoleremo un ‘minidelta’

sulle rispettive stringhe, mentre se sono nodi elemento troveremo un

‘minidelta’ sugli attributi.

• Il nodo appartiene a < ed e associato come ‘spostato’. In questo ca-

so generiamo due operazioni, una di insertTree e una deleteTree, che

contengono l’attributo move il cui valore le lega insieme.

56

• Il nodo non appartiene a <. Non e stata trovata nessuna associazione

per il nodo quindi sara considerato come cancellato.

• Per esplicitare gli inserimenti dobbiamo considerare i nodi di Vn+1 che

non appartengono a <. Questi nodi saranno considerati come inseriti.

Per ognuna delle operazioni precedenti e necessario salvare delle informazioni

che permettano di applicare correttamente l’operazione n alla versione Vn su

cui sono gia state applicate le n-1 operazioni precedenti. Dunque l’ordine

delle operazioni all’interno del delta e rilevante. Infatti l’operazione n, si

riferisce allo stato del documento ottenuto dopo le prime n-1 operazioni.

Il delta ottenuto e composto da tre blocchi di operazioni dove nel primo sono

inserite tutte le operazioni di cancellazione, nel secondo di inserimento e nel-

l’ultimo di aggiornamento. Per capire il motivo di questa scelta indichiamo

con ia l’indice di un nodo del documento Vn e con ib l’indice di un nodo del

documento Vn+1. L’applicazione partira dal documento Vn, quindi gli indici

degli elementi da cancellare saranno gli ia, cioe i nodi di Vn che non hanno

trovato nessuna associazione in <(l’asse delle X del grafico in fig.3.2). L’in-

dice di inserimento dei nuovi nodi sara invece ib, cioe la posizione dei nodi in

Vn+1 perche sara propio quella la posizione che dovranno occupare. L’ordine

delle operazioni di inserimento e molto importante in quanto l’inserimento di

un nodo potrebbe far riferimento ad un nodo padre non ancora presente nel

documento. Per prevenire il problema ordiniamo le operazioni di inserimen-

to secondo ib: questo ci garantisce che un’operazione sul nodo n, trovera gli

n-1 nodi dell’albero gia correttamente inseriti, da cui per la proprieta 3.1 nel

momento in cui inseriamo un nodo, siamo sicuri di aver gia eventualmente

inserito il padre ed i fratelli precedenti.

Le operazioni di aggiornamento faranno riferimento alla posizione ib, in quan-

to quella sara la posizione in cui si trovera il nodo dopo l’applicazione dei

primi due blocchi del delta. Volendo possiamo spostare l’ultimo blocco del

delta in prima posizione e per mantenere la correttezza ci bastera far riferi-

mento ai nodi da aggiornare attraverso le posizioni ia.

57

NDIFF

Per ogni tipo di operazione salveremo dei valori che indicano il punto e il

modo in cui applicarla nell’albero. La trattazione e le specifiche di questi

valori sono affrontate nel capitolo successivo in cui vedremo l’applicazione

del delta.

58

Capitolo 4

Napply:Motore di ricostruzione

Napply e un tool scritto in PHP che partendo dalla versione Vn e dal ∆,

ricostruisce la versione Vn+1. Lo schema di funzionamento del motore di ri-

costruzione e rappresentato in fig.4.1. In questo capitolo descriviamo il pro-

cedimento utilizzato nella ricostruzione. Nell’esposizione successiva indiche-

remo con ‘posizione di un nodo’ l’indice del vettore dei puntatori all’interno

del Vtree(cap.3.3) associato al documento Vn.

4.1 Sintassi del delta

Per comprendere la sintassi del delta partiamo da un esempio di confronto

di due documenti semplici che raccolgono tutte le tipologie di cambiamenti

Figura 4.1: Schema di applicazione del delta.

59

NAPPLY:MOTORE DI RICOSTRUZIONE

trattate.

I documenti che andiamo a confrontare sono la seguente versione Vn:

<?xml version="1.0"?><libro>

<capitolo data="19 feb 2007"><titolo> Ndiff un approccio natuale al diff di documenti XML </titolo>

<sezione><para> Primo approccio a livello naturalesul diff di documenti </para>

</sezione><para> Ndiff risulta modulare, quindi estremamente estendibile. </para>

</capitolo><capitolo info="da completare" data="22 feb 2007">

<titolo> Secondo capitolo, descrizione formale dell algoritmo </titolo><para> Il nostro approccio e estremamente modularein quanto permette di inserire o rimuovere moduli</para>

</capitolo><capitolo>

<titolo> Ricostruzione del documento Originale </titolo><sezione> In questo capitolo parliamo della riapplicazionedel delta al documento originale</sezione>


<titolo> Markup del documento originale</titolo><sezione> Un secondo modo di utilizzare il delta e per marcareil documento orginale in modo da evidenziare le modifiche</sezione>


<titolo> Conclusioni </titolo><sezione> La qualita nel delta di Ndiff risulta miglioredegli altri approcci.</sezione>

</capitolo></libro>

60

e la versione Vn+1:

<?xml version="1.0"?><libro>

<capitolo data="25 feb 2007"><titolo> Ndiff un approccio natuale al diff di documenti XML </titolo><para> Primo approccio a livello naturale sul diff di documenti </para><para> Ndiff risulta modulare, quindi estremamente estendibile. </para>

</capitolo><capitolo informazioni="completato">

<titolo> Secondo capitolo, descrizione formale dell algoritmo </titolo><sezione>

<para> Il nostro approccio e estremamente modularein quanto permette di inserire o rimuovere moduli</para>

</sezione></capitolo><capitolo>

<titolo> Markup del documento originale</titolo><sezione> Un secondo modo di utilizzare il delta e per marcareil documento orginale in modo da evidenziare le modifiche</sezione>




<titolo> Conclusioni </titolo><sezione> La qualita nel delta di Ndiff risulta molto miglioredegli altri approcci.</sezione>

</capitolo></libro>

61

il delta generato da Ndiff su questi due documenti e:

<?xml version="1.0"?><Ndelta>

<DeleteNode vp="4"><sezione/>

</DeleteNode><DeleteTree vp="19:4" move="19:14">

<capitolo><titolo> Markup del documento originale</titolo>

<sezione> Un secondo modo di utilizzare il delta e per marcareil documento orginale in modo da evidenziare le modifiche</sezione>

</capitolo></DeleteTree><InsertNode vp="11:8:1:1">

<sezione/></InsertNode><InsertTree vp="14:0:2:4" move="19:14">

<capitolo><titolo> Markup del documento originale</titolo>

<sezione> Un secondo modo di utilizzare il delta e per marcareil documento orginale in modo da evidenziare le modifiche</sezione>

</capitolo></InsertTree><UpdateElement vp="1">

<updAttr name="data" value="25 feb 2007"/></UpdateElement><UpdateElement vp="8">

<delAttr name="info"/><delAttr name="data"/><insAttr name="informazioni" value="completato"/>

</UpdateElement><UpdateText vp="28">

<Ins tp="39:6">molto </Ins></UpdateText>

</Ndelta>

Come detto nel capitolo precedente, e come si puo vedere dall’esempio,

il delta e espresso in tre blocchi principali, vediamo la composizione e le

operazioni di ognuno dei tre blocchi:

1. Operazioni di cancellazione: Le operazioni di cancellazione sono di

due tipi:

• <DeleteTree vp=‘19:4’ move=‘19:14’>/*albero da cancella-

62

re*/</DeleteTree>: Questa operazione indica la cancellazione

di un sotto-albero del documento, l’attributo vp specifica in ordine

la posizione della radice e il numero di nodi dell’albero da cancel-

lare. L’attributo opzionale move indica che questa operazione e

un’operazione di spostamento e quindi dovra esserci nel secondo

blocco un’operazione insertTree con lo stesso valore dell’attributo

move. Il contenuto del nodo e l’albero da cancellare, che non viene

utilizzato per l’applicazione ma solo per una maggiore chiarezza

all’interno del delta.

• <DeleteNode vp=‘4’> /*nodo da cancellare*/ </DeleteNode>:

In questo caso l’attributo vp specifica la posizione del nodo da

cancellare. Non sono necessarie altre informazioni per rimuovere

un nodo. Il contenuto del tag e il nodo da cancellare che viene

riportato solo per chiarezza del delta.

2. Operazioni di inserimento: Anche le operazioni di inserimento sono

di due tipi:

• <InsertTree vp=‘14:0:2:4’ move=‘19:14’> /* albero da inse-

rire */ </InsertTree>: L’attributo vp specifica rispettivamente

la posizione del nodo da inserire, la posizione del padre del no-

do, la posizione del nodo come figlio e il numero di nodi totali

dell’albero da inserire. Il contenuto del tag e l’albero da inserire.

• <InsertNode vp=‘11:8:1:1’> /* nodo da inserire */ </InsertNode>:

L’attributo vp specifica la posizione del nodo da inserire, la posi-

zione del padre del nodo, la posizione del nodo come figlio, il nu-

mero di figli che il nodo deve adottare dal contesto. Il contenuto

del tag e il nodo da inserire con rispettivi attributi.

3. Operazioni di aggiornamento: Queste operazioni si distinguono in

base al tipo di nodo che devono aggiornare:

63

• <UpdateElement vp=‘1’> /*minidelta*/ </UpdateElement>:

Qui vp specifica solo la posizione del nodo da aggiornare. Il mi-

nidelta interno specifica le sub-operazioni di aggiornamento da

compiere sul nodo elemento. Ci sono tre tipi di sub-operazioni:

– <updAttr name=‘data’ value=‘25 feb 2007’/>: che

indica l’aggiornamento dell’attributo name al valore value.

– <delAttr name=‘info’/>: che indica la cancellazione del-

l’attributo name.

– <insAttr name=‘info’ value=‘ok’/>: che indica l’inseri-

mento dell’attributo name con il valore value.

• <UpdateText vp=‘28’> /*minidelta*/ </UpdateText>: do-

ve vp specifica il nodo a contenuto testuale che deve essere aggior-

nato. L’aggiornamento avviene attraverso un minidelta contenuto

all’interno del nodo e comprende due tipi di operazione:

– <Ins tp=‘39:6’> /*testo da inserire */ </Ins>: qui tp

specifica l’offset iniziale da dove cominciare a inserire nel testo

e la lunghezza del testo da inserire. La stringa da inserire e

contenuta nel tag.

– <Del tp=‘39:6’> /*testo da cancellare */ </Del>: in que-

sto caso tp specifica l’offset iniziale da dove cominciare a can-

cellare il testo e la lunghezza del testo da cancellare. L’infor-

mazione relativa al testo da cancellare non viene usata, ed e

inserita solo per chiarezza del delta.

In tutte le operazioni l’attributo vp determina univocamente il punto dell’al-

bero DOM in cui applicare l’operazione.

4.2 Applicazione del delta

Prima di vedere lo schema di applicazione delle operazioni del delta, ricor-

diamo la sostanziale differenza fra inserimento/cancellazione di un nodo ed

64

inserimento/cancellazione di un sotto-albero. La cancellazione di un nodo

implica che i suoi sotto-alberi rimangono nel documento e vengono ‘adottati’

dal nodo padre del nodo cancellato. L’inserimento di un nodo invece compor-

ta ‘l’adozione’ di sotto-alberi gia appartenenti al documento, ma figli di altri

nodi. Per ‘adozione’ intendiamo dunque lo spostamento di sotto-alberi, gia

presenti nell’albero, come causa della cancellazione/inserimento di un singolo

nodo. Per cancellazione/rimozione di un sotto-albero intendiamo quella clas-

sica. Forniamo di seguito lo schema di applicazione dei vari tipi di operazione

espressi nel delta.

4.2.1 Inserimento di un nodo

Le informazioni a nostra disposizione per l’inserimento sono:

• p:Posizione del nodo da inserire

• pf :Posizione del nodo padre

• pc:Posizione come figlio del nodo da inserire.

• nc:Numero di figli che il nodo deve adottare dal contesto

• node: Nodo da inserire

Consideriamo la fig.4.2, dove viene inserito il nodo ‘1’. L’operazione delta

relativa a questo esempio e:

<InsertNode vp="2:1:1:2"><1/>

</InsertNode>

I passi dell’applicazione sono i seguenti:

1. Inserimento del nodo node come figlio del nodo pf nella posizione come

figlio pc.

2. Adozione di nc nodi dal contesto.

65


Figura 4.2: Un’esecuzione di operazione insert di un nodo.

66


Figura 4.3: Processo di adozione dei nodi

Il primo passo inserisce il nodo node nella giusta posizione dell’albero. Il

secondo passo inserisce come figli di node, i nodi rimasti uguali tra le due

versioni, che node aveva in Vn+1. I nodi rimasti uguali tra le due versioni

appartengono al documento e la loro posizione sara consecutiva a quella di

node. Dobbiamo quindi spostare un numero nc di nodi, rendendoli figli di

node. Prendiamo questi nodi dai fratelli successivi di node ed eventual-

mente dai fratelli successivi del padre di node e cosı ricorsivamente fino ad

arrivare al primo nodo rimasto uguale tra Vn e Vn+1, che avra necessariamente

per costruzione tutti i figli necessari. Nel peggiore dei casi questo nodo sara

la radice del documento. Per distinguere il nodo rimasto invariato tra le due

versioni bastera segnare i nodi inseriti: se un nodo non e segnato allora era

presente anche in Vn. La fig.4.3 mostra un esempio del processo di adozione,

dove abbiamo inserito il nodo ‘1’ e vogliamo adottare 4 figli dal contesto. I

figli che verranno adottati sono evidenziati in figura attraverso dei quadrati.

67

Figura 4.4: Esecuzione dell’operazione di inserimento di un albero.

4.2.2 Inserimento di un albero

Le informazioni a nostra disposizione per l’inserimento di un albero sono:

• p:Posizione della radice dell’albero da inserire

• pf :Posizione del nodo padre

• pc:Posizione come figlio

• ns:Numero di nodi presenti nel sotto-albero da inserire

• tree: Albero da inserire

L’inserimento di un albero e un’operazione semplice in quanto non dobbiamo

preoccuparci di correggere la struttura dell’albero dopo l’inserimento. Basta

infatti inserire l’intero albero tree come figlio pc del nodo padre pf. L’in-

formazione ns viene usata solo per un’applicazione efficiente dell’operazione.

Un’esempio di inserimento di un albero e dato in fig. 4.4 dove il delta relativo

e:

<InsertTree vp="7:0:2:2"><1>

<2/><3/>

</1></InsertTree>

68

Figura 4.5: Un’esecuzione di operazione delete di un nodo.

4.2.3 Cancellazione di un nodo

Nella cancellazione di un nodo abbiamo a disposizione solo l’informazione p

relativa alla posizione del nodo da cancellare. L’operazione di cancellazione

di un singolo nodo e molto semplice in quanto dobbiamo solo cancellare il

nodo in posizione p e far adottare i suoi figli dal padre. In fig. 4.5 e illustrato

l’esempio di cancellazione di un nodo dove il delta corrispondente e:

<DeleteNode vp="1">

</DeleteNode>

La figura mostra come i sotto-alberi radicati in ‘D’ e ‘G’, dopo la rimozine di

‘B’ diventano figli della radice ‘A’. La cancellazione di un nodo non portera

mai l’albero in una configurazione inconsistente, in quanto ci sara sempre la

radice che adottera i figli dei nodi cancellati.

4.2.4 Cancellazione di un albero

Per la cancellazione di un’albero abbiamo a disposizione l’informazione re-

lativa alla posizione p della radice dell’albero da rimuovere. La rimozione

consiste nel cancellare l’intero sotto-albero radicato nel nodo in posizione p.

Un esempio di cancellazione e dato in fig.4.6 dove il delta dell’operazione

relativa e:

69

Figura 4.6: Esecuzione di operazione di cancellazione di un albero.

<DeleteTree vp="7:3"><C>

<L/><M/>

</C>

</DeleteTree>

4.2.5 Aggiornamento di un nodo

L’aggiornamento di un nodo si distingue in base al tipo del nodo da aggior-

nare. E’ previsto l’aggiornamento di:

• Nodi elemento: L’aggiornamento di un nodo elemento e definito

in termini di inserimento, cancellazione e modifica del valore degli

attributi del nodo stesso. La sintassi relativa e stata illustrata in 4.1.

• Nodi a contenuto testuale: L’aggiornamento di un nodo di testo

consiste nell’inserire o rimuovere sotto-stringhe del suo contenuto.

4.3 Trasformazione da Vn a Vn+1

Vogliamo mostrare come il documento originale varia durante l’applicazione

del delta. L’ordine di applicazione del delta implica che l’albero verra pri-

70

4.3 Trasformazione da Vn a Vn+1

Figura 4.7: Trasformazione del documento Vn in Vn+1 attraversol’applicazione del delta.

71


ma ‘sfrondato’ e poi arricchito dalle operazioni di inserimento. I primi due

blocchi del delta trasformeranno la struttura del documento Vn in quella del

documento Vn+1, le operazioni di aggiornamento non influiranno sulla strut-

tura ma solo sul contenuto o sugli attributi dei singoli nodi. Un esempio

della trasformazione dell’albero dopo l’applicazione dei vari blocchi e dato

in fig.4.7. Dopo le cancellazioni, l’albero si trova in uno stato dove sono

presenti solo i nodi comuni a entrambe le versioni, inoltre ogni nodo inter-

medio soddisfa la condizione descritta nella fase di propagazione del match

bottom-up(cap.3.8). Su quest’albero andiamo ad applicare le operazioni di

inserimento. Ricordiamo che tali operazioni sono ordinate sulla posizione del

nodo sulla quale operano. Questo garantisce che l’operazione di inserimento

Oi sul nodo n trovera lo stato degli n-1 nodi precedenti corretto, in quanto le

Oi−1 operazioni precedenti saranno gia state applicate. Dopo l’applicazione

dei primi due blocchi avremo che la struttura del documento Vn sara divenuta

uguale a Vn+1. A questo punto applichiamo il terzo blocco che si occupera

di modificare i singoli nodi dell’albero, ma non ne cambiera la struttura.

72

Capitolo 5

Nmerge:Motore di markup deicambiamenti

Nmerge e un tool scritto in PHP che partendo dalla versione Vn e dal ∆,

costruisce un documento Vn→n+1 uguale a Vn con l’aggiunta di informazioni

relative ai cambiamenti espressi nel ∆. In questo capitolo descriveremo il

procedimento utilizzato per costruire il documento Vn→n+1. Facciamo notare

che avendo Vn→n+1 e sempre possibile ricondursi alla versione Vn+1 sfrut-

tando appunto le informazioni di markup dei cambiamenti presenti. Questo

vuol dire che il risultato ottenuto da Napply, puo essere ottenuto attraverso

Nmerge piu un ulteriore passo(un foglio di stile XSLT), ma comporterebbe

un costo computazionale maggiore. Nella discussione seguente indicheremo

con ‘posizione di un nodo’ l’indice del vettore dei puntatori all’interno del

Vtree(cap.3.3) associato al documento Vn.

5.1 Markup delle differenze

Per illustrare gli elementi ed attributi usati per esprimere le differenze fac-

ciamo riferimento all’esempio del capitolo precedente. La riapplicazione

all’esempio produce:

<?xml version="1.0"?><libro xmlns:diff="http://www.Ndiff.org" diff:stato="modificato">

<capitolo data="25 feb 2007"><titolo> Ndiff un approccio natuale al diff di documenti XML </titolo>

73

NMERGE:MOTORE DI MARKUP DEI CAMBIAMENTI

<para diff:stato="upgrade"> Primo approccio a livellonaturale sul diff di documenti </para><para> Ndiff risulta modulare, quindi estremamente estendibile. </para>

</capitolo><capitolo informazioni="completato">

<titolo> Secondo capitolo, descrizione formale dell algoritmo </titolo><sezione>

<para diff:stato="downgrade"> Il nostro approccio eestremamente modulare in quanto permette di inserireo rimuovere moduli </para>

</sezione></capitolo><diff:mossoDa id="19:14">

<capitolo><titolo> Markup del documento originale</titolo><sezione> Un secondo modo di utilizzare il delta e per marcareil documento orginale in modo da evidenziare le modifiche</sezione>

</capitolo></diff:mossoDa><capitolo>


</capitolo><diff:mossoIn id="19:14">

<capitolo><titolo> Markup del documento originale</titolo><sezione> Un secondo modo di utilizzare il delta e per marcareil documento orginale in modo da evidenziare le modifiche</sezione>

</capitolo></diff:mossoIn><capitolo diff:stato="modificato">

<titolo> Conclusioni </titolo><sezione diff:stato="modificato">

La qualita nel delta di Ndiff risulta<diff:inserito>molto </diff:inserito>miglioredegli altri approcci.

</sezione></capitolo>

</libro>

Il markup relativo ai cambiamenti fa parte del namespace http://www.Ndiff.org

per non creare ambiguita con i dati gia presenti nel documento. Vediamo per

ogni operazione del delta le relative informazioni inserite:

74

5.1 Markup delle differenze

• Inserimento di un albero: L’intero albero viene inserito nel tag

<diff:inserito>...</diff:inserito>, e viene collocato nella giusta posi-

zione.

• Inserimento di un nodo: Ai nodi che diventeranno i figli del nodo

inserito verra aggiunto l’attributo diff:stato=‘downgrade’.

• Cancellazione di un albero: L’intero albero cancellato viene inserito

nel tag <diff:cancellato>...</diff:cancellato> e viene lasciato nella sua

posizione.

• Cancellazione di un nodo: Ai nodi figli del nodo che verra cancellato

verra aggiunto l’attributo diff:stato=‘upgrade’.

• Spostamento di un albero: Lo spostamento di un sotto-albero del

documento corrisponde a due operazione del delta, deleteTree e insert-

Tree legate insieme dal valore di un attributo. La posizione iniziale del-

l’albero mosso viene segnata con in tag <diff:mossoIn id=‘19:14’>...</diff:mossoIn>,

la nuova posizione dell’albero nel documento viene segnata con il tag

<diff:mossoDa id=‘19:14’>...</diff:mossoDa>.

• Aggiornamento di nodo elemento: L’aggiornamento di nodi ele-

mento prevede l’inserimento, l’aggiornamento o la cancellazione degli

attributi del nodo. Per ora non e stato previsto nessun tipo di markup

per queste operazioni.

• Aggiornamento di nodo a contenuto testuale: Vengono segna-

te le stringhe inserite e cancellate nel nodo rispettivamente con i tag

<diff:inserito>...</diff:inserito> e <diff:cancellato>...</diff:cancellato>.

Ognuna delle operazioni precedenti, aggiunge sul percorso cha va dal nodo a

cui si riferisce fino alla radice del documento, l’attributo diff:stato=modifica-

to. Questo per indicare che e avvenuto un cambiamento nel suo sotto-albero.

Segue che se i documenti non sono identici(il delta non e vuoto) la radice del

documento Vn→n+1 avra sempre l’attributo diff:stato=‘modificato’.

75


Figura 5.1: Applicazione delle informazioni di markup alla versione Vn perottenere Vn→n+1

5.2 Inserimento del markup relativo alle dif-

ferenze

Il problema principale nell’inserire il markup dei cambiamenti relativo alle

operazioni descritte nel delta riguarda la non corrispondenza tra il documen-

to che si aspetta l’operazione n e il documento effettivo su cui deve essere

applicata.

Infatti l’operazione n verra applicata su un documento che contiene il mar-

kup dei cambiamenti inserito dalle n-1 operazioni precedenti e che quindi

76

5.2 Inserimento del markup relativo alle differenze

avranno modificato la struttura del documento in un modo diverso da quello

che si aspetta l’operazione. Per chiarezza in fig.5.1 mostriamo l’evoluzione

del documento durante il progressivo inserimento delle informazioni di cam-

biamento contenute nel delta. I problemi maggiori sono dati dalle operazioni

che modificano la struttura dell’albero. In particolare, oltre ai nodi elemento

inseriti a causa del markup(ins,del,ecc..), rimangono nell’albero le parti di

documento che dovrebbero essere rimosse(cancellazione di sotto-alberi) che

ne cambiano profondamente la struttura. Ricordiamo che le operazione de-

scritte nel delta identificano i nodi su cui operare attraverso la loro posizione,

data da una previsita sinistra dell’albero DOM ed equivalente all’indice del

vettore dei puntatori creato all’interno del relativo Vtree.

Per poter individuare correttamente i nodi a cui le operazioni si riferiscono,

dobbiamo trasformare i valori contenuti nel delta tenendo conto delle possi-

bili operazioni di markup presenti nell’albero al momento dell’applicazione

dell’operazione. L’idea e di mantenere la struttura di accesso ai nodi(il vetto-

re dei puntatori), simile al caso dell’applicazione semplice vista nel capitolo

precedente. Nelle sezioni successive vediamo il procedimento per inserire il

markup relativo ai diversi tipi di operazione esprimibili nel delta.

5.2.1 Inserimento di un nodo

L’applicazione dell’operazione di inserimento di un nodo, rimane identica al

caso semplice(cap.4.2.1). Il markup relativo all’inserimento consiste nell’ag-

giunta dell’attributo diff:stato=‘downgrade’ a tutti i suoi figli, in quanto que-

sti scenderanno di un livello nella struttura dell’albero. In fig.5.2 vediamo un

esempio dell’applicazione dell’operazione di inserimento, dove viene inserito il

nodo ‘1’ e ai nodi ‘D’ e ‘G’ viene aggiunto l’attributo diff:stato=‘downgrade’.

Notiamo che questa operazione lascia la struttura dell’albero uguale al caso

semplice in quanto le informazioni di markup vengono aggiunte come attri-

buti.

Tuttavia, nell’effettuare l’inserimento dobbiamo ricalcolare i valori p,pf,pc

77


Figura 5.2: Un’esecuzione di operazione insert di un nodo. I nuovi figli delnodo inserito vengono marcati come downgraded

e nc che dovranno considerare le possibili operazioni di markup dei cam-

biamenti aggiunte da operazioni precedenti. Le funzioni di trasformazione

sono:

• p′ = p, la posizione in cui inserire il nodo e uguale, in quanto dipende

dal vettore dei puntatori che e mantenuto uguale al caso di applicazione

semplice.

• pf ′ = pf , la posizione del nodo padre e corretta perche fa riferimento

al vettore dei puntatori.

• pc′ = pc + c, la posizione come figlio viene incrementata di un valore

c, pari al numero di nodi di markup relativi alle cancellazioni di nodi

presenti come figli di pf la cui posizione e minore di pc.

• nc′ = nc + d, il numero di figli da adottare viene aumentato di una

costante d rappresentante i nodi segnati come cancellati il cui indice

appartiene all’intervallo [pc + 1, pc + nc].

78


Figura 5.3: Un’esecuzione di operazione insert di un albero.

Le costanti c e d vengono motivate dalla condizione di non considerare i nodi

segnati come cancellati nell’albero. Notiamo che se le costanti sono nulle, ci

riconduciamo all’applicazione semplice.

5.2.2 Inserimento di un albero

Il markup relativo all’inserimento di un sotto-albero, consiste nell’introdurre

il nodo diff:inserito tra il sotto-albero e il contesto. I nodi del sotto-albero

inserito verranno considerati nella numerazione, eccetto il nodo diff:inserito.

Un esempio e dato in fig.5.3, dove nel vettore dei puntatori non viene con-

siderato il nodo di markup ins. Le funzione di trasformazione degli indici

sono:

• p′ = p, la posizione in cui inserire l’albero rimane uguale come nel caso

di inserimento di un nodo.

• pf ′ = pf , la posizione del nodo padre e corretta perche fa riferimento

al vettore dei puntatori.

79


Figura 5.4: Un’esecuzione di operazione delete di un nodo.

• pc′ = pc + c, la posizione come figlio viene incrementata di un valore c

uguale ai nodi di markup relativi ai nodi cancellati presenti come figli

di pf , la cui posizione e minore di pc.

5.2.3 Cancellazione di un nodo

La cancellazione di un nodo avviene allo stesso modo del caso semplice(cap.4.2.3).

Il markup relativo all’operazione consiste nell’aggiungere a tutti i figli del no-

do rimosso l’attributo diff:stato=upgrade. Questo indica che i figli del nodo

sono saliti di livello nell’albero. La fig.5.4 mostra un esempio di cancellazione

di un nodo, dove viene cancellato il nodo ‘B’. Di conseguenza i sotto-alberi

radicati in ‘D’ e ‘G’ salgono di un livello e gli viene aggiunto l’attributo

diff:stato=upgrade. Questa operazione lascia la struttura dell’albero ugua-

le al caso semplice in quanto le informazioni di markup vengono aggiunte

come attributi. La funzione di trasformazione per l’unico valore necessario

alla cancellazione e p′ = p, cioe la posizione del nodo da cancellare rimane

identica al caso semplice in quanto si fa riferimento al vettore dei puntatori.

80


Figura 5.5: Un’esecuzione di operazione delete di un albero.

5.2.4 Cancellazione di un albero

Il markup relativo alla cancellazione di un sotto-albero viene effettuato in-

serendo il nodo diff:cancellato tra il sotto-albero da cancellare e il contesto.

Il sotto-albero da cancellare rimane nell’albero del documento, ma i suoi

nodi non verranno indicizzati dal vettore dei puntatori. Questo ci permet-

tera di far coincidere le posizioni dei nodi al caso dell’applicazione semplice.

L’esempio in fig.5.5 mostra come i nodi dell’albero cancellato non vengano

piu considerati dal vettore dei puntatori. La funzione di trasformazione per

l’unico valore necessario alla cancellazione dell’albero e p′ = p, cioe la posi-

zione della radice dell’albero da cancellare rimane identica al caso semplice

in quanto si fa riferimento al vettore dei puntatori.

5.2.5 Aggiornamento di un nodo

Il markup relativo all’aggiornamento di un nodo e l’operazione piu complessa.

Distinguiamo i casi tra aggiornamento di nodo elemento e aggiornamento di

nodo a contenuto testuale.

• Aggiornamento di nodo elemento: L’aggiornamento di un nodo

81


Figura 5.6: Aggiornamento di un nodo di testo.

elemento comporta l’inserimento, l’aggiornamento del valore o la can-

cellazione di un attributo del nodo. Attualmente queste operazioni non

vengono evidenziate.

• Aggiornamento di un nodo a contenuto testuale: Questa e una

delle operazioni piu complesse in quanto la struttura dell’albero cambia

in modo radicale(fig. 5.6). In particolare il vecchio nodo di testo si tra-

sforma in un sotto-albero a causa delle informazioni di markup inserite.

L’aggiornamento consistera nel dividere il nodo di testo in tanti nodi

di testo piu piccoli, determinati dalle operazioni da applicare. I nuovi

nodi di testo ottenuti potranno avere come padre, o un nodo di markup

di cambiamento che identifica se la stringa contenuta e stata inserita

o cancellata, o il padre dell’ex-nodo di testo(parti di testo invariate).

Durante l’aggiornamento e importante fare attenzione al modo di cal-

colare l’offset da cui partire per inserire o cancellare le sotto-strighe, in

particolare calcoleremo l’offset in base ai nodi di testo che sono segnati

82


come inseriti e a quelli che rappresentano parti invariate. Nel vettore

dei puntatori viene lasciata una posizione che indica l’ex-posizione del

puntatore al nodo di testo.

La funzione di trasformazione per l’unico valore necessario all’aggiornamento

del nodo e p′ = p, cioe la posizione del nodo da aggiornare rimane identica

al caso semplice in quanto si fa riferimento al vettore dei puntatori.

83


84

Capitolo 6

Un’applicazione di Ndiff:LIBRA

Vediamo in questo capitolo l’utilizzo di Ndiff in un’applicazione reale. L’ap-

plicazione realizzata e un’interfaccia grafica che usa Ndiff come core per

effettuare il calcolo delle differenze tra due DDL(Disegno di Legge). L’appli-

cazione realizzata, soprannominata LIBRA, e schematizzata in fig.6.2.

6.1 Contesto

LIBRA si occupa di rilevare le differenze tra versioni diverse di un DDL.

Per capirne l’applicazione schematizziamo il procedimento formale che porta

all’approvazione di una legge.

Il procedimento legislativo statale per le leggi ordinarie e disciplinato nella

parte II della Costituzione al titolo I, sez II dagli artt. 71-74 della Costi-

tuzione e dai regolamenti parlamentari.Questo procedimento consta di tre

fasi:

• Fase dell’iniziativa: La fase dell’iniziativa consiste nell’esercizio da

parte di determinati soggetti del potere di sottoporre progetti di legge

al Parlamento. La Costituzione riconosce tale potere:

– al Governo

– ai membri del Parlamento

85

UN’APPLICAZIONE DI NDIFF: LIBRA

– al corpo elettorale (che puo essere esercitata attraverso la presen-

tazione alle Camere da una proposta sottoscritta da almeno 50.000

elettori)

– ai Consigli Regionali

– al Consiglio Nazionale dell’Economia e Lavoro

• Fase della discussione e della votazione:

La seconda fase del procedimento legislativo comincia con l’assegnazio-

ne da parte del presidente della camera cui e pervenuto il progetto di

legge alla commissione parlamentare competente ‘rationae materiae’.

La commissione parlamentare opera diversamente a seconda della ‘se-

de’ in cui viene autorizzata a operare. La commissione parlamentare

incaricata di esaminare il progetto di legge puo operare in:

– Sede referente: si tratta della sede in cui le commissioni opera-

no seguendo il cosiddetto ‘procedimento legislativo ordinario’, in

esso si prevede una discussione sul testo nel suo complesso seguita

da una discussione del testo articolo per articolo.Alla discussione

segue un voto sul progetto di legge.La commissione ha in tale sede

il compito di preparare i documenti( testo del progetto di legge e

relazioni) su cui lavorera poi piu accuratamente prima una e poi

l’altra camera del parlamento.

– Sede legislativa:la commissione che opera in sede legislativa (si

tratta di un procedimento speciale) si occupa della discussione,

della votazione e della approvazione del progetto di legge estromet-

tendo completamente il parlamento dai lavori. E sempre ammessa

durante i lavori della commissione la domanda di ‘rimessione in

assemblea’ del progetto di legge.

– Sede redigente:e la seconda procedura speciale prevista dai re-

golamenti di camera e senato; la commissione ha gli stessi compiti

86

6.1 Contesto

che aveva quando operava in sede referente con l’agiunta che la sua

votazione sui singoli articoli del progetto di legge assume caratte-

re di definitivita, ed il testo che viene presentato alla camera sara

votato nella sua interezza (senza quindi procedere alla votazione

articolo per articolo)

Il procedimento legislativo ordinario continua con l’assegnazione del

progetto di legge al presidente di una delle camere del parlamento il

quale permette la discussione, la votazione articolo per articolo ed infine

la votazione finale sull’intero progetto di legge. Qualora la maggioranza

dei presenti in aula abbiano votato favorevolmente il disegno di legge si

intende approvato e passa all’altra camera, la quale se vota favorevol-

mente al progetto senza apportarvi modifiche fa si che sia completata

la fase deliberativa.

• Fase della promulgazione e della pubblicazione

La terza ed ultima fase e quella che attiene alla produzione degli effetti

normativi della legge e riguarda la promulgazione e la pubblicazione.

La promulgazione deve avvenire entro 30 giorni dall’approvazione parla-

mentare o in un termine minore se entrambi la Camere, a maggioranza

assoluta, ne dichiarino l’urgenza (Art.73 della Costituzione) e spetta

al Presidente della Repubblica. Subito dopo la promulgazione ,e co-

munque entro 30 giorni dalla stessa, la legge deve essere pubblicata.

Quest’ultima fase vede l’intervento del Ministro della Giustizia, depo-

sitari del sigillo dello Stato. Una volta posto il sigillo alla legge, essa

viene pubblicata sulla Gazzetta ufficiale.

LIBRA e il tramite che fornisce il supporto dei cambiamenti nel passaggio dei

DDL da una camera all’altra, mettendo in evidenza le modifiche apportate da

ogni camera. Le differenze tra due DDL vengono riportate su un documento

TAF(Testo a Fronte), formato da due colonne, in cui a sinistra viene messo

il testo originale e a destra il testo modificato(fig.6.1).

87


Figura 6.1: Esempio di testo a fronte.

88

6.2 LIBRA

Figura 6.2: Funzionamento di LIBRA

6.2 LIBRA

LIBRA e un’interfaccia scritta in PHP che prende in input due versioni di

un disegno di legge e restituisce un documento TAF(Testo a Fronte), dove

attraverso una visualizzazione a due colonne, vengono riportate le differenze

riscontrate. Lo schema di esecuzione e riportato in fig.6.2 in cui partendo

dalle versioni Vn e Vn+1 viene applicato l’algoritmo Ndiff producendo il docu-

mento ∆. A questo punto il documento Vn e il ∆ vengono passati al motore

Nmerge per produrre il documento Vn→n+1 rappresentante in XML il docu-

mento Vn dove sono state aggiunte le informazioni di cambiamento(cap.5).

Per produrre il formato testo a fronte voluto, processiamo attraverso un foglio

di stile il documento Vn→n+1 ottenendo un file HTML che mette in evidenza

le differenze. Notiamo che la creazione del documento finale e indipendente

dall’algoritmo Ndiff e dall’applicativo Nmerge, infatti dipende sono dal foglio

di stile con il quale processiamo il documento Vn→n+1. Questo ci permette

di cambiare la visualizzazioni dei risultati modificando solo il foglio di stile.

89


90

Capitolo 7

Conclusioni

L’algoritmo Ndiff ha come punti di forza la modularita del procedimento,

che ci permette di aggiungere o togliere delle fasi e la parametrizzazione di

queste attraverso dei valori che esprimono la concezione umana di confron-

to. Questo modo di procedere, ci permette di scegliere un tipo di soluzione

delta variando i parametri delle fasi dell’algoritmo e attivando, escludendo

o cambiando l’ordine di queste. Inoltre Ndiff fornisce un delta molto detta-

gliato, andando a specificare sia l’inserimento/cancellazione di singoli nodi

che eventuali modifiche all’interno di nodi testuali. Grazie alla sua parame-

trizzazione, Ndiff diviene adattabile ad una molteplicita di contesti fornendo

una forte base sulla quale poter costruire sistemi di versionamento per diversi

tipi di applicazione. A livello implementativo abbiamo realizzato i tre tool

riportati in questa tesi, Ndiff, Napply ed Nmerge, oltre l’applicazione LIBRA

che come detto si basa sui tool precedenti. In LIBRA, le fasi usate da Ndiff

sono quelle descritte in questa tesi, nulla toglie pero una futura espansione

dell’algoritmo aggiungendo nuove fasi per poter individuare una maggiore

varieta di operazioni rilevanti nel contesto dei DDL.

7.1 Espansione future

Possibili espansioni dell’algoritmo saranno la realizzazione di una molteplicita

di moduli, capaci di individuare nuovi tipi di operazione. Questo e possibile

91

CONCLUSIONI

grazie all’indipendenza logica dei vari moduli, in quanto ogni modulo prende

in input una relazione sui nodi(eventualmente vuota) e i due Vtree rappre-

sentanti i documenti da confrontare e produce in output delle nuove relazioni

tra i nodi delle due versioni. La modularita permettera di inserire o togliere

dei moduli adattando il tool alle tipologie di modifica che vogliamo rilevare.

Un esempio di modulo che puo venir creato e il caso della rilevazione del par-

tizionamento di un nodo. Infatti si potrebbe voler identificare l’operazione

di strutturazione di un nodo testo, cioe il caso in cui un nodo di testo del

documento Vn diviene un albero strutturato nella versione Vn+1 attraverso

l’aggiunta di tag. Inoltre e doveroso un porting in java di Ndiff, Napply e

Nmerge, attualmente implementati in PHP, per dotare i tool di una maggiore

portabilita.

92

Bibliografia

[Vitali et al,95] Vitali F., Durand D., ‘Using Versioning to Provide Collabo-

ration on the WWW’,

The World Wide Web Journal, 1(1), 1995, 37-50.

[Vitali,99] Vitali F., ‘Versioning Hypermedia’,

ACM Computing Surveys, 31(4), 1999, article n. 24, pp. 7.

[Schirinzi,04] Schirinzi M., ‘Gestione dei cambiamenti per documenti digitali

sul web’.

Tesi , Universita degli studi di Bologna, Facolta di Scienze Matematiche

Fisiche e Naturali, Dipartimento di Informatica , 2004.

[Chawathe,99] Sudarshan S.Chawathe, ‘Comparing Hierarchical Data in Ex-

ternal Memory’,

Proceedings of the 25th International Conference on Very Large Data

Bases, Sept. 1999.

[Robin La Fontaine,2001] Robin La Fontaine, ‘A Delta Format for XML:

Identifying changes in XML and representing the changes in XML’,

XML Europe, 2001.

[Kuo-Chung,79] K.C. Tai, ‘The tree-to-tree correction problem’,

In Journal of the ACM, 26(3), pages 422-433, july 1979.

[Selkow,77] S. M. Selkow, ‘The tree-to-tree editing problem’,

Information Processing Letters, 6, pages 184-186,1977.

93

BIBLIOGRAFIA

[Hirschberg,75] D. S. Hirschberg, ’A linear space algorithm for computing

longest common sub-sequences’,

Communications of the ACM, 18 (1975), pp. 341-343.

[Conklin,87] Conklin E.J., ‘Hypertext: An Introduction and Survey’,

IEEE Computer, 20, 1987, 17-41.

[Maioli et al,94] Maioli C., Sola S., Vitali F., ‘The Support for Emergence

of Collaboration in a Hypertext Document System’

in: ACM CSCW’94 Workshop on Collaborative Hypermedia Systems,

Chapel Hill (NC), GMD Studien n. 239, ACM, 1994

[Chawathe,97] S. Chawathe, H. Garcia-Molina, ‘Meaningful Change Detec-

tion in Structured Data’,

Proceedings of the ACM SIGMOD International Conference on

Management of Data, June 1996

[Chawathe,96] S. Chawathe, A. Rajaraman, H. Garcia-Molina and J. Wi-

dom, ‘Change Detection in Hierarchically Structured Information’,

SIGMOD,vol.25,no.2,pp.493-504, 1996

[Kaizhong,90] Kaizhong Zhang and Dennis Shasha, ‘Fast algorithms for the

unit cost editing distance between trees’,

Journal of Algorithms, 11(6), pp. 581-621, 1990.

[Kaizhong et al,89] Kaizhong Zhang and Dennis Shasha, ‘Simple Fast Algo-

rithms for the Editing Distance Between Trees and Related Problems’,

SIAM Journal of Computing, 18(6), pp.1245-1262, 1989.

[XMLDiff] Logilab XMLDiff.

Project Website: http://www.logilab.org/projects/xmldiff/ .

[Shu yao et al,01] Shu-Yao Chien, Vassilis J. Tsotras, and Carlo Zaniolo,

‘Version management of XML documents’,

Lecture Notes in Computer Science, 2001.

94

BIBLIOGRAFIA

[Barnard et al,95] David T. Barnard, Gwen Clarke, and Nicolas Duncan,

‘Tree to tree Correction for Document Trees’,

Technical report 95-372,Department of Computing and Information

Science, Queen’s University, Kingston, 1995.

[Eugene W. Myers.,86] Eugene W. Myers., ‘An O(ND) difference algorithm

and its variations’,

In Algorithmica, 1986.

[Berk,96] Berk, E., ‘HtmlDiff: A Differencing Tool for HTML Documents’,

Student Project, Princeton University,1996

[A. Apostolico et al,97] A. Apostolico and Z. Galil, ‘Pattern Matching Algo-

rithms’,

Oxford University Press, 1997.

[V.I.Levenshtein,66] V. I. Levenshtein , ‘Binary codes capable of correcting

deletions, insertions,and reversals’,

Cybernetics and Control Theory 10, pages 707-710, 1966.

[R. A. Wagner et al,74] R. A. Wagner and M. J. Fischer, ‘The string-to-

string correction problem’,

Jour. ACM 21, pages 168-173, 1974

[GNU diff] GNU diff, FSF. GNU diff, www.gnu.org/software/diffutils/diffutils.html

[XyLemme] XyLemme, Xyleme Project, http://www-rocq.inria.fr/verso/

[G.Cobena et al] G. Cobena, S. Abiteboul, and A. Marian, XyDiff, ‘tools for

detecting changes in XML documents’

[DeltaXML] DeltaXML, ‘Change control for XML in XML.’,

http ://www.deltaxml.com/

[ISA] Vitali F., Creating sophisticated Web sites using well-know interfaces’

MCI Internation Conference 2003’, Creta(Greece), june 2003

95

Ndiï¬€ un approccio naturale al confronto di documenti XML

Documents

Transcript of Ndiï¬€ un approccio naturale al confronto di documenti XML