Условие Фано

Ни один код одного символа не является началом кода другого символа.
То есть, если у тебя есть коды a = 0, b = 01, то это не Фано — потому что 0 это начало 01.

Обратное условие Фано

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

# Информационная энтропия

Информацио́нная энтропи́я — мера неопределённости некоторой системы. Характеризует непредсказуемость появления какого-либо символа алфавита.

Формула Шеннона для дискретного источника

где \(p_i\)​ — вероятность появления i-го символа (например, байта 0..255). Получается среднее количество бит на символ в оптимальном коде.

Как оценить энтропию файла — шаги

1. Посчитать частоты символов (например, байтов 0..255).
2. Получить вероятности \(p_i=\frac{count_i}{N}\).
3. Посчитать \(H=-\sum_ip_i\log_2p_i\).
4. Оценить минимальный размер \(≈ H×N\) бит.

   Формула хартли

Формула Хартли или хартлиевское количество информации или мера Хартли — логарифмическая мера информации, которая определяет количество информации, содержащееся в сообщении.

Формула была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.