Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Kompresja Huffmana i Arytmetyczna

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest Tarlandil. Jeżeli został importowany poprawnie, usuń ten szablon!

Wstęp

No, w końcu zmusiłem się aby napisać tego arta (a szczególnie musiałem zmuszać się do zrobienia przykładowego kodu - bo pisanie arta aż takie wymagające nie jest). Właśnie czytacie artykuł opisujący zasadę działania prostszych metod kompresji: Huffmana i Arytmetycznej. Do kompresji Huffmana również dołączyłem kod przykładowy (Delphi).

Aktualnie używane w kompresji są trochę bardziej zaawansowane algorytmy, ale trzeba od czegoś zacząć. No więc do rzeczy...

Kompresja Huffmana

Ta kompresja opiera się na zastępowaniu słów w pliku o stałej długości (np. bajty o długości 8 bitów), słowami o zmiennej długości bitów. Dla przykładu. Plik w którym występują 4 znaki w następujących ilościach (proporcjach)

A - 10000 (o kodzie 00)
B - 3000 (o kodzie 01)
C - 1500 (o kodzie 10)
D - 500 (o kodzie 11)

Taki plik ma długość 10000+2000+1500+500=15000 znaków=30000 bitów. (bo każdy znak w przykładzie ma 2 bity).

Natomiast gdyby zastąpić te znaki przez następujące ciągi bitów:

A - 0
B - 10
C - 110
D - 111

To długość tak zapisanego pliku będzie wynosić:

10000*1+3000*2+1500*3+500*3=22000 bitów. A więc jest to już opłacalne w stosunku do tradycyjnego zapisu.

Porównanie tych dwóch sposobów zapisu (reprezentacji bitowej znaków):

1) bez uwzględnienia ilości wystąpień

                       / \
                    0/    \ 1
                   /       \
                 /          \
               /  \         /\
           0 /     \ 1  0 /   \ 1
           /        \    /     \
         A           B  C       D

2) z uwzględnieniem ilości wystąpień

                         / \
                       /    \ 1
                   0 /       \
                    A       / \1                            Jak widać mając dany ciąg bitów możemy
                        0 /    \                             jednoznacznie określić odpowiadający
                         B    / \                          mu ciąg znaków (idziemy od korzenia
                           0/    \1                      do liści, a jak dojdziemy na dół to mamy
                           C      D                      odkodowany znak i od nowa od korzenia)

Okazuje się, że jeżeli znaki występujące częściej zastąpimy krótszymi ciągami bitów, a znaki występujące rzadziej dłuższymi, to możemy często uzyskać zmniejszenie ilości danych potrzebnych do zakodowania pliku - im większa dysproporcja pomiędzy występowaniem znaków tym lepsza kompresja.

Cały problem sprowadza się więc do wyznaczenia tych nowych reprezentacji bitowych dla każdego znaku (i to takich, że żadna z nich nie jest prefixem innej - czyli, że można zrobić takie binarne drzewo jak to wyżej).

Takie drzewo buduje się w następujący sposób:

0) mamy n węzłów każdy ze swoją wartością (taka ile razy występował w pliku)
1) Wykonujemy krok 2, dopóki sa co najmniej 2 węzły.
2) Wybieramy 2 węzły o najmniejszej wartości i łączymy w 1, i ten nowy węzeł otrzymuje wartość taką jaką w sumie miały te węzły z których powstał.

Dla przykładu:

0)---------------------------------------------------------------------------------------------------------------
                   A(100)            C(15)              B(30)           D(5)         - wybieramy C i D i łączymy:


1)---------------------------------------------------------------------------------------------------------------
                                                                E(20)
                                                            0 /   \1
                    A(100)            B(30)                  C     D       - wybieramy B i E i łączymy:

2)---------------------------------------------------------------------------------------------------------------
                                             F(50)
                                        0  /     \1
                                         /        E
                                       /      0 /  \1
                    A(100)            B        C    D       - wybieramy A i F i łączymy:

2)---------------------------------------------------------------------------------------------------------------
                              G(150)
                            0/  \1
                           /     F(50)
                         /   0  /  \1
                       /      /     E
                     /      /   0 /  \1
                    A      B     C    D       - mamy gotowe drzewo

No tak, tylko że skąd dekompresor będzie znał użyte przez nas ciągi bitów? W tym celu należy to drzewo zapisać w pliku (np. zapisać jaki węzeł powstał z jakich)

Takie drzewo można zapisaćjako: (odpowiednio wezły EFG)

CDBEAF - (CD->E ; BE->F ; AF->G)

Teraz już program dekompresujący będzie potrafił odczytać zakodowany plik.

Kompresja Arytmetyczna

Ta kompresja jest lepsza od kompresji Huffmana lecz wymaga w implementacji użycia własnej arytmetyki. Lecz zasada kompresji jest zupełnie inna. Jedyne podobieństwo jest w tym, że także będziemy potrzebowali ilości wystąpień znaków pliku.

Weźmy na przykład ciąg znaków:

AABAACDABBCADBAA

A - ma 8 wystąpień
B - ma 4 wystąpienia
C - ma 2 wystąpienia
D - ma 2 wystąpienia

Normalnie ten plik zajmuje 16*2=32 bitów (po 2 bity na znak).

A - 8/16
B - 4/16
D - 2/16
E - 2/16

Weźmy sobie taki odcinek podzielony na 4 części zgodnie z tymi proporcjami podanymi wyżej.

|-------------------------------------------|------------------------|------------|------------|
0                      A                               8/16         B            12/16   C   14/16  D    16/16

Pierwsza jest A w związku z tym bierzemy fragment 0 - 8/16 i skalujemy ponownie:
|------------------------------------------|------------------------|------------|------------|
0                      A                                8/32         B             12/32   C   14/32 D    16/32=8/16

I znowu jest A w związku z tym bierzemy fragment 0 - 8/32 i skalujemy:
|------------------------------------------|------------------------|------------|------------|
0                     A                                8/64         B             12/64   C   14/64 D    16/64=8/32

Następny jest B:
|------------------------------------------------|------------------------|------------|------------|
16/128                 A                            20/128         B          22/128   C    23/128  D  24/128

itd....

Jak widać, w miarę dodawania nowych znaków przedział się zawęża, ale dodając znak występujący częściej przedział zawęża się słabiej niż dodając znak występujący rzadziej.

Teraz pokaże jak liczyć te nowe przedziały.

Oznaczmy przez
Niech przedziałem wejściowym będzie przedział

W takim razie

P=A+x*(B-A)=B*x+A*(1-x) Q=B*y+A*(1-y)

Tak więc zgodnie ze wzorem:

P0=<0,1) P1=<0,1/2) P2=<0,1/4) P3=<1/8,3/16) P4=<1/8,5/32) P5=<1/8,9/64)

itd... dalej już wypisywać nie będę, gdyż każdy może sobie sam doliczyć (a i tak sądzę że nie będzie się nikomu chciało - tak jak mi zresztą).

Załóżmy że wyszło nam (a pewnie wyjdzie zupełnie inny wynikJ) P16=<113/65536,151/65536).

Te liczby można zapisać (binarnie) jako

0,0000000001110001 oraz:
0,0000000010010111

Jeżeli wybierzemy dowolną liczbę z tego przedziału i będziemy ją znali, oraz będziemy znali ilości odpowiednich znaków w pliku to będziemy mogli na podstawie tej liczby zdekodować cały plik.

Skoro można wziąć dowolną liczbę to my wybierzemy oczywiści taką która wymaga najmniejszej ilości bitów aby ją zapisać. A jest nią:

0,000000001. Mamy więc 9 bitów po przecinku zamiast 16*2=32 bitów.

A jak teraz to zdekodować?

Załóżmy że mamy zdekodowanych ileś znaków (albo i wcale) wtedy ta liczba jest tylko w jednym z przedziałów(Tych dopasowanych do tych znaków), więc wybieramy ten przedział oraz liczymy nowy - za pomocą podanych wzorów. I mamy o jeden znak więcej oraz nowy przedział, i robimy to samo w kółko aż zdekodujemy cały plik.

Zakończenie

Mam nadzieję, że zrozumieliście moje wypociny i macie już (o ile wcześniej nie mieliście) jakiś pogląd na temat kompresji danych.

Kod przykładowy do kompresji huffmana jest napisany w Delphi i nie jest on w ogole zoptymalizowany, więc dekompresja dużych plików może dłuugo trwać. Artykuł napisany dla Warsztatu. All rights Reserved. Copyright Tarlandil.

Tarlandil
29 maja 2001

Tekst dodał:
Adam Sawicki
29.03.2006 21:13

Ostatnia edycja:
Adam Sawicki
29.03.2006 21:13

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 29.03.2006 21:13 Adam Sawicki 9.39 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)