Код на Хафман

Теория на информацията

Информационна поддръжка на системи за управление

Трансфер на данни

Кодът на Хъфман е изграден на базата на кодово дърво.

Кодово дърво - специална графика, която показва запис на всички възможни К -други н-битови числа, използвани като кодови комбинации за кодиране на съобщения в сумата М Ј K n . Освен това всяко число се показва от един от възлите на графиката. От всеки възел идва К клонове, които свързват този възел с други. Броят на символите, включени в числото, съответстващо на даден възел, се нарича негов ред.

Помислете за графика за двоичен триелементен код.

Фигура: 13 Двоично кодово дърво с три елемента

За да изградите оптимален код въз основа на кодово дърво, помислете за следното:

съобщението с най-голяма вероятност трябва да съответства на възела от най-ниския ред;
поне две съобщения с минимални вероятности трябва да бъдат кодирани от възли с максимален ред;
ако е избран възел за поръчка i, тогава всички възли от по-висок ред, свързани с него, не могат да бъдат използвани за кодиране, в противен случай еднозначната разграничимост на комбинациите няма да бъде извършена въз основа на факта, че нито един от тях не трябва да бъде началото на другия;
всички възможни възли за максимален ред не могат да се използват за кодиране на съобщения; това означава, че не всички възли от предишния ред са завършени (възел се нарича завършен, от който всички възможни К клонове);
ако комбинирате всички съобщения, кодирани от възли i -th ред, след това възела ( аз - 1) от тия ред ще съответства на съобщението с еквивалентна вероятност
.