Gestione dei cambiamenti
per documenti digitali
sul Web
Tesi di Laurea di:
MICHELE SCHIRINZI
Relatore: Chiar.mo Prof.
FABIO VITALI
Introduzione
“Un documento non può essere semplicemente pensato come una sequenza statica di
caratteri invariata nel tempo, ma è una struttura evolutiva a cui vengono aggiunte,
eliminate o modificate delle parti. Queste modifiche sono parte integrante del documento
stesso: è utile (se non fondamentale) poter ricostruire qualsiasi porzione di una qualsiasi
versione, così come era in un qualsiasi momento della storia del documento ”
[Nelson T.H.]
Un sistema che soddisfi questa definizione deve poter memorizzare tutti gli stati
di sviluppo intermedi(versioni) di un documento.
Possono esserci due modi per compiere questa operazione:
1. Memorizzare interamente ogni stato del documento.
2. Memorizzare i cambiamenti avvenuti fra una versione e la sua successiva.
Memorizzazione delle versioni
Nel primo caso immaginiamo di “fotografare” il documento in diversi momenti
del suo sviluppo e mantenere ordinatamente le varie “fotografie”.
Prima stesura del
documento
Questo è il
documento nella
sua versione
originale, la
prima stesura del
documento
Questo è il
documento nella
sua seconda
versione , la
seconda stesura
del documento
Questo è il
documento nella
sua terza
versione, la terza
stesura del
documento
Versione attuale del
documento
Questo è il
documento nella
sua versione
attuale, l’ultima
stesura del
documento
Nel secondo caso andiamo a memorizzare solo i cambiamenti avvenuti fra una
versione e la sua successiva (delta).
Prima stesura del
documento
Questo è il
documento nella
sua versione
originale, la
prima stesura del
documento
Delete(8)
Delete(15)
Insert(testo1)
Update(4,Ndelta)
Algoritmi di Diff.
Insert(testo4)
Delete(4)
Delete(9)
Insert(testo5)
• L’input consiste in due versioni
di uno stesso documento;
Versione del
documento
Diff
Versione del
documento
Insert(testo)
Insert(testo2)
Update(7,Ndelta)
Delete(12)
(Delta) Differenze
fra le due versioni
• Il risultato è un documento delta
che rappresenta i cambiamenti
avvenuti fra questi.
HML-diff: Un algoritmo di Diff
per documenti XML
Presentiamo ora un algoritmo ideato da noi per la ricerca dei cambiamenti fra
versioni all’interno del progetto IsaWiki.
L’algoritmo è stato implementato in PHP per essere usato all’interno del sistema
IsaWiki. Sono state realizzate la funzionalità di Diff, la ricostruzione di un
documento e la possibilità di visualizzare i cambiamenti fra due versioni.
L’algoritmo si divide in 4 passi principali:
1. Ricerca della massima parte invariata fra i documenti.
2. Ricerca delle parti spostate dei documenti (una parte è considerata spostata se
appare in punti diversi fra le due versioni rispetto alla parte più grande
rimasta invariata delle versioni).
3. Ricerca delle parti aggiornate dei documenti (una parte è considerata
aggiornata se appare nella stessa posizione fra le due versioni e differisce per
una certa quantità limitata da una costante).
4. Espressione delle informazioni rilevate nelle fasi precedenti.
Ricerca delle parti invariate
Il primo passo è serializzare i documenti XML.
La serializzazione avviene attraverso una visita in profondità con pre-ordine
degli alberi dei documenti.
Ogni elemento della sequenza è un valore hash che rappresenta un sottoalbero
dell’albero del documento.
1
2
3
7
8
4
9
sequenza
11
E1 E2
5
6
10
..
..
..
..
..
..
..
..
E11
Ricerca delle parti invariate
Applichiamo un algoritmo per trovare la LCS (Longest Common Subsequence)
fra le sequenze che rappresentano i documenti da confrontare.
L’algoritmo per trovare la LCS suppone che una LCS sia formata dalla
concatenazione ordinata di LCCS(Longest Common Continuous Subsequence).
Durante il calcolo della LCS possiamo usare i seguenti accorgimenti:
• Se S1[i]=S2[j] allora anche gli N elementi successivi a i e j saranno uguali, dove
N è il numero di nodi appartenenti al sottoalbero radicato nel nodo associato
all’elemento S1[i].
• Dividiamo gli elementi di una sequenza in classi, in modo da limitare i
confronti (Ha senso confrontare un nodo di testo con un nodo di testo).
Questa suddivisione può essere compiuta in tempo lineare all’atto della
creazione della sequenza.
Passi successivi
Una volta ottenute le parti uguali maggiori fra le due sequenze esaminiamo le
parti restanti per rifinire la qualità del delta.
Sequenza A
Sequenza B
In verde sono contrassegnate le parti uguali fra le due sequenze.
Espressione del delta
Raccolte tutte le informazioni delle fasi precedenti, consideriamo:
1. Se un nodo della sequenza A non è stato trovato in nessuna delle fasi
precedenti viene considerato cancellato
2. Se un nodo della sequenza B non è stato trovato in nessuna delle fasi
precedenti viene considerato inserito
3. I nodi mossi e i nodi aggiornati sono quelli trovati nelle rispettive fasi
Nell’espressione del delta vengono prima esplicitate tutte le operazioni di
cancellazione e aggiornamento, di seguito vengono esplicitate le operazioni di
inserimento.
Quest’ordine è importante perché ci garantisce di trovare dopo l’esecuzione
dell’ N-esima operazione, il documento nello stato in cui deve essere applicata
N+1-esima operazione.
Complessità e Qualità
L’algoritmo descritto ha una complessità di O(N * C * D) dove:
• N sono i numeri di nodi del documento A
• C la cardinalità media delle classi in cui vengono divisi gli elementi del
documento. C << N.
• D un valore proporzionale alle differenze fra i due documenti confrontati.
La qualità del delta ottenuto è buona in quanto oltre alle classiche operazioni di
inserimento e cancellazione descrive operazioni di:
• Move, riconosce parti del documento spostare fra le due versioni.
• Update, riconosce aggiornamenti di nodi Testo, Elemento, Commento.
Conclusioni
• Con la transizione del Web verso XML, sistemi di questo tipo assumono
un’importanza rilevante all’interno di CMS(Content Management System).
• Inoltre questi sistemi possono essere di supporto ad applicazione che usano i
nuovi standard basati su XML(DocBook, RSS, RDF, ecc..).
• In generale è un’utilità fondamentale all’interno di sistemi in cui è interessante
seguire lo sviluppo dei documenti in funzione del tempo, infatti permettono
un’analisi semplice e comoda dell’evoluzione di un documento.
Book
2
Chapter 7
Chapter
5
3
Title
8
Para
4
Text1
Text 2
13
11
Text 4
14
Text 5
match
Text 6
24
12
19 Chapter
15
Title
Para
9
6
Chapter
10
Title
1
Title
Img
Text 7
update
Para
Para
Title
25
17
16
22
20
Para
Chapter
18
21
23
Text 8
Text 9
Text 10
27
26
28
Text 11
Text 12
move
match
match
Book
5
2 Chapter
Chapter
Para
Title
3
4
Text 4
Para
10
9
Text 25
19 Chapter
Chapter
6
7
Text 2
24
12
8
Para
match
1
13
20
15
Title
11
14
16
Text 11
Text 6
Text 7
17
Img
22
Title
Para
Chapter
Para
18
21
23
Text 8
Text 9
Text 10
Title
25
26
Text 12
19
19
Chapter
oxfbng
Chapter
22
20
Title
qtrhky
Para
Title
23
21
qtrhky
21
Text 10 b5g43g
Text 9
22 eewgrt + b5g43g
20
eewgrt
oxfbng
Text 9
Para
19 oxfbng + eewgrt + b5g43g
23
Text 10 b5g43g
Chapter
bcnngh
bcnngh
22
20
Title
19 oxfbng + eewgrt + b5g43g
Chapter
21
Title
Para
Para
eewgrt + b5g43g
23
bcnngh Text 9
22
20
qtrhky
Text 10 b5g43g
eewgrt + b5g43g
qtrhky + bcnngh
21
Text 9
oxfbng + eewgrt + b5g43g + qtrhky + bcnngh
23
Chapter 19
Text 10 b5g43g
bcnngh
22
20
Title
Para
eewgrt + b5g43g
qtrhky + bcnngh
21
Text 9 bcnngh
23
Text 10 b5g43g
X=<A,B,F,H,F,G,T,R,K,W,E,S,D>
Y=<A,B,U,H,U,G,T,R,K,M,E,S,D>
X=<A,B,F,H,F>
X=<W,E,S,D>
Y=<A,B,U,H,U>
Y=<M,E,S,D>
LCCS
X=<F,H,F>
X=<>
Y=<U,H,U>
Y=<>
X=<F>
Y=<U>
Y=<U>
X=<>
Y=<M>
Y=<>
LCCS
LCCS
LCCS
<A,B>
X=<F>
X=<W>
<H>
<G,T,R,K>
<E,S,D>
LCS
Equa(x)
Move(x)
Nodi di T²
Update(x)
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Nodi di T¹
l3
l2
1° Ciclo
l1
a
b
c
d
a
f
c
t
e
a
b
c
d
a
b
b
a
n
max1 = l2 = 4
a
f
c
t
a
b
c
d
l1
e
c
d
b
a
d
e
b
b
m
b
b
a
n
l3
l2
l3
2° Ciclo
l2
l1
a
b
c
d
a
f
c
t
e
a
b
c
d
a
max2 = l1 = 4
a
f
c
t
a
b
l1
c
d
e
c
d
b
a
d
l3
l2
e
b
b
m
HML-diff: Esempio
Confrontare file con 'Diff Doc'
Ora è possibile confrontare documenti in modo
rapido e preciso. “Diff Doc” è una potente
utility per confronti e correzioni di cartelle/file
di facile utilizzo. Permette infatti di confrontare
file di tutti i tipi, compresi MS Word/Excel,
PDF, RTF, Text, XML, HTML, Wordperfect e
altri.
Indipendentemente dal programma di editing
utilizzato (MS Word, WordPad, Visual Basic,
ecc), basta caricare i file originali e quelli
modificati, premere il tasto Refresh (Aggiorna)
(o F5), e il documento confrontato apparirà
immediatamente. E’ inoltre possibile
confrontare le cartelle per vedere esattamente
quali file sono cambiati, prima ancora di
effettuare il confronto.
“Diff Doc” può indicare le differenze fra i file in
due diverse schermate, “All in One”, o “Side by
Side”. Entrambe presentano dei vantaggi, per
passare da una all’altra basta un clic col mouse
(o premere F6). Infine, sono disponibili
numerosi report, incluso quello in HTML, in cui
vengono specificate le differenze
Aggiornamento
Aggiornamento
Invariato
Spostamento
Confrontare documenti con
'Diff Doc'
Ora è possibile confrontare documenti in modo
veloce e preciso. “Diff Doc” è una potente
utility per confronti e correzioni di cartelle/file
di facile utilizzo. Permette infatti il confronto di
file di tutti i tipi, compresi MS Word/Excel,
PDF, RTF, HTML, Wordperfect e altri.
“Diff Doc” può indicare le differenze fra i file in
due diverse schermate, “All in One”, o “Side by
Side”. Entrambe presentano dei vantaggi, per
passare da una all’altra basta un clic col mouse
(o premere F6). Infine, sono disponibili
numerosi report, incluso quello in HTML, in cui
vengono specificate le differenze
Indipendentemente dal programma di editing
utilizzato (MS Word, WordPad, Visual Basic,
ecc), basta caricare i file originali e quelli
modificati, premere il tasto Refresh (Aggiorna)
(o F5), e il documento confrontato apparirà
immediatamente. E’ inoltre possibile
confrontare le cartelle per vedere esattamente
quali file sono cambiati, prima ancora di
effettuare il confronto.
Nodo Inserito
Nodo update
A
A
B
B
B
A
A
A
B
B
B
A
B
A
A
B
B
Nodo Cancellato
A
Nodo Mosso
B