Správa změn v dokumentech XML

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Diplomová práce

Správa změn v dokumentech XML Bc. Luděk Zika

Vedoucí práce: Ing. Ivan Šimeček, Ph.D.

Studijní program: Elektrotechnika a informatika, strukturovaný, Navazující magisterský Obor: Výpočetní technika 13. května 2011

iv

v

Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 13. 5. 2011

.............................................................

vi

Abstract Standard tools are mostly comparing files on line-by-line basis. They are not optimal choice for comparing documents, which are using hierarchical trees, such as XML documents. Better results could be obtained with algorithms for ordered labelled trees. This work presents efford to aplly selected algorithm in comparing XML documents.

Abstrakt Běžné postupy na porovnávání souborů po řádcích se nehodí pro porovnávání stromově strukturovaných dokumentů jako XML. Východiskem pro lepší uchopení problému mohou být algoritmy pro porovnání uspořádaných stromů. Tato práce si klade za cíl aplikovat vybraných algoritmus a uplatnit ho při porovnávání dokumentů XML.

vii

viii

Obsah 1 Úvod 1.1 XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Využití . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Popis problému, specifikace cíle 2.1 Porovnávání souborů . . . . . . . 2.2 Nejdelší společná podposloupnost 2.3 Porovnání řetězců . . . . . . . . . 2.4 Algoritmus Wanger-Fisher . . . . 2.5 Porovnávání stromů . . . . . . . . 2.5.1 Selkow . . . . . . . . . . . 2.5.2 Tai . . . . . . . . . . . . . 2.5.3 Zhang-Shasha . . . . . . . 2.6 Stávající řešení . . . . . . . . . . 2.6.1 diffxml . . . . . . . . . . . 2.6.1.1 FMES . . . . . . 2.6.1.2 xmdiff . . . . . . 2.6.2 XmlDiff . . . . . . . . . . 2.6.3 DeltaXML . . . . . . . . . 2.7 Cíle . . . . . . . . . . . . . . . . 2.8 Požadavky . . . . . . . . . . . . . 3 Analýza a návrh řešení 3.1 Ohodnocení operací . . . 3.2 Výstupní formát . . . . . 3.2.1 Stromové značky 3.2.2 Uzlové značky . .

. . . .

. . . .

4 Implementace 4.1 Třída XMLSAX . . . . . . . 4.2 Rozhraní Node . . . . . . . 4.3 Třída NodeXMLImpl . . . . 4.4 Třída ZHEDiffMatrix . . . . 4.4.1 CountMinimalValue 4.5 Třída Cost . . . . . . . . . . 4.6 Třída DiffOperation . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

ix

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

. . . . . . . . . . . . . . . .

. . . .

. . . . . . .

1 1 2

. . . . . . . . . . . . . . . .

5 5 6 6 7 7 8 8 9 10 10 10 10 10 10 11 11

. . . .

13 14 14 14 15

. . . . . . .

19 19 20 20 20 20 20 21

x

OBSAH

4.7

Třída Attribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Testování 5.1 Kontrola správnosti výstupu 5.1.1 Výchozí soubor . . . 5.1.2 Změna 1 . . . . . . . 5.1.3 Změna 2 . . . . . . . 5.2 Rychlost . . . . . . . . . . .

21

. . . . .

23 23 23 23 24 25

6 Závěr 6.1 Náměty pro budoucí práci . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27 27

A Seznam použitých zkratek

31

B Uživatelská příručka

33

C Obsah přiloženého CD

35

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

Seznam obrázků 1.1 1.2

Ukázka XML souboru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ukázka chybného XML souboru . . . . . . . . . . . . . . . . . . . . . . . . .

2.1 2.2 2.3 2.4

Stromová reprezentace XML . . . . . Pseudokód algoritmu Wanger-Fisher Srovnání vzdáleností stromů a lesů [3] Pseudokód algoritmu Z-S . . . . . . .

. . . .

5 8 9 12

3.1 3.2

Příklad změny stromu [3] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pseudokód rozšířeného algoritmu ZS . . . . . . . . . . . . . . . . . . . . . .

13 17

C.1 Seznam přiloženého CD — příklad . . . . . . . . . . . . . . . . . . . . . . .

35

xi

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

1 2

xii

SEZNAM OBRÁZKŮ

Seznam tabulek 2.1

Nedostatek řádkového srovnávání . . . . . . . . . . . . . . . . . . . . . . . .

6

3.1

Pole vzdáleností . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

xiii

xiv

SEZNAM TABULEK

Kapitola 1 Úvod Textové soubory nejčastěji obsahují pouze pouze plynulý tok textu, který dokáže pochopit pouze člověk. Pokud se však informace vhodně upraví do předem dohodnuté formátu, lze textovými soubory přenášet i data, které lze následně počítačově zpracovat. Jedním z obecných standardů je SGML (Standard Generalized Markup Language), který definuje význam pomocí značek. Text se tak skládá ze značek uzavřených mezi znaky < a > a pak samotný obsah, který je všude mimo takové značky. Jedním z jazyků, který vychází z SGML je jazyk XML (Extensible Markup Language). Tento jazyk našel široké uplatnění v oblasti strojově čitelného předávání informací. Samotné webové stránky jsou tvořeny mimo jiné odvozeným jazyk HTML. HTML však není podmnožinou XML, obsahuje některé prvky, které pravidla XML nesplňují. Kompromisní variantou je XHTML, který již je podmnožinou jazyka XML.

1.1

XML

<sklad> Golden Interstar 890HD 8356 Golden Reklamní leták <sklad> Obrázek 1.1: Ukázka XML souboru XML je značkovací jazyk, který definuje jednoduché formátování textových informací.V ukázce 1.1 je příklad soubor XML. Dokument XML je strukturován jako s jediným kořenovým prvkem. Další části dokumentu jsou vzájemně provázané prvky (elementy, atributy, komentáře a další).

1

2

KAPITOLA 1. ÚVOD

Zápis se skládá ze značek uzavřených mezi ostré závorky závorkami (znaky „<“ a „>“), kterým se říká tagy. Rozlišujeme počáteční a koncové tagy. Koncový tag se od počátečního liší znakem „lomítko” (/), který je umístěný bezprostředně před názvem tagu. Ve jménech tagu jsou rozlišována velká a malá písmena[120]. Základní jednotkou XML jsou dále elementy. Element je otevírací a ukončovací tag a text mezi nimi. Informace jsou neseny jak v samotném textu, tak právě v uspořádání textu v jednotlivých značkách. Z uvedeného příkladu je tedy vidět, že zachycuje výrobek, který může mít vlastnosti (název, cenu a měnu) a jakou hodnotu nabývají dané vlastnosti. Struktura XML je přesně dána. Příkladem 1.2 je neplatný dokument, neboť tag „sklad“ je ukončen uvnitř svého potomka. <sklad> Golden Interstar 890HD 8356 Golden <sklad> Reklamní leták

Obrázek 1.2: Ukázka chybného XML souboru

1.2

Využití

Dokumenty XML nalézají široké uplatnění, je určen pro počítačové zpracování, takže je v hodný pro udržování konfigurací, výměnu dat, strukturování dokumentu. Pro jejich univerzální použitelnost jsou často využívány i ve webových aplikacích, ať již jako XHTML či trošku odlišného HTML.[6] Takových dokumentů je značný počet a často se mění. Vhodné zpracování takových dat je proto obzvláště důležité, ke zjištění změn a případné slučování různých změn v dokumentu. Problémem je, že XML používá stromovou strukturu, takže nelze použít prosté porovnání po řádcích. Takové by mohlo porušit stromovou strukturu a nemusel by být vůbec zřejmé k jaké změně v dokumentu. Správné vyhodnocení změn v dokumentech XML lze uplatnit v několika oblastech:

Kontrola verzí Zaznamenání věcných rozdílů stromové struktury o proti formě při řádkovém porovnávání souborů. Pokud více lidí pracuje na jednou souboru, je důležité intuitivně zobrazit k jakým změnám v dokumentu dochází, tak aby se jednotlivý uživatelé mohli rozhodnou zda nevrženou změnu přijmou či nikoliv.

1.2. VYUŽITÍ

3

Databáze XML soubory se využívají jako databázové úložiště. Posílání pouze změnových dat se snižuje zátěž při spojení. Webová by tak mohla načítat pouze změnu o proti předchozí verzi uložené v dočasné paměti.

4

KAPITOLA 1. ÚVOD

Kapitola 2 Popis problému, specifikace cíle 2.1

Porovnávání souborů

Je mnoho nástrojů na porovnávání souborů. Nejznámější z nich je GNU Diff. XML soubory lze jistě porovnávat i tímto nástrojem, prostě je považujeme za text, na který lze použít algoritmy na porovnání textových řetězců. Jenže XML soubory nejsou běžné textové soubory. Jejich stromové uspořádání přináší předávaným informacím sémantiku. diff je program sloužící k porovnání dvou textových souborů a vypsání rozdílů mezi nimi. Název vychází z anglického slova difference, což znamená rozdíl. Výstup programu se obvykle ukládá do souboru a těmto souborům se říká patche nebo česky záplaty. Tyto soubory mají obvykle příponu .patch nebo .diff. Základní použití je velice prosté. Mějme dva soubory obsahující třeba 2 stejné řádky, dále jeden řádek, který bude v každém souboru jiný a dva řádky, které jsou obsaženy pouze ve druhém souboru.[5]

Obrázek 2.1: Stromová reprezentace XML

XML používá stromovou strukturu, jak naznačuje obrázek 2.1 , takže nelze použít prosté porovnání po řádcích. Takové by mohlo porušit stromovou strukturu a nemusel by být vůbec zřejmé k jaké změně v dokumentu došlo. Příklad k čemu může vést slučování bez ohledu na

5

6

KAPITOLA 2. POPIS PROBLÉMU, SPECIFIKACE CÍLE původní text

změna a

změna b

sloučení

Příklad textu v dokumentu

Příklad textu v dokumentu

Příklad textu v dokumentu

Příklad textu v dokumentu

Tabulka 2.1: Nedostatek řádkového srovnávání stromovou strukturu poskytuje 2.1. Slučování po řádcích by zneplatnilo dokument promícháním otevíracích a uzavíracích značek b a i. Dokument XML si můžeme představit jako uspořádaný strom, ve kterém každý uzel má neurčený počet potomků a uzly představují jednotlivé značky. Problém s dokumenty XML tak lze převést na obecnější problém uspořádaných stromů. Tento problém je podobný problému porovnání řetězců. Vzdálenost mezi dvěma řetězci se určuje jako počet operací nutných ke změně jednoho řetězce na druhý.

2.2

Nejdelší společná podposloupnost

Běžné textové algoritmy řešení porovnávání souborů jako problém nejdelší společné podposloupnosti (longest common subsequence) si lze představit jako porovnání dvou řetězců ∑︀ ∑︀ značí vstupní abecedu obsahující 𝑋[1..𝑚] a 𝑌 [1..𝑚], které jsou prvky množiny * ; kde 𝜎 symbolů. Podposloupnost (s) 𝑆[1..𝑠] získáme z 𝑋[1..𝑚] tím, že odstraníme m-s symbolů kdekoliv v řetězci. Společná podposloupnost (cs) řetězců 𝑋[1..𝑚] a 𝑌 [1..𝑚], značená jako 𝑐𝑠(𝑋, 𝑌 ), je taková podposloupnost, která se vyskytuje v obou řetězcích. Nejdelší společná podposloupnost (lcs) je potom společná podposloupnost největší délky a značí se jako 𝑙𝑐𝑠(𝑋, 𝑌 ).[4]

2.3

Porovnání řetězců

Nechť u a v jsou dva řetězce nad abecedou, A. jednotlivé znaky v řetězci můžeme reprezentovat jako pole např. u[i]. S množinou primitivních operací můžeme přeměnit řetězec u na řetězec v. Základními primitivní operace mohou být ku příkladu:

2.4. ALGORITMUS WANGER-FISHER

7

∙ Vložení; Vložení nového symbolu do řetězce u na pozici i. ∙ Odstranění; Odstranění znaku na pozici i z řetězce u. Tyto operace jsou považovány za souběžné, všechny pozice jsou vztaženy k původním řetězců před jakoukoliv změnou. Nejmenší počet operací které vyžaduje přeměnit u na v je znám jako nejkratší editační vzdálenost d. Obecně je takto označuje Levenshteinova vzdálenost (Levenshtein distance, editační vzdálenost) je vzdálenost dvou řetězců definovaná jako minimální počet operací vkládání, mazání a substituce takových, aby po jejich provedení byly zadané řetězce totožné. Levenshteinovu vzdálenost zavedl v roce 1965 Vladimir Levenshtein. Alternativně se nazývá „změnová vzdálenost“ nebo také „editační vzdálenost“ (edit distance). [8] Pokud bychom nehledali nejkratší vzdálenost mohli bychom pomocí základních operací odebrat všechny znaky z u a vložit všechny znaky do v, pak by vzdálenost d byla |u| + |v|, kde |u| a |v| jsou délky znaků v řetězcích u respektive ve v [7].

2.4

Algoritmus Wanger-Fisher

Tato úloha se rozpadá vlastně na dvě pod úlohy, zjištění nejkratší vzdálenosti a vytvoření seznamu operací. Algoritmus Wagner-Fischer používá 3 primitivní operace: ∙ přepsání jednoho znaku na jiný ∙ vložení znaku ∙ odstranění znaku Každá operace je ohodnocena nákladovou funkcí 𝛾 která přiřazuje každé přeměně dvojice a->b nezáporné číslo, vyjadřující složitost přeměny. Pokud máme porovnat dva řetězce 𝑆1 a 𝑆2 , s příslušnými délkami n a m, pak algoritmus vytvoří matici (𝑛 + 1) × (𝑚 + 1) kde každý prvek D[i;j] odpovídá vzdálenosti mezi prvními i znaky z 𝑆1 a prvními j znaky z 𝑆2 . Níže je uveden algoritmus v pseudokódu. Procházejí se oba řetězce a zkouší se, která z primitivních operací povede k nejmenší změně vzdálenosti. Po průchodu touto sekcí, pak prvek D[n,m] je nejmenší vzdálenost mezi oběma úplnými řetězci. Zjištění posloupnosti vhodných operací pak stačí projít matici "cestou nejmenšího odporu"po nejmenších změnách v rostoucích směrech matice.

2.5

Porovnávání stromů

Uspořádaný strom se běžně používá jako topologická struktura biologických dat a následně k určení podobností mezi těmito daty. Během posledních 30 let se vyvinulo několik algoritmů na porovnání uspořádaných stromů. Tyto algoritmy vychází z editační vzdálenosti, což je běžný přístup pro porovnání řetězců. [2]

8

KAPITOLA 2. POPIS PROBLÉMU, SPECIFIKACE CÍLE D[][] = int[n+1][m+1]; D[0][0] = 0; for (int i=1..n) D[i][0] = D[i-1][0] + 1; for (int j..m) d[0][j] = d[0][j-1] + 1; for (int i=1..n) for (int j..m){ d[i][j] = min(d[i-1][j-1] + gama(i,j), d[i-1][j] + 1, d[i][j-1] + 1 ); } Obrázek 2.2: Pseudokód algoritmu Wanger-Fisher

Dokument XML si můžeme představit jako uspořádaný strom, ve kterém každý uzel má neurčený počet potomků a uzly představují jednotlivé značky. Problém s dokumenty XML tak lze převést na obecnější problém uspořádaných stromů. Algoritmy pro řešení porovnání stromů vycházejí z algoritmů pro řetězce řetězce, jsou si v základech podobné. Strom schématu XML se vhodným způsobem uspořádá a postup pak již je podobný jako v případě řetězců. Algoritmy pro porovnání stromů je však třeba náležitě upravit, neboť struktura XML obvykle obsahuje podstatná data v listech stromu (textové uzly) zatímco vnitřní uzly dávají informace o schématu.

2.5.1

Selkow

Algoritmus navržený Selkowem vychází z porovnávání řetězců. Využívá definované primitivní operace, ale odstranění a vložení lze provést pouze na listech. Odebrat lze pouze uzel, který nemá žádné potomky, obdobně vložit lze pouze uzly bez potomků. Odebrání celého podstromu tedy vyžaduje sadu operací pro odebrání všech uzlů ve stromě. Výhodou je jednoduchost algoritmy a nižší časová náročnost, ta je 𝑂(𝑛𝑚𝑑). Algoritmus prochází strom rekurzivně. V pomocném poli pro všechny podstromy počítají vzdálenosti jednotlivých potomků vůči podstromům z cílového uzlu. O proti textovým algoritmů zde již nelze zpětně z výsledku vzdálenosti určit potřebné operace, neboť máme na výběr víc možností. Seznam operací je tedy třeba vytvářet průběžně.

2.5.2

Tai

I tento algoritmus vychází z porovnání řetězců, na rozdíl od algoritmu Selkow se v tomto případě nepoužívá rekurze, ale pomocné datové struktury pro dílčí výpočty při procházení

2.5. POROVNÁVÁNÍ STROMŮ

9

uzly. Algoritmus Tai používá seřazený uzlů stromu v pořadí preorder (kořen, levý podstrom, pravý podstrom). Kořen bude tam mít vždy pořadí 1. Pokud máme dva stromy 𝑇1 a 𝑇2 , a 𝐷(𝑇1 [𝑖], 𝑇2 [𝑗]) pak označuje vzdálenost mezi stromy 𝑇1 [1] − 𝑇1 [𝑖] a 𝑇2 [1] − 𝑇1 [𝑗]. Soubor změn nutných ke změně jednoho stromu v jiný se tady označuje jako mapování. Na rozdíl od porovnává řetězců je v tomto případě potřeba udržovat si strukturu. Neboť vztahy všech uzlů v řadě nelze míchat, mohou mít různého rodiče. Za tímto účelem je třeba o proti původnímu provést některé dodatečné kroky, které udrží příslušnou strukturu.

2.5.3

Zhang-Shasha

Algoritmus Zhang-Shasha provádí výpočty minimálního mapování potomků předem než se jsou potřeba a to díky dvěma jevů - klíčovým uzlům a průchodu postorder Klíčové uzly jsou definovány jako kořen a dále všechny uzly, které mají levého sourozence. Průchod postorder zaručuje, že se porovnávají nejprve nejnižší patra stromu. Tato definici klíčových uzlů umožňuje oddělit vzdálenosti stromů a vzdálenosti lesů. Vzdálenost lesů je vzdálenost dvou uzlů s přihlédnutím na jejich potomky a levé sourozence. Pokud bychom brali v úvahu pouze uzel a jeho potomky, pak se jedná o vzdálenost stromů.

Obrázek 2.3: Srovnání vzdáleností stromů a lesů [3]

Pokud chceme získat vzdálenost dvou stromů pak pro její zjištění je třeba uvažovat pouze vzdálenosti potomků. V tomto algoritmu to znamená zjistit nejkratší vzdálenosti u dětí. Algoritmus používá dočasné pole vzdáleností lesů pro každou dvojici klíčových uzlů. V příkladu na obrázku 2.3 vidíme, že vzdálenost lesů mezi uzlem b v T a uzlem b v T’ je šest (3 potomci, sourozenec a jeho dva potomci), zatímco vzdálenost stromů je pouze tři (3 potomci). Avšak v případě srovnání uzlů a a q jsou obě vzdálenosti stejné, jsou 3, protože ani jeden z nich nemá levého sourozence.

10

KAPITOLA 2. POPIS PROBLÉMU, SPECIFIKACE CÍLE

2.6 2.6.1

Stávající řešení diffxml

Diffxml je projekt v jazyce JAVA. Projekt si klade za cíl poskytnout open-source programy typu /uvdiff a /uvpatch, které operují s hierarchickou strukturou dokumentů XML. Využívá algoritmy FMES a xmdiff. Jeho výstupem Delta Update Language.

2.6.1.1

FMES

FMES (Fast Match Edit Script Algorithm) vznikl jako alternativa k rozšířenému algoritmu Zhang-Shasha (EZS). Tento algoritmus používá následující primitivní operace: ∙ Vložit list ∙ Odstranit list ∙ Změnit hodnotu uzlu ∙ Přesunout podstrom jinému rodiči Algoritmus se spoléhá na existenci nejvýše jednoho podobného uzlu v obou dokumentech. Jinak není zaručeno, že nalezne minimální vzdálenost. FMES se považuje za kompromis mezi rychlostí a minimální vzdáleností produkovanou algoritmem EZS.[1]

2.6.1.2

xmdiff

Algoritmus xmdiff se orientuje na zpracování velmi velkých souborů pomocí algoritmu externí paměti.[1]

2.6.2

XmlDiff

XmlDiff implementuje algoritmy FMES a EZS, je psán v Pythonu. Používá textový výstup a jazyk XMLUpdate.

2.6.3

DeltaXML

DeltaXML je proprietární software od Monsel EDM. Místo algoritmů pro porovnání stromů využívá nejmenší společnou sekvenci. Výstupem je delta formát nebo původní dokument s označenými změnami.

2.7. CÍLE

2.7

11

Cíle

Cílem je prozkoumat možnosti, jak lze využít některý z algoritmů určených k porovnávání stromů na soubory stromové struktury dokumentů XML. Vybereme vhodný algoritmus a na jeho základě vytvoříme program, který ho bude využívat a budeme moci zhodnotit, zda je využití takových algoritmů vhodné a efektivní. Vznikne tedy knihovna, která bude porovnávat dva XML soubory. Umožní je aplikovat změny, zobrazit změny. Zpracování tedy proběhne tak, že vložením dvou souborů vznikne výstup, který bude specifikovat jak se oba soubory vzájemně liší. Takto vzniklý výstup půjde dále zpracovat. Pokud tedy bude mít protistrana stejný původní soubor a zmíněný rozdílový výstup, pak jeho aplikováním vznikne soubor, který bude obsahovat všechny uplatněné změny a nebude se významově lišit od souboru, který změny vyvolal. Program se bude skládat ze dvou části, kterou mohou být samostatné nebo spojené. 1. Program na porovnání a vytvoření rozdílového souboru. Předobrazem je program diff z porovnávání textových souborů. Výstup bude definovaný formát určený pro další zpracování. 2. Program na uplatnění použití rozdílového souboru. Zde je předobrazem program patch. Program bude mít na vstupu jeden obsahový soubor a jeden rozdílový soubor definovaného formátu. Výstupem bude změněný obsahový soubor.

2.8

Požadavky

V této části bodově shrneme požadavky na program. ∙ Vytvořený nástroj bude schopen přečíst 2 platné dokumenty XML. A výstupem bude seznam rozdílů, ze kterého bude možné zrekonstruovat změny a vytvořit z jedno souboru ten druhý. Toto je hlavní požadavek. ∙ Program bude využívat stromovou strukturu souborů XML a nikoliv porovnání po řádcích. Popis rozdílů bude obsahovat příslšný popis významu změn. ∙ Program bude chopen použít rozdílový soubor vytvořený v předchozím kroku a aplikovat ho na soubor XML.

12

KAPITOLA 2. POPIS PROBLÉMU, SPECIFIKACE CÍLE

for (x : tree1.keyroots ) { int lx = tree1(x).leftmost; for (y : tree2.keyroots) { int ly = tree2(y).leftmost(); fd[0][0][0][0] = 0; for (int i = lx...x) { fd[lx][i][0][0] = fd[lx][i-1][0][0] + gamma(tree1(i).name, ""); } for (int j = ly...y) { fd[0][0][ly + 1][j + 1] = fd[0][0][ly][j-1] + gamma("", tree2(j).name); } for (int i = lx...x) { for (int j = ly...y) { int part = min(fd[lx][i-1][ly][j] + gamma(tree1(i)name, ""), fd[lx][i][ly][j-1] + gamma("", tree2(j).name)); if (tree1(i).leftmost == lx && tree2(j).leftmost == ly) { fd[lx][i][ly][j] = min(part, fd[lx][i-1][ly][j-1] + gamma(tree1(i).name(), tree2(j)name())); d[i][j] = fd[lx][i][ly][j]; } else { fd[lx][i][ly][j] = min(part, fd[lx][tree1(i).leftmost-1][ly][tree2.(j).leftmost-1] + d[i][j]); } } } } } Obrázek 2.4: Pseudokód algoritmu Z-S

Kapitola 3 Analýza a návrh řešení Z nastíněných řešení v předchozí kapitole se nejvhodnější jevil algoritmus Zhang-Shasha. Pro použití se strukturu XML bude výhodnější použít jeho upravenou variantu. Úpravu algoritmu navrhli David T. Barnardy, Gwen Clarke, Nicholas Duncan. [3] Původní algoritmus Zhang-Shang se rozšiřuje změnou základních operací. Aby se uzly nemuseli odstraňovat po jednom, nabízí se vytvoření operace, která odstraňuje celý podstrom, tedy uzel a všechny jeho potomky. Místo obyčejného odstraňování a vkládání uzlů, lze takto operovat přímo se celými podstromy. Nadefinujeme tak nové operace. Dále lze celé podstromy vyměnit. I k tomu můžeme založit novou operaci. Možné operace tedy budou: insertTree, deleteTree, swapTree a updateNode.

Obrázek 3.1: Příklad změny stromu [3]

Algoritmus používá dočasné dvourozměrné pole fd[][], pro určení vzdáleností jednotlivých podstromů. Pokud se podíváme na příklad porovnání na obrázku 3.1, máme dva stromy T a T’. Čísla u uzlů určují pořadí postorder. Množina klíčových uzlů pro strom T je: {𝑒, 𝑓, 𝑐, 𝑎} a pro strom T’ je: {𝑒, 𝑎}. V prvním kroku algoritmu se porovnávají stromy e z T a strom e z T’. Jelikož jsou oba uzly stejné, přeměna jednoho v druhý bude mít cenu 0 operací. V dalším kroku ze zjišťuje vzdálenost mezi e z T a stromem a z T’. V tomto případě se ještě srovnává také vzdálenost e z T a stromem b z T’, které je rovna 1, neboť ani jeden uzel nemá potomky a stačí změnit jméno uzlu. V případě změny na uzel a z T’ je počet operací 2, neboť by bylo třeba vložit uzly a,b. Dále následují opět dva obdobné kroky, tentokrát se uzel f z T porovná s oběma klíčovými uzly e,a z T’. Tady bude počet operací větší neboť nelze využít stejný uzel e jako v předchozích krocích.

13

14

KAPITOLA 3. ANALÝZA A NÁVRH ŘEŠENÍ

b c d e f a

b 0 1 1 1 2 2

c 1 1 0 1 2 2

a 2 3 2 3 3 2

Tabulka 3.1: Pole vzdáleností Další z množiny klíčových uzlů v T je uzel c. Uzel d se také porovnává neboť je na cestě od nejlevější potomka c. Celkově bude změna v tomto kroku obnášet tři operace: b na d, c na a a smazání f. Stav pole vzdáleností ukazuje tabulka 3.1 Abychom mohli po vytvoření matice zpětně zrekonstruovat jaké operace jsou potřeba, je třeba seznam vybraných operací udržovat ve vhodné struktuře. Algoritmus při běhu vybere ten nejmenší rozdíl a tedy vhodně zvolí potřebnou operaci, kterou následně přidá do struktury. Struktura bude obsahovat: hodnocení, seznam operací.

3.1

Ohodnocení operací

Důležitým aspektem algoritmu je vhodné ohodnocení jednotlivých operací. Hlavně u nově přidaných operací, které se netýkají listů stromu je třeba náležitě zvážit jejich skutečnou náročnost. Operace odstranění podstromu nebude nijak zvláště náročná, neboť stačí odstranit záznam v seznamu potomků rodiče. Naopak v případě vložení podstromu je třeba zohlednit jeho velikost, takže cena této operace bude závislá na počtu uzlů podstromu.

3.2

Výstupní formát

Z rešerše stávajících řešení nevyplynul jednoznačný kandidát pro universální výstup. Pro to výstupem porovnání souborů bude rozdílový soubor XML o vlastním formátu. Jako uzly je několik voleb, které určují definovanou operaci. Pro identifikaci uzlu se použije jazyk XPath. Zde je bližší popis:

3.2.1

Stromové značky

V případě značek append, insert, before je ve vnitřních uzlech očekáván samotný strom, který se má vložit. Značka swap očekává specifikaci druhého uzlu pro výměnu. <XModify:insert select="xpath">

3.2. VÝSTUPNÍ FORMÁT

15

Vložení stromu jako potomka vybraného uzlu. Parametry: xpath - jednoznačná identifikace uzlu tree - XML struktura, která je určena k vložení <XModify:append select="xpath"> Vložení XML struktury bezprostředně za zadaný uzel jako jeho sourozence. Parametry: xpath - jednoznačná identifikace uzlu tree - XML struktura, která je určena k vložení <XModify:before select="xpath"> Vložení XML struktury bezprostředně před zadaný uzel jako jeho sourozence. Parametry: xpath - jednoznačná identifikace uzlu tree - XML struktura, která je určena k vložení <XModify:delete select="xpath"/> Odstranění uzlu na pozici „xpath“ včetně všech jeho potomků. Parametry: xpath - jednoznačná identifikace uzlu <XModify:swap select="xpath1"> <XModify:node select="xpath2" /> Operace výměny dvou uzlů. Parametry: xpath1 - identifikace prvního uzlu xpath2 - identifikace druhého uzlu

3.2.2

Uzlové značky

<XModify:update select="xpath"> Kořenový uzel pro změnu samotného uzlu. Obsahuje další identifikaci změny. Parametry: xpath - identifikace uzlu <XModify:name>name<XModify:name> Patří do kontextu XModify:update. Změna se týká samotného nazvu uzlu. name - nový název

16

KAPITOLA 3. ANALÝZA A NÁVRH ŘEŠENÍ

<XModify:attribute-update qName="qName">value<XModify:attribute-update> Změna hodnoty zadaného atributu Parametry: qName - jméno atributu value - nová hodnota <XModify:attribute-insert qName="qName">value<XModify:attribute-insert> Vložení nového atributu Parametry: qName - jméno atributu value - hodnota <XModify:attribute-delete qName="qName" /> Odstranění atributu Parametry: qName - jméno atributu k odstranění

3.2. VÝSTUPNÍ FORMÁT

17

for (x : tree1.keyroots ) { int lx = tree1(x).leftmost; for (y : tree2.keyroots) { int ly = tree2(y).leftmost(); fd[lx-1][ly-1] = 0; for (int i = lx...x) { fd[i][ly-1] = fd[tree1(u).leftmost()-1][ly-1] + deleteTree(tree1(i)); } for (int j = ly...y) { fd[lx-1][j] = fd[lx-1][tree2(k).leftmost()-1] + insertTree(tree2(j)); } for (int i = lx...x) { for (int j = ly...y) { int part = min(fd[i-1][j] + gamma(tree1(i), ""), fd[i][j-1] + gamma("", tree2(j)), fd[tree1(i).leftmost()-1][j] + deleteTree(tree1(i) ), fd[i][tree2(j).leftmost()-1] + deleteTree(tree2(j) ) ); if (tree1(i).leftmost == lx && tree2(j).leftmost == ly) { fd[i][j] = min(part, fd[i-1][j-1] + gamma(tree1(i),tree2(j))); d[i][j] = fd[i][j]; } else if (tree1(i).isKeyroot && tree2(j).isKeyroot ) { fd[i][j] = min(part, fd[tree1(i).leftmost-1][tree2.(j).leftmost-1] + d[i][j], fd[tree1(tree1(i).leftmost-1).leftmost-1] [tree2.(tree2.(j).leftmost-1).leftmost-1] + swap(i,j)); } else { fd[i][j] = min(part, fd[tree1(i).leftmost-1][tree2.(j).leftmost-1] + d[i][j]); } } } } } Obrázek 3.2: Pseudokód rozšířeného algoritmu ZS

18

KAPITOLA 3. ANALÝZA A NÁVRH ŘEŠENÍ

Kapitola 4 Implementace Pro vytvoření programu bylo použito standardní API Java SE. Žádné externí knihovny nebyly použity.

4.1

Třída XMLSAX

Jelikož tento program načítá XML soubory, implementuje třída XMLSAX načtení takových souborů. Ke zpracování souborů se použilo rozhraní SAX (Simple API for XML), které je součástí standardních knihoven Java SE. Nachází se v balíku org.xml.sax. Z balíku org.xml.sax.helpers je použita třída DefaultHandler,která implementuje rozhraní EntityResolver, DTDHandler, ContentHandler (o toto rozhraní jde, získává oznámení o logickém obsahu dokumentu) a ErrorHandler - Výchozí implementace metod je většinou prázdná. Pro vývoj aplikace je tedy třeba odvodit podtřídu a definovat potřebné události. Z balíku javax.xml.parsers jsou použity třídy SAXParser a SAXParserFactory. SAXParser implementuje aplikační rozhraní XMLReader (rozhraní pro čtení XML dokumentů použitím zpětného dotazu) do třídy. SAXParserFactory je pomocná třída, která vytvoří a předá instanci parseru určeného pro k rozbor XML dokumentů. Vytvořenému parseru se předá instance odvozená ze třídy ContentHandler. Parser rozhraní SAX prochází XML dokument od začátku do konce a vytváří události. Pokud narazí na značku, zavolá příslušnou metodu metoda ze ContentHandler, která tuto událost zachytí. Vhodnou implementací takových metod lze během čtení XML dokumentu dál manipulovat se získaným textem. Začátek dokumentu označuje metoda startDocument() a konec metoda endDokument(). Každá značka na kterou parser při průchodu narazí spustí volání metody startElement( String namespace, String localName, String qName, Attributes atts). Získá se tak jméno uzlu a atributy značky. Ve vyvolané metody se vytvoří uzel a zařadí do stromu. V tuto chvíli ovšem nejsou známy případné vnořené značky, je třeba si uzel zapamatovat pro další volání. Uzavírací značka spustí metodu endElement(String uri, String localName, String qName). Textový obsah souboru vyvolává metodu characters(char buf[],int offset,int len). Jelikož pro potřeby algoritmu je vhodnější, aby byl text rozdělen na menší uzly, jsou i slova, které přijdou jako parametr této metody rozdělena na sadu uzlů.

19

20

KAPITOLA 4. IMPLEMENTACE

K vytvoření instance analyzátoru SAX je nutné získat odkaz na instanci typu SAXParserFactory. Tento objekt se pak dá použít k tvorbě instance typu SAXParser: SAXParserFactory factory = SAXParserFactory.newInstance(); SAXParser saxParser = factory.newSAXParser();

4.2

Rozhraní Node

Obecné rozhraní Node pro reprezentaci uzlů se struktury dokumentu. Zahrnuje základní definici metod, které by měl splňovat obecný uzel. Vychází se z předpokladu, že stromy, které vstupují do nemusí být reprezentovány jako dokumenty XML, ale mohou mít i jiný formát, kupř. textová reprezentace.

4.3

Třída NodeXMLImpl

Třída implementuje rozhraní Node. Tato konkrétní třída obsahuje metody pro manipulaci se stromem z dokumenty XML. Objekty třídy NodeXMLImpl odpovídají uzlům dokumentu. Objekty jsou uspořádány stromově stejně jako dokument. Objekt obsahuje mimo jiné identifikaci uzlu, seznam atributů, seznam jeho bezprostředních potomků, odkaz na rodiče. Třída mimo jiné obsahuje metody pro výpis rozdílů vůči zadaným uzlům.

4.4

Třída ZHEDiffMatrix

V této třídě samotné je implementace vybraného algoritmu. V maticích algoritmu jsou udržovány instance třídy Cost, nad kterými se volá příslušná zvolená operace. Tato je důležité pro následné vytvoření seznamu operací.

4.4.1

CountMinimalValue

CountMinimalValue je pomocná třída, která slouží pro výběr nejmenší hodnoty z instancí třídy Cost. Výběr je realizované průchodem seznamu.

4.5

Třída Cost

Třída Cost slouží při průběhu rozdílového algoritmu k pro udržení informací o dosavadní nejmenší vzdálenosti a dále nese seznam minimálních operací. Právě instance této třídy jsou udržovány v maticích algoritmu. Každá nově provedená vybrané operace volá příslušnou metodu této třídy. Volající objekt vytvoří novou instanci, která obsahuje nový seznam operací i nově přidanou.

4.6. TŘÍDA DIFFOPERATION

4.6

21

Třída DiffOperation

Každý objekt této třídy nese informaci o změně. Obsahuje identifikaci druhu změny a dále 1 nebo dva uzly, kterých se změna týká. Třída dále obsahuje metody pro výpis rozdílu do výstupního formátu. Využívá se tříd za balíku org.w3c.dom.Element. Na základně předeného elemetu se vytvoří nový uzel výstupního formátu s rozlišením operace. Tento uzel se naplní identifikací stromu, který se má odstranit: el = root.getOwnerDocument().createElement("XModify:delete"); xpath = node1.toString(); root.appendChild(el); el.setAttribute("select", xpath);

4.7

Třída Attribute

Třída Attribute udržuje informace atributu jednotlivých uzlů XML. Umožňuje srovnávat atributy se stejnými názvy.

22

KAPITOLA 4. IMPLEMENTACE

Kapitola 5 Testování Testování se zaměřilo na správnost vytvořeného rozdílového souboru. Byl vybrán vzorový soubor a na něm uplatněno několik možných změn.

5.1 5.1.1

Kontrola správnosti výstupu Výchozí soubor

Výchozím souborem je část přehledu obcí. Soubor je tařka typickým XML dokumentem. Obsahuje několik vnořených elementů s atributy.

5.1.2

Změna 1

Na výchozím souboru provedeme změnu, která má za cíl otestovat operaci výměny dvou uzlů. Zaměníme tedy pořadí oblastí „Aš“ a „Benešov“

23

24

KAPITOLA 5. TESTOVÁNÍ

Rozdílový výstup skutečně správně popisu vzájemnou výměnu dvou uzlů, konkrétně druhý a třetí uzel „oblast“. <XModify filename="obce.xml"> <XModify:swap select="/adresy[0]/oblast[2]"> <XModify:Node select="/adresy[0]/oblast[1]"/>

5.1.3

Změna 2

Pro další test použijeme opět stejný výchozí soubor, tentokrát provedeme několik změn, které se vzájemně neovlivňují: Výsledkem je sada operací: 1. Odstranění uzlu (!nikoliv celého podstromu) „oblast Praha“ a přesun jeho potomků výše

5.2. RYCHLOST

25

2. Odstranění uzlu „obec Aš“ 3. Úprava hodnoty atributu „zeny“ u „obec Bukovany“ na číslo 55 Popsané operace odpovídají provedeným změnám. <XModify filename="obce.xml"> <XModify:remove select="/adresy[0]/oblast[0]"/> <XModify:delete select="/adresy[0]/oblast[1]/obec[0]"/> <XModify:update select="/adresy[0]/oblast[2]/obec[1]"> <XModify:attribute-update qName="zeny">55 I program určený pro aplikaci rozdílových souborů uvedené rozdíly správně zpracoval. Došlo pouze k přeházení jednotlivých atributů, takže byť věcně nebyl žádný rozdíl, přesto se výsledný soubor od referenční lišil.

5.2

Rychlost

Použitý algoritmus rozšířený Zhang-Shasha má udávanou časovou složitost 𝑂(𝑛2 𝑚2 𝑑𝑑′ ). Kde n a m jsou počty uzlů a d a d’ hloubky stromů. Jelikož i paměťové nároky si vyžádali poměrně velkou režii a vytváření velkého počtu různých ohodnocení, které si nesou dále celý seznam operací. Ukázalo se, že zvolený algoritmus není v tomto směru příliš efektivní. Lze je uplatnit jen na poměrně malé soubory do desítek kilobytů. Ač je algoritmu udáván jako ideální ve smyslu nalezení minimální editační vzdálenosti, tak v tomto ohledu selhává.

26

KAPITOLA 5. TESTOVÁNÍ

Kapitola 6 Závěr Zadáním této práce bylo využít algoritmů porovnávání uspořádaných stromů na porovnávání souborů XML. Základní vytyčené body byly splněny: ∙ Program implementuje vybraný algoritmus. ∙ Program vytváří rozdílové soubory dvou XML dokumentů. ∙ Program je schopen využít původní soubor,vytvořený rozdílový soubor a sloučit je do jednoho souboru, který odpovídá změněnému dokumentu. Problematickým se však ukázala paměťová a časová náročnost. Zvolené řešení je vhodné pro porovnání poměrně malých souborů. Existují i jiné algoritmy, které nevychází tak striktně z porovnávání uspořádaných stromů. Nezaručují nalezení minimální vzdálenosti, ale přináší kompromisní alternativu s nižší výpočetní náročností.

6.1

Náměty pro budoucí práci

Pro budoucí vylepšení programu je možné navrhnout následující: ∙ Rozšířit program o implementaci jiného typu algoritmu, který bude rychlejší, a bude umožňovat srovnávat větší soubory. ∙ Umožnit přepínání mezi algoritmy, tak aby se i pro menší soubory, kde to bude vhodné použil stávající. ∙ Rozšířit možnosti výstupu o formáty jiných podobných programů.

27

28

KAPITOLA 6. ZÁVĚR

Literatura [1] Adrian Mouat. XML Diff And Patch Utilities, 2002. [2] Aïda Ouangraoua, Pascal Ferraro. A New Constrained Edit Distance Between Quotiented Ordered Trees, 2008. [3] BARNARD, D. T. – CLARKE, G. – DUNCAN, N. Tree-to-tree Correction for Document Trees. Technical Report 95-372, Department of Computing and Information Science, Queen’s University, 1995. [4] BERGROTH, L. – HAKONEN, H. – RAITA, T. A Survey of Longest Common Subsequence Algorithms. In Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE’00), s. 39–, Washington, DC, USA, 2000. IEEE Computer Society. Dostupné z: . ISBN 0-7695-0746-8. [5] David Watzke. Unixové nástroje – 8 (diff a patch) [online]. 2010. [cit. 20. 4. 2011]. Dostupné z: . [6] Jiří Kosek ml. XML [online]. 2011. [cit. 10. 04. 2011]. Dostupné z: . [7] Julian. Comparing Strings: An Analysis of Diff Algorithms [online]. 2011. [cit. 10. 04. 2011]. Dostupné z: . [8] Pavel Mička. Algoritmy.net - Levenshteinova vzdálenost [online]. 2011. [cit. 10. 04. 2011]. Dostupné z: .

29

30

LITERATURA

Příloha A Seznam použitých zkratek API Application Programming Interface HTML HyperText Markup Language XML Extensible Markup Language

31

32

PŘÍLOHA A. SEZNAM POUŽITÝCH ZKRATEK

Příloha B Uživatelská příručka Program se ovládá z příkazové řádky. Pro vytvoření rozdílového souboru se využije takovýto příkaz: xmodify.bat diff soubor1 soubor2 [výstup] kde soubor1 a soubor2 jsou cesty ke xml souborům, které se mají porovnat. A výstup jméno souboru, do kterého se má zapsat rozdíl; tento parametr je nepovinný, program případně použije výchozí jméno. Použití pro aplikaci rozdílového souboru jsou obdobné: xmodify.bat modify soubor1 soubor2 [výstup] kde soubor1 je původní soubor, soubor2 je rozdílový soubor a výstup jméno souboru, do kterého se má zapsat sloučený soubor; tento parametr je nepovinný, program případně použije výchozí jméno.

33

34

PŘÍLOHA B. UŽIVATELSKÁ PŘÍRUČKA

Příloha C Obsah přiloženého CD CD README.TXT ... popis CD data build ... adresář s programem src ... adresář zdrojového projektu text pdf ... adresář s textem práce v PDF latex ... adresář se zdrojovými soubory textu práce v LaTexu Obrázek C.1: Seznam přiloženého CD — příklad

35