Komprese a dotazování nad XML dokumenty Prezentace diplomové práce
Lukáš Skˇrivánek ˇ Ceské vysoké uˇcení technické v Praze Fakulta elektrotechnická Katedra poˇcítaˇcu˚
ˇ kveten 2007
Vedoucí práce: Ing. Miroslav Balík, Ph.D.
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
1 / 18
Osnova 1
Výhody a nevýhody XML
2
Postup komprese a dotazování
3
Existující implementace komprese XML souboru˚
4
Návrh XML komprese
5
Popis implementace
6
Testování
7
ˇ Záver
8
Demonstraˇcní aplikace
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
2 / 18
Výhody a nevýhody XML Výhody obecný formát pro libovolná data, jednoduchost, rozšiˇritelnost, veˇrejná specifikace, mezinárodní podpora, ˇ snadná cˇ itelnost pro cˇ loveka, jednoduchá editace v libovolném textovém editoru, podpora v dalších technologiích a programovacích jazycích, ˇ podpora od rˇady svetových producentu˚ software i v aplikacích, ˇreší problém univerzální výmeny ˇ dat mezi ruznými ˚ systémy.
Nevýhody ˇ pamet’ové nároky (redundantní formát), efektivnost naˇcítání a práce s daty. ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
3 / 18
Postup komprese a dotazování
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
4 / 18
Existující implementace komprese XML souboru˚
Kompresní programy nepodporující dotazování XMill XMLPPM
Kompresní programy podporující dotazování XMLZip XGrind XPress XQueC (XQuery processor and Compressor)
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
5 / 18
XML Compression (XCo) algoritmus komprese XML dokumentu: ˇ oddelení struktury od dat, komprese elementu˚ a atributu˚ slovníkovou metodou, komprese hodnot semi-adaptivním Huffmanovým kódováním, zvlášt’ kompresní model Huffmanova kódování pro každý název elementu nebo atributu, kódování ukazatelu˚ do slovníku Fibonacciho kódováním.
pˇrípona souboru (*.xco).
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
6 / 18
XML Compression DOM (XCoDOM) implementace standardního rozhraní DOM, naˇcítán pˇrímo z XCo souboru (komprimovaného XML souboru), dekomprimuje všechny Fibonacciho kódy (ukazatele do slovníku), nedekomprimuje Huffmanovy kódy.
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
7 / 18
Popis implementace
název XML Compression (XCo), implementováno jako knihovna funkcí (API), ˇ implementace rozdelena do balíku: ˚ compression – poskytuje metody pro kompresi XML, decompression – poskytuje metody pro dekompresi XCo ˇ do XML dokumentu, souboru zpet xcoDOM – implementace standardní sady rozhraní org.w3c.dom.
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
8 / 18
XML soubory použité pˇri testování
Název souboru autobazar.xml student.xml shakespeare.xml wsu.xml docbook.xml nasa.xml
Velikost 380 B 32,7 kB 245 kB 1,57 MB 2,90 MB 23,8 MB
Název souboru autobazar.xml student.xml shakespeare.xml wsu.xml docbook.xml nasa.xml
ˇ Lukáš Skˇrivánek (CVUT FEL)
ˇ elementu˚ Pocet 11 831 6347 74557 66757 476646 Unikátních elementu˚ 6 6 17 20 236 61
ˇ atributu˚ Pocet 2 332 0 0 41456 53882
Výška stromu 3 3 6 4 16 8
Unikátních atributu˚ 1 2 0 0 50 8
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
9 / 18
ˇ Kompresní pomer
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
10 / 18
ˇ u˚ XQueC a XCo Porovnání kompresních pomer
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
11 / 18
Velikost DOMu
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
12 / 18
ˇ Casová nároˇcnost vykonání XPath dotazu
Soubor wsu docbook docbook nasa nasa
XPath dotaz //course/days/text() //LINK/text() //ENTRY/text() /datasets/dataset/title/text() //attribute::footnoteId
ˇ Lukáš Skˇrivánek (CVUT FEL)
Java DOM 1238 ms 1347 ms 1331 ms 4024 ms 5055 ms
Komprese a dotazování nad XML dokumenty
XCo DOM 960 ms 1292 ms 1290 ms 7716 ms 8672 ms
ˇ kveten 2007
13 / 18
Porovnání vlastností kompresních programu˚ podporujících dotazování
Program XMLZip XGrind XPress
XQueC XCo
Kompresní algoritmus LZSS Huffmanovo kódování, slovníková metoda Huffmanovo kódování, slovníková metoda, reverzní aritmetické kódování Huffmanovo kódování, ALM, slovníková metoda Huffmanovo kódování, slovníková metoda, Fibonacciho kódování
ˇ Lukáš Skˇrivánek (CVUT FEL)
Podporovaný jazyk DOM – XPath podmnožina XPath
ˇ pohybu Smer ˇ všemi smery od koˇrene k list˚um
podmnožina XPath
od koˇrene k list˚um
podmnožina XQuery
ˇ všemi smery
DOM – XPath
ˇ všemi smery
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
14 / 18
ˇ Záver Výsledky: ˇ o 9 % lepší výsledky než XQueC, v prum ˚ eru ˇ o 60 % méneˇ místa než zdrojové XML soubory, v prum ˚ eru ˇ o 30 % méneˇ pameti. ˇ rozhraní DOM v prum ˚ eru
Doporuˇcení: pro obyˇcejnou kompresi XML dokumentu˚ použít zip, ˇ použít XMill, pro vysoký kompresní pomer pro kompresi s dotazováním použít XML Compression (XCo).
Budoucnost: implementovat sémantickou kompresi, implementovat dotazovací jazyk XPath využívající urychlovacích algoritmu, ˚ ˇ vytvoˇrení pomocných struktur a cache pamet’. ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
15 / 18
Demonstraˇcní aplikace XCo Aplikace urˇcená ke kompresi a dekompresi XML souboru.
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
16 / 18
Demonstraˇcní aplikace XCoViewer Aplikace urˇcená pro pˇrímé prohlížení souboru typu XCo jako puvodního ˚ XML souboru.
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
17 / 18
Demonstraˇcní aplikace XCoXPath Aplikace urˇcená pro dotazování jazykem XPath nad rozhraním DOM naˇcteným pˇrímo ze souboru typu XCo.
ˇ Lukáš Skˇrivánek (CVUT FEL)
Komprese a dotazování nad XML dokumenty
ˇ kveten 2007
18 / 18
