Один из методов сжатия данных заключается в оптимальном кодировании символов. Общеупотребительный код ASCII не дает полного кодирования.
Числовые данные более экономно держать в БД в двоичном виде, алфавитные данные в 5-ти битах кодируются более эффективно, чем в 8-ми. В компактном коде наряду с другими управляющими символами есть символы буквенного и цифрового регистра, которые меняют значения битовых комбинаций.
В 5-ти битовом коде с тремя регистрами можно закодировать практически любые нужные символы. В нем биты 1, 2, 3 и 5 несут информацию, а бит 4 (всегда равный 0) игнорируется. Любой 8-ми битовый символ можно представить двумя 5-ти битовыми.
Коды с символами разной длины.Обычно при кодировании на каждый символ отводится фиксированное число битов. Однако более плотную упаковку можно построить, применяя коды с переменной длиной символов, так называемые неравномерные коды. В них часто встречающиеся символы кодируются короткими комбинациями, а встречающиеся редко - длинными. Самый короткий и наиболее употребительный символ кодируется одним битом. Например, предположим, что надо кодировать только четыре символа: А, В. С, Д. При способе кодирования с фиксированной длиной символов на каждый символ потребуется два бита. Пусть указанные символы встречаются с частотами 60, 25, 10 и 5% соответственно. Поскольку А встречается чаще других закодируем его одним битом равным 0. Чтобы распознать начало символа, коды всех остальных символов должны начинаться с 1. Следующий по распространенности - это символ В. Закодируем его двумя битами: В = 10. Чтобы оставшиеся символы отличались от В, их коды не должны начинаться с 10. Поэтому символам С и Д можно присвоить коды ПО и 111 соответственно. При таком кодировании взвешенная длина одного символа оказывается равной 1.55 бита, что меньше 2-х бит при представлении символов в коде с фиксированной длиной.
Рассматриваемый вид кодирования был впервые предложен Д. А. Хаффманом и называется по имени автора. Такая схема кодирования дает эффект только за счет неравномерности распределения частот. Если бы частоты возникновения символов были бы равны между собой, то среднее число битов на символ оказалось бы больше, чем при фиксированной длине символов (2,25 > 2). Чем неравномернее частоты, тем эффективнее код Хаффмана. Так в английском тексте буквы встречаются с разной частотой и в коде Хаффмана средняя длина символа составляет 4.12 бита. В коммерческой информации в изобилии содержатся цифры и много нулей. Были измерены относительные частоты встречаемости символов в файлах коммерческих БД. Для них можно достичь средней длины кода около 3-х бит на символ. В настоящее время известно достаточно большое число кодов с символами переменной длины.
Реализация кода Хаффмана в настоящее время осуществляется преимущественно программным методом. Хотя возможна и аппаратная реализация. Так фирма Codex реализовала аппаратное сжатие данных в интеллектуальных сетевых процессорах серии 6000.
Простой метод преобразования в код Хаффмана состоит в использовании исходных символов в качестве адресов таблицы памяти, из ко горой выбираются сжатые символы. Поскольку позиции в памяти имею! фиксированную длину, а символы в коде Хаффмана - переменную. В каждой позиции таблицы должно быть указано, какие биты используются.
Обратное преобразование можно также в принципе проводить различным способом. Однако при простом одноразовом поиске число позиций в таблице должно быть очень большим и большинство из них будут пустыми. Поэтому, для сокращения объема таблиц применяют поиск с древовидной структурой. Дерево поиска зависит от способа кодирования. Поэтому если применяются несколько разных кодов, то преобразование удобнее осуществлять с помощью программных средств.
При применении кода Хаффмана к обычному тексту с прописными и строчными буквами, цифрами и знаками препинания, а также управляющими символами удается получить 4,9 бита на символ.
Большего уменьшения объема удавалось получить, если сначала уплотнялись повторяющиеся символы, а затем применялся код Хаффмана. Исследования по применению кода Хаффмана к сжатию данных позволяли получать уплотнения от 35 до 75 %.
Сочетание методов позволяет получить и более впечатляющие результаты.
