Optymalizacja kompresji Huffmana pod kątem podziału na bloki

• Autorzy: Rybak K. , Jamro E. , Wielgosz M. , Wiatr K.

Warianty tytułu

EN

Optimization of Huffman compression employing different block sizes

• Języki publikacji: PL

Abstrakty

PL

Prezentowane w pracy badania dotyczą bezstratnej kompresji danych opartej o metodę Huffmana i zgodnej ze standardem deflate stosowanym w plikach .zip / .gz. Zaproponowana jest optymalizacja kodera Huffmana polegająca na podziale na bloki, w których stosuje się różne książki kodowe. Wprowadzenie dodatkowego bloku z reguły poprawia stopień kompresji kosztem narzutu spowodowanego koniecznością przesłania dodatkowej książki kodowej. Dlatego w artykule zaproponowano nowy algorytm podziału na bloki.

EN

According to deflate [2] standard (used e.g. in .zip / .gz files), an input file can be divided into different blocks, which are compressed employing different Huffman [1] codewords. Usually the smaller the block size, the better the compression ratio. Nevertheless each block requires additional header (codewords) overhead. Consequently, introduction of a new block is a compromise between pure data compression ratio and headers size. This paper introduces a novel algorithm for block Huffman compression, which compares sub-block data statistics (histograms) based on current sub-block entropy E(x) (1) and entropy-based estimated average word bitlength Emod(x) for which codewords are obtained for the previous sub-block (2). When Emod(x) - E(x) > T (T - a threshold), then a new block is inserted. Otherwise, the current sub-block is merged into the previous block. The typical header size is 50 B, therefore theoretical threshold T for different sub-block sizes S is as in (3) and is given in Tab. 2. Nevertheless, the results presented in Tab. 1 indicate that optimal T should be slightly different - smaller for small sub-block size S and larger for big S. The deflate standard was selected due to its optimal compression size to compression speed ratio [3]. This standard was selected for hardware implementation in FPGA [4, 5, 6, 7].

Słowa kluczowe

PL

kompresja danych; kodowanie Huffmana; deflate

EN

data compression; Huffman coding; deflate

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 7
• Strony: 519--521
• Opis fizyczny: Bibliogr. 10 poz., tab., rys.

Twórcy

autor

Rybak K.

• AGH Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków

autor

Jamro E.

• AGH Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków
• ACK Cyfronet AGH, Nawojki 11, 30-950 Kraków

autor

Wielgosz M.

• AGH Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków
• ACK Cyfronet AGH, Nawojki 11, 30-950 Kraków

autor

Wiatr K.

• AGH Akademia Górniczo-Hutnicza, Katedra Elektroniki, Al. Mickiewicza 30, 30-059 Kraków
• ACK Cyfronet AGH, Nawojki 11, 30-950 Kraków

Bibliografia

• [1] Huffman D.A.: A method for the construction of minimumredundancy codes, Proc. Inst. Radio Eng, Vol.40, No.9, pp.1098-1101, Sep. 1952.
• [2] P. Deutsch DEFLATE Compressed Data Format Specification version 1.3: RFC1951, 05/1996.
• [3] Collin L.: A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA, http://tukaani.org/lzma/benchmarks.html, 2005-05-31.
• [4] Jamro E., Wiatr K.: Implementacja w układach FPGA dekompresji danych zgodnie ze standardem Deflate, Pomiary Automatyka Kontrola, 2013 vol. 59 nr 8, s. 739–741.
• [5] Gwiazdoń M., Jamro E., Wiatr K.: Optymalizacja sprzętowej architektury kompresji danych metodą słownikową, Pomiary Automatyka Kontrola, 2013 vol. 59 nr 8, s. 827–829.
• [6] Jamro E., Wielgosz M., Wiatr K.: FPGA Implementation of the Dynamic Huffman Encoder, Proc. IFAC Workshop on Programmable Devices and Embedded Systems, Brno, Feb. 14-16, 2006, pp.60-65.
• [7] Rybak K., Jamro E., Wiatr K.: Realizacja kompresji danych metodą Huffmana z ograniczeniem długości słów kodowych, Pomiary, Automatyka, Kontrola, 2012 vol. 58 nr 7 s. 662–664.
• [8] Abdul Mannan M., Kaykobad M.: Block Huffman coding, Computers & Mathematics with Applications, Volume 46, Issues 10–11, November-December 2003, Pages 1581–1587.
• [9] ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus/, styczeń 2014.
• [10] http://www.statystyka.org/wspolczynnik_korelacji_rang_spearmana.php, styczeń 2014.