Постановка задачи

У вас есть набор символов, каждому из которых соответствует известная частота (или вероятность) появления. Требуется присвоить каждому символу уникальную двоичную строку (кодовое слово) так, чтобы:

  • ни одно кодовое слово не было префиксом другого — это обеспечивает мгновенное и однозначное декодирование;
  • средняя длина закодированного сообщения (взвешенная по частотам символов) была минимальной.

 

Входные данные

  • Исходный алфавит $\Sigma = {\sigma_1, \sigma_2, \dots, \sigma_n}$.
  • Неотрицательная частота $p_\sigma$ для каждого символа $\sigma \in \Sigma$, где $n \ge 2$.

Выходные данные

Беспрефиксный двоичный код с минимально возможной средней длиной кодирования:

$$ \sum_{\sigma \in \Sigma} p_\sigma \cdot \text{(number of bits used to encode } \sigma \text{)} $$

Last updated 09 мая 2025, 23:43 +0500 . history