“e” - 4, “b” - 3, “ “ - 2, “o” – 2, “p” – 2, “r” – 1, “!” – 1 Далее формируется так называемое дерево Хаффмана. Для его построения применяется следующий алгоритм: Формируется новый узел и присоединяется к нему, в качестве дочерних, два узла выбранных из списка. При этом частоту появления сформированного узла положим равной сумме частот дочерних узлов. Добавим сформированный узел к списку. Если в списке больше одного узла, то повторить 1-3.
Метод RLE (Run Length Encoding) является одним из самых быстрых и простых и понятных алгоритмов сжатия информации. В некоторых случаях он является достаточно эффективным. Данный метод применяется для сжатия изображений в формате PCX. Принцип работы этого алгоритма можно описать так: последовательность повторяющихся символов заменяется последовательностью из трёх байт – байта prefix, указывающего, что встретилась последовательность повторяющихся символов, байта length, указывающего длину последовательности и байта symbol, указывающего собственно символ, из которых состоит последовательность. Рассмотрим работу данного алгоритма на примере конкретной: шестнадцатеричной последовательности 05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF из 20 байт. Выберем в качестве префикса байт FF. Тогда на выходе архиватора мы получим последовательность FF 05 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF Длина выходной последовательности - 18 байт, соответственно достигнуто некоторое сжатие. Однако, нетрудно заметить, что при кодировании некоторых символов размер выходного кода возрастает (например, вместо 01 01 - FF 02 01). Очевидно, что последовательности повторяющиеся символов длиною менее четырёх кодировать бессмысленно - их надо записывать в явном виде. Получим новую последовательность: FF 06 05 01 01 FF 06 03 05 03 FF 04 FF
Do'stlaringiz bilan baham: |
