5. Системное ПО
Кодовые таблицы упрощают процедуру кодирования. Однако для длительного хранения информации или для ее передачи по каналу связи можно использовать более сложную процедуру кодирования, которая обеспечит уменьшение размера файла при сохранении исходной информации.
При упаковке по методу Хаффмана часто встречающиеся символы кодируются короткими последовательностями битов, а более редкие символы – длинными последовательностями. К каждому сжатому архиву прикладывается таблица соответствия имеющихся символов и кодов, заменяющих эти символы.
Рассмотрим пример.
Пусть входной алфавит сообщения состоит всего из четырех символов: а, b, с, d, частоты появления которых в исходном (несжатом) документе равны соответственно, 1/2, 1/4, 1/8 и 1/8. Кодирование Хаффмана для этого алфавита задается табл.
Текст abbadaca, представленный на входе кодом 00 01 01 00 11 00 10 00, после архивации будет иметь вид: 0 10 10 0 111 0 1100. Таким образом, 16 битов исходного текста превратились в 14 битов упакованной информации. Заметим, что указанные в таблице частоты не отражают реальной статистической картины частот появления букв английского алфавита, а взяты такими лишь для иллюстрации данной идеи (только для учебных целей).
Сжатие данных по методу Хаффмана производится в следующей последовательности .
Вначале производится анализ частоты повторения каждого символа сообщения. Затем наиболее часто встречающийся символ заменяется самым коротким кодом, а следующий по частоте появления символ кодируется более длинной последовательностью и т. д. К архиву прикладывается таблица соответствия сжатых и несжатых символов.
Вторая основная идея упаковки состоит в использовании того факта, что в сообщениях часто встречаются несколько подряд идущих одинаковых байтов, а некоторые последовательности байтов повторяются многократно. При упаковке такие места можно заменить командами вида «повторить данный байт п раз» или «взять часть текста длиной k байтов, которая встречалась т байтов назад». Такой алгоритм архивации носит имя RLE (Run Length Encoding – кодирование путем учета повторений).