Методы эффективного кодирования

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Теорема Шеннона не указывает способа кодирования. Первый из методов эффективного кодирования – код Шеннона-Фано. Рассмотрим его подробнее.

Знаки алфавита сообщения выписывают в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве единичного символа присваивают 0, а всем нижним – 1. Каждую из полученных групп, в свою очередь, разбивают на две подгруппы с одинаковыми вероятностями и присваивают 2-й знак, и продолжают процесс до исчерпания символов. Методика годится не для всех возможных алфавитов.

Методика Хаффмана гарантирует однозначное построение кода с наименьшим средним числом знаков на букву.

1. Подсчитываются вероятности появления знаков алфавита в исходном тексте (если они не заданы заранее)

2. Знаки алфавита сообщения выписывают в порядке убывания вероятностей.

3. Последние 2 знака объединяют в новый (составной) знак, вероятность которого равна суммарной вероятности этих знаков. Удаляют эти знаки и вставляют составной в список остальных знаков на соответствующее место (по вероятности). Последние 2 знака снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив знаки, вошедшие в объединение.

4. Предыдущий шаг повторяют до тех пор, пока сумма всех знаков не станет равной 1.

Этот процесс можно представить как построение дерева, корень которого – знак с вероятностью 1, получившийся при объединении знаков из последнего шага, его потомки – знаки из предыдущего шага и т. д.

Каждые m₂ элементов, стоящих на одном уровне, нумеруются от 0 до m₂-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится знак, стоящий в листе и производится возврат в корень.

Бинарное дерево, соответствующее коду Хаффмана, называют деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева.

1. Составим список кодируемых знаков (при этом будем рассматривать каждый знак как одноэлементное бинарное дерево, вес которого равен весу знак).

2. Из списка выберем 2 узла с наименьшим весом (под весом можно понимать частоту использования знак – чем чаще используется, тем больше весит).

3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

5. Если в списке больше одного узла, то повторить 2-5.

Более удобна методика, использующая принцип префиксности кодов, при которой эффективный код строится так, чтобы ни одна комбинация кода не совпадала с началом более длинной комбинации.

Недостатки системы эффективного кодирования:

– различие в длине кодовых комбинаций требует буферов на обеих сторонах канала;