Kompresja i dekompresja danych

Wprowadzenie
Potrzeba kompresji danych (tekstowych) pojawiła się przy realizacji projektu Wikipedia offline - pobrane i zapisane na dysku hasła Wikipedii zajmowały bardzo dużo miejsca, a ponieważ były to zwykłe pliki tekstowe, to się bardzo dobrze kompresowały. Samo pakowania plików rozwiązałem w PHP poprzez wywołanie zewnętrznego pakera, bo tak było najprościej (i szybciej, niż zakodowanie algorytmu kompresji w PHP), ale rozpakowanie takich plików musiało już być napisane w JavaScripcie. Szukałem w internecie takich rozwiązań i znalazłem aplikację, korzystające z algorytmu deflate. Przykładowy plik testowy, mający 1678 KB, został spakowany za pomocą tego programu do 61 KB (czyli był 27,5 raza mniejszy). Całkiem nieźle, ale testy programem 7-Zip wykazały, że używając algorytmu LZMA można taki plik skompresować nawet do 33 KB (czyli będzie on 50-krotnie mniejszy). Ponieważ zależało mi na jak najsilniejszej kompresji, szukałem w internecie opisu tego algorytmu albo jakiegoś programu z darmowymi źródłami, korzystającego z takiej silnej kompresji. W ten sposób trafiłem na projekt Lzip, skąd mogłem pobrać zarówno wersję binarną dla Windows, jak i kod źródłowy (napisanego w C) programu lunzip do rozpakowywania. Program lzip pakuje pojedyncze pliki tak samo dobrze, jak program 7-Zip (bo w obu przypadkach używany jest algorytm LZMA).

Opis rozwiązania
Zająłem się zatem analizą kodu źródłowego programu lunzip i na jego bazie zamierzam napisać swoją wersję dekompresora LZMA w JavaScripcie. Ponieważ najwygodniej kompiluje się programy napisane w C/C++ pod Linuksem, postanowiłem zainstalować sobie środowisko Cygwin, czyli narzędzia linuksowe pod Windowsem. Przeanalizowałem kod źródłowy programu lunzip i wywaliłem z niego zbędny kod odpowiadający za obsługę całego zestawu parametrów wywołania (ja potrzebowałem podawać tylko nazwę pliku do rozpakowania). Zrezygnowałem też z kodu odpowiadającego za ładne wyświetlanie informacji i błędów przy dekompresowaniu pliku. Dodatkowo przeniosłem część kodu odpowiadającą za odczyt kolejnych kawałków pliku (do zdefiniowanego w programie bufora) do głównej funkcji, w której sprawdzam rozmiar skompresowanego pliku i przydzielam sobie pamięć o takim właśnie rozmiarze, by go tam w całości wczytać. Realizuję to w ten sposób dlatego, ponieważ w JavaScripcie będę dysponował stringiem zawierającym cały skompresowany plik i będę chciał, by funkcja dekompresji otrzymywała go jako parametr wywołania i zwracała ciąg zawierający rozpakowane dane (oraz status tej operacji). Dodatkowo oryginalny program lunzip może operować na scalonych ze sobą wielu kawałkach danych (spakowanych osobno a potem scalonych plikach), co w moim przypadku jest zbędne. Uproszczenie kodu i wywalenie z niego zbędnych funkcji dodatkowo przyspieszy działanie programu a ja będę miał potem mniej kodu do przerobienia z C na JavaScript. No i dzięki analizie kodu orientuję się już całkiem nieźle, jak działa ten program. Kolejne wprowadzane modyfikacje sprawdzam poprzez kompilację kodu i testowanie programu na 4 różnych plikach tekstowych. Z kodu, mającego ok. 1400 linii (nie licząc komentarzy), uzyskałem ok. 600 linii właściwego kodu i zacząłem pisać jego wersję w JavaScripcie.

Własny format spakowanego pliku
Postanowiłem także zmodyfikować nagłówek skompresowanego pliku *.lz, by usunąć z niego niepotrzebne rzeczy: usunąłem z niego numer wersji (obecnie 0x01), który dla mnie jest zupełnie zbędny) oraz wartość długości pliku po kompresji (ten rozmiar pliku jest znany, bo w programie wczytuję go w całości do pamięci), a długość nieskompresowanego pliku przechowuję na 4 bajtach (co ogranicza jego rozmiar do 4 GB, co nie jest żadnym problemem). Dodatkowo, ponieważ znam rozmiar wypakowanych danych, to nie potrzebuję używać bajtu z zakodowanym rozmiarem słownika (który był zapisywany w nagłówku pliku LZIP). Na końcu pliku *.lz była przechowywana wartość kodu CRC-32 nieskompresowanego pliku - postanowiłem go przenieść na początek, tak by uzyskać jeden spójny nagłówek. Dodatkowo zmieniłem 4-znakowy identyfikator nagłówka z "LZIP" na 2-znakowy "LZ", dzięki czemu dane nagłówkowe zmniejszyły się z 26 do 10 bajtów - teraz w nagłówku są 2 bajty dla "LZ", 4 bajty rozmiaru danych po rozpakowaniu i 4 bajty kodu CRC-32). Dodatkowo usunąłem pierwszy bajt skompresowanych danych, który był zawsze równy 0 (jest on generowany przez Range Encoder i potem ignorowany przez Range Decoder), także łącznie na każdym pliku oszczędzam w ten sposób 17 bajtów.
Aby uzyskać spakowany plik w tak zmodyfikowanym formacie wykorzystuję do pakowania najpierw standardowy program lzip.exe, a następnie programem napisanym przez siebie przerabiam go do postaci docelowej. W przyszłości planuję przerobić kod źródłowy programu lzip tak, by od razu generował spakowany plik w postaci docelowej.
Jeśli chodzi o samo pakowanie, to na razie nie planuję się jeszcze tym zajmować, ale być może w przyszłości przygotuję sobie taką funkcję zarówno w PHP, jak i JavaScripcie. Trzeba tylko zdawać sobie sprawę, że pakowanie danych jest bardzo czasochłonnym procesem i dlatego o ile jest to możliwe, warto korzystać z programów wykonywalnych (np. skompilowanych źródeł w C/C++), a nie skryptowych (jak PHP czy JavaScript).

Powrót do strony z wykazem projektów

Valid HTML 4.01 TransitionalValid CSS