Łódzkie Towarzystwo Naukowe - Łódź Innowacyjna od zawsze

Kodowanie Huffmana


Data 18.04.2018

Godzina 09:00 - 09:45

Miejsce imprezy Wydział Matematyki i Informatyki UŁ

Adres ul. Banacha 22

Numer sali D102

Rodzaj imprezy wykład
prezentacja multimedialna

Organizator Uniwersytet Łódzki - Wydział Matematyki i Informatyki

Prowadzący imprezę dr Marek Majewski

Adresaci imprezy Liceum

Wymagana wcześniejsza rejestracja na imprezę:

E-mail festiwal@math.uni.lodz.pl

Opis imprezy

Jak zakodować tekst używając zer i jedynek? Każdej literze trzeba przyporządkować pewien ciąg zer i jedynek (będziemy taki ciąg-kod nazywać binarnym). Jeżeli mamy dziesięć różnych liter, a każda litera ma mieć kod binarny jednakowej długości, to potrzebujemy kodów długości co najmniej 4 (wszystkich ciągów binarnych długości 3 jest 8 - to za mało dla 10 liter, a długości 4 - 16 - za dużo, ale nie musimy użyć wszystkich kodów). A jeśli kody liter nie muszą mieć tej samej długości? Wtedy możemy częściej występujące w tekście litery zakodować krótszymi kodami. Cały kod zdania złożonego z kodowanych liter może być wtedy znacznie krótszy. Ale jak rozpoznać gdzie kończy się, a gdzie zaczyna litera, jeśli nie mają one tej samej, stałej długości? Z pomocą przychodzi nam tu kodowanie Huffmana oparte na tak zwanych kodach prefiksowych (żaden kod litery nie może być początkiem - prefiksem kodu innej litery). Okazuje się, że metodę takiego kodowania łatwo zdefiniować za pomocą drzewa. W wykładzie oprócz konstrukcji takiego drzewa przedstawimy również inne warianty kodowania Huffmana.