- алфавит (конечное, непустое множество) - множество двоек символов, - троек символов, и т.д.

- слова над алфавитом

- конкатенация:

1. Операция ассоциативна:
2. - нейтральный элемент Моноид

Код

Код однозначный (декодируемый), если: - то-есть иньективна

ZIP:
JPEG:

Раздельный (Гомоморфный) код (например конвертация "ч" в "ch" в заграннике)

Теорема

Не кода , который не увеличивает текст, а некоторый уменьшает (одноз. декодирование)

- строка - кол-во вхождений

План капкан:

• Префиксные коды
• Код Хаффмана
• Нер-во Крафта-МакМиллана

Префиксный код - однозначно декодируем

Пример:


Ни один код не является префиксом другого

Построим дерево для кода из примера:

Все коды - листья

Задача: ищем префиксный код,

Лемма 1

В дереве оптимального кода дав символа с являются братьями на максимальной глубине

- минимальные - самые глубокие

Метод Хаффмана

1. Берём два символа которые встречаются минимальное кол-во раз Они листья с максимальной глубиной
2. Обьеденим их в один символ
3. Рекурсивно повторяем, достраивая дерево

Пример:

Теорема (Нер-во Крафта МакМиллана)

- число вхождений
Можно построить однозначно декодируемый двоичный код с длинами