Сжатие данных

 В основе алгоритмов сжатия без потерь лежат свойства префиксных кодов, а именно то, что их алфавит можно представить кодами разной длинны.

 Префисный код - код переменной длинны позволяющий однозначно декодировать его в сообщении.Таким образом хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа.  

 Идея, положенная в основу кода Шеннона, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Это нужно, так как мы хотим, чтобы, когда мы обработали весь ввод, самые частотные символы заняли меньше всего места ( и меньше, чем они занимали в оригинале), а самые редкие — побольше (но так как они редкие, это не имеет значения). Например  буквенно цифровое сообщение 2,1,1,1,3 в бинароном виде будет представлено как 10 01 01 01 11 (10 bit)  а в префисном коде как 01 1 1 1 001 (8 bit)

Алгоритм Хаффмана — это еще один из алгоритмов получения оптимальных префиксных кодов переменной длины.