1 VŠB Technická univerzita Ostrava Fakulta elektrotechniky a informatiky Katedra informatiky Komprese XML souborů Compression of XML Files 2010 Pavel ...
ˇ – Technicka´ univerzita Ostrava VSB Fakulta elektrotechniky a informatiky Katedra informatiky
Komprese XML souboru˚ Compression of XML Files
2010
Pavel Hruˇska
Souhlas´ım se zveˇrejnˇen´ım t´eto diplomov´e pr´ace dle poˇzadavku˚ cˇ l. 26, odst. 9 Studijn´ıho ˇ a zkuˇsebn´ıho rˇa´ du pro studium v magistersk´ych programech VSB-TU Ostrava.
V Ostravˇe 7. kvˇetna 2010
.............................
Prohlaˇsuji, zˇ e jsem tuto diplomovou pr´aci vypracoval samostatnˇe. Uvedl jsem vˇsechny liter´arn´ı prameny a publikace, ze kterych ´ jsem cˇ erpal.
V Ostravˇe 7. kvˇetna 2010
.............................
Dˇekuji vˇsem, kteˇr´ı mi pom´ahali bˇehem pˇr´ıprav t´eto diplomov´e pr´ace, pˇredevˇs´ım vedouc´ımu pr´ace Ing.Janu Martinoviˇcovi, Ph.D. za jeho ochotu, trpˇelivost a cenn´e rady.
Abstrakt Pr´ace s XML soubory je dnes cˇ ´ım d´al t´ım v´ıce cˇ astˇejˇs´ı. Existuj´ı tak´e XML dokumenty, kter´e obsahuj´ı velk´e mnoˇzstv´ı dat. Tato diplomov´a pr´ace popisuje existuj´ıc´ı algoritmy ˚ pouˇz´ıvan´e ke kompresi XML dokumentu˚ a tak´e popisuje nˇekter´e nov´e zpusoby, jak st´avaj´ıc´ı pˇr´ıstupy vylepˇsit. Zamˇerˇ uje se na nˇekolik popul´arn´ıch kompresn´ıch algoritmu˚ a jejich pouˇzit´ı jak pˇri kompresi XML jako textu, tak i pˇri kompresi XML s vyuˇzit´ım s´emantickych ´ informac´ı dostupnych ´ v XML dokumentech. D´ale popisuje rozˇs´ırˇ en´ı tˇechto metod o optimalizaci XML pomoc´ı shlukov´an´ı. Na z´akladˇe provedenych ´ testu˚ jsou porovn´any efektivnosti jednotlivych ´ algoritmu˚ a vysloven z´avˇer, zda lze rozˇs´ırˇ en´ım st´avaj´ıc´ıch metod komprese XML dokumentu˚ dos´ahnout lepˇs´ıch vysledk u˚ komprese. ´ ˇ a´ slova: komprese, komprese textu, XML, shlukov´an´ı dokumentu, ˚ analyza Kl´ıcov ´ XML.
Abstract Working with XML files is now becoming more frequent. There are XML documents containing large amount of data. This thesis deals with existing algorithms used for XML compression and some new ways of improving current approaches. This thesis focuses on some popular text compression algorithms and their application either in standard text file compression or in XML compression through semantic information that is present in XML documents. The thesis also describes extending the methods with XML optimization through agglomerative clustering. Various compression methods are compared on the basis of testing in order to find out whether XML compression methods extension can achieve better results. Keywords: Compression, Text Compression, XML, Documents Clustering, Parsing XML.
XML [29] je v dneˇsn´ı dobˇe velmi rozˇs´ırˇ eny´ jazyk pro ukl´ad´an´ı a vymˇ ´ enu dat. Pˇres sv´e ne´ sporn´e vyhody, kter´ e pramen´ ı pˇ r edevˇ s ı m z jeho univerz´ a lnosti a tak´e z textov´e podoby ´ jeho datov´eho form´atu (dobˇre cˇ iteln´eho pro cˇ lovˇeka), m´a i nˇekter´e nevyhody. Mezi hlavn´ı ´ patˇr´ı pˇredevˇs´ım nutnost analyzy ´ XML dat pˇred jejich pouˇzit´ım. Pokud jej srovn´ame s nativn´ımi bin´arn´ımi form´aty, jedn´a se tak´e o relativnˇe vyˇ ´ reˇcny´ jazyk, ktery´ klade vˇetˇs´ı n´aroky na prostor nutny´ k uloˇzen´ı reprezentovanych ´ dat. V t´eto pr´aci struˇcnˇe charakterizujeme XML a zabyv´ ´ ame se tak´e problematikou spojenou s jeho analyzou. ´ Probl´em vyˇ ´ reˇcnosti XML lze rˇ eˇsit pomoc´ı komprese dat. Jelikoˇz se na XML d´a d´ıvat ˚ e poˇzadavky, je z v´ıce pohledu˚ a i na samotnou kompresi XML se mohou kl´ast ruzn´ ˚ moˇzn´e tak´e k problematice komprese XML pˇristupovat v´ıce zpusoby. Jelikoˇz je XML v podstatˇe textovy´ dokument, je pˇrirozen´a myˇslenka komprimovat jej bˇezˇ n´ymi kompresn´ımi n´astroji, kter´e dennˇe pouˇz´ıv´ame pro kompresi jinych ´ nejen textovych ´ dokumentu˚ a ˚ Tyto n´astroje vyuˇz´ıvaj´ı osvˇedˇcen´e kompresn´ı algoritmy, kter´e jsou d´ıky obecnˇe souboru. bohat´e historii prakticky ovˇerˇ en´e a velmi cˇ asto vyuˇz´ıvan´e jako spolehliv´e prostˇredky ke kompresi dat. Jejich pouˇzit´ı je tedy velmi snadn´e a vysledky se dostavuj´ı okamˇzitˇe. ´ V t´eto pr´aci testujeme kompresi XML souboru˚ pomoc´ı algoritmu˚ Deflate, BZip2, PPMdI a LZMA. Kompresi XML lze rˇ eˇsit i specializovanymi n´astroji, ty se nazyvaj´ ´ ´ ı XML-aware kompre˚ kter´e jsme shrom´azˇ dili studiem sory. V t´eto pr´aci uv´ad´ıme pˇrehled n´astroju˚ a algoritmu, odbornych ´ cˇ l´anku˚ a internetovych ´ zdroju˚ vˇenuj´ıc´ıch se XML kompresi. D´ale se podrobnˇeji vˇenujeme n´astroji XMill. Popisujeme zde v´ıce detailnˇeji jeho princip komprese, datovy´ form´at a dalˇs´ı informace. S t´ımto n´astrojem pak d´ale pracujeme, pˇredevˇs´ım s naˇs´ı vlastn´ı implementac´ı v prostˇred´ı .NET Framework (v jazyce C#). XMill jsme si zvolili pˇredevˇs´ım proto, zˇ e se jedn´a o velmi popul´arn´ıho z´astupce XML-aware komprese, ktery´ velmi cˇ asto slouˇz´ı jako etalon pˇri srovn´an´ı odliˇsnych ´ pˇr´ıstupu˚ komprese XML. Nav´ıc je velmi dobˇre zdokumentov´an. Po detailn´ım popisu XMill d´ale popisujeme naˇs´ı implementaci tohoto n´astroje, kterym ´ je SXMill (SharpXMill). Zamˇerˇ ujeme se pˇredevˇs´ım na z´akladn´ı architekturu navrˇzen´eho ˚ syst´emu a na jeho odliˇsnosti oproti puvodn´ ımu XMill. D´ale se vˇenujeme problematice shlukov´an´ı dat, pˇredevˇs´ım vyuˇzit´ı t´eto metody ve spojen´ı s kompres´ı XML. Konkr´etnˇe jsme shlukov´an´ı dat vyuˇzili k optimalizaci XML a experimentovali jsme, zda nepovede k dosaˇzen´ı lepˇs´ıch vysledk u˚ komprese. Vyzkouˇseli ´ jsme dvˇe moˇzn´e cesty optimalizace — shlukov´an´ı dat v kontejnerech bˇehem XMill komprese a shlukov´an´ı cel´ych XML souboru. ˚ V z´avˇeru pr´ace pak vyhodnocujeme proveden´e experimenty. Testovali jsme bˇezˇ n´e metody komprese dat i navrˇzen´e optimalizace. Veˇsker´e vysledky srovn´av´ame v kontextu ´ ˚ jednotlivych ´ metod komprese a n´astroju.
1.1
´ Struktura prace
Charakteristikou XML a jeho vyhodami a nevyhodami se zabyv´ ´ ´ ´ ame v sekci 2. V sekci ˚ zpra2.4 se vˇenujeme problematice zpracov´an´ı XML a nejˇcastˇeji pouˇz´ıvanym ´ modelum
5
cov´an´ı XML — XML DOM a SAX. Kompresi XML je vˇenov´ana sekce 3, konkr´etnˇe v sekci 3.2 popisujeme kompresi XML jako textu (vˇcetnˇe popisu jednotlivych metod kompre´ se) a v sekc´ıch 3.3, 3.4 a 3.5 se zamˇerˇ ujeme na kompresi specializovanymi (XML-aware) ´ n´astroji, kde postupnˇe rozeb´ır´ame kompresi XML s podporou dotazovan´ı a n´aslednˇe bez podpory dotazov´an´ı. Sekce 4 se podrobnˇe vˇenuje n´astroji XMill, ktery´ je typickym ´ pˇredstavitelem kategorie XML-aware komprese bez podpory dotazov´an´ı. V sekci 4.1 popisujeme jeho architekturu, v sekci 4.2 uv´ad´ıme na jednoduch´em pˇr´ıkladu j´ım pouˇz´ıvany´ princip oddˇelen´ı struktury od dat a v sekci 4.3 popisujeme datovy´ form´at tohoto n´astroje. Sekce 5 popisuje n´ami implementovany´ n´astroj SXMill (SharpXMill). Jeho architektura je pops´ana v sekci 5.1, podporovan´e kompresn´ı metody pak v sekci 5.2 a popis ˚ rozˇs´ırˇ en´ı oproti puvodn´ ımu XMill je uveden v sekci 5.3. ˚ V sekci 6.2.1 jsou Sekce 6 se vˇenuje prezentaci vysledk u˚ provedenych ´ ´ experimentu. k dispozici vysledky komprese XML souboru˚ jako textu (bˇezˇ n´a komprese), v sekci 6.2.2 ´ uv´ad´ıme vysledky komprese pomoc´ı n´astroje XMill. Sekce 6.2.3 se zabyv´ ´ ´ a ot´azkou, jak ’ ˇ ´ esˇ nost komprese pˇri pouˇzit´ı u n´astroje XMill ovlivnuje velikost pamˇet ov´eho okna jeho uspˇ jednotlivych ´ kompresn´ıch metod. Sekce 6.2.4 se vˇenuje kompresi XML pomoc´ı n´astroje XMill s optimalizac´ı kontejneru˚ vyuˇz´ıvaj´ıc´ı shlukov´an´ı. V sekci 6.2.5 ukazujeme vysledky ´ ˚ komprese XML bˇezˇ nou kompres´ı po proveden´ı shlukov´an´ı celych ´ XML souboru. V sekci 7 shrnujeme vysledky experimentu˚ a vyslovujeme z´avˇer, zda je moˇzn´e pomoc´ı ´ ˚ shlukov´an´ı vylepˇsit st´avaj´ıc´ı metody komprese XML souboru.
6
2
XML
XML (eXtensible Markup Language, cˇ esky rozˇsiˇritelny´ znaˇckovac´ı jazyk) je obecny, ´ otevrˇ eny´ znaˇckovac´ı jazyk, standardizovany´ konsorciem W3C. Vznik tohoto jazyka se datuje do roku 1998, kdy byla standardizov´ana verze 1.0. XML je zaloˇzen na obecn´em metajazyku SGML, pˇresnˇeji rˇ eˇceno tvoˇr´ı jeho podmnoˇzinu. Ve srovn´an´ı s SGML je jednoduˇssˇ´ı, snadnˇeji se analyzuje 1 [29, 32].
2.1
Charakteristika XML
ˇ XML je obecny´ jazyk, ktery´ umoˇznuje definovat vlastn´ı jazyky — pˇredstavuje sadu pravi˚ V dneˇsn´ı dobˇe se vyuˇz´ıv´a pˇredevˇs´ım del, kter´e se pouˇz´ıvaj´ı k definici konkr´etn´ıch jazyku. jako prostˇredek pro vymˇ ´ enu dat v prostˇred´ı internetu, napˇr. u rˇ eˇsen´ı B2B2 [5] apod. D´ıky ˚ u kterych sv´e univerz´alnosti mu d´avaj´ı vyvoj´ ´ arˇ i pˇrednost u syst´emu, ´ nen´ı v dobˇe n´avrhu pˇredem jasn´e, s jakymi dalˇs´ımi syst´emy bude nutn´e komunikovat. XML nach´az´ı uplat´ ´ ziˇstˇe, velmi popul´arn´ı jsou v dneˇsn´ı dobˇe tak´e na nˇen´ı tak´e jako univerz´aln´ı datov´e uloˇ XML zaloˇzen´e konfiguraˇcn´ı soubory. ˚ kde znakem se rozum´ı libovolny´ UniXML dokument je tvoˇren posloupnost´ı znaku, code znak. XML je tedy ve sv´e podstatˇe textovy´ dokument. V XML dokumentu se rozliˇsuj´ı dva z´akladn´ı elementy — znaˇcky a obsah. Znaˇcky jsou uvozeny znakem <“ (menˇs´ı) a ” konˇc´ı >“ (vˇetˇs´ı), nebo zaˇc´ınaj´ı znakem &“ (ampersand) a konˇc´ı znakem ;“ (stˇredn´ık). ” ” ” Vˇse ostatn´ı, co nen´ı znaˇcka, je obsah [29]. XML je strukturovany´ jazyk, jeho struktura se tvoˇr´ı vz´ajemnym ´ vnoˇrov´an´ım znaˇcek. ˇ Jako kaˇzdy´ jazyk, m´a i XML svou syntaxi. Kaˇzdy´ XML soubor mus´ı splnovat minim´alnˇe pravidla well-formed XML3 z´apisu. Well-formed XML nedovoluje napˇr´ıklad pouˇzit´ı pˇrekˇr´ızˇ enych ´ znaˇcek [29]. Na jazyku XML jsou postaveny nˇekter´e dalˇs´ı jazyky. Jedn´a se napˇr´ıklad o RSS [34] a Atom [20] (syndikace obsahu), SOAP [36] (vymˇ ´ ena zpr´av), XML-RPC (vzd´alen´e vol´an´ı procedur) [40] cˇ i XHTML [37] (rozˇsiˇritelny´ hypertextovy´ znaˇckovac´ı jazyk). Mnoho aplikac´ı zaˇc´ın´a vyuˇz´ıvat XML tak´e jako z´akladn´ı datovy´ form´at, napˇr´ıklad jako popul´arn´ı kancel´arˇ sk´e bal´ıky Microsoft Office (form´at Open XML) [31] a OpenOffice.org (form´at OpenDocument) [3].
2.2
Vyhody ´ XML
Jak jiˇz bylo rˇ eˇceno, XML je velmi rozˇs´ırˇ enym ´ a hojnˇe pouˇz´ıvanym ´ jazykem v praxi. Jeho velk´e rozˇs´ırˇ en´ı pramen´ı z nespornych kterymi tento jazyk disponuje. Pˇredevˇs´ım ´ vyhod, ´ ´ se jedn´a o univerz´aln´ı jazyk, do kter´eho je moˇzn´e serializovat4 a zpˇetnˇe z nˇej deserializovat5 libovoln´a data. D´ıky tomu se velmi cˇ asto pouˇz´ıv´a jako prostˇredn´ık u vz´ajemn´e ko1
Z anglick´eho parse. Business-to-Business 3 ˚ Syntaktick´a pravidla pro z´apis XML dokumentu. 4 ˚ kter´e reprezentuj´ı stav nˇejak´e informace. Vytvoˇren´ı proudu symbolu, 5 Reverzn´ı operace k operaci serializace. 2
7
˚ ymi munikace mezi ruzn ´ syst´emy, kter´e vnitˇrnˇe vyuˇz´ıvaj´ı odliˇsn´e form´aty, ale pro vymˇ ´ enu ˚ dat pouˇz´ıvaj´ı univerz´aln´ı XML. T´ım odpad´a nutnost vytv´arˇ et specifick´e pˇrevodn´ı mustky pro kaˇzdy´ novy´ partnersky´ syst´em, se kterym ´ je potˇreba komunikovat, pˇri jejichˇz tvorbˇe se dopodrobna mus´ıme sezn´amit s form´atem druh´e strany. Nam´ısto toho se definuje ˚ ze komunikovat jakykoliv pouze XML rozhran´ı, se kterym syst´em, aniˇz by znal ´ pak muˇ ´ vnitˇrn´ı strukturu dat dan´eho syst´emu. Textovy´ form´at je v neposledn´ı rˇ adˇe tak´e dobˇre cˇ itelny´ pro cˇ lovˇeka.
2.3
Nevyhody ´ XML
Zm´ınˇen´e vyhody XML pˇrin´asˇ ej´ı na druhou stranu i jeho nevyhody. Mezi hlavn´ı nevyho´ ´ ´ du XML patˇr´ı pˇredevˇs´ım jeho vyˇ ´ reˇcnost. Vyˇ ´ reˇcnost vede v porovn´an´ı s konkr´etn´ımi ˚ Pokud s XML datovymi form´aty k mnohem vˇetˇs´ı datov´e n´aroˇcnosti XML dokumentu. ´ ˚ ze chceme pracovat, je tak´e nutn´e nejdˇr´ıve jej analyzovat (anglicky parse XML), coˇz muˇ pˇredevˇs´ım pˇri zpracov´an´ı rozs´ahlejˇs´ıch XML znamenat vyznamnou z´atˇezˇ pro vypoˇ ´ ´ cetn´ı vykon syst´emu [19]. ´ Tyto nevyhody jsou obecnˇe zn´am´e, proto vznikl napˇr´ıklad XML Binary. Jedn´a se o ´ standardizovany´ form´at, ktery´ se neshoduje se specifikac´ı XML, ale pouze si zachov´av´a ˚ ˚ ze jisty´ vztah s puvodn´ ım XML [39]. XML Binary tak lze pouˇz´ıt u aplikac´ı, u kterych ´ muˇ byt ´ vyˇ ´ reˇcnost bˇezˇ n´eho XML probl´em, ale existuje u nich poˇzadavek na vyuˇzit´ı standardizovan´eho form´atu vymˇ ´ eny dat.
2.4
´ ı XML Zpracovan´
˚ datovym ´ ziˇstˇem jsou pak tyXML data jsou pˇredstavov´ana s´eri´ı Unicode symbolu, ´ uloˇ picky textov´e soubory. Pˇri pr´aci proto mus´ı bˇezˇ n´e aplikace tuto line´arn´ı strukturu zpracovat — analyzovat — a identifikovat v n´ı jednotliv´e prvky struktury a samotnych ´ dat. ´ Samozˇrejmˇe je nutn´e m´ıt k dispozici i inverzn´ı operaci, tedy vytvoˇren´ı a upravu wellformed XML reprezentuj´ıc´ıho danou strukturu a obsahuj´ıc´ıho poˇzadovan´a data. Existuje nˇekolik modelu˚ zpracov´an´ı XML, dva nejˇcastˇeji pouˇz´ıvan´e SAX (Simple Api for XML) [35] a XML DOM (XML Document Object Model) [28] struˇcnˇe pˇredstav´ıme v dalˇs´ı ˚ zitou cˇ a´ st´ı anal´yza XML, protoˇze pr´avˇe ona cˇ a´ sti textu. U zpracov´an´ı XML je velmi duleˇ ˚ ze m´ıt z´asadn´ı vliv na chov´an´ı c´ılov´e aplikace. Problematice analyzy muˇ ´ XML se vˇenujeme v n´asleduj´ıc´ım textu t´eto kapitoly. ˚ Obecny´ model zpracov´an´ı XML dat popisuje zpusob cˇ ten´ı a z´apisu XML dat ve vztahu ke klientsk´e aplikaci. Jeden z modelu˚ je zn´azornˇen na obr´azku 1. Obr´azek ukazuje ´ na nejvyˇssˇ´ı urovni klientskou aplikaci, kter´a cˇ te, popˇr. mˇen´ı XML data. Niˇzsˇ´ı vrstvy ˇ ı tuto aplikaci od operac´ı spojenych pak odstinuj´ ´ s vlastn´ım zpracov´an´ım XML dat. D´ıky ˚ ze aplikace pˇristupovat k XML na vyˇssˇ´ı, abstraktnˇejˇs´ı urovni. ´ tomuto modelu muˇ Pod klientskou aplikac´ı jsou v modelu zn´azornˇeny vrstvy XML Core (ta obsahuje funkce pro zpracov´an´ı XML dat dle konkr´etn´ıch poˇzadavku˚ implementace cˇ i prostˇred´ı) a dvojice komponent XML Writer a XML Parser (ty slouˇz´ı ke cˇ ten´ı a z´apisu XML).
8
Klientská aplikace
SAX
DOM
XML Model
XML Core
XML Writer
XML Parser
Obr´azek 1: Obecny´ model zpracov´an´ı XML 2.4.1
XML DOM (XML Document Object Model)
XML DOM (XML Document Object Model) vych´az´ı z obecn´e definice DOM (Document ˇ Object Model), coˇz je jazykovˇe a platformˇe neutr´aln´ı rozhran´ı, kter´e umoˇznuje progra˚ a skriptum ˚ dynamicky pˇristupovat a aktualizovat obsah, strukturu a styl dokumum mentu˚ [28]. ˚ KoˇrenoXML DOM nahl´ızˇ ´ı na XML jako na strom, ktery´ se skl´ad´a z jednotlivych ´ uzlu. ´ ˚ ze obsahovat uzly podˇr´ızen´e. Rekurzivnˇe vym a ten muˇ ´ uzlem je uzel na nejvyˇssˇ´ı urovni tato vlastnost plat´ı i pro podˇr´ızen´e uzly, tedy podˇr´ızen´e prvky mohou obsahovat sobˇe podˇr´ızen´e prvky a tak d´ale. Bˇehem analyzy ´ vstupn´ıch dat se v pamˇeti postupnˇe vytvoˇr´ı jim odpov´ıdaj´ıc´ı strom. ´ Upravy pak prob´ıhaj´ı v pamˇeti a cely´ strom nebo jeho cˇ a´ st je kdykoliv moˇzn´e zapsat ve ˚ form´atu XML. Z uveden´eho zpusobu pr´ace je patrn´e, zˇ e XML DOM potˇrebuje m´ıt ke sv´e ˚ ze cˇ init probl´em pˇri zprapr´aci v pamˇeti neust´ale celou strukturu i samotn´a data, coˇz muˇ ˚ Vyhodou ˚ ze cov´an´ı rozs´ahlych tohoto modelu je fakt, zˇ e aplikace muˇ ´ XML dokumentu. ´ ˇ ´ ˇ libovolnˇe cıst i mˇenit strukturu a data, protoˇze DOM podporuje operace cten´ı i modifikace a to typicky objektovˇe. 2.4.2
SAX (Simple API for XML)
SAX prov´ad´ı postupnou analyzou vstupn´ıch XML dat a bˇehem n´ı identifikuje jednotliv´e ´ cˇ a´ sti XML dokumentu, jako jsou znaˇcky, atributy, entity, koment´arˇ e atp. SAX je zaloˇzen na ud´alostech, na kter´e se klientsk´a aplikace v´azˇ e a pomoc´ı nichˇz pak z´ısk´av´a data. Hlavn´ı rozd´ıl oproti dˇr´ıve zm´ınˇen´emu modelu DOM je v tom, zˇ e SAX neudrˇzuje v pamˇeti strukturu ani data cel´eho dokumentu, ale pouze data aktu´alnˇe analyzovan´e cˇ a´ sti [35]. D´ıky tomu je moˇzn´e zpracovat libovolnˇe rozs´ahly´ XML dokument, nicm´enˇe, z principu je moˇzn´e data pouze cˇ ´ıst a to pouze line´arnˇe. V praxi se bˇezˇ nˇe SAX model implemen-
9
<poloˇzka> ´ an´ ´ ı textu Formatov <popis>V textu muˇ ˚ zeme pouˇz´ıt tuˇcne´ p´ısmo ale ne kurz´ıvu. ... <poloˇzka> ´ ´ Pˇr´ıklad platneho zaznamu ˇ ı: Nepouˇz´ıvat! <popis>Upozornen´ ...
Obr´azek 2: Pˇr´ıklad XML s nejasnˇe analyzovatelnou strukturou tuje jako SAX parser, coˇz je konkr´etn´ı analyz´ator podporuj´ıc´ı model SAX. SAX je vhodny´ pˇri pouˇzit´ı s aplikacemi, kter´e potˇrebuj´ı vstupn´ı data pouze cˇ ´ıst a nevyˇzaduj´ı v jednom okamˇziku komplexn´ı pohled na cely´ XML dokument.
2.5
Analyza ´ XML
XML se skl´ad´a ze znaˇcek a obsahu [29]. Znaˇcky jsou definov´any pomoc´ı speci´aln´ıch ˚ ze znaku˚ ( <“ a >“). Vˇse, co nen´ı znaˇcka, je povaˇzov´ano za obsah. Ne vˇzdy ovˇsem muˇ ” ” byt ´ rozdˇelen´ı znaˇcek a obsahu zcela zˇrejm´e. U well-formed XML dokumentu nen´ı probl´em identifikovat veˇsker´e znaˇcky, nicm´enˇe nˇekter´e znaˇcky nemus´ı m´ıt vyznam znaˇcky ´ ˚ ze se jednat o znaˇcku, kter´a je um´ıstˇena v kontextu nˇejak´eho jako definuj´ıc´ı strukturu, ale muˇ obsahu jako form´atovac´ı nebo jiny´ pomocn´y prvek (napˇr. oznaˇcen´ı tuˇcn´eho textu znaˇckou ˚ ze m´ıt za n´asledek nestandardn´ı chov´an´ı c´ılov´e aplikace. Pˇr´ıklad kon). To muˇ kr´etn´ıho XML, ktery´ odpov´ıd´a podobn´emu popisu, je zn´azornˇen na obr´azku 2. ˚ Zpusob analyzy ´ takov´eho XML souboru m´a vliv na strukturu a obsah informac´ı, jak´e ´ aplikace z´ısk´a od analyz´atoru. Dvˇe konkr´etn´ı uskal´ ı popisuj´ı n´asleduj´ıc´ı dvˇe podkapitoly. 2.5.1
Analyza ´ struktury a obsahu
Uk´azkovy´ pˇr´ıklad obsahuje dle form´aln´ı definice XML celkem cˇ tyˇri jedineˇcn´e znaˇcky poloˇzka, nadpis, b, i a k nim odpov´ıdaj´ıc´ı koncov´e znaˇcky. Nicm´enˇe tyto znaˇcky v dan´em kontextu spadaj´ı do dvou kategori´ı. Prvn´ı kategorii tvoˇr´ı znaˇcky, pomoc´ı kterych ´ se tvoˇr´ı poˇzadovan´a struktura dat — to jsou znaˇcky poloˇzka a nadpis. Vˇse ostatn´ı, tedy texty um´ıstˇen´e uvnitˇr tˇechto znaˇcek, m´a byt ´ povaˇzov´ano za obsah. Ovˇsem vloˇzen´ı textu podobn´emu naˇsemu pˇr´ıkladu tuto myˇslenku rozb´ıj´ı. Znaˇcky b a i, kter´e slouˇz´ı v kontextu pouze ˚ jako form´atovac´ı prvky, vytv´arˇ´ı v puvodn´ ı definici XML dodateˇcnou strukturu. Jak je patrn´e, v tomto pˇr´ıkladu nejsou znaˇcky b a i znaˇckami ve smyslu struktury ˚ ze m´ıt neˇza´ douc´ı vliv na choXML, ale jsou souˇca´ st´ı obsahu znaˇcky popis. A pr´avˇe to muˇ v´an´ı aplikace, pokud analyz´ator nebude o definovan´e struktuˇre dostateˇcnˇe informov´an (napˇr. XML sch´ematem). Nav´ıc, dan´e XML je v tuto chv´ıli velmi citliv´e na zpracov´an´ı form´atov´an´ı, neboli white-spaces.
˚ zeme prozradit, zˇ e XMill6 ve vychoz´ S pˇredstihem muˇ ım nastaven´ı vyuˇz´ıv´a optimalizaci ´ ˇ komprese XML t´ım, zˇ e odstranuje form´atov´an´ı XML (white-spaces), kter´e pak vytv´arˇ´ı pˇri dekompresi programovˇe. Dalˇs´ı podrobnosti o n´astroji XMill jsou v sekci 4. XML podporuje celkem cˇ tyˇri druhy white-spaces7 : carriage-return (\r), line-feed (\n), ˚ ze zd´at, zˇ e tyto informace nenetab (\t) a spacebar (mezera) [29]. Na prvn´ı pohled se muˇ ˇ sou obsahovou informaci, proto pr´avˇe zminovan y´ XMill ve vychoz´ ım nastaven´ı white´ spaces ignoruje a bˇehem dekomprese je rekonstruuje programovˇe [38]. Pokud se ale pod´ıv´ame na n´ami uv´adˇeny´ pˇr´ıklad, bude m´ıt pouˇzit´ı t´eto optimalizace vliv na obsah dat, protoˇze pˇri prov´adˇen´ı dekomprese nebudou white-spaces rekonstruov´ana korektnˇe. V pˇr´ıkladu se za koncovou znaˇckou (mezi slovy p´ısmo a ale) nach´az´ı mezera a pˇri aktivn´ı optimalizaci by se bˇehem komprese jako white-space symbol ignorovala. T´ım by doˇslo ke ztr´atˇe informace, protoˇze pˇri programov´e rekonstrukci form´atov´an´ı XMill nikdy ned´av´a za znaˇcku mezeru, maxim´alnˇe odsazuje n´asleduj´ıc´ı obsah na dalˇs´ı rˇ a´ dek. Bˇehem naˇsich experimentu˚ jsme proto vˇzdy tento druh optimalizace potlaˇcili a to i ˚ u kterych u souboru, ´ to vzhledem k jejich obsahu nebylo nutn´e. Toto opatˇren´ı n´am tak´e ˚ zajistilo, zˇ e se po dekompresi soubory zcela shodovaly s puvodn´ ımi origin´aly. Jedinou nevyhodou je to, zˇ e se spolu s komprimovanymi ´ ´ daty mus´ı ukl´adat i vlastn´ı form´atov´an´ı, coˇz m´ırnˇe zhorˇsuje vysledek komprese. ´ 2.5.3
Analyza ´ XML v kontextu komprese XML
Pˇri experimentech s n´astrojem XMill a n´aslednˇe i bˇehem vyvoje vlastn´ıho n´astroje SXMill ´ ˚ zitym jsme doˇsli k z´avˇeru, zˇ e duleˇ ´ bodem komprese XML je analyza ´ vstupn´ıch XML dat. ˚ zit´e je Na uvedenych pˇr´ıkladech z pˇredchoz´ı kapitoly jsme se snaˇzili uk´azat, jak duleˇ ´ spr´avnˇe vyhodnotit strukturu dokumentu a identifikovat v n´ı data. Nespr´avn´e rozliˇsen´ı ˚ ze m´ıt neˇza´ douc´ı vliv na efektivitu komprese, protoˇze bude tˇechto dvou elementu˚ muˇ ˇ ˚ ze v´est doch´azet k nespr´avn´emu odvozen´ı s´emantickych a analyza ´ vazeb. Spatn´ ´ ale muˇ ˇ aˇz ke ztr´atˇe dat. Vylepˇsen´ı analyz´atoru XML, ktery´ by uveden´e skuteˇcnosti zohlednoval, je proto t´ematem dalˇs´ıho vyvoje. ´ V praktick´e cˇ a´ sti t´eto diplomov´e pr´ace jsme se pˇresvˇedˇcili o tom, zˇ e typickym ´ pˇredsta˚ u nichˇz je tˇreba specifickym ˚ vitelem kategorie XML souboru, analyzovat struk´ zpusobem turu XML, je soubor wiki.xml. Podrobnosti jsou k dispozici v kapitole 6, kter´a se vˇenuje testov´an´ı.
6 7
XMill je specializovany´ XML-aware kompresor. B´ıl´a m´ısta.
11
3
Komprese XML
XML je ze sv´e podstaty velmi vyˇ ´ reˇcnym ´ form´atem. Veˇsker´e informace jsou v XML uloˇzeny v textov´e podobˇe (samotn´e texty ale i cˇ ´ıseln´e hodnoty, vyˇ ´ ctov´e typy a dalˇs´ı specifick´e informace, kter´e se do textov´e podoby pˇrev´adˇej´ı serializac´ı dat). Nav´ıc u kaˇzd´e poloˇzky se neust´ale opakuje jej´ı s´emantick´a definice, tedy jej´ı znaˇcka. Ta urˇcuje vyznam obsahu, ´ ktery´ je v n´ı uzavˇren. Napˇr´ıklad pokud je v XML uloˇzeno nˇekolik poloˇzek obsahuj´ıc´ıch informaci o autorech knihy, napˇr´ıklad pomoc´ı znaˇcky , bude se neust´ale tato dvojice znaˇcek opakovat u kaˇzd´eho jednotliv´eho jm´ena autora. A t´ım velice rychle roste objem dat v XML souboru. Zm´ınˇen´e vlastnosti XML mohou pˇredstavovat probl´em pˇri pr´aci s rozs´ahlymi XML ´ ˚ ze pˇredstavovat z´atˇezˇ pro vypoˇ soubory. Jednak je nutn´e XML data analyzovat, coˇz muˇ ´ cet˚ ze byt n´ı vykon syst´emu, ktery´ s XML pracuje. Probl´emem muˇ ´ ´ tak´e velk´e mnoˇzstv´ı dat, kter´e je nutn´e archivovat na disku nebo jin´em m´ediu, cˇ i pˇren´asˇ et po s´ıti nebo pomalych ´ ˇ ˚ ze rˇ eˇsit pr´avˇe komprese XML. WAN8 link´ach. A oba zminovan´ e nedostatky muˇ
3.1
Principy komprese
˚ kter´e lze pouˇz´ıt ke kompresi XML dat. Obecnˇe je moˇzn´e Existuje cel´a rˇ ada algoritmu, vˇsechny rozdˇelit do dvou skupin: • XML komprese bez podpory dotazov´an´ı • XML komprese s podporu dotazov´an´ı Algoritmy prvn´ı kategorie se zamˇerˇ uj´ı na zmenˇsen´ı velikosti XML dat s t´ım, zˇ e pokud s komprimovanymi daty potˇrebujeme pozdˇeji pracovat, mus´ıme je nejdˇr´ıve dekompri´ movat jako celek, zpracovat a posl´eze jako celek znovu komprimovat. V t´eto diplomov´e ˚ Tyto algoritmy lze d´ale pr´aci se zamˇerˇ ujeme pˇredevˇs´ım na tuto kategorii algoritmu. rozdˇelit na dalˇs´ı dvˇe podskupiny: • Komprese XML jako textu (bˇezˇ n´a komprese) • Komprese XML s vyuˇzit´ım s´emantickych ´ informac´ı (XML-aware komprese) Na kompresi XML jako textu se vyuˇz´ıvaj´ı bˇezˇ n´e kompresn´ı n´astroje, kter´e v praxi ˚ Vzhledem k tomu, zˇ e XML data slouˇz´ı ke kompresi i jinych, nejen textovych ´ ´ souboru. jsou v podstatˇe text, dosahuj´ı nejlepˇs´ıch vysledk u˚ programy implementuj´ıc´ı metody spe´ cializuj´ıc´ı se na kompresi textu. Pˇredstaviteli t´eto kategorie komprese XML jsou napˇr´ıklad programy GZip, BZip29 cˇ i 7-zip, ale existuj´ı i mnoh´e dalˇs´ı. My si d´ale v n´asleduj´ıc´ım textu ˚ ymi pop´ısˇ eme nejˇcastˇejˇs´ı metody komprese, kter´e se napˇr´ıcˇ ruzn programy pouˇz´ıvaj´ı. ´ XML-aware kompresory obecnˇe vyuˇz´ıvaj´ı s´emantiku dostupnou v XML datech (pracuj´ı se strukturou XML), ale ve sv´em j´adru st´ale zamˇestn´avaj´ı klasick´e kompresn´ı algoritmy. Fin´aln´ı komprese tedy prob´ıh´a napˇr´ıklad algoritmem Deflate cˇ i BZip2 [14]. Od 8 9
Wide-Area-Network, rozs´ahl´e s´ıtˇe. ˚ kter´e vyuˇz´ıvaj´ı kompresn´ı algoritmy Deflate, resp. BZip2. GZip, resp. BZip2 jsou n´azvy programu,
12
˚ komprese XML jako textu se odliˇsuj´ı pˇredevˇs´ım t´ım, zˇ e se snaˇz´ı specifickym ´ zpusobem ˚ neˇz pˇripravit XML data tak, aby komprese bˇezˇ nymi algoritmy dos´ahla lepˇs´ıch vysledk u, ´ ´ jakych se dosahuje pˇri kompresi XML jako textu. Vyuˇz´ıv´a se pˇritom znalost principu˚ ´ ˚ komprese danych ´ kompresn´ıch algoritmu. XML-aware kompresory s podporou dotazov´an´ı pak zachov´avaj´ı u komprimovanych ´ ˚ dat moˇznost dotazov´an´ı. Dotazov´an´ı m´ıv´a ruznou podporu — liˇs´ı se rozsah podporovanych ´ dotazu˚ i to, zda je moˇzn´e data pouze cˇ ´ıst nebo i mˇenit. Tyto algoritmy ve srovn´an´ı s doposud popsanymi algoritmy dosahuj´ı obvykle horˇs´ıch pomˇeru˚ komprese. Nicm´enˇe ´ vedle sn´ızˇ en´ı datov´e n´aroˇcnosti mohou odlehˇcit i vypoˇ potˇrebn´emu ke ´ cetn´ımu vykonu ´ ˚ ze byt zpracov´an´ı XML dat — vzhledem k nutnosti zpracovat menˇs´ı mnoˇzstv´ı dat muˇ ´ zpracov´an´ı komprimovanych ´ dat paradoxnˇe m´enˇe n´aroˇcn´e a to i s pˇrihl´ednut´ım na vypo´ cˇ etn´ı vykon, ktery´ je vyˇzadovany´ k dekompresi cˇ a´ st´ı XML dokumentu. ´
3.2
Komprese XML jako textu
Pˇri kompresi XML jako textu se soubor komprimuje jako celek bez ohledu na vnitˇrn´ı strukturu. Na soubor se pohl´ızˇ ´ı jako na bˇezˇ ny´ soubor, nicm´enˇe vzhledem k tomu, zˇ e se ´ esˇ nˇe aplikovat algoritmy specializuj´ıc´ı se na komjedn´a o textovy´ soubor, lze na nˇej uspˇ ˚ presi textu. Vyhoda toho zpusobu komprese je pˇredevˇs´ım v jednoduchosti jeho nasazen´ı, ´ ˚ kter´e se zamˇerˇ uj´ı na kompresi dat, existuje cel´a rˇ ada. Modern´ı algoprotoˇze programu, ritmy komprese textu jsou nav´ıc velmi efektivn´ı (jak ukazuj´ı napˇr´ıklad vysledky naˇsich ´ experimentu˚ v kapitole 6). 3.2.1
Deflate (gzip)
Deflate je bezeztr´atov´a metoda, kter´a kombinuje kompresi pomoc´ı LZ77 a Huffmanovo k´odov´an´ı [10]. Jedn´a se o velmi popul´arn´ı metodu komprese dat, coˇz napˇr´ıklad dokazuje fakt, zˇ e jej´ı podpora je implementov´ana ve vˇetˇsinˇe modern´ıch vyvojov ych ´ ´ prostˇred´ıch nebo operaˇcn´ıch syst´emech. Metodu Deflate vyuˇz´ıv´a zn´amy´ program a form´at ZIP, to je mimo jin´e tak´e obecnˇe zaˇzity´ pojem vyjadˇruj´ıc´ı kompresi dat10 nejen u laick´e veˇrejnosti. Deflate je pomˇernˇe rychly´ algoritmus, coˇz se tyk´ ´ a jak komprese, tak i pˇredevˇs´ım dekomprese. Jeho nespornou vyhodou je i to, zˇ e nen´ı pamˇet’ovˇe pˇr´ıliˇs n´aroˇcny. ´ ´ Proud dat komprimovany´ metodou Deflate je tvoˇren nˇekolika bloky, kde kaˇzdy´ blok ˚ ze byt ˚ muˇ u˚ [10]: ´ uloˇzen jedn´ım z n´asleduj´ıc´ıch zpusob ´ • Blok uloˇzeny´ bez kodov´ an´ı / komprese (hrub´a data) ´ • Blok kodovan y´ pomoc´ı pˇredem dohodnut´eho Huffmanova stromu ´ • Blok kodovan y´ pomoc´ı Huffmanova stromu, ktery´ je souˇca´ st´ı bloku Samotn´a komprese metodou Deflate prob´ıh´a dvouf´azovˇe: 1. Pomoc´ı LZ77 jsou odstranˇeny opakuj´ıc´ı se rˇ etˇezce 10
Slangovˇe se cˇ asto pouˇz´ıv´a term´ın zazipovat soubor“ ”
13
´ ´ 2. Vystup (1.) je kodov´ an pomoc´ı Huffmanova kodov´ an´ı ´ Huffmanovo kodov´ ´ an´ı [11] patˇr´ı do skupiny statistick´ych kompresn´ıch algoritmu. ˚ Statistick´e metody pracuj´ı s cˇ etnost´ı jednotlivych ´ znaku˚ (nebo jejich skupin) ve vstupn´ım sou˚ s vyˇssˇ´ı cˇ etnost´ı jsou pˇriˇrazov´any kratˇs´ı kody ´ (m´enˇe bitu, ˚ napˇr. nejˇcastˇeboru dat. Znakum ˚ ze byt ´ ˚ s m´enˇe cˇ astym ji se vyskytuj´ıc´ı znak muˇ an pouze jedn´ım bitem) a znakum ´ kodov´ ´ ´ vyskytem jsou pˇriˇrazov´any kody delˇs´ı. ´ Existuj´ı dvˇe varianty tohoto algoritmu. Statick´a varianta prov´ad´ı kompresi ve dvou ˚ pˇri f´az´ıch — v prvn´ı f´azi je provedena statistika cˇ etnosti vyskytu jednotlivych znaku, ´ ´ ´ ´ kter´e je vytvoˇren strom kodov´ an´ı, ve druh´e f´azi doch´az´ı k samotn´emu zakodov´ an´ı vstupn´ıch dat s vyuˇzit´ım z´ıskan´e statistiky. Vyhodou t´eto metody je vytvoˇren´ı optim´aln´ı statis´ tiky pro cely´ vstupn´ı soubor, nevyhodou je pomal´e zpracov´an´ı, protoˇze jsou nutn´e dva ´ ˚ pruchody cel´eho vstupn´ıho souboru. Dalˇs´ı nevyhodou je nutnost uloˇzen´ı bin´arn´ıho stro´ mu spolu s komprimovanymi daty. Dynamick´a varianta vytv´arˇ´ı statistiku cˇ etnosti znaku˚ a ´ ´ ˚ samotn´e kodov´ an´ı bˇehem jedin´eho pruchodu. To plat´ı jak pˇri kompresi, tak i pˇri dekompresi. D´ıky tomu nen´ı nutn´e ukl´adat bin´arn´ı strom spolu s komprimovanymi daty. Z´aro´ venˇ je proces komprese rychlejˇs´ı, protoˇze nen´ı nutn´e vstupn´ı soubor proch´azet dvakr´at, ale na druhou stranu je nutn´e upravovat strom cˇ etnost´ı, coˇz samotny´ proces komprese ve srovn´an´ı se statickou variantou zpomaluje. Jelikoˇz m´a kompresor informace o cˇ etnosti ´ u˚ znaku˚ pouze u t´e cˇ a´ sti souboru dat, kterou doposud proˇsel, nemus´ı byt ´ pˇriˇrazen´ı kod ˚ ze doch´azet v r´amci cel´eho souboru k dosaˇzen´ı horˇs´ıho vysledku zcela optim´aln´ı, cˇ ´ımˇz muˇ ´ komprese. LZ77 [23], publikovany´ v roce 1977 Abrehamem Lempelem a Jacobem Zivem, je algo˚ Algoritmus vyuˇz´ıv´a tzv. ritmus patˇr´ıc´ı do skupiny slovn´ıkovych ´ kompresn´ıch algoritmu. posuvn´e okno — sliding window — kter´e obsahuje konec (typicky posledn´ıch nˇekolik kB) doposud pˇreˇctenych ´ dat ze zdrojov´eho souboru. Bˇehem komprese se algoritmus snaˇz´ı naj´ıt v oknˇe opakuj´ıc´ı se vyskyt cˇ a´ sti vstupn´ıch dat, d´ıky cˇ emuˇz by bylo moˇzn´e tento ´ ´ vyskyt zakodovat pouze jako ofset a d´elku v posuvn´em oknˇe. Pˇri dekompresi je nutn´e ´ ˚ posuvn´e okno udrˇzovat stejnym jak tomu bylo bˇehem f´aze komprese. ´ zpusobem, ˚ e varianty algoritmu, liˇs´ıc´ı se v z´avislosti na tom, jak koduj´ ´ Existuj´ı ruzn´ ı vystup. Jako ´ ˚ zeme uv´est varianty LZSS, LZH a LZB [2]. pˇr´ıklad muˇ 3.2.2
BZip2
BZip2 je svobodny, ´ bezeztr´atovy´ kompresn´ı algoritmus a tak´e program. Jeho autorem je Julian Seward, ktery´ prvn´ı verzi publikoval v roce 1996. Jedn´a se opˇet o pomˇernˇe rychly´ algoritmus, ktery´ ve srovn´an´ı s metodou Deflate dosahuje ve vˇetˇsinˇe pˇr´ıpadu˚ ´ cinnˇejˇs´ı algoritmus. Prvn´ı verze tohoto allepˇs´ıch vysledk u˚ a jedn´a se tak celkovˇe o uˇ ´ goritmu vyuˇz´ıvala aritmetick´e k´odov´an´ı, kter´e ale bylo z´ahy nahrazeno Huffmanovym ´ ´ kodov´ an´ım. Algoritmus komprimuje bloky dat o velikosti v rozmez´ı 100 aˇz 900kB (nastaviteln´e skokovˇe po 100kB). Kombinuje techniky BWT (Burrows-Wheeler Transform), MTF (Move-To-Front transform), Huffmanovo k´odov´an´ı a RLE (Run-Length Encoding) [26]. Burrows-Wheeler Transform [16] je transformace zn´am´a tak´e pod oznaˇcen´ım komprese blokov´ym tˇr´ıdˇen´ım. Tato transformace ve vstupn´ım souboru nemˇen´ı hodnotu zˇ a´ dn´eho
14
symbolu, prov´ad´ı pouze permutaci jejich poˇrad´ı. Pokud vstupn´ı soubor obsahuje opakuj´ıc´ı se podˇretˇezce, budou po proveden´ı transformace ve vystupu m´ısta, na kterych se ´ ´ budou za sebou nach´azet stejn´e opakuj´ıc´ı se znaky. A to je pˇredpoklad, d´ıky kter´emu je moˇzn´e n´aslednˇe dos´ahnout lepˇs´ıho vysledku komprese. Transformace se prov´ad´ı setˇr´ıdˇe´ n´ım vˇsech rotac´ı textu v tabulce a jako vystup se pouˇzije posledn´ı sloupec dan´e tabulky. ´ ˇ ´ BWT transformace, inverzn´ı operaci pak zobrazuje Algoritmus 1 zn´azornuje pseudokod algoritmus 2. Algoritmus 1 Transformace BWT (string s) ´ dky jsou vˇsechny moˇzn´e rotace s 1: vytvoˇr tabulku, rˇ a ´ dky abecednˇe 2: setˇrid’ rˇ a 3: return posledn´ı sloupec tabulky
Algoritmus 2 Inverzn´ı BWT (string s) 1: vytvoˇr pr´ azdnou tabulku 2: for i = 1 to d´elka(s) do 3: vloˇz s jako sloupec tabulky pˇred prvn´ı sloupec tabulky 4: . (prvn´ım vloˇzen´ım se vytvoˇr´ı prvn´ı sloupec) ’ 5: setˇrid sloupce tabulky abecednˇe 6: end for ´ dek, u kter´eho sloupec konˇc´ı znakem EOF 7: return rˇ a Move-To-Front transform [4], cˇ esky pˇresunˇ na zaˇca´ tek, je metoda, kter´a pracuje na principu nahrazov´an´ı symbolu˚ vstupn´ı abecedy za jejich indexy do pole symbolu˚ a naopak. Jedn´a se o reverzibiln´ı transformaci, tzn. zˇ e existuje inverzn´ı operace, kterou je ˚ moˇzn´e data vr´atit do puvodn´ ı podoby. Proces transformace MTF je n´asleduj´ıc´ı — kaˇzd´a ´ hodnota vstupu je kodov´ ana pomoc´ı indexu, ktery´ odkazuje do pole. Toto pole se v ˚ ehu transformace neust´ale mˇen´ı. Tedy — v poli je nalezena odpov´ıdaj´ıc´ı hodnota prubˇ znaku na vstupu a index t´eto hodnoty je zaps´an na vystup. Na zaˇca´ tku je pole uspoˇra´ d´ano ´ ´ podle hodnot (napˇr´ıklad kodujeme-li jednobajtovˇe, pak 0, 1, . . . , 255), prvn´ı hodnota vs´ ´ tupu je tak vˇzdy zakodov´ ana vlastn´ı“ hodnotou. Po zakodov´ an´ı kaˇzd´eho znaku je v poli ” znak pˇresunut na zaˇca´ tek (odtud n´azev metody). Reverzn´ı MTF transformace prob´ıh´a tak, zˇ e se ve vychoz´ ım stavu opˇet zaˇc´ın´a s uspo´ ´ rˇ a´ danym an´ı prob´ıh´a postupnˇe tak, zˇ e ´ polem (napˇr. hodnoty 0, 1, . . . , 255). Dekodov´ ´ zakodovan´ a hodnota ze vstupu urˇcuje index v poli, kde je uloˇzena hodnota pro vystup. ´ ´ Po dekodov´ an´ı kaˇzd´eho znaku doch´az´ı k pˇresunut´ı tohoto znaku na zaˇca´ tek, stejnˇe jako ´ bˇehem procesu kodov´ an´ı. ´ MTF transformace je zobrazen na vypisu ´ inPseudokod algoritmus 3, pseudokod ´ verzn´ı operace MTF je pak zn´azornˇen na vypisu algoritmus 4. ´ RLE (Run-length encoding) pˇredstavuje jednoduchou formu bezeztr´atov´e kompre´ se. Koduje vstupn´ı data tak, zˇ e opakuj´ıc´ı se posloupnosti znaku˚ zapisuje jako dvojici
15
Algoritmus 3 MTF (string s) ´ dan´e jednobajtov´e hodnoty (0..255)) 1: vytvoˇr pole p (obsahuj´ıc´ı uspoˇra 2: for all (char z in s) do 3: v poli p vyhledej index i znaku z 4: zapiˇs i na vystup v ´ 5: v poli p pˇresunˇ z na zaˇca´ tek 6: end for 7: return vystup v ´ Algoritmus 4 Invezn´ı MTF (int[] vstup) ´ dan´e jednobajtov´e hodnoty (0..255)) 1: vytvoˇr pole p (obsahuj´ıc´ı uspoˇra 2: for all (int i in vstup) do 3: na vystup v zapiˇs znak z v poli p um´ıstˇeny´ na pozici i ´ 4: v poli p pˇresunˇ znak z na zaˇca´ tek 5: end for 6: return vystup v ´
´ . Nevyhodou tohoto kodov´ an´ı je to, zˇ e vyskyt jednoho opa´ ´ ´ kov´an´ı znaku (jeden bajt) je nutn´e kodovat pomoc´ı dvojice <1, znak> (dva bajty) a t´ım ´ cinnost komprese proto z´avis´ı na charakteru vstup˚ doch´az´ı k neˇza´ douc´ımu n´arustu dat. Uˇ n´ıch dat. 3.2.3
LZMA
LZMA (Lempel-Ziv-Markov-Chain Algorithm) je vylepˇsen´a verze algoritmu Deflate, resp. ˚ vyuˇz´ıv´a vylepˇsenou verzi algoritmu LZ77. LZMA pouˇz´ıv´a stejnˇe jako puvodn´ ı LZ77 slovn´ık, ale narozd´ıl od nˇej podporuje jeho mnohem vˇetˇs´ı velikost (aˇz 4GB) a tuto velikost je moˇzn´e uˇzivatelsky nastavit. LZMA se skl´ad´a celkem ze tˇr´ı souˇca´ st´ı — vedle ´ vylepˇsen´eho LZ77 pak jeˇstˇe z kodov´ an´ı Markov-Chain a range kod´eru. Algoritmus dosahuje vˇetˇsinou lepˇs´ıch vysledk u˚ neˇz Deflate nebo BZip2, jedn´a se ale o pamˇet’ovˇe n´aroˇcnˇejˇs´ı al´ goritmus, coˇz plat´ı hlavnˇe pro kompresi. Komprese dat je tak´e vyraznˇ e pomalejˇs´ı, nicm´e´ nˇe dekomprese je extr´emnˇe rychl´a a pamˇet’ovˇe m´alo n´aroˇcn´a. LZMA je vychoz´ ı kom´ presn´ı metodou form´atu 7z programu 7-zip [25]. ´ Range kod´er, neboli k´odov´an´ı pomoc´ı intervalu, vyuˇz´ıv´a k zakodov´ an´ı vˇsech symbolu˚ ´ zpr´avy pouze jedno cˇ ´ıslo — narozd´ıl napˇr´ıklad od Huffmanova kodov´ an´ı, kter´e kaˇzd´emu ˚ co nejsymbolu pˇriˇrazuje urˇcitou bitovou reprezentaci (nejˇcastˇeji se opakuj´ıc´ım znakum ˚ a na vystup ´ m´enˇe bitu) pak ukl´ad´a postupnˇe za sebou odpov´ıdaj´ıc´ı kody. D´ıky t´eto ´ ˚ ze kodov´ ´ ˚ neˇz je horn´ı odliˇsnosti muˇ an´ı pomoc´ı intervalu dos´ahnout lepˇs´ıch vysledk u, ´ ´ ´ hranice jeden-bit-na-symbol u Huffmanova kodov´ an´ı [15]. Kodov´ an´ı pomoc´ı intervalu je ´ matematicky ekvivalentn´ı k aritmetick´emu kodov´ an´ı. Podrobnˇejˇs´ı informace o principu t´eto metody jsou dostupn´e napˇr´ıklad v [15].
16
Markov-chain je matematick´a metoda pro statistick´e modelov´an´ı. Podrobnˇejˇs´ı informace jsou k dispozici napˇr´ıklad v [9]. 3.2.4
PPM (Prediction by Partial Matching)
PPM [8] je adaptivn´ı, statistick´a metoda komprese dat, zaloˇzen´a na modelech kontextu a ˚ Od sv´eho vzniku, tedy od 90. let minul´eho stolet´ı, patˇr´ı PPM k pˇredpov´ıd´an´ı symbolu. ˚ komprese textu˚ v pˇrirozen´em jazyce. Jeho historie sah´a nejv´ıce efektivn´ım algoritmum jeˇstˇe d´ale, jeho dˇr´ıvˇejˇs´ımu rozˇs´ırˇ en´ı br´anil ale fakt, zˇ e je velmi n´aroˇcny´ na pamˇet’ov´e prostˇredky. Jedn´a se tak´e o cˇ asovˇe n´aroˇcnˇejˇs´ı metodu a to se tyk´ ´ a jak komprese, tak i dekomprese. Existuje nˇekolik variant t´eto metody, nˇekter´e z nich implementuj´ı napˇr´ıklad programy WinRAR nebo 7-zip. Metoda PPM je zaloˇzena na modelech [6, 8]. Kaˇzdy´ z modelu˚ si udrˇzuje statistiky ˚ Kaˇzdy´ model m´a doposud zhl´ednutych ´ symbolu˚ v kontextu pˇredch´azej´ıc´ıch symbolu. urˇceno, kolik symbolu˚ si bude takto udrˇzovat. Cel´a metoda PPM pak udrˇzuje nˇekolik ˚ y´ poˇcet symbolu˚ — od nula symbolu˚ aˇz po tˇechto modelu˚ a kaˇzdy´ z nich udrˇzuje ruzn maxim´aln´ı poˇcet n, kde hodnota n pˇredstavuje stupenˇ PPM a znaˇc´ı se typicky PPM(n). ˇ nejsou tedy nijak limitov´any Existuj´ı tak´e varianty, kter´e nemaj´ı pevnˇe stanoveny´ stupen, d´elkou kontextu, ty se oznaˇcuj´ı PPM*. Modely slouˇz´ı k vypoˇ ´ ctu pˇredpovˇed´ı toho, s jakou pravdˇepodobnost´ı se budou vyskytovat n´asleduj´ıc´ı symboly. Vypoˇcten´a pravdˇepodob´ nost se pak pouˇz´ıv´a k zakodov´ an´ı dan´eho symbolu pomoc´ı aritmetick´eho k´odov´an´ı. Po zpracov´an´ı kaˇzd´eho symbolu se model uprav´ı tak, aby zachytil pr´avˇe zpracovany´ symbol. Pˇredpovˇed’ pravdˇepodobnosti pracuje n´asledovnˇe. Pokud je symbol nalezen v nejdelˇs´ım kontextu, je pravdˇepodobnost urˇcena jako relativn´ı cˇ etnost symbolu v dan´em kontextu. Pokud nen´ı v tomto kontextu symbol nalezen, pouˇzije se dalˇs´ı nejdelˇs´ı kontext. Pˇrechod na jiny´ kontext je indikov´an z´apisem tzv. escape-znaku [6]. Tento proces se opakuje do t´e doby, dokud nen´ı nalezena shoda, nebo dokud nen´ı k dispozici zˇ a´ dny´ dalˇs´ı kontext. V pˇr´ıpadˇe, zˇ e jiˇz nelze pravdˇepodobnost urˇcit z zˇ a´ dn´eho modelu, doch´az´ı k proveden´ı fixn´ı pˇredpovˇedi. ˚ e varianty PPM se liˇs´ı v tom, jak rˇ eˇs´ı problematiku urˇcen´ı pravdˇepodobnosti Ruzn´ ˚ Nˇekter´e varianty tˇemto symbolum ˚ pˇriˇrazuj´ı konstantnˇe doposud nezn´amych ´ symbolu. hodnotu 1. Varianta PPMd, kterou jsme vyuˇzili prakticky pˇri implementaci algoritmu˚ komprese XML, navyˇsuje hodnotu pro kaˇzdy´ doposud neshl´ednuty´ symbol o jedna a pravdˇepodobnost vyskytu tohoto symbolu je pak vypoˇctena jako pomˇer jedineˇcnych ´ ´ ˚ symbolu˚ k celkov´emu poˇctu doposud shl´ednutych ´ symbolu.
3.3
XML-Aware komprese
Metody komprese, kter´e se pˇr´ımo zamˇerˇ uj´ı na XML, vyuˇz´ıvaj´ı s´emantick´e informace uloˇzen´e v XML datech. Tyto informace jsou v XML pˇr´ıtomny v podobˇe znaˇcek — ty d´avaj´ı s´emanticky´ vyznam obsahu, ktery´ je v nich uzavˇren. Z´akladn´ı myˇslenka vˇetˇsiny tˇechto ´ kompresoru˚ je pˇripravit data XML souboru pro bˇezˇ n´e kompresn´ı algoritmy tak, aby se vyuˇzit´ım vlastnost´ı tˇechto algoritmu˚ dos´ahlo efektivnˇejˇs´ı komprese [1, 6, 14]. Existuj´ı
17
i algoritmy, kter´e se specializuj´ı na kompresi struktury XML, pˇriˇcemˇz vyuˇz´ıvaj´ı sch´emat XML (napˇr´ıklad DTD), nicm´enˇe i ty prov´ad´ı fin´aln´ı kompresi bˇezˇ nymi algoritmy [13]. ´ XML-aware algoritmy lze rozdˇelit do dvou z´akladn´ıch skupin — algoritmy s podporou dotazov´an´ı a algoritmy bez podpory dotazov´an´ı.
3.4
´ ı Komprese XML s podporou dotazovan´
Komprese s podporou dotazov´an´ı komprimuje vstupn´ı XML data a pˇri tom ponech´av´a moˇznost d´ale s daty pracovat i v komprimovan´e podobˇe. Motivace k pouˇzit´ı toho ˚ principu komprese XML nemus´ı byt zmenˇsen´ı datov´e n´aroˇcnosti se za´ cˇ istˇe z duvodu chov´an´ım dotazov´an´ı. Pr´ace s komprimovanymi daty a dekomprese pouze vybranych ´ ´ ˚ ze byt cˇ a´ st´ı XML muˇ stejn´eho XML v nekompri´ cˇ asovˇe m´enˇe n´aroˇcnˇejˇs´ı, neˇz analyza ´ movan´e podobˇe. Typickymi pˇredstaviteli t´eto kategorie jsou metody XGrind, XPRESS a ´ XQzip. 3.4.1
XGrind
˚ ktery´ se zaˇcal zabyvat XGrind je dle dostupnych ´ materi´alu˚ jedn´ım z prvn´ıch n´astroju, ´ problematikou komprese XML s podporou dotazov´an´ı. Podrobnˇejˇs´ı informace jsou k dispozici v [21]. ´ ´ XGrind oddˇeluje strukturu od dat a strukturu koduje slovn´ıkovym an´ım. U nˇej ´ kodov´ ´ koduje kaˇzdou znaˇcku jako T (tag) a atribut jako A n´asledovan´e jedineˇcnym ´ identifik´atorem. Pomoc´ı tohoto identifik´atoru se pak odkazuje do slovn´ıku, ktery´ obsahuje ˚ ´ ´ puvodn´ ı upln y´ z´apis znaˇcky nebo n´azvu atributu. Koncov´e znaˇcky se pak koduj´ ı speci´aln´ım znakem, XGrind pouˇz´ıv´a konkr´etnˇe symbol /. Pˇri dekompresi je koncov´a znaˇcka vˇzdy odvozena z kontextu11 , nen´ı tedy nutn´e pro konkr´etn´ı koncov´e znaˇcky vytv´arˇ et z´aznamy ve slovn´ıku. ´ Kodov´ an´ı struktury je homomorfn´ı, to znamen´a, zˇ e komprimovany´ soubor je tak´e strukturovany. n´astroji, jak´e ´ T´ım p´adem je moˇzn´e prohl´ızˇ et jej a zpracov´avat stejnymi ´ se pouˇz´ıvaj´ı pro pr´aci s XML v bˇezˇ n´e formˇe [21]. Tento pˇr´ıstup m´a nˇekolik vyhod: ´ ´ • Upravy dokumentu lze prov´adˇet pˇr´ımo v komprimovan´e verzi. • Lze vyuˇz´ıt osvˇedˇcen´e techniky vyvinut´e pro pr´aci s XML (analyza ´ cˇ i dotazov´an´ı). ˚ ci komprimovan´e verzi sch´e• Komprimovanou verzi XML dat je moˇzn´e ovˇerˇ it vuˇ matu XML dokumentu. XGrind pracuje specificky s vyˇ ´ ctovymi ´ typy. K jejich identifikaci vyuˇz´ıv´a DTD sch´ema ´ ´ a koduje je pomoc´ı log2 K kodov´ an´ı, kde K je celkovy´ poˇcet hodnot dan´e dom´eny vyˇ ´ ctov´eho typu [21]. Data XGrind komprimuje pomoc´ı bezkontextov´e komprese12 . Bezkontextov´a komˇ prese umoˇznuje lokalizovat rˇ etˇezce pˇr´ımo v komprimovanych datech bez nutnosti je ´ 11
ˇ Vzpomenme, zˇ e well-formed XML dokumenty nedovoluj´ı pˇrekˇr´ızˇ en´ı znaˇcek. ´ ˚ tak, zˇ e tyto kody ´ Bezkontextov´a komprese pˇriˇrazuje kody jednotlivym nejsou z´avisl´e na ´ rˇ etˇezcum aktu´aln´ı pozici dan´eho rˇ etˇezce ve zdrojov´em souboru dat. 12
18
˚ pˇri jejich hled´an´ı dekomprimovat. Toho se dosahuje jednoduchym protoˇze ´ zpusobem, hledany´ rˇ etˇezec je nejdˇr´ıve komprimov´an stejnou metodou, jak´a se pouˇzila pˇri kompresi vstupn´ıho souboru. Takto komprimovany´ rˇ etˇezec se pak pˇr´ımo hled´a v komprimovanych ´ datech. ´ Proto XGrind vyuˇz´ıv´a konkr´etnˇe neadaptivn´ı Huffmanovo kodov´ an´ı. Kontextov´e13 algoritmy, jako napˇr´ıklad LZ77, nejsou pro pouˇzit´ı v t´eto situaci vhodn´e. Pokud by se ˚ pouˇzila kontextov´a komprese, doˇslo by k n´arustu reˇzie nutn´e k dekompresi kaˇzd´eho rˇ etˇezce pˇred jeho porovn´an´ım s hledanou hodnotou a pˇred proveden´ım samotn´e dekomprese by musela aplikace vyhodnotit pozici rˇ etˇezce v souboru a podle toho urˇcit pˇr´ısluˇsn´e ´ kodov´ an´ı. ´ Pro zvyˇ an´ı rozd´ıln´e tabulky roz´ sen´ı efektivity komprese pouˇz´ıv´a XGrind pˇri kodov´ loˇzen´ı cˇ etnosti znaku˚ a to zvl´asˇ t’ pro jednotliv´e prvky a pro nevyˇ ´ ctov´e atributy. T´ım ˇ zohlednuje s´emantiku dat, protoˇze jak jiˇz bylo nˇekolikr´at zm´ınˇeno, data uloˇzen´a ve stejn´e struktuˇre byvaj´ ´ ı s´emanticky pˇr´ıbuzn´a. Architektura XGrind podporuje dotazov´an´ı v komprimovanych ´ datech v z´avislosti na typu dotazu. Dotazy na pˇresnou shodu, pˇri kterych se hled´a znaˇcka nebo atribut ´ pˇresnˇe se shoduj´ıc´ı s hledanym a dotazy na shodu prefixu, pˇri kterych ´ vyrazem ´ ´ se hled´a prefix znaˇcky odpov´ıdaj´ıc´ı hledan´e hodnotˇe. V obou pˇr´ıpadech XGrind komprimuje cestu dotazu a predik´at dotazu stejnou metodou, jakou pouˇzil pˇri kompresi dat. D´ıky tomu, zˇ e ´ se v obou pˇr´ıpadech vyuˇz´ıv´a bezkontextov´a komprese, odpov´ıdaj´ı kodovan´ e hodnoty dotazu pˇresnˇe hodnot´am v komprimovanych ´ datech. XGrind vyuˇz´ıv´a bajtov´e zarovn´an´ı ´ ˚ coˇz je mnohem rychlejˇs´ı (nikoliv bitov´e), tzn. porovn´av´an´ı prob´ıh´a vˇzdy na urovni bajtu, neˇz pˇri operac´ıch s jednotlivymi bity, nicm´enˇe nen´ı tak efektivn´ı. Teprve aˇz po nalezen´ı ´ poˇzadovan´eho prvku doch´az´ı k jeho dekompresi. U dotazu˚ na cˇ a´ steˇcnou shodu a rozsah ˚ komprimuje XGrind pouze cestu dotazu. Pˇri postupn´em pruchodu komprimovanych ´ dat pak vyhled´av´a vˇsechny shody hledan´e cesty a teprve u odpov´ıdaj´ıc´ıch prov´ad´ı dekompresi hodnot a vyhodnocen´ı dotazu. Tento typ dotazu je tedy n´aroˇcnˇejˇs´ı na vyhodnocen´ı. ˚ Dany´ zpusob dotazov´an´ı nen´ı zcela optim´aln´ı, jeho nedostatky jsou nast´ınˇeny v kapitole 3.4.3. 3.4.2
XPRESS
XPRESS je dalˇs´ım n´astrojem pro kompresi XML z rodiny algoritmu˚ podporuj´ıc´ıch dotazov´an´ı. Pˇri jeho n´avrhu vych´azeli autoˇri pˇredevˇs´ım z vlastnost´ı n´astroje XGrind. XPRESS pˇredstavil nov´e, efektivnˇejˇs´ı metody komprese XML a optimalizoval principy dotazov´an´ı v komprimovanych ´ datech [18]. ´ XPRESS vyuˇz´ıv´a automatick´e odvozen´ı datovych ´ typu˚ a prov´ad´ı jejich efektivn´ı koˇ dov´an´ı. Autoˇri se inspirovali XML-aware kompresorem XMill, ktery´ tak´e umoˇznuje efek´ tivnˇe kodovat specifick´e datov´e typy (cel´a cˇ ´ısla atp.), nicm´enˇe XPRESS narozd´ıl od XMill prov´ad´ı jejich automatickou detekci bez nutnosti uˇzivatelsk´eho z´asahu. Podporuje celkem sˇ est s´emantick´ych kompresoru, ˚ jejichˇz pˇrehled zobrazuje tabulka 1. S´emantick´e kom13
´ Pˇri kontextov´e kompresi jsou generovan´e kody z´avisl´e na pozici symbolu ve vstupn´ıch datech.
19
presory u8, u16, u32 a f32 jsou rozd´ılov´e kod´ery cˇ ´ıselnych ´ hodnot a kompresory dict8 a ´ huff jsou urˇcen´e pro kodov´ an´ı textu. kod ´ u8 u16 u32 f32 dict8 huff
popis kompresoru ´ kodov´ an´ı celych ´ cˇ ´ısel, kde max − min < 27 ´ kodov´ an´ı celych ´ cˇ ´ısel, kde 27 + 1 < max − min < 215 ´ kodov´ an´ı celych ´ cˇ ´ısel, kde 215 + 1 < max − min < 231 ´ kodov´ an´ı cˇ ´ısel s desetinnou cˇ a´ rkou ´ kodov´ an´ı vyˇ ´ ctovych ´ dat ´ Huffmanovo kodov´ an´ı textovych ´ dat
Tabulka 1: Pˇrehled s´emantickych ´ kompresoru˚ n´astroje XPRESS ´ XPRESS komprimuje data bezkontextovˇe — kodov´ an´ı prob´ıh´a bez z´avislosti na jeˇ jich pozici v souboru. To opˇet umoˇznuje prov´adˇet dotazov´an´ı pˇr´ımo v komprimovanych ´ datech. Vystup je, stejnˇe jako u XGrind, homomorfn´ı [18]. ´ ˚ XPRESS oddˇeluje strukturu od dat. Oproti ostatn´ım algoritmum, popsanych ´ v tomto ´ ´ textu, ale zcela jinak pˇristupuje k jej´ımu kodov´ an´ı. XPRESS nevyuˇz´ıv´a slovn´ıkov´e kodov´an´ı, ale reverzn´ı aritmetick´e k´odov´an´ı. Pˇri nˇem pˇriˇrazuje kaˇzd´e cestˇe, nebo jej´ı podmnoˇzinˇe, ´ jednoznaˇcny´ interval v rozmez´ı <0.0, 1.0). Reverzn´ı aritmetick´e kodov´ an´ı rozdˇeluje cely´ ˚ Kaˇzd´emu subinterval na subintervaly a jednotliv´e subintervaly jsou pˇriˇrazeny prvkum. ´ ern´a cˇ etnosti intervalu je pˇriˇrazen pr´avˇe jeden prvek. Velikost kaˇzd´eho intervalu je umˇ ˚ Podrobnosti postupu vypoˇ prvku (v pomˇeru k celkov´e cˇ etnosti prvku). ´ ctu intervalu jsou k dispozici napˇr´ıklad v [18]. ˚ Procesor dotazu Vyhodnocen´ı cesty dotazu pak pˇredstavuje vyhodnocen´ı intervalu. pˇrevede cestu dotazu (posloupnost prvku˚ od koˇrene k aktu´aln´ımu prvku) na interval ˚ stejnym jakym ´ zpusobem, ´ to provedl u cest bˇehem komprese XML. Pot´e vyhled´a ty prvky, kter´e odpov´ıdaj´ı dan´e cestˇe podle toho, zda interval cesty dotazu leˇz´ı v intervalu ˚ kter´e odpov´ıdaj´ı hledan´e cesty prvku. Vyhodnocen´ı dotazu pak prob´ıh´a pouze u prvku, cestˇe. Tento postup je tedy efektivnˇejˇs´ı, neˇz v pˇr´ıpadˇe XGrind, ktery´ porovn´av´a kaˇzdou ˚ cestu. Nicm´enˇe ani tento zpusob nen´ı zcela optim´aln´ı, jak je pops´ano v n´asleduj´ıc´ı kapitole 3.4.3. 3.4.3
XQzip
Autoˇri XQzip si vˇsimli u kompresn´ıch algoritmu˚ XGrind a XPRESS nˇekolika nedostatku˚ a navrhli dalˇs´ı metodu komprese XML s podporou dotazov´an´ı. XQZip rˇ eˇs´ı efektivnˇejˇs´ım ´ kodov´ an´ım struktury jak samotnou kompresi, tak i efektivnˇejˇs´ı dotazov´an´ı. Pro zvyˇ ´ sen´ı efektivity tak´e pracuje s vyrovn´avac´ı pamˇet´ı, pomoc´ı kter´e zrychluje prov´adˇen´ı opakovanych ´ cˇ i podobnych ´ dotazu˚ [7]. Nejdˇr´ıve k problematickym ´ parti´ım XGrind a XPRESS. XGrind mus´ı pˇri vyhodno´ cen´ı dotazu proch´azet cely´ dokument a u kaˇzd´eho zakodovan´ eho prvku cˇ i atributu mus´ı porovn´avat jeho cestu s cestou dotazu. Pokud se cesty shoduj´ı, dotaz se vyhodnot´ı. Pˇri
20
prov´adˇen´ı dotazu tak mus´ı proj´ıt cely´ soubor a porovn´avat jednotliv´e cesty. XPRESS rˇ eˇs´ı ´ ˇ tuto problematiku pomoc´ı reverzn´ıho aritmetick´eho kodov´ an´ı, kter´e odstranuje nutnost porovn´avat kaˇzdou cestu, protoˇze se s vyuˇzit´ım intervalu˚ vybere pouze odpov´ıdaj´ıc´ı podmnoˇzina cest. Nicm´enˇe i zde je nutn´e d´ale vyhodnotit cestu kaˇzd´eho prvku t´eto ˚ ze byt podmnoˇziny a tato podmnoˇzina muˇ ´ st´ale velmi obs´ahl´a (pˇredevˇs´ım u rozs´ahlych ´ ˚ u kterych XML dokumentu, ´ se cˇ asto opakuje stejn´a struktura). XGrind i XPRESS vytv´arˇ´ı ˇ homomorfn´ı vystup, ktery´ je stejnˇe strukturovany´ jako vstup, coˇz m´a pˇres zminovan´ e ´ vyhody i jednu nevyhodu — pokud se v dokumentu objevuje v´ıce dat um´ıstˇenych ´ ´ ´ ve ˚ stejn´e struktuˇre, doch´az´ı k n´arustu dat samotn´e struktury, protoˇze se uloˇzen´ı struktury nijak neoptimalizuje [7]. XQzip rˇ eˇs´ı oba uveden´e probl´emy zaveden´ım struktury SIT (Structure Index Tree), d´ıky kter´e doch´az´ı k odstranˇen´ı duplikovanych struktur. Pomoc´ı hashovac´ıch tabulek ´ ˚ t´eto struktury. XQzip dok´apak pˇriˇrazuje komprimovan´e bloky dat jednotlivym ´ prvkum ˚ zˇ e efektivnˇeji vyhodnocovat dotazy, protoˇze nemus´ı prohled´avat celou puvodn´ ı strukturu, ale pouze optimalizovanou v podobˇe SIT [7]. XQzip podporuje sˇ irˇs´ı sˇ k´alu XPath dotazu˚ [7], nab´ız´ı tak rozs´ahlejˇs´ı moˇznosti dotazovan´ı v komprimovanych ´ datech, neˇz jak je tomu u XGrind cˇ i XPRESS. Dalˇs´ı optimalizaˇcn´ı technikou, kterou XQzip vyuˇz´ıv´a, je buffer-pool, ktery´ v pamˇeti udrˇzuje posledn´ı dekomprimovan´e bloky dat, cˇ ´ımˇz se cˇ a´ steˇcnˇe ˇ odstranuje reˇzie potˇrebn´a pro opakovanou dekompresi dat u podobnych ´ cˇ i stejnych ´ dota˚ zu. Dalˇs´ı podrobnosti o XQzip jsou k dispozici napˇr´ıklad v [7].
3.5
´ ı Komprese XML bez podpory dotazovan´
Kategorie kompresn´ıch algoritmu˚ bez podpory dotazovan´ı zahrnuje ty algoritmy, kter´e komprimuj´ı XML data s vyuˇzit´ım s´emantickych ´ informac´ı (z´ıskanych ´ ze struktury XML). Pokud ale chceme s daty pracovat, mus´ıme je nejdˇr´ıve jako celek dekomprimovat, pak zpracovat a n´aslednˇe opˇet jako celek komprimovat. Do t´eto kategorie patˇr´ı napˇr´ıklad XMill, MHMPPM (XMLPPM), SCMPPM a Xml Structure Compression. Prvn´ı tˇri pˇredstavitel´e — XMill, XMLPPM a SCMPPM — pracuj´ı na stejn´em principu. Zpracov´avaj´ı a pˇripravuj´ı XML data tak, aby vyuˇzili co nejv´ıce vlastnost´ı kompresn´ıch ˚ kter´e pouˇz´ıvaj´ı k fin´aln´ı kompresi. Mezi ty patˇr´ı pˇredevˇs´ım GZip, BZip2 a algoritmu, PPM. Metoda Xml Structure Compression se nezabyv´ ´ a kompres´ı samotnych ´ dat, ale speciali´ zuje se na efektivn´ı kodov´ an´ı struktury. K tomu vyuˇz´ıv´a sch´emata XML, konkr´etnˇe DTD. 3.5.1
XMill
˚ XMill [14] patˇr´ı mezi nejzn´amˇejˇs´ı pˇredstavitele t´eto kategorie kompresn´ıch algoritmu. Jako jeden z prvn´ıch pouˇzil myˇslenku komprimovat XML oddˇelen´ım struktury od dat a ´ data seskupit podle jejich s´emantick´e pˇr´ıbuznosti. Struktura se koduje pomoc´ı slovn´ıkov´eho ´ kodov´ an´ı, znaˇcky a n´azvy atributu˚ jsou tedy m´ısto neust´al´eho vypisov´an´ı nahrazeny ˚ ´ odkazy do slovn´ıku. Uˇz jen tento zpusob kodov´ an´ı zaruˇc´ı sn´ızˇ en´ı datov´e n´aroˇcnosti ´ kodovan ych dat. Data se ukl´adaj´ı oddˇelenˇe, seskupen´a podle s´emantick´eho vyznamu ´ ´
21
(jinak rˇ eˇceno podle jejich um´ıstˇen´ı v XML), a pak se komprimuj´ı nˇekterym ´ z bˇezˇ nych ´ al˚ Puvodn´ ˚ goritmu. ı verze XMill podporuje metody Deflate, BZip2 a PPM. Tomuto n´astroji se v t´eto diplomov´e pr´aci vˇenujeme podrobnˇeji a jeho popisu je vˇenov´ana speci´aln´ı kapitola, konkr´etnˇe kapitola 4. 3.5.2
MHMPPM (XMLPPM)
MHMPPM (Multiplexed Hierarchical Modeling based on Prediction by Parital Match) [6] pˇred˚ stavuje dalˇs´ı zpusob komprese XML zaloˇzeny´ na obdobn´em principu, jaky´ pouˇz´ıv´a XMill. ˚ ´ Rozd´ıl mezi nimi je pˇredevˇs´ım ve zpusobu kodov´ an´ı struktury a samotnych ´ dat. MHMPPM je zaloˇzen na pouˇzit´ı metody PPM [6]. MHMPPM pracuje dvouf´azovˇe. V ´ prvn´ı f´azi prob´ıh´a kodov´ an´ı vstupn´ıho XML metodou ESAX (Encoded SAX) a v druh´e ´ f´azi je vystup ESAX kodov´ an pomoc´ı metody PPM. ´ ˚ ´ Bˇehem prvn´ıch experimentu˚ se autoˇri zamˇerˇ ili na odliˇsny´ zpusob kodov´ an´ı, neˇz jaky´ pouˇz´ıv´a XMill. Zvolili ESAX, ktery´ je zaloˇzen na SAX modelu, kdy se jednotliv´e ud´alosti ´ vyvol´avan´e SAX analyz´atorem koduj´ ı dle n´asleduj´ıc´ıho postupu. Jednotliv´e ud´alosti (za´ ˚ Pˇri cˇ a´ tek znaˇcky, konec znaˇcky, atributy, pozn´amky, . . . ) se koduj´ ı jako sekvence bajtu. ˚ V pˇr´ıpadˇe, zˇ e jejich tvorbˇe si kod´er a dekod´er udrˇzuj´ı konzistentn´ı tabulky symbolu. ´ a ten zap´ısˇ e do kod´er naraz´ı na novy, ´ dosud nezn´amy´ symbol, pˇriˇrad´ı mu novy´ kod ´ pak zap´ısˇ e jeho samotnou hodnotu. Pˇri opakovan´em vystupu. Ihned za kaˇzdy´ novy´ kod ´ ´ ´ kodov´ an´ı stejn´eho symbolu (ˇretˇezce) se pak do vystupu zapisuje pouze dany´ kod. ´ ´ Uk´azku kodov´ an´ı pomoc´ı ESAX si uk´azˇ eme na pˇr´ıkladu n´asleduj´ıc´ı znaˇcky [6]: <elt att ="asdf">XYZ Nyn´ı budeme pˇredpokl´adat, zˇ e kod´er jiˇz v minulosti narazil na znaˇcku <elt> a pˇriˇra´ 10. Naopak na atribut att v tuto chv´ıli naraz´ı poprv´e a pˇriˇrad´ı mu prvn´ı dostupdil ji kod ´ pro atributy, coˇz je 0D. Vysledek ´ ny´ volny´ kod kodov´ an´ı pak bude n´asleduj´ıc´ı [6]: ´ <elt | att = | "asdf" | > | XYZ | 10| 0D a t t 00 | a s d f 00 | FF | FE X Y Z 00 | FF ´ Takto kodovan y´ vystup je bˇehem druh´e f´aze komprimov´an metodou PPM nebo jinou ´ dostupnou metodou komprese dat. Dalˇs´ım vylepˇsen´ım algoritmu bylo pouˇzit´ı metody Multiplexed Hierarchical Modeling. ˚ ´ U puvodn´ ı varianty vyuˇz´ıval ESAX bˇehem kodov´ an´ı pouze jeden model, pomoc´ı kter´e´ ho postupnˇe zapisoval kodovan´ a data. Nov´a metoda pouˇz´ıv´a celkem cˇ tyˇri modely, mezi kterymi pˇrep´ın´a14 a do kterych zapisuje vystup. Jedn´a se o modely pro n´azvy prvku˚ a ´ ´ ´ ˚ vlastn´ı stav, atributu, ˚ strukturu prvku, ˚ atributy a rˇetˇezce. Kaˇzdy´ model si pak udrˇzuje svuj ale vˇsechny cˇ tyˇri modely sd´ılej´ı spoleˇcny´ aritmeticky´ kod´er [6]. ´ N´asˇ dˇr´ıve uvedeny´ pˇr´ıklad by se do jednotlivych n´asle´ modelu˚ rozdˇelil a zakodoval dovnˇe [6]: 14
Odtud n´azev multiplexed.
22
Prvky: Att: Znaky: Symb:
| <elt |10 | | |
| att = | | 0D | | a t t | 00
| "asdf" | > | | | a s d f 00 | FF | | | |
| XYZ | FE | | X Y Z | 00 | |
| | FF | | |
Pouˇzit´ım nˇekolika od sebe oddˇelenych u˚ predikce ´ modelu˚ se dosahuje lepˇs´ıch vysledk ´ pravdˇepodobnosti symbolu˚ a dosahuje se tak efektivnˇejˇs´ı komprese. MHMPPM vyuˇz´ıv´a jeˇstˇe dalˇs´ı optimalizaˇcn´ı techniky, kdy do jednotlivych modelu˚ vkl´ad´a dalˇs´ı pomocn´e ´ ˚ Podrobnosti v [6]. informace, aby metoda PPM dos´ahla jeˇstˇe lepˇs´ıch vysledk u. ´ 3.5.3
SCMPPM
Dalˇs´ı metodou komprese XML vyuˇz´ıvaj´ıc´ı PPM je SCMPPM (Structural Contexts Model and Prediction by Partial Matching). Kombinuje obecny´ model pro kompresi strukturovanych ´ dokumentu˚ SCM (Structural Context Model) a kompresn´ı techniku PPM (Prediction by Partial Matching) [1]. ˚ ktery´ vych´az´ı z mySCM je obecny´ model komprese strukturovanych ´ dokumentu, sˇ lenky, zˇ e informace uloˇzen´e ve stejn´e struktuˇre budou m´ıt velmi podobnou slovn´ıkovou distribuci a naopak, zˇ e informace uloˇzen´e v odliˇsn´e struktuˇre budou m´ıt tuto distribuci odliˇsnou [1]. I zde se tedy pˇredpokl´ad´a, zˇ e data ve stejn´e struktuˇre jsou s´emanticky pˇr´ıbuzn´a a jejich seskupen´ım se bude dosahovat lepˇs´ıch vysledk u˚ komprese. Mohou ale ´ existovat i pˇr´ıpady, zˇ e i data z odliˇsnych ´ struktur jsou s´emanticky pˇr´ıbuzn´a. Pˇredstavme si informace o kniˇzn´ıch z´aznamech, kde mohou byt ´ informace o autorovi knihy a d´ale ˚ informace o lidech, kteˇr´ı knihy nˇejakym revidovali nebo hodnotili — vˇsechny ´ zpusobem ’ tyto z´aznamy, byt um´ıstˇen´e v jin´e struktuˇre, obsahuj´ı jm´ena lid´ı. Proto SCM prov´ad´ı heuristick´e sluˇcov´an´ı s´emanticky pˇr´ıbuznych ´ skupin do spoleˇcn´eho kontextu [1]. SCMPPM udrˇzuje PPM model pro kaˇzdy´ kontext. Ty se vytv´arˇ´ı a udrˇzuj´ı pro kaˇzdou ˚ strukturu. Bˇehem pruchodu skrz XML pak SCMPPM mezi jednotlivymi modely pˇrep´ın´a ´ ´ a zapisuje do nich data. Kodov´ an´ı vystupu pouˇz´ıv´a sd´ıleny´ aritmeticky´ kod´eru. SCMPPM ´ ´ pˇrep´ın´an´ı modelu˚ je uveden na vypisu obsahuje vˇzdy jeden vychoz´ ı model. Pseudokod ´ ´ algoritmu 5. SCMPPM pracuje na velmi podobn´em principu jako XMill. Dalˇs´ı podrobnosti o t´eto metodˇe jsou k dispozici pˇredevˇs´ım v [1]. 3.5.4
Komprese struktury XML
Doposud popsan´e metody komprese XML se zamˇerˇ uj´ı na vyuˇzit´ı s´emantickych infor´ mac´ı pˇr´ıtomnych ´ v XML datech k seskupen´ı s´emanticky pˇr´ıbuznych ´ dat a n´aslednˇe je˚ Strukturu koduj´ ´ jich kompresi nˇekterym ı s vyuˇzit´ım ´ z bˇezˇ nych ´ kompresn´ıch algoritmu. ´ slovn´ıkov´eho kodov´ an´ı, kter´e ale nijak d´ale neoptimalizuj´ı. Xml Structure Compression ´ [13] (komprese struktury Xml) se zabyv´ struk´ a pˇredevˇs´ım moˇznost´ı efektivnˇeji kodovat turu XML a to v pˇr´ıpadˇe, zˇ e je k dispozici ke konkr´etn´ımu jazyku jeho sch´ema DTD. Document Type Definition (DTD) definuje strukturu XML dokumentu t´ım, zˇ e urˇcuje ˚ DTD lze vloˇzit pˇr´ımo do XML (inline), nebo jej lze seznam povolenych ´ prvku˚ a atributu. pouˇz´ıt pomoc´ı reference na extern´ı soubor [30].
23
Algoritmus 5 Pˇrep´ın´an´ı modelu˚ MHMPPM 1: aktualniM odel ← def aultM odel 2: while existuje slovo ke zpracov´ an´ı do 3: slovo ← prectiDalsiSlovo() 4: for all symbol ze slovo do 5: kodujDekduj(symbol, aktualniM odel) 6: end for 7: if slovo je then 8: ulozNaZasobnik(aktualniM odel) 9: aktualniM odel ← modelP roSlovo 10: else 11: if slovo je then 12: aktualniM odel ← vyzvedniM odelZeZasobniku() 13: end if 14: end if 15: end while
Obr´azek 3: Pˇr´ıklad DTD [13] Princip komprese je n´asleduj´ıc´ı — eliminovat informace definovan´e ve sch´ematu, kter´e se nach´azej´ı redundantnˇe tak´e v samotn´em XML souboru. Komprese struktury pracuje s DTD sch´ematem, ze kter´eho jeho analyzou z´ısk´av´a charakteristiku XML doku´ ˚ kter´e jsou vuˇ ˚ ci nˇemu validn´ı. Tyto informace pak pouˇz´ıv´a k efektivn´ımu kodov´ ´ mentu, an´ı struktury konkr´etn´ıho XML dokumentu. Postup komprese si uk´azˇ eme na jednoduch´em pˇr´ıkladu. Vzorov´e sch´ema DTD je ˚ ci nˇemu validn´ı vzorov´a XML data jsou pak zobrazena na zn´azornˇeno na obr´azku 3, vuˇ ˚ ci DTD obr´azku 4 (pro spr´avnou kompresi je nutn´e, aby konkr´etn´ı XML data byla vuˇ ˚ Napˇr´ıklad u prvku book specivalidn´ı). Dan´e DTD sch´ema popisuje celkem sˇ est prvku. fikuje, zˇ e jeho prvn´ı podˇr´ızeny´ prvek bude prvek author, druhy´ title a d´ale bude n´asle˚ podˇr´ızeny´ prvek mus´ı dovat jeden nebo v´ıce prvku˚ chapter. Prvek chapter pak jako svuj obsahovat prvek title, za kterym ´ mus´ı n´asledovat jeden nebo v´ıce prvku˚ paragraph nebo figure. Podrobn´e informace o pravidlech z´apisu DTD jsou k dispozici napˇr´ıklad v [30]. ˚ patrnych ´ Vzhledem k uvedenym nˇekter´e in´ pravidlum ´ z DTD, nen´ı nutn´e kodovat formace pˇr´ımo do struktury XML. Napˇr´ıklad prvek book mus´ı obsahovat jako sv´e pod´ rˇ´ızen´e prvky author a title v dan´em poˇrad´ı. Proto je nutn´e do vystupu zakodovat pouze ´ informaci o poˇctu n´asleduj´ıc´ıch prvku˚ paragraph nebo figure. V naˇsem pˇr´ıpadˇe tedy hod-
24
Darrell Huff < title >How to Lie with Statistics < title >Introduction <paragraph>With prospects of ... <paragraph>Then a Sunday newspaper ... [ 8 more paragraphs ] < title >The Sample with the Built−in Bias [ 53 paragraphs and 7 figures ]
Obr´azek 4: Pˇr´ıklad XML pro kompresi pomoc´ı DTD [13] notu 11 (dekadicky), coˇz odpov´ıd´a souˇctu jednoho prvku figure a deseti prvku˚ paragraph. Analogicky postupujeme pro dalˇs´ı prvky. Bˇehem f´aze dekomprese se k odvozen´ı pouˇzitych ´ dat). ´ pravidel pouˇzije opˇet dan´e DTD (kter´e je souˇca´ st´ı komprimovanych ´ Komprimovany´ vystup se pak skl´ad´a celkem ze tˇr´ı cˇ a´ st´ı — DTD, kodovan´ e struk´ tury a dat. Ke kompresi dat lze pouˇz´ıt nˇekterou z metod, kterou vyuˇz´ıvaj´ı dˇr´ıve popsan´e kompresory XML. Podrobnosti a pˇr´ıklady komprese struktury jsou d´ale k dispozici v [13].
25
4
XMill
XMill [14] je specializovany´ n´astroj pro kompresi XML dat. Z´akladn´ım principem jeho komprese je zpracov´an´ı a pˇr´ıprava XML dat tak, aby existuj´ıc´ı kompresn´ı algoritmy ˚ neˇz jak´e dosahuj´ı pˇri kompresi XML jako celku. K pˇr´ıpravˇe dos´ahli lepˇs´ıch vysledk u, ´ dat se vyuˇz´ıvaj´ı s´emantick´e informace pˇr´ıtomn´e v XML datech — znaˇcky, kter´e urˇcuj´ı vyznam obsahu v nich uzavˇren´em. ´ XMill je zaloˇzeny´ na knihovnˇe zlib (podporuje tedy kompresi pomoc´ı GZip a BZip2) ˇ a vyuˇz´ıv´a nˇekolik vlastn´ıch s´emantick´ych kompresoru. ˚ Architektura XMill nav´ıc umoˇznuje rozˇs´ırˇ en´ı o dalˇs´ı uˇzivatelsky definovan´e kompresory pro komplexn´ı a specifick´a data ˚ ych ruzn ´ aplikac´ı [14]. ´ esˇ n´e komprese u dat, jeXMill vych´az´ı z toho, zˇ e slovn´ıkov´e algoritmy dosahuj´ı uspˇ jichˇz slovn´ıkov´e rozloˇzen´ı je podobn´e. XMill pˇredpokl´ad´a, zˇ e data um´ıstˇen´a uvnitˇr stejn´e struktury jsou s´emanticky pˇr´ıbuzn´a — napˇr´ıklad vˇsechna data um´ıstˇen´a ve struktuˇre budou obsahovat jm´ena autoru˚ knihy — a tud´ızˇ budou m´ıt podobn´e slovn´ıkov´e rozloˇzen´ı [14]. ˚ kter´e prob´ıh´a auVedle pˇr´ıpravy dat seskupov´an´ım s´emanticky pˇr´ıbuznych ´ prvku, ˇ tomaticky na z´akladˇe struktury XML dokumentu, umoˇznuje XMill d´ale ruˇcnˇe doladit parametry komprese uˇzivatelskym ´ z´asahem dle jeho osobn´ıch znalost´ı komprimovan´eho ´ XML, pˇredevˇs´ım jeho struktury. Jednou z moˇznost´ı je uprava automatick´eho seskupov´an´ı s´emanticky pˇr´ıbuznych dat. Typicky´ je jiˇz zm´ınˇeny´ pˇr´ıklad se jm´eny autoru˚ kniˇzn´ıch ´ ˚ ke kterym ˚ zeme pˇridat dalˇs´ı jm´ena lid´ı, kteˇr´ı se na pˇr´ıpravˇe knih nˇejakym titulu, ´ muˇ ´ ˚ zpusobem pod´ıleli. Tyto informace jsou ale vˇetˇsinou k dispozici v jin´e struktuˇre, napˇr´ıklad v , ale protoˇze se st´ale jedn´a o jm´ena, bude vhodn´e je seskupit a komprimovat jako jednu skupinu. K dosaˇzen´ı efektivnˇejˇs´ı komprese vyuˇz´ıv´a XMill typovˇe z´avisl´e kompresory15 . Po´ moc´ı nich se snaˇz´ı kodovat specifick´e informace do efektivnˇejˇs´ı bin´arn´ı podoby. XMill nenab´ız´ı automatickou detekci datovych ´ typu˚ 16 , ale nech´av´a definici na uˇzivateli. Uˇzivatel ˚ ze urˇcit dvojici struktura-datov´y typ a bˇehem komprese je text v dan´e struktuˇre tak muˇ analyzov´an a pˇreveden na odpov´ıdaj´ıc´ı datovy´ typ v bin´arn´ı podobˇe. Zcela pˇrirozen´e je pouˇz´ıt tuto myˇslenku na cˇ ´ıseln´e hodnoty. XMill nab´ız´ı celkem osm vestavˇenych ´ s´eman˚ jejich seznam je uveden v tabulce 2. tickych ´ kompresoru, S´emantick´e kompresory je moˇzn´e d´ale kombinovat. K dispozici jsou sekvenˇcn´ı, stˇr´ıdav´y ´ a opakovan´y kompresor. Sekvenˇcn´ı kompresor lze pouˇz´ıt napˇr´ıklad ke kodov´ an´ı IP adres17 . Vzhledem k form´atu IP adresy (ˇctyˇri cˇ ´ısla v rozsahu 0–255, oddˇelen´a navz´ajem teˇckou, ´ napˇr´ıklad 192.168.10.50) je moˇzn´e zakodovat ji jako cˇ tveˇrici jednobajtovych ´ hodnot. Vyˇ ´ cet vˇsech sekvenˇcn´ıch kompresoru˚ je uveden v tabulce 3. ˇ Architektura XMill umoˇznuje rozˇs´ırˇ it nab´ıdku s´emantickych ´ kompresoru˚ pomoc´ı uˇzivatelsk´ych kompresoru. ˚ Ty se k XMill pˇripojuj´ı pomoc´ı specializovan´eho API18 rozhran´ı SCAPI (Semantic Compressor API). Vyhodou pouˇzit´ı vlastn´ıch s´emantickych ´ ´ kompresoru˚ 15
Nˇekdy oznaˇcovan´e jako s´emantick´e kompresory. Automatickou detekci vyuˇz´ıv´a napˇr´ıklad n´astroj pro kompresi dat s podporou dotazov´an´ı XPRESS 17 IP adresa identifikuje s´ıt’ov´e rozhran´ı v poˇc´ıtaˇcov´e s´ıti pˇri pouˇzit´ı IP protokolu. 18 Application Programming Interface, rozhran´ı pro programov´an´ı aplikac´ı. 16
Tabulka 2: Standardn´ı s´emantick´e kompresory XMill kod ´ seq alt rep
popis kompresoru Sekvenˇcn´ı kompresor seq(s1 s2 . . . ). Stˇr´ıdavy´ kompresor or(s1 s2). Opakovany´ kompresor rep(ds), kde d je oddˇelovaˇc a s s´emanticky´ kompresor. Tabulka 3: Kombinovan´e kompresory XMill
˚ ze byt muˇ ´ pˇresn´e c´ılen´ı komprese na specifickou dom´enu. Pˇri jejich pouˇzit´ı se ale st´av´a komprimovany´ soubor z´avisly´ na dan´em kompresoru a nen´ı bez nˇej moˇzn´e prov´est dekompresi. Dalˇs´ı podrobnosti o s´emantickych ´ kompresorech a jejich kombinov´an´ı jsou k dispozici v [14].
4.1
Architektura XMill
Architektura XMill je postavena na tˇrech z´akladech. Prvn´ım je oddˇelen´ı struktury od dat, druhym dat a tˇret´ım komprese pomoc´ı exis´ seskupen´ı s´emanticky pˇr´ıbuznych ´ tuj´ıc´ıch kompresn´ıch algoritmu. ˚ Model architektury je zn´azornˇen na obr´azku 5 [14]. Nyn´ı si pop´ısˇ eme z´akladn´ı prvky architektury. SAX parser analyzuje vstupn´ı XML data a identifikuje strukturu a obsah XML dat. Analyzovan´e cˇ a´ sti pos´ıl´a d´ale ke zpracov´an´ı do Path Procesoru. Path procesor je zodpovˇedny´ za mapov´an´ı jednotlivych ´ elementu˚ z´ıskanych ´ ze SAX ˚ Path Processor lze ovlivnit definov´an´ım uˇzivaparseru do odpov´ıdaj´ıc´ıch kontejneru. ˚ coˇz je v podstatˇe vlastn´ı definice s´emanticky pˇr´ıbuznych telskych u, ´ vyraz ´ ´ dat. Kontejnery obsahuj´ı data a jsou vytv´arˇ eny dle potˇreby. Path Processor rozhoduje o tom, zda dany´ prvek um´ıst´ı do jiˇz existuj´ıc´ıho kontejneru, nebo zda vytvoˇr´ı kontejner novy. ´ Ke kaˇzd´emu kontejneru je pˇriˇrazen pr´avˇe jeden s´emanticky´ kompresor. Existuj´ı tak´e speci´aln´ı kontejnery, jako napˇr´ıklad kontejner struktury.
27
Obr´azek 5: Model architektury XMill [14] S´emanticky´ kompresor je zodpovˇedny´ za anal´yzu dat vstupuj´ıc´ıch do kontejneru a jejich uloˇzen´ı v odpov´ıdaj´ıc´ım datov´em form´atu19 . Z´akladn´ım s´emantickym ´ kompresorem ˚ je textov´y kompresor, ktery´ vstupn´ı data vubec neupravuje a um´ıst’uje je pˇr´ımo do kontejneru˚ jako rˇ etˇezce. Pˇrehled vˇsech s´emantickych ´ kompresoru˚ ukazuje tabulka 2. Napˇr´ıklad s´emanticky´ kompresor pro celoˇc´ıseln´e hodnoty vstupn´ı data analyzuje a pˇrev´ad´ı na bin´arn´ı hodnotu. V pˇr´ıpadˇe, zˇ e analyza ´ s´emantickym ´ kompresorem selˇze, pˇred´a se hodnota dalˇs´ımu, v hierarchii nadˇr´ızen´emu s´emantick´emu kompresoru. Na vrcholu hierarchie je vychoz´ ı textovy´ kompresor, tzn. zˇ e nejpozdˇeji zde se podaˇr´ı danou hodnotu do ´ nˇekter´eho z kontejneru˚ um´ıstit. Komprese dat prob´ıh´a nad pamˇet’ov´ym oknem20 . Pamˇet’ov´e okno je kompresorem rezervovan´a pamˇet’, do kter´e se postupnˇe zapisuj´ı doposud zpracovan´e informace. Velikost pamˇet’ov´eho okna je voliteln´a. Standardn´ı XMill pracuje ve vychoz´ ım nastaven´ı ´ ’ s pamˇet ovym ´ oknem o velikosti 8MB, naˇsi implementaci SXMill jsme pˇri experimentech nejˇcastˇeji pouˇz´ıvali s velikost´ı okna 32MB21 . Jakmile dojde k zaplnˇen´ı pamˇet’ov´eho okna, pˇrejde se k f´azi komprese tohoto okna. Bˇehem n´ı se postupnˇe komprimuj´ı jednotliv´e cˇ a´ sti okna — kontejnery. Kaˇzdy´ kontejner je komprimov´an zvl´asˇ t’ do samostatn´eho komprimovan´eho bloku dat a to pomoc´ı urˇcen´eho kompresoru (gzip, bzip2, ppmdi atd.). Takto komprimovan´e bloky se postupnˇe za sebou ukl´adaj´ı na vystup. Obecnˇe by komprimova´ 19
Napˇr´ıklad pˇrevod cel´eho cˇ ´ısla z textov´e podoby do bin´arn´ı. Memory window v terminologii XMill. 21 ´ cinnost komprese u modern´ıch textovych ˚ v´ıce viz Velikost pamˇet’ov´eho okna m´a vliv na uˇ ´ kompresoru, vysledky testov´an´ı. ´ 20
28
Typ (1) Otev´ırac´ı znaˇcky (2) N´azvy atributu˚ (3) Hodnoty (data) (4) Koncov´e znaˇcky
˚ ymi ny´ soubor mohl obsahovat bloky komprimovan´e ruzn kompresory (za pˇredpokladu, ´ zˇ e kaˇzdy´ blok je uvozen hlaviˇckou — coˇz standardnˇe je), nicm´enˇe v praxi se vyuˇz´ıv´a v r´amci jednoho souboru pouze jedna kompresn´ı metoda. ´ Pamˇet’ov´e okno je rezervovan´e m´ısto v pamˇeti, do kter´eho XMill ukl´ad´a kodovan´ a data. Um´ıst’uje se zde hlaviˇcka, kontejner struktury, datov´e a dalˇs´ı speci´aln´ı kontejnery. V okamˇziku zaplnˇen´ı pamˇet’ov´eho okna, popˇr. po dosaˇzen´ı konce vstupn´ıho XML souboru, vznik´a bˇeh, ktery´ je ihned komprimov´an a zaps´an na vystup. ´ Bˇeh22 je term´ın, kterym ı kom´ se oznaˇcuj´ı data jednoho pamˇet’ov´eho okna. Vystupn´ ´ ˚ primovany´ soubor se skl´ad´a z jednoho nebo v´ıce po sobˇe n´asleduj´ıc´ıch bˇehu.
4.2
´ ´ ı ukazkov ´ ´ Pˇr´ıklad kodov an´ eho XML
Pˇri zpracov´an´ı vstupn´ıho souboru prov´ad´ı XMill nˇekolik operac´ı, jejichˇz vysledkem je ´ vystup s´erie komprimovanych ´ ´ dat. Princip komprese si uk´azˇ eme na pˇr´ıkladu XML, ktery´ je uveden na obr´azku 6. V tabulce 4 je uveden pˇrehled cˇ a´ st´ı vyskytuj´ıc´ıch se v uveden´em XML. Pˇri zpracov´an´ı vstupn´ıch dat prov´ad´ı XMill postupnˇe tyto operace: 1. Oddˇelen´ı struktury od dat. 2. Zpracov´an´ı dat s´emantickymi kompresory. ´ ˚ 3. Um´ıstˇen´ı dat do odpov´ıdaj´ıc´ıch kontejneru. 4. Komprese jednotlivych ´ kontejneru˚ (kaˇzd´eho zvl´asˇ t’) zvolenou kompresn´ı metodou. 5. Z´apis komprimovanych ıho souboru. ´ dat do vystupn´ ´ Body 1 aˇz 3 prob´ıhaj´ı bˇehem analyzy ´ vstupn´ıch dat (odpovˇednost maj´ı komponenty SAX Parser, path processor a jednotliv´e s´emantick´e kompresory), body 4 a 5 prob´ıhaj´ı po naplnˇen´ı pamˇet’ov´eho okna (nebo po dosaˇzen´ı konce vstupn´ıch XML dat). ´ ´ Struktura se koduje pomoc´ı slovn´ıkov´eho kodov´ an´ı, kde n´azvy znaˇcek (1) a atributu˚ (2) se oznaˇcuj´ı jako n´avˇesˇ t´ı a kaˇzd´e nov´e, doposud nezn´am´e n´avˇesˇ t´ı se pˇrid´a na konec slovn´ıku. XMill udrˇzuje speci´aln´ı kontejner struktury (na modelu je vidˇet zcela vlevo). Do ˚ nˇej se ukl´adaj´ı informace o struktuˇre XML dokumentu v podobˇe jednoduchych ´ pˇr´ıkazu. 22
Obr´azek 6: XMill – uk´azkovy´ fragment XML pro pˇr´ıklad zpracov´an´ı dat Tyto pˇr´ıkazy jsou napˇr. , , , kde parametr id pˇredstavuje odkaz na konkr´etn´ı n´avˇesˇ t´ı, resp. kontejner. U ˚ ˚ ehu komnˇekterych uv´adˇen, protoˇze je patrny´ z kontextu prubˇ ´ pˇr´ıkazu˚ nen´ı odkaz vubec prese cˇ i dekomprese (napˇr´ıklad vloˇzen´ı koncov´e znaˇcky, protoˇze well-formed XML nedovoluje pˇrekˇr´ızˇ en´ı znaˇcek). ´ ˚ Napˇr´ıklad pro rozliˇsen´ı odkazu na XMill vyuˇz´ıv´a sofistikovan´e kodov´ an´ı pˇr´ıkazu. n´avˇesˇ t´ı od odkazu na kontejner se vyuˇz´ıv´a znam´enka u indexu. Zda se m´a dan´e n´avˇesˇ t´ı ˚ ehu zpracov´an´ı dat. Veˇsker´e pˇr´ıkazy zpracovat jako znaˇcka nebo atribut, je patrn´e z prubˇ jsou tak v kontejneru struktury uloˇzeny jako jedna hodnota — cˇ ´ıslo. Z´aporn´a cˇ ´ısla odkazuj´ı na datov´e kontejnery, kladn´a cˇ ´ısla pak na znaˇcky a atributy. Speci´aln´ı pˇr´ıkazy (vloˇzen´ı koncov´e znaˇcky apod.) maj´ı pˇridˇelenu konstantn´ı hodnotu reprezentuj´ıc´ı dany´ pˇr´ıkaz a je jim vyhrazen prostor v rozsahu indexu˚ n´avˇesˇ t´ı, kdy cˇ ´ısla do urˇcit´e hodnoty pˇredstavuj´ı speci´aln´ı pˇr´ıkazy a nad touto hodnotou se jedn´a o odkazy do slovn´ıku (ab˚ solutn´ı hodnotu indexu z´ısk´ame po odeˇcten´ı konstanty poˇctu definovanych ´ pˇr´ıkazu). Data (3) se vkl´adaj´ı do samostatnych ´ kontejneru˚ a to v z´avislosti na jejich um´ıstˇen´ı ve struktuˇre XML dokumentu. V kontejneru struktury se po jejich um´ıstˇen´ı do konkr´etn´ıho kontejneru vytvoˇr´ı pˇr´ıkaz odkazuj´ıc´ı na pˇr´ısluˇsny´ kontejner. ´ ktery´ se jako pˇr´ıkaz Vˇsem koncov´ym znaˇck´am (4) je pˇridˇelen speci´aln´ı konstantn´ı kod, vkl´ad´a do kontejneru struktury. Koncov´a znaˇcka se pˇrid´av´a i na konci kaˇzd´eho atributu. Tabulka 5 ukazuje slovn´ık n´avˇesˇ t´ı naplnˇeny´ tak, jak by vypadal po zpracov´an´ı uk´azkov´eho XML souboru. Rozliˇsen´ı znaˇcky a atributu nen´ı nikde uloˇzeno, jak jiˇz bylo zm´ınˇeno, je patrn´e z kontextu bˇehem zpracov´an´ı dat. V tabulce je uvedeno pouze pro orientaci. Bˇehem zpracov´an´ı uk´azkovych ´ XML dat dojde k vytvoˇren´ı nˇekolika datovych ´ kon˚ Jejich pˇrehled ukazuje tabulka 6. V tabulce jsou v cestˇe odliˇseny atributy od tejneru. znaˇcek pomoc´ı znaku @. Jak je patrn´e, pro kaˇzdou znaˇcku nebo atribut dan´e struktury je vytvoˇren jeden kontejner, do kter´eho jsou um´ıst’ov´any postupnˇe za sebou zpracovan´a
30
Kod ´ 1 2 3 4 5 6 7 8 9
Typ Znaˇcka Znaˇcka Atribut Atribut Znaˇcka Znaˇcka Znaˇcka Znaˇcka Znaˇcka
N´avˇesˇ t´ı items item id type name ppu batters batter topping
Tabulka 5: XMill – pˇr´ıklad naplnˇen´ı slovn´ıku
data. V naˇsem pˇr´ıpadˇe neuvaˇzujeme pouˇzit´ı zˇ a´ dnych ´ speci´aln´ıch s´emantickych ´ kompre˚ proto jsou vˇsechna data uloˇzena ve formˇe textu. Bˇehem dekomprese se pak z konsoru, tejneru˚ postupnˇe vyzved´avaj´ı jednotliv´e prvky a zapisuj´ı do vystupn´ ıho XML souboru. ´ Kontejnery pracuj´ı na principu fronty — FIFO. Tabulka 7 ukazuje obsah kontejneru struktury. Kaˇzd´a hodnota pˇredstavuje jeden pˇr´ıkaz, ktery´ se bˇehem dekomprese provede. Kladn´a cˇ ´ısla odkazuj´ı do slovn´ıku n´avˇesˇ t´ı (uveden v tabulce 5) a z´aporn´a cˇ ´ısla odkazuj´ı do datovych kontejneru˚ (uvedeny v ta´ bulce 6). Ve vypisu kontejneru struktury je z´astupnym ´ ´ symbolem tˇr´ı teˇcek (...) nahrazeno pˇetin´asobn´e opakov´an´ı cˇ a´ sti YYY. Poznamenejme, zˇ e v tomto pˇr´ıkladu jsme nebrali v potaz form´atov´an´ı dokumentu (whitespaces). Pseu´ K je pˇr´ıkaz ke vloˇzen´ı koncov´e znaˇcky a pseudokod ´ PK je pˇr´ıkaz k vloˇzen´ı pr´azdn´e dokod znaˇcky (<priklad />). Symbolem # je zn´azornˇen konec kontejneru. ˇ ı pˇredpoklady pro Pˇri pohledu na kontejner struktury je patrn´e, zˇ e jeho data splnuj´ efektivn´ı kompresi pomoc´ı slovn´ıkovych algoritmu˚ (Deflate, . . . ). I pˇres rozd´ıln´a data ´ ´ nˇekterych cˇ a´ st´ı vstupn´ıho XML je struktura kodov´ ana stejnymi sekvencemi (zm´ınˇen´a ´ ´ vynechan´a cˇ a´ st pˇetin´asobn´eho opakov´an´ı), protoˇze se zde vyskytuj´ı odkazy na stejn´a m´ısta ve slovn´ıku a odkazy na stejn´e datov´e kontejnery. V praxi opravdu komprese kon´ cinnosti napˇr´ıcˇ vˇsemi testovanymi tejneru struktury dosahuje velmi vysok´e uˇ algoritmy. ´
4.3
´ XMill Datovy´ format
´ ˚ ymi XMill zpracov´av´a vstupn´ı XML data a koduje je nˇekolika ruzn ´ technikami do vystup´ n´ıho souboru. Z´akladn´ı vlastnosti form´atu souboru XMill v0.8 (v dobˇe psan´ı tohoto textu posledn´ı verze, datovan´a bˇrezen 2008) si nyn´ı pop´ısˇ eme. 4.3.1
ˇ ısel, rˇetezc ˇ u˚ a seznamu˚ Uloˇzen´ı c´
˚ XMill pracuje pouze s celymi cˇ ´ısly (s vyjimkou specifickych ´ ´ ´ s´emantickych ´ kompresoru). ˇ ısla se ukl´adaj´ı pomoc´ı jednoForm´at uloˇzen´ı cˇ ´ısel je podobny, ´ jako se pouˇz´ıv´a u UTF-8. C´ ˚ Poˇcet bajtu˚ se urˇcuje podle specifickych ho, dvou nebo cˇ tyˇrech bajtu. bitu˚ u prvn´ıho ´
31
Kod ´ 1 2 3 4
Cesta /items/item/@id /items/item/@type /items/item/name /items/item/batters/batter/@id
Popis 6 bitov´e cˇ ´ıslo (znam´enko b6, hodnota b5 – b0) 13 bitov´e cˇ ´ıslo (znam´enko b5, hodnota b4 – b0 tohoto bajtu a b7 – b0 dalˇs´ıho bajtu) 29 bitov´e cˇ ´ıslo ˚ (znam´enkob5, hodnota b4 – b0 tohoto a b7 – b0 n´asleduj´ıc´ıch tˇrech bajtu) Tabulka 9: XMill – uloˇzen´ı cˇ ´ısel se znam´enkem (sint32)
naˇcten´eho bajtu (viz tabulky 8 a 9). Data jsou ukl´ad´ana v ne-intelovsk´em23 form´atu. V tabulk´ach se odvol´av´ame na jednotliv´e bity v bajtu. Bity cˇ ´ıslujeme od 7 (bit s nejvˇetˇs´ım vyznamem) do 0 (bit s nejmenˇs´ım vyznamem). Bin´arn´ı cˇ ´ıslo zapsan´e jako 10000000 (de´ ´ kadicky 128) m´a bit b7 (bit na pozici 7) nastaven na hodnotu 1, ostatn´ı b6 aˇz b0 jsou nastaveny na hodnotu 0. Ukl´ad´an´ı cˇ ´ısel bez znam´enka, oznaˇcovan´e jako uint32, se rˇ´ıd´ı logikou uvedenou v tabulce 8. Ukl´ad´an´ı cˇ ´ısel se znam´enkem, oznaˇcovan´e jako sint32, se pak rˇ´ıd´ı logikou popsanou v tabulce 9. ˇ ezce jsou ukl´ad´any s prefixem obsahuj´ıc´ım d´elku rˇ etˇezce (uint32), za kterym Retˇ ´ n´asleˇ duj´ı jednotliv´e znaky rˇ etˇezce. Retˇezec nen´ı ukonˇcen zˇ a´ dnym ´ speci´aln´ım znakem. Jedn´a se o datovy´ typ oznaˇcovany´ jako lstring. Seznamy hodnot jsou ukl´ad´any ve form´atu prefix + seznam hodnot. Hodnota prefixu urˇcuje poˇcet elementu˚ v seznamu. Prvky seznamu mohou byt ´ cˇ ´ısla (uint32, sint32) nebo ˚ rˇ etˇezce. Seznam rˇ etˇezcu˚ se v XMill vyskytuje pomˇernˇe cˇ asto (napˇr´ıklad data kontejneru) a oznaˇcuje se jako slist. 4.3.2
´ souboru XMI Format
XMill ukl´ad´a komprimovan´a data do souboru ve form´atu XMI. Ten se skl´ad´a ze s´erie komprimovanych bloku˚ a kaˇzdy´ blok je komprimovany´ nˇekterym ´ ´ z podporovanych ´ kompresn´ıch algoritmu˚ (gzip, bzip2, . . . ). Kaˇzdy´ komprimovany´ blok je uloˇzen vˇcetnˇe hlaviˇcky a signatury kompresoru. 23
Tabulka 10: XMill – form´at souboru XMI Id 0 1 2 3 4 5 a v´ıce z´aporn´e
Pˇr´ıkaz Vloˇz koncovou znaˇcku Vloˇz pr´azdnou koncovou znaˇcku Vloˇz form´atov´an´ı Vloˇz form´atov´an´ı atributu Vloˇz data speci´aln´ıho kontejneru Vloˇz odpov´ıdaj´ıc´ı n´avˇesˇ t´ı (index = id − 5) Vloˇz data z odpov´ıdaj´ıc´ıho kontejneru
Tabulka 11: XMill – pˇr´ıkazy kontejneru struktury
Glob´aln´ı hlaviˇcka obsahuje z´akladn´ı informace popisuj´ıc´ı XMI soubor. Jsou zde ulozˇ eny informace o verzi form´atu souboru, zda bylo bˇehem komprese ignorov´ano form´atov´an´ı (white-spaces) a informace o path expressions. Hlaviˇcka bˇehu uv´ad´ı kaˇzdy´ bˇeh. Hlaviˇcka mimo popisnych ´ informac´ı n´asleduj´ıc´ıho bˇehu obsahuje tak´e data mal´ych kontejneru. ˚ Jako maly´ kontejner se bˇehem komprese oznaˇc´ı kaˇzdy´ kontejner, jehoˇz velikost je menˇs´ı neˇz stanoven´a hodnota (vychoz´ ı, v aplikaci pevnˇe ´ nastaven´a, hodnota je 2kB). Uloˇzen´ı mal´eho mnoˇzstv´ı dat pˇr´ımo do hlaviˇcky vych´az´ı faktu, zˇ e kompresn´ı algoritmy dosahuj´ı horˇs´ıch vysledk u˚ komprese nad malym ´ ´ mnoˇz˚ ze reˇzie spojen´a s kompres´ı objem dat dokonce stv´ım dat a v nˇekterych ´ pˇr´ıpadech muˇ zvˇetˇsit. Hlaviˇcka bˇehu se komprimuje jako jeden proud dat. ˚ Datov´e bloky obsahuj´ı data kontejneru. Kontejnery obsahuj´ı samotn´a data. XMill rozliˇsuje celkem cˇ tyˇri druhy kontejneru˚ — kontejner struktury, kontejner speci´aln´ıch dat (zde se ukl´adaj´ı procesn´ı informace, DTD, ˇ CDATA a koment´arˇ e), kontejner form´atov´an´ı a datov´e kontejnery. Prvn´ı tˇri zminovan´ e kontejnery se nach´az´ı vˇzdy v prvn´ım datov´em bloku a tento datovy´ blok existuje v kaˇzd´em bˇehu.
34
5
SharpXMill
´ cely proveden´ı experimentu˚ jsme v prostˇred´ı rozhran´ı .NET Framework, konkr´etnˇe Pro uˇ v jazyce C#, implementovali vlastn´ı verzi n´astroje XMill. Bˇehem implementace jsme se soustˇredili na pokryt´ı z´akladn´ı funkcionality standardn´ıho XMill, proto jsme implemen´ cely tovali podporu pouze textov´eho s´emantick´eho kompresoru, coˇz ovˇsem bylo pro uˇ naˇsich experimentu˚ zcela dostaˇcuj´ıc´ı. V prvn´ı f´azi vyvoje jsme vytvoˇrili aplikaci kompati´ ˚ biln´ı s datovym ıho n´astroje XMill. D´ale jsme aplikaci rozˇs´ırˇ ili o pod´ form´atem puvodn´ poru dalˇs´ıch kompresn´ıch algoritmu˚ (konkr´etnˇe LZMA a PPMdI) a o podporu shluko˚ v´an´ı kontejneru.
5.1
´ Navrh architektury SharpXMill
Pˇri n´avrhu architektury jsme se soustˇredili na dodrˇzen´ı kompatibility datov´eho form´atu ´ cely testov´an´ı. Plnˇe jsme vyuˇzili moˇznost´ı a na moˇznosti rozˇs´ırˇ en´ı funkcionality pro uˇ objektovˇe orientovan´eho pˇr´ıstupu n´avrhu a programov´an´ı, pˇredevˇs´ım dˇediˇcnosti a poly˚ zit´e komponenty morfizmu. Architektura syst´emu je zachycena na obr´azku 7. Mezi duleˇ architektury v r´amci procesu komprese XML patˇr´ı: • SAX Parser – analyzuje vstupn´ı XML data a jako ud´alosti reportuje jednotliv´e elementy vyˇssˇ´ı vrstvˇe architektury. • XMICompress – komponenta pˇrij´ım´a data od SAX Parseru a je zodpovˇedn´a za ´ rˇ´ızen´ı vytv´arˇ en´ı aktu´aln´ıho bˇehu, kontroly obsazenosti pamˇet’ov´eho okna, zakodov´an´ı bˇehu do form´atu XMill (vytv´arˇ en´ı jednotlivych, zat´ım nekomprimovanych, ´ ´ proudu˚ dat) a je zodpovˇedn´a za rˇ´ızen´ı komprese jednotlivych ´ proudu˚ dat zvolenym ´ ˚ ych kompresorem. Je zodpovˇedn´a tak´e za reportov´an´ı ruzn ´ statistickych ´ informac´ı ˚ potˇrebnych ´ pro vyhodnocen´ı experimentu. ´ ziˇstˇe vˇsech dat aktu´alnˇe vytv´arˇ en´eho bˇehu. Obsahuje • XMIRun – slouˇz´ı jako uloˇ n´avˇesˇ t´ı, bloky kontejneru˚ a jednotliv´e kontejnery. ´ • XMIRunEncoder – koduje cˇ a´ sti XMIRun do jednotlivych ´ bloku˚ (nekomprimovanych) dat. Samotn´a komprese je spuˇstˇena v okamˇziku, jakmile je zaplnˇeno pamˇet’ov´e ´ okno. • BaseStreamEncoder – obecn´e rozhran´ı pro kompresi bloku dat. Jednotliv´e konkr´etn´ı algoritmy (gzip, bzip2, . . . ) jsou implementov´any ve tˇr´ıd´ach odvozenych ´ z t´eto tˇr´ıdy. ˚ zit´e komponenty architektury v r´amci procesu dekomprese XML zahrnuj´ı: Duleˇ • BaseStreamDecoder – obecn´e rozhran´ı pro dekompresi bloku dat. Dekomprimuje data jednoho komprimovan´eho bloku a pˇred´av´a je d´ale ke zpracov´an´ı.
Obr´azek 7: Architektura SharpXMill ˚ ehu dekomprese • XMIDecompress – tato komponenta je zodpovˇedn´a za rˇ´ızen´ı prubˇ ˇ ıd´ı naˇc´ıt´an´ı komprimovanych ˚ jejich dekompresi a vytv´arˇ en´ı objektu dat. R´ ´ bloku, XMIRun. ´ • XMIRunDecoder – dekoduje vstupn´ı proud dat form´atu XMill a vytv´arˇ´ı objekt XMIRun. • XMIRun – stejnˇe jako bˇehem f´aze komprese, je XMIRun zodpovˇedny´ za repre´ ˚ obsah zapsat tak´e do zentaci vˇsech naˇctenych ych ´ a dekodovan ´ dat. Dok´azˇ e svuj XML souboru. 5.1.1
SAX Parser
Bˇehem implementace jsme museli vyˇreˇsit problematiku analyzy ´ XML. Zjistili jsme totiˇz, zˇ e XML-aware komprese vyˇzaduje specificky´ pˇr´ıstup k analyze ı rˇ eˇsen´ı, ´ XML. Vychoz´ ´ kter´e vyuˇz´ıvalo tˇr´ıdy dostupn´e pˇr´ımo v prostˇred´ı .NET Framework (konkr´etnˇe tˇr´ıdu XMLTextReader), jsme museli opustit, protoˇze pˇri pr´aci s XML daty doch´azelo k neˇza´ douc´ımu zpracov´an´ı obsahu. Tˇr´ıda XMLTextReader je odvozena od tˇr´ıdy XmlReader, tato z´akladn´ı tˇr´ıda slouˇz´ı v prostˇred´ı .NET Framework k analyze ´ a zpracov´an´ı XML. XmlTextReader je velmi komplexn´ı a flexibiln´ı tˇr´ıda, kter´a dok´azˇ e mimo z´akladn´ı analyzy ´ XML (rozliˇsen´ı jednotlivych ´ elementu˚ XML) tak´e prov´adˇet nadstandardn´ı XML ope´ cely race, jako je zpracov´an´ı odkazu˚ znakovych entit, DTD entit apod. Bohuˇzel, pro uˇ ´ ´ cely komprese XML, se uk´azala tato funkcionalita jako naˇseho projektu, a obecnˇe pro uˇ
36
zcela neˇza´ douc´ı, protoˇze takto zpracovan´e soubory se neshodovaly s origin´aly, i kdyˇz doch´azelo k tomu, zˇ e dle specifikace XML obsahovaly stejnou informaci. Nˇekter´e tyto nadstandardn´ı operace jsme nedok´azali deaktivovat, proto jsme museli od pouˇzit´ı t´eto tˇr´ıdy upustit. Implementovali jsme proto vlastn´ı SAX parser (XMLRawReader), coˇz je tˇr´ıda, kter´a je odvozen´a od z´akladn´ı abstraktn´ı tˇr´ıdy XmlReader. XMLRawReader bˇehem analyzy ´ identifikuje n´asleduj´ıc´ı z´akladn´ı prvky XML: • Otev´ırac´ı znaˇcky (napˇr. ). • Koncov´e znaˇcky (napˇr. ). • Pr´azdn´e znaˇcky (napˇr. ). • Atributy (n´azvy a jejich hodnoty). • Form´atov´an´ı (white-spaces). • Obsah (textov´e prvky). • Speci´aln´ı prvky (koment´arˇ e, deklarace XML, CDATA apod.), kter´e vrac´ı jako text. ˚ pˇred´av´a aplikaci bez jak´ehokoliv zpraVeˇskery´ obsah (textov´e prvky, obsah atributu) ´ cov´an´ı nebo zmˇeny kodov´ an´ı.
5.2
Podporovane´ kompresn´ı metody
˚ SXMill Ned´ılnou souˇca´ st´ı cel´eho syst´emu je podpora bˇezˇ nych ´ kompresn´ıch algoritmu. podporuje kompresi pomoc´ı GZip, BZip2, LZMA a PPMdI. Metody GZip a BZip2 jsou pˇrevzaty z knihovny #ziplib (SharpZipLib) [24]. Podporu komprese LZMA jsme z´ıskali d´ıky LZMA-SDK, kter´e je dostupn´e na webu autora aplikace 7-zip [25]. Podpora PPMdI je zajiˇstˇena knihovnou SharpPpmd, kter´a je dispozici na [27].
5.3
ˇ ırˇen´ı funkcionality XMill SXMill – rozs´
´ cely testov´an´ı jsme rozˇs´ırˇ ili puvodn´ ˚ Pro uˇ ı XMill o n´asleduj´ıc´ı funkcionalitu: • Podpora novych ´ kompresoru˚ LZMA a PPMdI. • Podpora shlukov´an´ı kontejneru˚ s vyuˇzit´ım shlukov´an´ı. Bˇehem testu˚ s kompres´ı XML jsme experimentovali s vyuˇzit´ım metody shlukov´an´ı dat. Shlukov´a analyza nebo podobnymi vla´ je proces rozdˇelen´ı dokumentu se stejnymi ´ ´ ´ stnostmi (obsahem) do skupin, kter´e jsou relevantn´ı pro stejn´e poˇzadavky. Uzce vztaˇzen´e ˚ ci tymˇ ˚ [17]. dokumenty smˇerˇ uji k tomu, zˇ e jsou relevantn´ı vuˇ ´ z poˇzadavkum Algoritmy shlukov´an´ı se dˇel´ı do nˇekolika skupin, podrobn´e rozdˇelen´ı shlukovac´ıch algoritmu˚ je napˇr´ıklad v [22]. My jsme konkr´etnˇe vyuˇzili aglomerativn´ı shlukov´an´ı. Do
37
skupiny hierarchickych ´ algoritmu˚ pak patˇr´ı napˇr´ıklad jeˇstˇe divizivn´ı hierarchick´e shlukov´a˚ n´ı. Rozd´ıl mezi nimi je v postupu tvorby shluku. Aglomerativn´ı shlukov´an´ı nejdˇr´ıve vytvoˇr´ı pro kaˇzdy´ objekt jeden shluk. N´aslednˇe vybere vˇzdy dva nejpodobnˇejˇs´ı shluky a ty slouˇc´ı do jednoho shluku. V posledn´ım kroku jsou pak vˇsechny shluky sjednoceny do jedin´eho shluku. Naopak divizivn´ı hierarchick´e ˚ Nejdˇr´ıve je tedy vytvoˇren jeden shluk, shlukov´an´ı vytv´arˇ´ı rozklady existuj´ıc´ıch shluku. ktery´ se postupnˇe dˇel´ı tak, aˇz jsou vˇsechny shluky jednoprvkov´e. Dalˇs´ı podrobnosti o shlukov´e analyze ´ jsou napˇr´ıklad v [17, 22].
38
´ ı Testovan´
6
˚ Soustˇredili jsme se V t´eto kapitole shrnujeme vysledky n´ami provedenych ´ ´ experimentu. ´ cinnosti komprese nˇekolika zpusob ˚ bˇehem nich na porovn´an´ı uˇ u˚ komprese XML dat. Do testu˚ jsme zahrnuli jak bˇezˇ nˇe dostupn´e kompresn´ı programy (RAR [33], 7-zip [25]), tak i ˚ XML-aware kompresor XMill [14] v puvodn´ ı a n´ami modifikovan´e variantˇe.
´ ı Parametry testovan´
6.1
˚ jejichˇz seJako vstupn´ı data pro experimenty jsme zvolili sadu re´alnych ´ XML souboru, znam uv´ad´ı tabulka 12. Testovac´ı soubory jsme pˇred pouˇzit´ım normalizovali, abychom dos´ahli jednotn´e formy XML dat — vˇsechny atributy jsou uzavˇreny do uvozovek (nˇekter´e XML soubory pouˇz´ıvaly apostrofy), doˇslo k sjednocen´ı form´atov´an´ı (u atributu˚ jedna ´ celem normezera mezi znakem rovn´a se (=) zleva i zprava, jednotn´e odsazen´ı) atp. Uˇ malizace bylo poskytnout vstupn´ı data ve stejn´em form´atu tak, aby vysledky nebyly ´ ˚ ovlivnˇeny pr´avˇe odliˇsnym z´apisu. Vysledkem normalizace je to, zˇ e po zpra´ zpusobem ´ cov´an´ı normalizovanych souboru˚ naˇsimi n´astroji doˇslo k vytvoˇren´ı vˇzdy identickych ´ ´ ˚ souboru˚ (po kompresi a dekompresi, shlukov´an´ı). Informace o puvodn´ ıch a normalizovanych ´ souborech shrnuje tabulka 1324 . 6.1.1
Testovac´ı stroje
Na proveden´ı experimentu˚ jsme pouˇzili dva hlavn´ı testovac´ı stroje. Konfigurace stroje A byla n´asleduj´ıc´ı: • Intel Core 2 Quad CPU Q6600 2,40 GHz. • 4 GB operaˇcn´ı pamˇeti. • 32 bitovy´ operaˇcn´ı syst´em Windows Vista Business SP2. U stroje B se jednalo o virtu´aln´ı stroj, jehoˇz (virtu´aln´ı) parametry byly n´asleduj´ıc´ı: • Six-Core AMD Opteron 8425 HE 2.08 GHz25 . • 16 GB operaˇcn´ı pamˇeti. • 64 bitovy´ operaˇcn´ı syst´em Windows Server Enterprise SP2. ˚ stroj B pouze pro nˇekter´e pˇr´ıpady Stroj A jsme pouˇzili k proveden´ı drtiv´e vˇetˇsiny testu, ’ pamˇet ovˇe n´aroˇcnych ´ operac´ı (shlukov´an´ı a nˇekter´e testy s kompres´ı LZMA). 24
˚ Normalizace probˇehla autoSoubor wiki.xml vznikl spojen´ım nˇekolika tis´ıc jednotlivych ´ XML souboru. ˚ maticky bˇehem spojov´an´ı souboru. 25 Na virtu´aln´ım stroji bylo k dispozici bylo pouze jedno j´adro.
39
Soubor psd 7003.xml
Velikost 683 MB
dblp.xml
681 MB
wiki.xml
516 MB
swissprot.xml
109 MB
nasa.xml
23,8 MB
mondial.xml
1,7 MB
sigmod.xml
0,5 MB
hamlet.xml
0,3 MB
Zdroj XML Data Repository http://www.cs.washington.edu/research/xmldatasets/ XML Data Repository http://www.cs.washington.edu/research/xmldatasets/ Wikipedia XML Corpus http://www-connex.lip6.fr/ denoyer/wikipediaXML/ XML Data Repository http://www.cs.washington.edu/research/xmldatasets/ XML Data Repository http://www.cs.washington.edu/research/xmldatasets/ XML Data Repository http://www.cs.washington.edu/research/xmldatasets/ XML Data Repository http://www.cs.washington.edu/research/xmldatasets/ The Plays of Shakespeare in XML http://xml.coverpages.org/bosakShakespeare200.html
Tabulka 12: Sada testovac´ıch XML souboru˚
Soubor psd 7003.xml dblp.xml wiki.xml swissprot.xml nasa.xml mondial.xml sigmod.xml hamlet.xml
S0 716 853 016 B 714 339 712 B –B 114 820 211 B 25 050 288 B 1 784 825 B 478 416 B 288 735 B
Sn 716 860 101 B 714 338 879 B 541 873 094 B 114 820 211 B 25 054 691 B 1 511 087 B 478 416 B 288 735 B
Tabulka 13: Testovac´ı soubory XML pˇred a po normalizaci
40
Metoda GZip BZip2 PPMd (var. PPMdH)
Program 7-zip 4.65 7-zip 4.65 7-zip 4.65
LZMA
7-zip 4.65
RAR (PPMd var. PPMII)
WinRAR 3.90
Parametry Slovn´ık 32kB, velikost slova 32 Slovn´ık 900kB Slovn´ık 256 MB, ppm-order 16, blok dat 4 GB) Slovn´ık 32 MB, velikost slova 64, blok 4 GB Vynucen´a komprese textu, ppm-order 16, slovn´ık 128 MB (max. dostupn´a hodnota)
V prvn´ı f´azi experimentu˚ jsme provedli kompresi XML bˇezˇ nymi n´astroji pro kompresi ´ ˚ Parametry jednotlivych souboru. testu˚ shrnuje tabulka 14. Druh´a cˇ a´ st experimentu˚ se ´ soustˇredila na testy prov´adˇen´e XML-aware n´astrojem SXMill. Parametry tˇechto testu˚ byly shodn´e napˇr´ıcˇ pouˇzitymi metodami komprese, vˇse shrnuje tabulka 15. ´
6.2
´ ı Vysledky ´ testovan´
V n´asleduj´ıc´ım textu budeme pouˇz´ıvat k oznaˇcen´ı jednotlivych u˚ ´ parametru˚ a vysledk ´ testu˚ notaci, kterou shrnuje tabulka 16. Pokud to m´a vyznam, je v pˇrehledu vysledk u˚ ´ ´ nejlepˇs´ı hodnota ze skupiny oznaˇcena tuˇcnˇe. U srovn´an´ı pomˇeru˚ vysledk u˚ komprese ´ ´ cinnosti komprese dan´e metody (hodnoty vˇetˇs´ı jak 100%) jsou hodnoty znaˇc´ıc´ı zhorˇsen´ı uˇ oznaˇceny odliˇsnou barvou. 6.2.1
Komprese XML jako textu
Pro z´ısk´an´ı referenˇcn´ıch hodnot komprese XML jsme provedli kompresi vˇsech testo˚ Tabulka 17 uv´ad´ı absolutn´ı vanych ´ XML souboru˚ pomoc´ı bˇezˇ nych ´ kompresn´ıch n´astroju. velikosti souboru˚ pˇred a po proveden´ı komprese a tabulka 18 spoleˇcnˇe s grafem 8 shrnuje kompresn´ı pomˇery.
41
Symbol S0 Sn
Vyznam ´ ˚ Velikost puvodn´ ıho souboru ˚ Velikost normalizovan´eho puvodn´ ıho souboru
Jednotky bajty bajty
CSrar CSgz CSbz CSlz CSpp
Velikost souboru komprimovan´eho metodou RAR Velikost souboru komprimovan´eho metodou Deflate (gzip) Velikost souboru komprimovan´eho metodou BZip2 Velikost souboru komprimovan´eho metodou LZMA Velikost souboru komprimovan´eho metodou PPMdI
bajty bajty bajty bajty bajty
CRrar CRgz CRbz CRlz CRpp
Pomˇer komprese pˇri pouˇzit´ı metody RAR Pomˇer komprese pˇri pouˇzit´ı metody Deflate (gzip) Pomˇer komprese pˇri pouˇzit´ı metody BZip2 Pomˇer komprese pˇri pouˇzit´ı metody LZMA Pomˇer komprese pˇri pouˇzit´ı metody PPMdI
procenta procenta procenta procenta procenta
CSx/gz CSx/bz CSx/lz CSx/pp
Velikost souboru komprimovan´eho metodou XMill/gzip Velikost souboru komprimovan´eho metodou XMill/bzip2 Velikost souboru komprimovan´eho metodou XMill/lzma Velikost souboru komprimovan´eho metodou XMill/ppmdi
bajty bajty bajty bajty
CRx/gz CRx/bz CRx/lz CRx/pp
Kompresn´ı pomˇer pˇri pouˇzit´ı metody XMill/gzip Kompresn´ı pomˇer pˇri pouˇzit´ı metody XMill/bzip2 Kompresn´ı pomˇer pˇri pouˇzit´ı metody XMill/lzma Kompresn´ı pomˇer pˇri pouˇzit´ı metody XMill/ppmdi
procenta procenta procenta procenta
CRwavg
˚ er kompresn´ıch pomˇeru˚ jednotlivych V´azˇ eny´ prumˇ ´ metod
Z vysledk u˚ je patrn´e, zˇ e nejlepˇs´ıch vysledk u˚ dosahuje metoda PPM, kterou imple´ ´ ˚ rozd´ıly plynou mentuje jak WinRAR, tak i 7-zip. Oba dosahuj´ı podobnych vysledk u, ´ ´ z m´ırnˇe odliˇsnych variant implementovanych algoritmu˚ PPM a ne zcela identickych ´ ´ ´ ˚ ern´a hodnota kompresn´ıho pomˇeru metody PPM byla 7,85%. parametru˚ komprese. Prumˇ ˚ ernou hodnotou 14,78%. Pokud tyto dvˇe Nejhorˇs´ıch vysledk u˚ dosahoval GZip s prumˇ ´ ˚ metody srovn´ame, dosahuje PPM t´emˇerˇ o 50% lepˇs´ıch vysledk u. ´ 6.2.2
XML-aware komprese XMill
Testovac´ı soubory jsme d´ale komprimovali pomoc´ı n´astroje SXMill. Pouˇzit´e metody komprese jsme volili tak, abychom mohli prov´est srovn´an´ı s bˇezˇ nymi kompresn´ımi n´astroji ´ (uveden´e v pˇredchoz´ı kapitole). V tabulce 19 a v grafu na obr´azku 9 jsou uvedeny kom˚ ci vysledku ˚ presn´ı pomˇery jednotlivych komprese bˇezˇ nych ´ metod a pomˇer vuˇ ´ ´ n´astroju. ˚ eru doˇslo ke zlepˇsen´ı u metod GZip (∼ 19%) a BZip2 Z vysledk u˚ je patrn´e, zˇ e v prumˇ ´ (∼ 5%), naopak pouˇzit´ı XMill spolu s PPM vedlo ke zhorˇsen´ı (∼ 7%) a pˇri pouˇzit´ı LZMA ˚ jako u bˇezˇ n´e komprese. jsme dos´ahli srovnatelnych u, ´ vysledk ´
44
Soubor psd7003 dblp wiki SwissProt nasa mondial Sigmod hamlet CRwavg
Pˇri podrobnˇejˇs´ım prozkoum´an´ı vysledk u˚ jednotlivych ´ ´ metod komprese je zˇrejm´e, zˇ e metoda PPM dosahuje velmi dobrych u˚ komprese pˇri kompresi XML jako textu a ´ vysledk ´ zˇ e pouˇzit´ı struktur´aln´ı komprese (XMill) pˇrin´asˇ´ı zlepˇsen´ı pouze v nˇekterych ´ pˇr´ıpadech a to nav´ıc pouze nepatrn´e (v rˇ a´ du jednotek procent). PPM, stejnˇe jako i LZMA, pracuj´ı pˇri kompresi s velmi dlouhym ´ objemech textu generovat ´ kontextem a zvl´adaj´ı pˇri velkych ´ efektivn´ı kodov´ an´ı s vyuˇzit´ım statistiky pracuj´ıc´ı s dlouhou histori´ı (jedn´a se o pamˇet’ovˇe n´aroˇcnˇejˇs´ı algoritmy). Proto nedoch´az´ı pˇri pouˇzit´ı struktur´aln´ı komprese, kdy se data ˚ k vyrazn´ tˇr´ısˇ t´ı do jednotlivych emu vylepˇsen´ı komprese. ´ kontejneru, ´ Nav´ıc po proveden´ı testu˚ bylo ihned zˇrejm´e, zˇ e soubor wiki.xml je zcela nevhodny´ pro kompresi n´astrojem XMill. Po zjiˇstˇen´ı vysledk u˚ komprese u tohoto souboru jsme proto ´ podrobnˇeji prozkoumali jeho obsah. Zjistili jsme, zˇ e se jedn´a o specificky´ pˇr´ıpad XML souboru. Danou problematiku popisujeme v kapitole 2.5, resp. 2.5.3. V souboru wiki.xml ˚ kdy jednotliv´e cˇ l´anky jsou uzavˇreny mezi znaˇckami <article> je obsaˇzen souhrn cˇ l´anku, ´ a (jedin´a znaˇcka na 1. urovni). Veˇskery´ dalˇs´ı obsah pˇredstavuj´ı jednotliv´e cˇ l´anky. Ostatn´ı znaˇcky, kter´e se v nich vyskytuj´ı, maj´ı pouze form´atovac´ı vyznam, nikoliv ´ ˚ s´emanticky. ı myˇslenku ´ Seskupov´an´ı dat dle tˇechto informac´ı pak zcela postr´ad´a puvodn´ a v´ıce m´enˇe prob´ıh´a chaoticky. Mimo to ovlivnil vysledek komprese tak´e fakt, zˇ e doˇslo k ´ vytvoˇren´ı velmi velk´eho mnoˇzstv´ı kontejneru˚ — vzniklo jich v´ıce jak 4000. 6.2.3
ˇ ’ove´ okno XMill Pamet
Pˇri kompresi XML pracuje XMill s pamˇet’ovym ´ oknem, coˇz je rezervovan´e m´ısto v pamˇeti, do kter´eho se ukl´adaj´ı doposud zpracovan´a data. Po zaplnˇen´ı tohoto okna jsou data ˚ zkomprimov´ana. Puvodn´ ı XMill [14] pracuje s vychoz´ ı velikost´ı tohoto okna 8MB, my ´ ˚ jsme pˇri testech pracovali s oknem o velikosti 32MB. Zaj´ımalo n´as, jakym ´ zpusobem ˇ ´ esˇ nost jednotlivych ˇ ovlivnuje velikost okna uspˇ metod komprese. Graf 10 zn´azornuje ´ z´avislost zlepˇsen´ı komprese na rostouc´ı velikosti pamˇet’ov´eho okna. ˚ Puvodn´ ı XMill byl navrˇzen pˇredevˇs´ım pro pouˇzit´ı s metodami GZip a BZip2 a jako vychoz´ ı hodnotu pro velikost pamˇet’ov´eho okna zvolili autoˇri hodnotu 8MB. Jak je z ´
45
Obr´azek 10: Zlepˇsen´ı komprese v z´avislosti na velikosti pamˇet’ov´eho okna grafu patrn´e, byla tato hodnota zvolena jako kompromis, pˇri kter´em jiˇz dalˇs´ım zvˇetˇsov´an´ım efektivita komprese neroste natolik, aby se vyplatilo kl´ast vˇetˇs´ı n´aroky na pamˇet’. Metody PPM a LZMA ale ukazuj´ı, zˇ e efektivita jejich komprese roste s vˇetˇs´ım mnoˇzstv´ım ˚ zlepˇsen´ı komprese ust´av´a souˇcasnˇe komprimovanych dat, kdy relativnˇe velky´ n´arust ´ aˇz kolem hranice velikosti okna 128MB, resp. 256MB a d´ale i za touto hranic´ı doch´az´ı ˚ pˇri takto objemnych st´ale k zaj´ımav´emu zlepˇsen´ı. Vzhledem k pamˇet’ovym ´ n´arokum ´ pamˇet’ovych oknech se ale praktick´e vyuˇzit´ı ukazuje jako nere´aln´e a sp´ısˇ e to ukazuje ´ na fakt, zˇ e architektura XMill nen´ı vhodn´a pro efektivn´ı vyuˇzit´ı tˇechto metod komprese. 6.2.4
´ ı kontejneru˚ Shlukovan´
˚ Jeden z provedenych u˚ optimalizace XML komprese bylo prov´adˇen´ı shlukov´an´ı ´ zpusob ˚ Jedn´a se o metodu, pˇri kter´e pˇred komprimac´ı jednotlivych kontejneru. ´ kontejneru˚ prov´ad´ıme shlukovan´ı dat v nich obsaˇzenych. Vzhledem k architektuˇre XMill je ale nutn´e po ´ ˚ proveden´ı shlukov´an´ı uloˇzit dodateˇcn´e informace o puvodn´ ım rozloˇzen´ı prvku˚ kontejneru˚ do paty bˇehu (v komprimovan´e podobˇe) — t´ım ale vznik´a jisty´ overhead, ktery´ negaˇ tivnˇe ovlivnuje vysledek komprese. ´ Bˇehem prov´adˇen´ı praktickych ´ testu˚ jsme narazili na dva z´asadn´ı probl´emy: • Shlukov´an´ı kontejneru˚ je v souˇcasn´e implementaci cˇ asovˇe velmi n´aroˇcn´e. ˚ ale overhead celkovou kompresi zhorˇsu• Shlukov´an´ı zlepˇsuje kompresi kontejneru, je.
46
Soubor nasa
Velikost 25 054 691
T Cx/gz 3:45:26
T Cx/bz 3:33:57
T Cx/pp 3:36:22
T Cx/lz 3:38:05
ˇ Tabulka 20: Casov´ a n´aroˇcnost XMill komprese se shlukov´an´ım kontejneru˚ α x/gz x/bz x/pp x/lz
CSα 3 477 590 2 973 524 2 523 919 2 645 959
z toho reˇzie 507 785 441 997 420 525 300 488
∆CR bez reˇzie 94,99 97,45 97,69 96,33
∆CR s reˇz´ı 111,24 114,47 117,22 108,67
Tabulka 21: XMill komprese se shlukov´an´ım kontejneru˚
Vzhledem k cˇ asov´e n´aroˇcnosti testu˚ jsme uskuteˇcnili prakticky´ test pouze na jednom XML souboru (nasa.xml) a u nˇej jsme provedli kompresi vˇsemi testovanymi algoritmy ´ ˇ ˚ Casovou spolu s aktivn´ım shlukov´an´ım kontejneru. n´aroˇcnost shrnuje tabulka 20. Tabulka 21 a graf 11 zobrazuj´ı dosaˇzen´e vysledky. U vˇsech metod komprese doˇslo ´ d´ıky shlukov´an´ı kontejneru˚ ke zlepˇsen´ı komprese (∼ 3%), ale zapoˇcten´ım reˇzie, kter´a mus´ı byt ´ uloˇzena u kaˇzd´eho bˇehu, doˇslo k celkov´emu zhorˇsen´ı komprese v rozmez´ı 8 aˇz 14 %. Vzhledem k proveden´ı pouze jednoho testu je tˇezˇ k´e u t´eto metody uˇcinit z´avˇer. Nicm´enˇe je jasn´e, zˇ e bez vylepˇsen´ı cˇ asov´e n´aroˇcnosti a navrhnut´ı efektivnˇejˇs´ıho uloˇzen´ı ˚ puvodn´ ıho uspoˇra´ d´an´ı prvku˚ v kontejnerech, nelze tuto metodu v praxi aplikovat. 6.2.5
´ ı celych Shlukovan´ ´ XML souboru˚
U vybranych ´ XML souboru˚ jsme provedli n´asleduj´ıc´ı optimalizaci: ´ 1. Rozdˇelen´ı XML od prvn´ı urovnˇ e na jednotliv´e podsoubory. ˚ 2. Proveden´ı shlukov´an´ı tˇechto souboru. 3. Sloˇzen´ı souboru˚ zpˇet do jednoho XML dle vysledk u˚ shlukov´an´ı. ´ Vzhledem k tomu, zˇ e jsme prov´adˇeli pˇreh´azen´ı jednotlivych ´ prvku˚ v XML souboru, nen´ı moˇzn´e v praxi tuto optimalizaci pouˇz´ıt obecnˇe na vˇsechny XML soubory. Vhodny´ ˇ XML soubor mus´ı splnovat tato krit´eria: • Pˇreh´azen´ı prvku˚ je povoleno (nezakazuje ho napˇr´ıklad sch´ema). ´ • Obsahuje nˇekolik prvku˚ na prvn´ı urovni, v ide´aln´ım pˇr´ıpadˇe vhodnych ´ pro shlukov´an´ı (obs´ahlejˇs´ı texty). My jsme vhodn´e soubory vybrali ruˇcnˇe, neˇreˇsili jsme vybˇ ´ er vhodnych ´ souboru˚ algoritmicky. Takto optimalizovan´e XML soubory jsme komprimovali nejdˇr´ıve bˇezˇ nymi ´
47
Obr´azek 11: XMill komprese se shlukov´an´ım kontejneru˚ Soubor psd7003 dblp wiki SwissProt nasa
Treshold 0,05 0,05 0,05 0,05 0,05
Prvku/soubor ˚ 5 30 1 1 1
Souboru˚ 52 506 71 988 75 036 50 000 2 435
ˇ Cas 0:27:08 0:52:24 0:38:10 0:12:41 0:00:19
Tabulka 22: Parametry shlukov´an´ı celych ´ XML souboru˚
˚ Seznam n´astroji a pak pomoc´ı XMill ve standardn´ım reˇzimu (bez shlukov´an´ı kontejneru). vybranych ´ souboru˚ a z´akladn´ı parametry shlukov´an´ı shrnuje tabulka 22. ˚ vˇcetnˇe srovn´an´ı Vysledky komprese bˇezˇ nymi n´astroji celych ´ ´ ´ shlukovanych ´ souboru, ˚ ci kompresi bˇezˇ nymi pomˇeru vuˇ n´astroji bez proveden´ı shlukov´an´ı, shrnuje tabulka 23 a ´ graf na obr´azku 12. Jak je vidˇet, aˇz na jeden pˇr´ıpad, kdy doˇslo k nepatrn´emu zhorˇsen´ı, mˇelo shlukov´an´ı celych komprese. Komprese ´ XML souboru˚ pozitivn´ı vliv na vysledek ´ ˚ eru zlepˇsila (∼3 aˇz 5 %). U souboru wiki.xml doˇslo k t´emˇerˇ desetiprocentn´ımu se v prumˇ zlepˇsen´ı, coˇz je vysledek dany´ povahou obsahu tohoto souboru — tento vysledek je v ´ ´ kontrastu s vysledky komprese wiki.xml pomoc´ı XMill. ´ ˚ vˇcetnˇe srovn´an´ı pomˇeru˚ Vysledky komprese pomoc´ı XMill u shlukovanych ´ ´ souboru, ˚ ci kompresi XMill u souboru˚ bez proveden´ı shlukov´an´ı, shrnuje tabulka 24 a graf na vuˇ ˚ eru k m´ırn´emu zlepˇsen´ı obr´azku 13. Vysledky ukazuj´ı, zˇ e u t´eto metody doˇslo v prumˇ ´ vysledk u˚ komprese (∼ 1 aˇz 3%). U nˇekolika jednotlivych ´ ´ XML souboru˚ ale doˇslo k m´ırn´emu zhorˇsen´ı.
48
Obr´azek 12: Srovn´an´ı bˇezˇ n´e komprese po proveden´ı shlukovan´ı celych ´ XML souboru˚
Obr´azek 13: Srovn´an´ı XMill komprese po proveden´ı shlukovan´ı celych ´ XML souboru˚
∆CR 98,34 99,46 90,40 95,51 98,93 96,53
CRgz 13,64 16,52 17,94 10,40 14,01 15,54
∆CR 100,51 93,92 91,92 86,60 94,23 95,24
CRbz 10,51 10,79 13,06 6,84 10,61 11,06
∆CR 98,91 98,14 87,79 89,98 96,59 95,28
CRpp 8,95 7,87 10,09 4,94 7,75 8,64
∆CR 99,52 97,99 91,26 95,90 99,80 96,69
∆CR 100,44 99,92 93,01 92,38 97,93 97,89
CRx/bz 9,68 10,42 14,71 5,54 10,32 11,00
∆CR 100,10 98,55 94,17 95,60 99,47 97,80
CRx/pp 8,58 8,93 12,61 4,67 8,60 9,52
∆CR 99,69 100,50 94,98 96,87 100,01 98,60
CRx/lz 8,53 10,74 12,65 5,77 9,58 10,19
Tabulka 24: Komprese shlukovanych ´ XML souboru˚ pomoc´ı XMill
Z proveden´eho sˇ etˇren´ı vyplyv´ ´ a, zˇ e ke kompresi XML souboru˚ lze vyuˇz´ıt jak bˇezˇ n´e n´astroje pro kompresi (archivaci) dat, tak i specializovan´e XML-aware n´astroje. Popul´arn´ım n´astrojem v kategorii XML-aware komprese je XMill. XMill v dobˇe sv´eho vzniku dos´ahl zaj´ımav´eho zlepˇsen´ı u algoritmu˚ GZip a BZip2 t´ım, zˇ e vyuˇzil struktur´aln´ı informace pˇr´ıtomn´e v XML. Seskupen´ım s´emanticky pˇr´ıbuznych ´ ˚ dos´ahnout lepˇs´ıch vysledk dat pom´ah´a slovn´ıkovym u˚ komprese. Z n´ami ´ algoritmum ´ provedenych ´ testu˚ ale vyplyv´ ´ a, zˇ e modern´ı kompresn´ı metody, jako jsou PPM a LZMA, ˚ eru s minim´alnˇe srovnatelnou uˇ ´ cindok´azˇ ´ı komprimovat XML soubory jako text v prumˇ ˚ jako uveden´e metody GZip a BZip2 pˇri pouˇzit´ı nost´ı (v implementaci bˇezˇ nych ´ n´astroju), struktur´aln´ı komprese (implementovan´e v XMill). Uk´azalo se tak´e, zˇ e architektura XMill nen´ı pˇr´ıliˇs vhodn´a pro nahrazen´ı metod GZip a BZip2 metodami PPM cˇ i LZMA, protoˇze ˚ tˇr´ısˇ tˇen´ı dat do skupin (kontejneru) ˚ naplno vyuˇz´ıt jejich s´ıly. Vyuˇzit´ı tˇechto nedok´azˇ e kvuli n´astroju˚ by mˇelo smysl pouze s velmi obs´ahlym ´ pamˇet’ovym ´ oknem, coˇz by ale kladlo ’ velk´e n´aroky na pamˇet jak pˇri procesu komprese, tak i dekomprese. Z provedenych testu˚ tak´e vyplynulo, zˇ e XML-aware komprese je velice citliv´a na ´ ˚ zit´a je spr´avn´a identifikace a oddˇelen´ı od sebe analyzu vstupn´ıch XML dat. Velice duleˇ ´ ´ cinnost komprese. Uk´azalo struktury od dat. Nespr´avn´e proveden´ı analyzy ´ m´a vliv na uˇ ˚ se tak´e, zˇ e nˇekter´e XML soubory nejsou vubec vhodn´e pro kompresi XML-aware n´astrojem XMill a lepˇs´ıch vysledk u˚ se dos´ahne jejich kompres´ı jako textu. ´ Uk´azali jsme tak´e, zˇ e efektivitu XML komprese lze zvyˇ ´ sit pouˇzit´ım metod shlukov´an´ı dat. Otestovali jsme shlukov´an´ı dat v kontejnerech n´astroje XMill a tak´e shlukov´an´ı celych kompresory a pomoc´ı XMill. ´ XML souboru˚ a jejich n´aslednou kompresi bˇezˇ nymi ´ Shlukov´an´ı kontejneru˚ m´ırnˇe jejich kompresi zlepˇsuje, ale v aktu´aln´ı implementaci je ˇ cˇ asovˇe pˇr´ıliˇs n´aroˇcn´e a nav´ıc tak vznik´a dodateˇcn´a reˇzie, kter´a celkovˇe zabranuje dosaˇzen´ı zlepˇsen´ı komprese. Naproti tomu shlukov´an´ı celych ´ XML souboru˚ u drtiv´e vˇetˇsiny testovac´ıch souboru˚ vedlo ke zlepˇsen´ı komprese a to jak pˇri jejich kompresi jako textu, tak ˚ eru jsme dos´ahli m´ırn´eho zlepˇsen´ı v rˇ a´ du nˇekolika i pˇri kompresi pomoc´ı XMill. V prumˇ procent, u individu´aln´ıch souboru˚ bylo zlepˇsen´ı aˇz o 10 % v z´avislosti na pouˇzit´e metodˇe komprese.
51
8
Reference
[1] J. Adiego, G. Navarro, P. Fuente. Using Structural Contexts to Compress Semistructured Text Collections. Depto. de Inform´atica, Universidad de Valladolid, Depto. de Ciencias de la Computaci´on, Universidad de Chile, Depto. de Inform´atica, Universidad de Valladolid, 2007. [2] T. Bell, D. Kulp. Longest-match String Searching for Ziv–Lempel Compression. 1993. [3] M. Brauer, P. Durusaum, G. Edwards, D. Faure, T. Magliery, D. Vogelheim. Open Document Format for Office Applications (OpenDocument) v1.0. OASIS Standard, 2005. [4] M. Burrows and D.J. Wheeler. A Block-sorting Lossless Data Compression Algorithm. 1994. [5] Ch. Bussler. B2B Protocol Standards and their Role in Semantic B2B Integration Engines. Oracle Corporation, 2001. [6] J. Cheney. Compressing XML with Multiplexed Hierarchical PPM Models. Cornell University, Ithaca, 2001. [7] J. Cheng, Wilfred Ng. XQzip: Querying Compressed XML Using Structural Indexing. Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, 2004. [8] J. G. Cleary, I. H. Witten. Data Compression Using Adaptive Coding and Partial String Matching. 1984. [9] G. V. Cormack, R. N. S. Horspool. Data Compression Using Dynamic Markov Modelling. 1986. [10] P. Deutsch. DEFLATE Compressed Data Format Specification version 1.3. RFC 1951. 2003. [11] D. Huffman. A method for the construction of minimum redundancy codes. 1952. ˇ an. Shlukov´a analyza. [12] J. Kelbel, D. Silh´ ´ [13] M. Levene, P. Wood. XML Structure Compression. Birkbeck College, University of London, 2002. [14] H. Liefke, D. Suciu. XMill: an Efficient Compressor for XML Data. Univ. of Pennsylvania, 2000. [15] G. N. N. Martin. Range encoding: an algorithm for removing redundancy from a digitised message. 1979. http://www.compressconsult.com/rangecoder/rngcod.pdf.gz
52
[16] G. Manzini. The Burrows-Wheeler Transform: Theory and Practice. 1999. [17] J. Martinoviˇc. Search in Documents based on Similarity. Department of Computer Sciˇ – Technical University ence, Faculty of Electrical Engineering and Computer Science, VSB of Ostrava, 2008. [18] J. Min, M. Park, Ch. Chung. XPRESS: A Queriable Compression for XML Data. Division of Computer Science, Department of Electrical Engineering & Computer Science Korea Advanced Institute of Science and Technology, Taejon, Korea, 2003. [19] M. Nicola J. John. XML Parsing: A Threat to Database Performance. 2003. [20] M. Nottingham, R. Sayre. The Atom Syndication Format. RFC 4287, 2005 [21] P. M. Tolani, J.R. Haritsa. XGRIND: A Query-friendly XML Compressor. Dept. of Comput. Sci. & Autom., Indian Inst. of Sci., Bangalore, 2002. ˇ – Technick´a univerzita Ostra[22] M. Vicher. Shlukov´an´ı pomoc´ı algoritmu COBWEB. VSB va, 2010. [23] J. Ziv, A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory. 1977. [24] .NET Zip Library #ziplib (3.5.2010). http://www.icsharpcode.net/OpenSource/SharpZipLib/Default.aspx [25] 7-Zip – domovsk´a str´anka (3.5.2010). http://www.7-zip.org/ [26] BZip2 Manual (3.5.2010). http://www.bzip.org/1.0.5/bzip2-manual-1.0.5.pdf [27] Dmitry Shkarin’s PPMd Ported To C# by Michael Bone (3.5.2010). http://users.senet.com.au/ mjbone/Compression.html [28] Document Object Model (DOM) (3.5.2010). http://www.w3.org/DOM/ [29] Extensible Markup Language (XML) (3.5.2010). http://www.w3.org/XML/ [30] Introduction to DTD (3.5.2010). http://www.w3schools.com/dtd/dtd intro.asp [31] Introducing the Office (2007) Open XML File Formats (3.5.2010). http://msdn.microsoft.com/en-us/library/aa338205.aspx [32] Overview of SGML Resources (3.5.2010). http://www.w3.org/MarkUp/SGML/
