Ściskanie informacji

🎯 Po co Ci to?

W poprzedniej jednostce wyszło Ci, że zdjęcie „waży" 144 MB, a z aparatu wychodzi plik 4 MB. Ktoś po drodze zmniejszył dane trzydziestosześciokrotnie — i nie widać różnicy. Jak? I czemu ta sama sztuczka nie działa na plik z programem, gdzie każdy bajt jest święty? Kompresja to jedna z tych technologii, których używasz setki razy dziennie, nie wiedząc o tym: każda strona internetowa, każdy film, każda rozmowa wideo dociera do Ciebie ściśnięta.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wyjaśnić, na czym polega kompresja bezstratna, i wykonać ręcznie prostą kompresję (RLE);
  • wyjaśnić ideę kompresji stratnej i wskazać, co i dlaczego wolno „wyrzucić";
  • dobrać rodzaj kompresji do rodzaju danych — i uzasadnić, czemu nie da się ścisnąć wszystkiego.

📘 Wyjaśnienie

Kompresja bezstratna: zapisz to samo krócej. Dane bywają rozrzutne. Jeśli w obrazie sto pikseli z rzędu jest białych, bitmapa zapisuje sto razy „biały". A można inaczej:

💭 Pomyśl: Wiersz obrazu wygląda tak: BBBBBBBBBBCCBBBBBB (B = biały, C = czarny). Wymyśl zapis krótszy, z którego da się odtworzyć wiersz co do piksela.

Sprawdź odpowiedź

Na przykład: 10B 2C 6B — „dziesięć białych, dwa czarne, sześć białych". Z 18 znaków zostało 8, a informacja jest identyczna. Ten pomysł nazywa się kodowaniem długości serii (RLE, run-length encoding) i naprawdę bywa używany — np. w faksach i prostych formatach obrazów.

To jest kompresja bezstratna: po rozpakowaniu odzyskujesz dane co do bitu. Prawdziwe archiwizatory (formaty w rodzaju ZIP) idą dalej niż RLE: wyszukują powtarzające się fragmenty i zapisują je raz, a potem tylko odwołania („to samo, co 40 bajtów temu"), oraz dają częstym symbolom krótsze kody bitowe niż rzadkim. Wspólny mianownik: wykorzystać regularność danych. Tekst po polsku, tabela z powtarzającymi się nazwami, logo z płaskimi plamami koloru — ściskają się świetnie.

I tu ważna granica: danych bez regularności nie da się ścisnąć bezstratnie. Ciąg naprawdę losowych bitów nie ma się czym „streszczać". Prosty argument, że cudownej kompresji nie ma: gdyby każdy plik dało się skrócić choć o bit, to plików 1000-bitowych (jest ich $2^{1000}$) nie dałoby się wzajemnie jednoznacznie upchnąć w krótszych zapisów, bo tych jest mniej ($2^{999}+2^{998}+\dots < 2^{1000}$). Coś musiałoby się pomylić przy rozpakowaniu. Dlatego spakowanie ZIP-a drugi raz nic już nie daje — regularności zjadło pierwsze pakowanie.

Kompresja stratna: wyrzuć, czego nie zauważysz. Zdjęcia i dźwięk mają inną naturę: są pomiarami świata oglądanymi przez niedoskonałe zmysły. Skoro oko słabo widzi drobne różnice kolorów (dużo słabiej niż różnice jasności), a ucho nie słyszy cichego tonu tuż po głośnym — po co przechowywać to, czego odbiorca i tak nie odbierze? Formaty stratne (JPEG dla zdjęć, MP3 i pokrewne dla dźwięku, kodeki wideo) modelują ludzką percepcję i wyrzucają informację od najmniej zauważalnej. Stąd ich potęga: 10–30 razy mniejsze pliki przy niezauważalnej stracie — i stąd ich ryzyko: strata jest nieodwracalna, a każdy kolejny zapis stratny dokłada swoją.

Którą wybrać? Kryterium jest jedno: czy wolno stracić choć bit. Program, arkusz z ocenami, dokument prawny, kod źródłowy — tylko bezstratnie (jeden zmieniony bit programu to inny program). Zdjęcie na komunikator, muzyka do biegania, wideorozmowa — stratnie, bo liczy się rozmiar, a odbiorcą jest zmysł, nie procesor. Fotograf trzyma oryginał bezstratnie, a wysyła wersję stratną — i to jest wzorcowy kompromis.

⚠️ Uwaga, pułapka

„Skompresowałem zdjęcie do ZIP-a, więc mogę skasować oryginał" — możesz, ZIP jest bezstratny. Ale „zapisałem mem po raz dziesiąty w formacie stratnym" to dziesięć kolejnych strat — stąd charakterystyczna „rozmyta zupa" wielokrotnie przesyłanych obrazków. Bezstratna: pakuj do woli. Stratna: każde pokolenie zapisu kosztuje.

🛠️ Teraz Ty

Bez komputera: zakoduj RLE wiersz AAAABBBAACCCCCCCC, a potem odkoduj 3X 1Y 5X 2Y. Zastanów się, dla jakiego wiersza RLE wydłuża zapis zamiast skracać. Z komputerem: spakuj do ZIP-a długi plik tekstowy i zdjęcie z telefonu; porównaj, o ile procent zmalał każdy — i wyjaśnij różnicę tym, czego nauczyłeś się dzisiaj.

📐 Definicje tej lekcji

  • Kompresja bezstratna — skrócenie zapisu z gwarancją odtworzenia danych co do bitu; działa dzięki regularnościom.
  • Kompresja stratna — zmniejszenie danych przez nieodwracalne usunięcie informacji najmniej istotnej dla odbiorcy (percepcji).
  • RLE (kodowanie długości serii) — najprostsza kompresja bezstratna: serie powtórzeń zapisuje jako „ile × co".

📌 Najważniejsze w pigułce

  • Bezstratna streszcza regularności; losowego szumu nie ściśnie nikt i nic.
  • Stratna wyrzuca to, czego zmysły nie zauważą — zysk ogromny, strata nieodwracalna.
  • Dobór: dane „cyfrowe z natury" (kod, dokumenty) — bezstratnie; pomiary świata dla ludzkich zmysłów — stratnie.

🎒 Zadania

  1. Zakoduj RLE: WWWWWWWWWWWWCCWWWWWWWWWWWW (12 W, 2 C, 12 W). O ile skrócił się zapis? Podaj też przykład danych, na których RLE zawiedzie.
Wskazówka i odpowiedź

12W 2C 12W — z 26 symboli do ~7: ponad trzykrotnie. Zawiedzie na danych bez serii, np. ABABABAB: zapis „1A 1B 1A 1B…" jest dłuższy niż oryginał. Morał ogólniejszy niż RLE: każda metoda bezstratna ma dane, na których powiększa plik — kompresja to zakład o regularność, nie magia.

  1. Znajomy wysyła Ci ten sam dokument dwa razy: raz jako ZIP, raz „ZIP w ZIP-ie". Drugi plik jest odrobinę większy. Wyjaśnij dlaczego.
Wskazówka i odpowiedź

Pierwsze pakowanie zużyło regularności — wynik wygląda niemal jak szum. Drugie pakowanie nie ma czego streszczać, a musi dołożyć własne metadane (nagłówki archiwum, sumy kontrolne) — stąd lekki przyrost. To praktyczna ilustracja granicy z 📘: nie istnieje kompresja skracająca wszystko.

  1. Szkoła archiwizuje: (a) świadectwa w PDF, (b) nagrania z monitoringu, (c) kopie zapasowe dziennika elektronicznego, (d) zdjęcia z balu na stronę WWW. Dla każdego wybierz rodzaj kompresji i uzasadnij jednym zdaniem.
Wskazówka i odpowiedź

(a) bezstratna — dokument urzędowy musi być wierny co do znaku; (b) stratna — godziny wideo są ogromne, a liczy się rozpoznawalność zdarzeń, nie perfekcja klatki; (c) bezstratna — dane, z których się odtwarza system, nie mogą mieć przekłamań; (d) stratna — zdjęcia dla ludzkiego oka, priorytetem szybkie ładowanie strony.

🔍 Sprawdź, czy umiesz

  • Wykonać i odwrócić kompresję RLE na kartce.
  • Wyjaśnić, czemu ZIP nie zmniejszy losowych danych ani samego siebie.
  • Rozstrzygnąć dla pięciu typów plików, która kompresja jest właściwa.

Ucz się tej jednostki z asystentem