Оптимальные префиксные коды

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

Предположим, для каждой буквы х ^ S существует относительная частотаf., представляющая долю в тексте букв, равных х. Другими словами, если текст состо- ит из n букв, то nfx из этих букв равны х. Сумма всех относительных частот равна 1,

то есть

Если префиксный код γ используется для кодирования заданного текста, то какой будет общая длина кодирования? Она будет равна сумме (по всем буквам х ^ S) количества вхождений х, умноженной на длину битовой цепочки γ(χ), ис- пользуемой для кодирования х. Если ^(х) обозначает длину γ^), этот факт можно записать в виде

Исключая коэффициент n из последнего выражения, получаем

среднее количество битов, необходимых для представления буквы. В дальнейшем эта величина обозначается ΑΒΙ(γ) (Average Bits per Letter).

В продолжение этого примера допустим, что имеется текст с буквами S = {a, b, c, d, e} и следующим набором относительных частот:

Тогда среднее количество битов на букву для префиксного кода γ1, определен- ного ранее, составит

0, 32 · 2 + 0,25 · 2 + 0,20 · 3 + 0,18 · 2 + 0,05 · 3 = 2,25.

Интересно сравнить эту величину со средним количеством битов на букву при использовании кодировки с фиксированной длиной. (Заметьте, что кодировка с фиксированной длиной является префиксным кодом: если все буквы кодиру- ются последовательностями одинаковой длины, то никакой код не может быть префиксом любого другого.) Очевидно, в множестве S из пяти букв для кодировки с фиксированной длиной понадобится три бита на букву, так как два бита позволят закодировать только четыре буквы. Следовательно, кодировка γ1 сокращает коли- чество битов на букву с 3 до 2,25 — экономия составляет 25 %.

На самом деле γ1 не лучшее, что можно сделать в этом примере. Рассмотрим префиксный код γ2, определяемый следующим образом:

Среднее количество битов на букву для γ2 составит

0, 32 · 2 + 0,25 · 2 + 0,20 · 2 + 0,18 · 3 + 0,05 · 3 = 2,23.

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

префиксный код называется оптимальным.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Оптимальные префиксные коды:

  1. СЛОВЕСНЫЕ УТЕЧКИ И РЕЧЕВЫЕ КОДЫ
  2. СЛОВЕСНЫЕ УТЕЧКИ И РЕЧЕВЫЕ КОДЫ
  3. ГЛАВА ШЕСТАЯ Коды входа в Телос
  4. Глава 21 ПАРНЫЕ КОДЫ И НАВЕДЕННЫЕ ПРОГРАММЫ. ПРИНЦИП АНАЛОГОВ
  5. Оптимальные условия
  6. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  7. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  8. 6.2.4. Поиск оптимальной финансовой модели СМИ
  9. 1.1.4. Оптимальная модель социальной сферы современного общества
  10. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  11. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  12. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  13. ПРИНЦИП КЛЮЧА — ПРИНЦИП ОПТИМАЛЬНОСТИ.
  14. ПРИНЦИП КЛЮЧА — ПРИНЦИП ОПТИМАЛЬНОСТИ.