Construction of compressed Gray code and its usage in compression.
An n-bit cyclic Gray code is a cyclic list of all n-bit strings where consecutive strings differ in exactly one bit. We may see Gray code also as a graph where strings are vertices of a hypercube and transitions are edges between vertices in a dimension which is defined by the position of the transition. The index of the transition can be encoded as a binary number and it gives again an n-bit string, now with length of [log2n]. If we create another graph from these strings as vertices, we can have a sub-graph of dimension [log2n]. Compressed n-bit Gray code is such list of strings whose graph of transitions is isomorphic to an induced sub-graph of hypercube with dimension [log2n]. the compressed Gray Code may be represented by the first string, the first transition and list of transitions in induced graph.
Documentation of the source code in Czech language.
Program na kompresi bitmapových indexů pomocí Grayových kódů (dále jen KomBIG) je aplikace na kompresi dat v podobě indexů bitmap. Bitmapový index je seznam n-bitových posloupností, tedy takových, že jejich jednotlivé hodnoty můžou být pouze pravda či nepravda. Tento index se velmi často používá například v databázích, kde hodnoty atributů mají velmi malou doménu. Tento druh záznamu má tu výhodu, že se na něj snadno kladou databázové dotazy, hlavně v podobě bitových operací, které jsou velmi rychlé na dnešních počítačích. Je však náročný na diskovou paměť a je tedy výhodné ho komprimovat.
Pokud bychom chtěli použít standardní komprimovací techniky (např. Huffmanovo kódování), ztratíme výhodu rychlého dotazování. Je tedy třeba použít takovou techniku, která data sice zhustí, ale stále na nich bude možno klást dotazy. Nejpoužívanější algoritmus pro takovou kompresi je dnes WAH. Ten v principu fungují tak, že v datech nalezne dlouhé posloupnosti stejných hodnot (nul nebo jedniček) a uloží je jako jednu hodnotu a počet. Je tedy jasné, že komprese bude tím větší, čím delší posloupnosti v datech budou. Jednotlivé bitmapy můžeme poskládat tak, že v nich bude co nejméně posloupností. Setřídit takto optimálně bitmapy je v3ak NP-těžký problém. Přesto existují heuristiky na přerozdělení. Jednou z nich jsou i Grayovy kódy.
Grayův kód (dále jen GK) je posloupnost všech n-prvkových bitmap takových, že dvě sousední bitmapy se liší právě v jedné hodnotě. Tato posloupnost není jedna, ale je jich mnoho. Pokud bychom měli soubor, který obsahuje všechny n-prvkové bitmapy, a setřídili ho podle GK, potom jsou data seřazena nejlepším možným způsobem. Ve skutečných souborech dat se však zdaleka všechny n-prvkové bitmapy nevyskytují. Je tedy otázkou, zda se v takovýchto datech přerozdělení pomocí GK vyplatí.
Z experimentálních výsledků vyplývá, že pokud použijeme zrcadlový typ GK (ZGK), je výsledné přerozdělení stejně výhodné jako prosté lexikografické rozdělení. Zrcadlový typ GK je definován rekurzivně. Mějme GK S1 = (0,1). Další n-bitové GK vytvoříme z rovnosti Sn+1 = 0Sn, 1SRn, kde SR posloupnost S seřazen pozpátku. Otevřenou otázkou zůstává, zda při použití jiného typu GK nebude výsledné uspořádání výhodnější. Program KomBIG implementuje speciální typ GK právě pro účely zkoumání jeho výhodnosti.
Jednou z vlastností GK je jejich samotné uspořádání. V tomto uspořádání si nemusíme ukládat celé bitmapy, ale pouze jedna bitmapa a seznam čísel pozic, ve kterých se liší dva sousední bitmapy (tzv. přechody). Takto dokážeme zmenšit kód z původních n bitů na [log2n] bitů na jedna bitmapa. Existuje ještě další způsob reprezentace kódu, který dokáže zhustit průměrně jedna bitmapa na velikost [log2log2n] Všechny GK ale tímto způsobem zmenšit nelze, pro nalezení takového kódu existuje speciální technika, kterou implementuje KomBIG.
Řekněme, že cyklický Grayův kód je takový, ve kterém se liší první prvek od posledního právě v jednom bitu. Cyklický GK si můžeme představit jako Hamiltonovskou kružnici v n-dimenzionální-hyperkrychli Qn. N-dimenzionální hyperkrychle je graf na 2n vrcholech takový, že pokud vrcholy označíme sekvencí n nul a jedniček, potom mezi vrcholy vede hrana právě, když se vrcholy liší právě v jedné hodnotě svých sekvencí. Hamiltonovská kružnice je kružnice grafu taková, že prochází všechny vrcholy grafu. Každá hrana v hyperkrychli má směr. Směr hrany určuje pozice lišícího se bitu mezi dvěmi sekvencemi koncových vrcholů hrany. Hamiltonovská kružnice se tedy dá reprezentovat jako jeden vrchol Hyperkrychle a posloupnost směrů.
Nyní definujme indukovaný graf Hamiltonovské kružnice jako graf, jehož vrcholy jsou směry hyperkrychle a mezi těmito vrcholy vede hrana právě, když z alespoň jednoho vrcholu Hamiltonovské kružnice vede hrana do směrů udaných těmito vrcholy indukovaného grafu. Indukovaný graf může mít rozličné „tvary“ [5], nás zajímají jen ty Hamiltonovské kružnice, které indukují hyperkrychli. GK, který tato kružnice představuje, nazveme komprimovaný Grayův kód (dále jen KGK) [1]. Zde je příklad KGK s bitmapy délky 4 a počtem bitmap 24 = 16.
0011000011001111
0001111110000110
0111100111100000
0000001111111100
Program je v podstatě logicky rozdělený na tři části:
- První část programu umí vstupní bitmapový index setřídit, a to hlavně podle KGK. Generuje se tedy rekurzivní metodou KGK s velikostí bitmap n, kde n je velikost bitmap v nesetříděném souboru. Výstup je nový soubor se bitmapy ze vstupního souboru setříděnými pomocí KGK. Pokud program žádný vstupní soubor nedostane, je možné vygenerovat pro zadané n do výstupního souboru samotný KGK.
- Na bitmapový index setříděný podle KGK (ale i na jakýkoliv jiný bitmapový index) se používá komprimační algoritmus WAH.
- Poslední část vytvoří pro seznam jmen souborů statistiku, která pro každý soubor znázorňuje velikost souborů při použití daného přerozdělení a komprimačního algoritmu WAH. Ve statistice se mohou objevit tyto čtyři přerozdělení: žádné, lexikografické, pomocí zrcadlového typu GK a pomocí KGK. Aby se nemusel každý soubor komprimovat zvlášť, podporuje KomBIG typ souboru se seznamem jmen souborů.
KomBIG pracuje podle vstupu uživatele, který předá programu informace pomocí argumentů příkazové řádky nebo pomocí vstupních souborů. Nyní si ukážeme druhy souborů, které program přijímá. Pokud chceme pracovat s nějakými daty z externích zdrojů, musíme je převést do formátu podporovaném KomBIGem pomocí jiných programů. To samozřejmě může změnit velkost původního souboru, ale my využíváme především informaci z bitmap, tedy na velikost komprimovaného souboru to nic nemění.
Soubor s indexem má jednoduchý tvar. Na každém řádku souboru se nalézá bitový vektor. Tento vektor je představován řetězcem znaků 0 a 1. Každý znak představuje bitovou informaci v indexu tak, že první znak je i první bitová hodnota v indexu. Na jenom řádku mohou být pouze tyto dva znaky. Pokud jsou v souboru prázdné řádky, program je přeskočí. Aby program věděl, jaká je šířka indexu, jako první řádek je nutné zadat číslo, které udává šířku indexu. Všechny bitové řetězce musí být stejně dlouhé. Při chybném vstupu se vypíše příslušné chybové hlášení.
Seznam jmen souborů má také jednoduchý formát. Jedná se o list jmen, každý na jednom řádku. Jelikož ve jménu souboru mohou být různé divné znaky, je vhodné dávat jména do uvozovek. V uvozeném jménu se jednoduché uvozovky zapíšou jejich zdvojením.
Jako výstup programu můžeme brát jednak výpis zpráv na standardní výstup, jednak výstupní soubory. Při pouhém třídění indexu je výstupní soubor znovu index s formátem popsaným výše. Při kompresi se vytvoří komprimovaný soubor. Ten je v podobném formátu jako index, akorát sloupce jsou zobrazeny jako řádky. Implementace v tomto programu ve skutečnosti soubor nezmenší. Jelikož nám jde o názornost, v místech, ve kterých algoritmus data redukoval, jsou mezery. Je potom pouhym okem vidět, jak byl algoritmus úspěšný. Komprimovaný soubor lze poté získat jednoduše odstraněním mezer.
Soubor se statistikou se ukládá do formátu CSV. Tento formát je jednoduchý a pro uložení statistiky naprosto postačující, navíc je podporován mnoha aplikacemi pro správu dat. Data, která se při vytváření statistiky vytvoří, jsou v CSV souboru uspřádána takto:
- První položka prvního řádku je prázdný řetězec
- Další položky na prvním řádku jsou jména sloupců, které mohou představovat použité přerozdělovací techniky a komprimačního algoritmu nebo nějaké vlastnosti souborů.
- První položky ostatních řádků jsou jména souborů (i s cestou)
- Ostatní položky jsou čísla označující velikost komprimovaných souborů v bytech taková, že řádek určuje, jaký soubor byl komprimován, a sloupec určuje, jakou technikou byl sloupec komprimován. Můžou to také být hodnoty udávající počet bitmap, velikost bitmap nebo násobek těchto dvou hodnot.
Program se ovládá z příkazové řádky. Zde je šablona příkazu:
kombig [-i <soubor>] [-o <soubor>] [-c] [-r <trideni>] [-s (trideni | vlastnost) ...] [-g n] [-h]
Pořadí parametrů může být libovolně přeházené (až na výjimky). Formátování řádku je pouze v rukou operačního systému, na kterém program běží, tedy například bílé znaky a uvození nemůže program rozeznat. Program rozlišuje malá a velká písmena.
Vysvětlíme si význam přepínačů:
- -i - Přijímá jako parametr jméno vstupního souboru. Jméno může být jak s úplnou cestou, tak i s relativní cestou vzhledem k umístění programu.
- -o - Přijímá jako parametr jméno souboru, do kterého bude zapsaný výsledek operace. Pokud soubor existuje, program vypíše chybu a skončí.
- -c - Provádí kompresi pomocí algoritmu WAH. Přepínače –i a –o musí být uvedené.
- -r - Setřídí vstupní soubor podle zadaného druhu třídění a vypíše do výstupního souboru. Přepínače –i a –o musí být uvedené. Při kombinaci s přepínačem –c se nejdříve provede setřídění a poté komprese.
- -s - Vytvoří statistiku. Jako parametr je seznam hodnot ve tvaru třídění nebo vlastnost, kde třídění je typ třídění (viz níže) a vlastnost nějaká další vlastnost (viz níže). Jako vstupní soubor bere seznam jmen souborů, na kterých má být provedena statistika. Výstupní soubor je ve formátu CSV. Jelikož přepínač bere seznam parametrů, musí být uveden jako poslední. Přepínače –i a –o musí být uvedené.
- -g - Vygeneruje KGK s bitmapy délky n a vypíše je do výstupního souboru. Přepínač –o musí být uveden.
- -h - vypíše nápovědu
Druhy třídění mohou být Zadne – žádné, Lexikograficke – lexikografické, Zgk – podle zrcadlového typu GK a Kgk – podle komprimovaného GK. Další vlastnosti, které mohou být uvedeny do statistiky, jsou Delka – délka bitmap, Pocet – počet bitmap a Velikost – součin předchozích dvou vlastností. Pro ilustraci je uvedeno několik příkladů:
kombig –i vstup.txt –o komprimovany.txt –r Kgk -c
V prvním příkladu se vstupní soubor setřídí podle KGK a poté se zkomprimuje pomocí WAH. Programu nezáleží na pořadí přepínačů (kromě -s), toto je také platný zápis:
kombig –o komprimovany.txt -c –r Lexikograficke –i vstup.txt
V tomto případě se soubor setřídí lexikograficky. Nyní si uvedeme příklad vytvoření statistiky:
kombig –i seznam.txt –o stats.csv –s Velikost Zgk Kgk
Program zde vytvoří statistiku se třemi sloupci. V prvním budou součiny délek bitmap a počtů bitmap, v dalších dvou budou velikosti souborů ze seznamu setříděné postupně pomocí ZGK a KGK a komprimované pomocí WAH.
Zde popíšeme, jak jsou jednotlivé algoritmy implementovány. Program je napsaný v jazyce C++. Budeme postupovat po jednotlivých souborech, přičemž implementaci a hlavičkové soubory jsou prány jako jeden soubor:
Zde je uložena reprezentace bitového vektoru. Aby byla práce rychlá, implementuje se jako vektor čísel typu int. S tímto typem totiž pracuje procesor nejrychleji. Výhodou této reprezentace je také to, že některé bitové operace na bitovém vektoru není nutné provádět po jednom bitu, ale lze je provést najednou na typu int. Metody bitmapy většinou tuto bitmapu upravují (například metody nastavBit, invertujBit, prohodBity). Bitmapy lze také zvětšovat (metody pripojPrefix, pripojPostfix).
Bitmapový index je reprezentován jako vektor řádkových bitmap. Třída BitmapovyIndex je v podstatě pouze kontejner na vektorem bitmap. Jsou zde však implementovány nějaké dodatečné užitečné metody (bitXor, pripojPrefix, pripojPostfix, prohodSloupce). Pro potřeby třídění dle KGK obsahuje dodatečný vektor, který udává pořadí každého bitmapu v KGK. Tento vektor se však používá pouze v případě třídění.
Třída ZaznamovyFormat se jednoduchým obalem nad standardními knihovnami, které čtou nebo zapisují do souborů. Je užitečný hlavně tím, že uchovává informaci o tom, zda se právě ze souboru čte nebo se do něj zapisuje. Dále se používá jako interface pro třídy CsvInterface a SerializovatelnyIndex.
Tento soubor obsahuje jednoduchou implementaci parseru a formátovače CSV. Třída CsvTokenizer umí načítat záznamy z formátu CSV, má pouze jednu užitečnou metodu dejZáznam, která načte záznam. Třída CsvWriter umí zapisovat soubor CSV. Má různé metody pro zápis různých druhů dat. Třída CsvUniversal umí obojí.
Třída SerializovatelnyIndex je potomek třídy BitmapovyIndex a ZaznamovyFormat. Užívá se k zápisu indexu do souboru. Výhoda této implementace je v tom, že bitmapový index se chová jako stream, stačí tedy zavolat jednu metodu a index se ze souboru načte nebo do souboru zapíše korektně. Tato třída má dva potomky.
Třída VstupBitmap se užívá k načítaní bitmap, k čemuž slouží metoda nacti. Užitečnou metodou je také zjistiDelkuBitmap, která se podívá na první řádek souboru s indexem a přečte číslo, které udává délku indexu. Nejdůležitější je však funkce setridSoubor. Ta jako parametry bere typ třídění a odkaz na třídu VystupBitmap (viz níže). Funkce třídí bitmapový index podle zadaného třídění. Pokud je index příliš velký, setřídí bloky určité velikosti a ty poté slévá.
Třída VstupBitmap se užívá k zápisu bitmap do souboru. Za zmínku stojí metoda slij, která slévá bloky indexu a používá se v již zmíněné metodě setridSoubor.
V tomto souboru je uložena třída BitmapoveTrideni. Metoda setrid podle toho, jaké má nastavené uspořádání. Jsou implementovány tří třídící algoritmy: Dle lexikografického uspořádání, podle ZGK a podle KGK. Jelikož u KGK není znám efektivní třídící algoritmus, třídění funguje tak, že se nejdříve podle existujícího KGK každému bitmapu přiřadí jeho pořadí (to děla metoda vytvorPoradiProKgk) a dle tohoto pořadí se třídí. Je však nutno upozornit, že tato procedura má exponenciální složitost podle šířky indexu.
Třída Kgk je nejdůležitější částí programu. Má jednu hlavní veřejnou statickou metodu vytvorKgk, která vytvoří KGK. Konstrukce KGK funguje rekurzivně. Z kódu délky 4 je pomocí funkce zdvojnasobKgk možné vytvořit postupně všechny KGK mocniny dvě. Funkce funguje zhruba tak, že vytváří automorfní kódy KGK, které poté spojuje do KGK s dvojnásobnou délkou řetězců. Princip výroby těchto automorfismů je nad rámec této dokumentace. Pro zvětšení na obecnou šířku indexu se používá podobná technika spojování, jako u ZGK. To provádí metoda rozsirKgkNaObecneN.
Třída Komprese obsahuje dvě veřejné metody. Metoda komprimuj dostane jako parametr bitmapový index. Ten pomocí kompresního algoritmu WAH komprimuje do výstupního souboru. Kompresní algoritmus hledá dlouhé řetězce stejných bitů a ty poté komprimuje do jednoho slova, výpis tohoto slova děla metoda zapisFillWord. Metoda vypocti dělá téměř to samé jako komprimuj, jen neukládá výsledek do souboru, ale vypočítává velikost (hypotetického) komprimovaného souboru, což je rychlejší.
Třída zpracovává vstup z příkazové řádky a vykonává jednotlivé operace. Nejdříve pomocí metody zpracuj zkontroluje všechny parametry příkazové řádky, zda dávají smysl a poté vrátí objekt třídy NastaveniVypoctu, kde je uchována konfigurace, co se má provést. Následně celá požadovaná procedura lze vyvolat metodou proved. Metoda provedStatistiku je speciálně určena pro vytváření statistiky, protože pro každou statistiku provádí velkou část stejných operací jako metoda proved.
This project is licensed under the terms of the BSD 3-clause "New" (or "Revised") license. See the LICENSE file for more details.