Кодування Гаффмана: як зрозуміти стиснення без втрат

Коротко: Кодування Гаффмана дає частим символам короткі, а рідкісним — довгі бітові послідовності, тож дані зменшуються без втрати інформації.

Докладніше: Зазвичай кожен символ займає однакову кількість бітів (ASCII: 8). Але літери трапляються з різною частотою (у німецькій «e» дуже часта, «q» рідкісна). Девід Гаффман (1952) знайшов оптимальний безпрефіксний метод: часті символи → короткі коди.