Przeczytaj

Sposoby zapisów informacji

Komputery korzystają z systemu binarnego, tzn. każda wartość, znak lub obrazek są złożone z ciągów liczb w systemie dwójkowymsystem dwójkowysystemie dwójkowym.

O systemach liczbowych możesz przeczytać w e‑materiale Systemy liczbowePuXcOXfLKSystemy liczbowe.

Kompresja danych

Kompresja jest to proces zmniejszania objętości, zagęszczenia lub wielkości czegoś. Można kompresować gazy, dane lub ciała stałe. W tym e‑materiale interesuje nas kompresja danych w informatyce, tzn. zmiana sposobu zapisu informacji, tak aby zmniejszyć redundancjęredundancja danychredundancję i tym samym objętość zapisanego zbioru.

Możemy zmniejszyć długość wiadomości na kartce przez zmianę sposobu kodowania.

Dany jest ciąg znaków, który nie zawiera cyfr.

Jeśli mamy ciąg znaków: „AAAAAAAAA”, możemy go zapisać w postaci: „9A” i dodać adnotację, że taki zapis oznacza dziewięć znaków „A”.

Stopień kompresji

Definicja: Stopień kompresji

Miara względnego zmniejszenia rozmiaru reprezentacji danych generowanej przez algorytm kompresji danych (ang. compression rate, CR). Zwykle wyrażana jako wynik dzielenia rozmiaru nieskompresowanego przez rozmiar po skompresowaniu.

Dzięki temu udało nam się „skompresować” dziewięć znaków do dwóch, uzyskaliśmy stopień kompresji rzędu 4,5.

Stopień kompresji zapisuje się zgodnie z następującym wzorem:

Stopień kompresji = \frac{Rozmiar nieskompresowanych danych}{Rozmiar danych po skompresowaniu}

Kompresja bezstratna

Definicja: Kompresja bezstratna

Kompresja bezstratnakompresja bezstratnaKompresja bezstratna polega na zmianie kodowania wiadomości w taki sposób, że nie tracimy żadnych informacji. Operacja ta jest w pełni odwracalna, ponieważ polega jedynie na zmianie sposobu kodowania.

Kompresja bezstratna oznacza głównie zmianę sposobu kodowania wiadomości.

Przykład 1

Dana jest niezawierająca cyfr wiadomość: „AAAAAAAAAAAAAAAAAAAAAAAA”. Można skompresować ją poprzez zmianę kodowania do „24A” – co oznaczałoby, że została ona skrócona z 24 do 3 znaków.
Stopień kompresji wynosiłby więc: 24 : 3 = 8.

Przykładem kodu, którym posługujemy się na co dzień podczas korzystania z komputerów, jest kod ASCII (skrót ang. American Standard Code for Information Interchange) oraz jego rozszerzenia. Kod ASCII koduje tylko na 7 bitach wszystkie litery alfabetu łacińskiego, języka angielskiego, znaki interpunkcyjne i znaki kontrolne.

Ciekawostka

ASCII jest kodem 7‑bitowym, przy czym oryginalny standard nie definiuje roli ósmego bitu. Ósmy bit bywa wykorzystywany do kontroli parzystości lub do przechowywania dodatkowego atrybutu (np. podświetlenia). Najczęściej jednak ósmy bit służy rozszerzeniu podstawowego kodu ASCII o niezbędne znaki alfabetów narodowych, symbole matematyczne itp. Więcej na temat kodu ASCII znajdziesz w e‑materiale Reprezentacja tekstu w komputerzePGxPIpBPkReprezentacja tekstu w komputerze.

Ważne!

Co prawda zmiana sposobu kodowania jest niezbędna w kompresji, jednak sama nie powoduje oszczędności pamięci. Przykładowo przejście z kodu binarnego na kod Gray'a nie powoduje żadnej zmiany w ilości zajmowanej pamięci.

Kompresja przedstawiona w powyższym przykładzie, polega na zapisaniu informacji w inny sposób (w tym wypadku każdy zduplikowany znak występujący obok siebie możemy zastąpić liczbą, która oznacza, ile razy dany znak został powtórzony).

Kompresja stratna

Definicja: Kompresja stratna

Polega na zmianie kodowania oraz na nieodwracalnym usunięciu części informacji. W kompresji stratnej niemożliwe jest odzyskanie informacji pierwotnej w postaci sprzed kompresji.

Algorytmy bezstratnej kompresji danych

Jest wiele algorytmów, które pozwalają bezstratnie kompresować dane. Przywołamy jedynie kilka z nich.

Kodowanie Shannona

Kodowanie Shannona to metoda kompresji bezstratnej polegająca na zliczeniu częstości występowania danego ciągu liter lub poszczególnych znaków $x_i$ w ciągu $X$ , a następnie posortowaniu ich w sposób nierosnący, zgodnie z prawdopodobieństwem $P$ ich wystąpienia $p_i$ .

Przykład 2

Dla dwudziestoelementowego ciągu „AAABBBBBBCCCCDDDDDDD” tworzymy zbiór znaków: $X = \lbrace A, B, C, D \rbrace$ . Następnie zliczamy wystąpienie każdego ze znaków:

$A: 3$

$B: 6$

$C: 4$

$D: 7$

Co pozwala nam policzyć prawdopodobieństwo $p_i$ wystąpienia każdego ze znaków (zbiór składa się z $20$ znaków):

$p_A: \frac{3}{20} = 0,15$

$p_B: \frac{6}{20} = 0,3$

$p_C: \frac{4}{20} = 0,2$

$p_D: \frac{7}{20} = 0,35$

Następnie sortujemy symbole wraz z częstościami nierosnąco:

$X = \lbrace D, B, C, A \rbrace$

$P = \lbrace 0,35; 0,3; 0,2; 0,15 \rbrace$

Tworzymy sumy prawdopodobieństw kolejnych znaków:

$P_D = 0$

$P_B = p_1 = 0,35$

$P_C = p_1 + p_2 = 0,35 + 0,3 = 0,65$

$P_A = p_1 + p_2 + p_3 = 0,35 + 0,3 + 0,2 = 0,85$

Obliczamy teraz długości Shannona, czyli długość kodów w bitach. Posłużymy się następującym wzorem:

$l_i = \lceil - log_{2}\ p_i \rceil$

Podstawiając kolejne prawdopodobieństwa, uzyskamy następujące wartości:

$l_D = \lceil - log_{2}\ 0,35 \rceil = \lceil 1,514573173 \rceil = 2$

$l_B = \lceil - log_{2}\ 0,3 \rceil = \lceil 1,736965594 \rceil = 2$

$l_C = \lceil - log_{2}\ 0,2 \rceil = \lceil 2,321928095 \rceil = 3$

$l_A = \lceil - log_{2}\ 0,15 \rceil = \lceil 2,736965594 \rceil = 3$

Zamieniamy prawdopodobieństwa z postaci dziesiętnej na binarną (prezentujemy pięć pierwszych bitów po przecinku):

$P_D = 0,00_{10} = 0,00000_{2}$

$P_B = 0,35_{10} = 0,01011_{2}$

$P_C = 0,65_{10} = 0,10100_{2}$

$P_A = 0,85_{10} = 0,11011_{2}$

Na koniec bierzemy z postaci binarnej pierwsze $l_i$ bitów po przecinku – będzie to nasze słowo kodowe:
$kod(A) = 0,\textbf{110}11 = 110$

$kod(B) = 0,\textbf{01}011 = 01$

$kod(C) = 0,\textbf{101}00 = 101$

$kod(D) = 0,\textbf{00}000 = 00$

Wynikiem kodowania będzie następujący łańcuch znaków:

110 110 110 01 01 01 01 01 01 101 101 101 101 00 00 00 00 00 00 00Indeks dolny 2₂

Kodowanie Huffmana

Kodowanie Huffmana to kolejna metoda bezstratnej kompresji danych. Jest to kodowanie prefiksowe polegające na zliczeniu częstości występowania danego ciągu liter lub znaków, które następnie będą kodowane zgodnie ze swoją częstością występowania. Więcej na temat tego kodowania możesz przeczytać w e‑materiale Kodowanie HuffmanaPt9KZMbi8Kodowanie Huffmana.

Wiadomość „AAABBBBBBCCCCDDDDDDD” po zastosowaniu kodowania Shannona przyjęłaby postać: 110 110 110 01 01 01 01 01 01 101 101 101 101 00 00 00 00 00 00 00Indeks dolny 2₂ i miałaby długość 47 bitów. Ta sama wiadomość zgodnie z kodowaniem Huffmana wyglądałaby następująco: 110 110 110 10 10 10 10 10 10 111 111 111 0 0 0 0 0 0 0 Indeks dolny 2₂ i miałaby długość 37 bitów.

Aby zdekompresować wiadomość zapisaną zgodnie z kodowaniem Shannona, należy dopasować metodą prób i błędów słowa kodowe do odpowiednich fragmentów wiadomości.

Aby zdekodować wiadomość zakodowaną zgodnie z kodowaniem Huffmana, możemy posłużyć się zbudowanym drzewem binarnymdrzewo binarnedrzewem binarnym i przechodzić po jego wierzchołkach zgodnie z kolejnymi bitami lub również próbować dopasowywać odpowiednie bity do słów kodowych.

Oczywiście możemy skonstruować drzewo również w kodowaniu Shannona, jednak posłużenie się nim byłoby działaniem dodatkowym, wymagającym kolejnych obliczeń.

Słownik

drzewo binarne

podtyp drzewa, w którym każdy wierzchołek ma nie więcej niż dwóch synów

kompresja bezstratna

kompresja, która pozwala po skompresowaniu odtworzyć dane wejściowe ze skompresowanej wiadomości

redundancja danych

nadmiarowość danych w bazie danych, które nie są konieczne do prawidłowego jej działania

system dwójkowy

(inaczej: binarny) system liczbowy, którego podstawą jest liczba 2, a do zapisu potrzebne są w nim tylko dwie cyfry: 0 i 1

Wprowadzenie

Animacja