дискретная-математика - Кодировка (длина кода)

Имеется в виду следующий "сюжет". Представим себе, что у нас имеется какой-нибудь файл, в котором с разной частотой могут встречаться те или иные символы. Пусть их всего имеется $%n$%. Можно рассмотреть случай $%n=256$%. Если каждый символ закодировать в виде 8-битного двоичного слова, файл всегда можно однозначно декодировать. Однако те или иные символы могут встречаться чаще или реже других. Тогда выгодно было бы "редкие" символы закодировать длинными словами (двоичными), а те, которые встречаются чаще -- более короткими. Точная постановка задачи такая.

Даны положительные числа $%p_1,\ldots,p_n$%, сумма которых равна 1. Это частоты символов; они как бы даны нам "сверху". Например, при чтении файла мы можем составить частотный словарик, и эти числа узнать. Требуется построить однозначно декодируемый двоичный код, у которого длины кодовых слов равны $%l_1,\ldots,l_n$% соответственно. При этом требуется, чтобы средняя длина кодового слова, то есть величина $%p_1l_1+\cdots+p_nl_n$%, была минимально возможной.

Общее решение этой задачи излагается в учебниках по дискретной математике -- см., например, книгу С.В.Яблонского (раздел про коды с минимальной избыточностью, или коды Хаффмана).

Здесь требуется подобрать 5 таких чисел (частот), чтобы ни у какого кодового слова длина не оказалась равной 1. Этого добиться легко, если не брать "слишком больших" частот. Скажем, если один символ встречается с частотой 96%, а остальные четыре с частотой 1%, то становится ясно, что первый из них выгодно закодировать всего одним символом (например, 0), а остальные четыре -- кодовыми словами типа 100, 101, 110, 111 длины три.

Если же взять равные или примерно равные частоты -- например, 20% для каждого из символов, то по алгоритму Хаффмана будет построен код типа 000, 001, 01, 10, 11 с длинами кодовых слов 2 или 3. Он будет при этом однозначно декодируемым и оптимальным.