Теория информации
Ни один код одного символа не является началом кода другого символа.
То есть, если у тебя есть коды a = 0, b = 01, то это не Фано — потому что 0 это начало 01.
Обратное условие Фано
Если код не удовлетворяет условию Фано, значит есть хотя бы один код, который является префиксом другого, и чтение закодированного сообщения может быть двусмысленным.
# Информационная энтропия
Информацио́нная энтропи́я — мера неопределённости некоторой системы. Характеризует непредсказуемость появления какого-либо символа алфавита.
Формула Шеннона для дискретного источника
где $p_i$ — вероятность появления i-го символа (например, байта 0..255). Получается среднее количество бит на символ в оптимальном коде.
Как оценить энтропию файла — шаги
- Посчитать частоты символов (например, байтов 0..255).
- Получить вероятности $p_i=\frac{count_i}{N}$.
- Посчитать $H=-\sum_ip_i\log_2p_i$.
- Оценить минимальный размер $≈ H×N$ бит.
Формула хартли
Формула Хартли или хартлиевское количество информации или мера Хартли — логарифмическая мера информации, которая определяет количество информации, содержащееся в сообщении.
Формула была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.