Алгоритм построения дерева
Пример: построить дерево Хаффмана и найти префиксные коды для сообщения: «КОЛ_ОКОЛО_КОЛОКОЛА» Решение: · Составим таблицу частот вхождения символов
· Построим дерево Хаффмана Блочное кодирование по методу Хаффмана формирует коды для буквосочетаний, составленных из m символов исходного алфавита. Буквосочетания можно рассматривать как новый, расширенный алфавит объемом K=Nm , где N – объем исходного алфавита; M – число символов в буквосочетании. Блочное кодирование применяется к алфавитам, в которых вероятность появления одной какой-то буквы значительно превышает вероятность появления других букв.
Рассчитаем коэффициент сжатия сообщения. Пример 3. Вычислили объем сообщения «КОЛ ОКОЛО КОЛОКОЛА» при использовании кодировок ASCII (Vascii =144 бита) и Unicode (Vunicode = 288 бит). Выше построили код Хаффмана для этой же фразы, на основании которого оценили объем сообщения Vхаффмана=39 бит. В результате мы получаем коэффициент сжатия равный 144/39 = 3,7 для кодировки ASCII и 288/39 =7,4 для кодировки Unicode. Метод RLE В основу алгоритмов RLE (Run-Length Encoding – кодирование путем учета числа повторений) положен принцип выявления повторяющихся последовательностей данных и замены их простой структурой: повторяющийся фрагмент и коэффициент повторения. Рассмотрим идею сжатия методом RLE. Во входной последовательности: 1. все повторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, повторяющийся байт}, причем управляющий байт в десятичной системе счисления должен иметь значение 128 + число повторений байта. Это означает, что старший бит управляющего байта для цепочки повторяющихся байтов всегда равен 1. 2. все неповторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, цепочка неповторяющихся байтов}, причем управляющий в десятичной системе счисления должен иметь значение 0+ длина цепочки. Это означат, что старший бит управляющего байта для цепочки неповторяющихся байтов всегда равен 0. Замечание. В обоих случаях длина обрабатываем фрагмента не может превосходить 127 байт.
Пример 4. Упакуем методом RLE следующую последовательность из 14-ти байтов: 11111111 11111111 11111111 11111111 11111111 11110000 00001111 11000011 10101010 10101010 10101010 10101010 10101010 10101010 В начале последовательности 5 раз повторяется байт 11111111. Чтобы закодировать эти 5-ть байтов, запишем вначале управляющий байт 10000101, а затем сам повторяющийся байт 11111111. Рассмотрим как получился управляющийся байт: к значению 128 мы прибавили число повторений байта 5, получили 13310=100001012. Далее идут 3 разных байта. Чтобы их закодировать, мы записываем управляющий байт 00000011 (112=310), а затем эти неповторяющиеся байты. Далее в последовательности 7 раз идет байт 10101010. Чтобы закодировать эти 7 байтов, мы записываем управляющий байт 10000111 (128+7=13510=10001112), а затем повторяющийся байт 10101010. В результате применения метода RLE мы получаем последовательность из 8-ми байтов: 10000101 11111111 00000011 11110000 00001111 11000011 10000111 10101010. Таким образом, коэффициент сжатия 14/8=1,75. Схема распаковки: 1. Если во входной (сжатой) последовательности встречается управляющий байт с единицей в старшем бите, то следующий за ним байт данный надо записать в выходную последовательность столько раз, сколько указано в оставшихся 7-ми битах управляющего байта. 2. Если во входной (сжатой) последовательности управляющий байт с нулем в старшем бите, то в выходную последовательность нужно поместить столько следующих за управляющим байтов входной последовательности, сколько указано в оставшихся 7-ми битах управляющего байта. Пример 5. Распакуем сжатую последовательность данных методом RLE: 00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101. Первый байт данной последовательности управляющий 000000010, начинается с 0. Следовательно, следующие за ним 102=210 байта помещаются в выходную последовательность. Замечание. Будем зачеркивать обработанные байты. 00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101 Следующий управляющий байт 10000110 начинается с 1. Следовательно, следующий за ним байт нужно поместить в выходную последовательность 1102=610 раз. 00000010 00001111 11110000 10000110 11000011 00000011 00001111 00111100 01010101 Следующий управляющий байт 00000011 начинается с 0. Следовательно, следующие за ним 112=310 байта нужно поместить в выходную последовательность. Таким образом, все входные данные мы обработали. А распакованная последовательность байтов выглядит следующим образом: 00001111 11110000 11000011 11000011 11000011 11000011 11000011 11000011 00001111 00111100 01010101
Наилучшими объектами для данного алгоритма являются графические данные, в которых встречаются большие одноцветные участки. Различные реализации данного метода используются в графических форматах PCX, BMP и факсимильной передаче информации. Для текстовых данных данный метод неэффективен.
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (774)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |