Коды Фано и Хаффмана
Проверка условия Фано, построение кода Хаффмана, однозначность декодирования и кратчайший код для новой буквы — задачи ЕГЭ.
Калькулятор кодов Фано и Хаффмана проверяет условие Фано, строит оптимальный код Хаффмана по частотам символов или по тексту, проверяет однозначность декодирования и подбирает кратчайший код для новой буквы — типовые задачи ЕГЭ.
Условие Фано
Ни одно кодовое слово не должно быть началом (префиксом) другого. Тогда сообщение декодируется однозначно и сразу. Если выполняется обратное условие — ни одно слово не является окончанием другого, — сообщение тоже декодируется однозначно, но с конца.
Код Хаффмана
Два символа с наименьшими частотами объединяются в узел, и так до одного дерева; левая ветвь — 0, правая — 1. Частые символы получают короткие коды, общая длина сообщения минимальна.
Однозначность декодирования
Если условие Фано не выполняется, однозначность проверяют алгоритмом Сардинаса — Паттерсона: ищут «висячие» окончания и проверяют, не совпадёт ли одно из них с кодовым словом.
Пример. Коды А — 00, Б — 010, В — 011, Г — 101. Код для новой буквы: слова длины 1 не подходят (0 — начало кода А, 1 — начало кода Г), из слов длины 2 подходит только 11.
Комментарии
Комментариев пока нет.