На этот раз Динго решил уделить немного внимания способам кодирования информации в вычислительной технике.
Любая информация выдаваемая компьютером (текстовая, звуковая, графическая) в привычном для нас виде представлена в памяти компьютера в виде последовательности бит. Иначе говоря это информация закодирована в двоичной системе. Например, в стандарте кодирования текстовой информации ASCII используется 8 битная кодировка символов (изначально было 7 битов). Такая система способна закодировать до 256 символов (2^8).
Как правило, кодирование предполагает, что каждому символу сопоставляется одинаковое количество битов - равномерный двоичный код.
Более компактным может являться неравномерный код, при котором каждый символ может быть закодирован различным числом битов. При этом часто, при построении неравномерного кода используется частота встречаемости символа в тексте - самым часто встречающимся символам присваивается самый короткий код. По данному принципу работает метод Хаффмана - жадный алгоритм оптимального кодирования алфавита.
Одной из важнейших задач в кодировании информации является возможность однозначно декодировать эту информацию в дальнейшем. В связи с этим коды символам назначаются в соответствии с условиями Фано. Общей формулировкой условия Фано является - "Никакое кодовое слово не может быть началом другого кодового слова".
Существует прямое и обратное условия Фано:
- Прямое условие Фано: никакой из кодов не совпадает с началом (префиксом) какого либо другого, более длинного кода.
- Обратное условие Фано: никакой из кодов не совпадает с окончанием (постфиксом) какого либо другого, более длинного кода.
Подписывайся на канал, чтобы узнавать больше интересных фактов из мира науки. Благодаря Вашим отзывам Динго сможет узнать, что нравится читателям.