|
Deja Vu #0A
30 сентября 2000 |
|
__________________________________________ (C) N.B. __________________________________________ Немного относительно методов упаковки данных. Здесь рассматриваются только алгоритмы, производящие сжатие без потерь, т.е. допу- скающие восстановление исходной информа- ции "байт в байт". Running - Это самый простой из методов упаковки информации. Предполо- жите, что Вы имеете строку текста,и в кон- це строки стоит 40 пробелов. Налицо явная избыточность имеющейся информации. Пробле- ма сжатия этой строки решается очень прос- то - эти 40 пробелов ( 40 байт ) сжимаются в 3 байта с помощью упаковки их по методу повторяющихся символов (running). Первый байт, стоящий вместо 40 пробелов в сжатой строке, фактически, будет являться пробе- лом (последовательность была из пробелов). Второй байт - специальный байт "флажка", который указывает, что мы должны развер- нуть предыдущий в строке байт в последова- тельность при восстановлении строки. Тре- тий байт - байт счета (в нашем случае -это будет 40). Как Вы сами можете видеть, дос- таточно, чтобы любой раз, когда мы имеем последовательность из более 3-х одинаковых символов, заменять их выше описанной пос- ледовательностью, чтобы на выходе получить блок информации меньший по размеру, но до- пускающий восстановление информации в ис- ходном виде. Оставляя все сказанное выше истинным, добавлю лишь то, что в данном методе ос- новной проблемой является выбор того само- го байта "флажка", так как в реальных бло- ках информации, как правило, используются все 256 вариантов байта, и нет возможности иметь 257-ой вариант - "флажок". На первый взгляд эта проблема кажется неразрешимой, но к ней есть ключик, который Вы найдете, прочитав о кодировании с помощью алгоритма Хаффмана ( Huffman ). LZW - История этого алгоритма начинает- ся с опубликования в мае 1977 г. Дж. Зивом (J. Ziv) и А. Лемпелем (A. Lem- pel) статьи в журнале "Информационные тео- рии" под названием "IEEE Trans". В послед- ствии,этот алгоритм был доработан Терри А. Велчем (Terry A. Welch), и в окончательном варианте отражен в статье "IEEE Compute" в июне 1984. В этой статье описывались под- робности алгоритма и некоторые общие проб- лемы, с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch). Алгоритм LZW представляет собой алго- ритм кодирования последовательностей нео- динаковых символов. Возьмем, для примера, строку "Объект TSortedCollection порожден от TCollection.". Анализируя эту строку,мы можем видеть, что слово "Collection" пов- торяется дважды. В этом слове 10 символов - 80 бит. И если мы сможем заменить это слово в выходном файле,во втором его вклю- чении на ссылку на первое включение,то по- лучим сжатие информации. Если рассматри- вать входной блок информации размером не более 64К и ограничиться длиной кодируе- мой строки в 256 символов, то, учитывая байт "флаг", получим, что строка из 80 бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе сжатия фай- ла. Если существуют повторяющиеся строки в файле, то они будут закодированны в табли- цу. Очевидным преимуществом алгоритма яв- ляется то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжа- тие по алгоритму LZW является однопроход- ной операцией в противоположность алгорит- му Хаффмана (Huffman), которому требуется два прохода. Huffman - Сначала кажется, что создание файла меньших размеров из ис- ходного без кодировки последовательностей или исключения повтора байтов будет невоз- можной задачей. Но давайте мы заставим се- бя сделать несколько умственных усилий и понять алгоритм Хаффмана (Huffman). Поте- ряв не так много времени, мы приобретем знания и дополнительное место на дисках. Сжимая файл по алгоритму Хаффмана, пер- вое, что мы должны сделать - это необходи- мо прочитать файл полностью и подсчитать, сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового или другого файла. После подсчета частоты вхождения каж- дого символа, необходимо просмотреть таб- лицу кодов ASCII, и сформировать мнимую компоновку между кодами по убыванию. Т.е., не меняя местонахождение каждого символа из таблицы в памяти, отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем "узлом". В дальнейшем (в дереве) мы будем позже раз- мещать указатели, которые будут указывать на этот "узел". Для ясности давайте рас- смотрим пример: Мы имеем файл длиной в 100 байт и имею- щий 6 различных символов в себе. Мы под- считали вхождение каждого из символов в файл и получили следующее: |-----------------|-----|-----|-----|-----|-----|-----| | cимвол | A | B | C | D | E | F | |-----------------|-----|-----|-----|-----|-----|-----| | число вхождений | 10 | 20 | 30 | 5 | 25 | 10 | |-----------------|-----|-----|-----|-----|-----|-----| Теперь мы берем эти числа и будем назы- вать их частотой вхождения для каждого символа. Разместим таблицу, как ниже. ------------------------------------------ cимвол C E B F A D ------------------------------------------ число вхождений 30 25 20 10 10 5 ------------------------------------------ Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае -это D (5) и какой-либо символ из F или A (10), можно взять любой из них, например A. Сформируем из узлов D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A : Частота 30 10 5 10 20 25 Символа C A D F B E ---- - 15 = 5 + 10 -- Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исклю- чая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной часто- той вхождения. Самая низкая частота теперь у F и нового "узла".Снова сделаем операцию слияния узлов: Частота 30 10 5 10 20 25 Символа C A D F B E ?-- -15 - ?-- ----25- = 10 + 15 -- Рассматриваем таблицу снова для следую- щих двух символов ( B и E ). Мы продолжаем этот режим пока все "дерево" не сформиро- вано, т.е. пока все не сведется к одному узлу. Частота 30 10 5 10 20 25 Символа C A D F B E ?-- -15 - ?-- ?--- ----25- -45- - - ?-- ----55------ - ------------ --- Root (100) --- ------------ Теперь, когда наше дерево создано, мы можем кодировать файл.Мы должны всегда на- чинать из корня ( Root ). Кодируя первый символ (лист дерева С), мы прослеживаем вверх по дереву все повороты ветвей, и,ес- ли мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C - 00. Для следующего символа (А) у нас получается -лево, право, лево, лево, что выливается в последовательность 0100. Выполнив вышесказанное для всех символов получим: C = 00 ( 2 бита ) A = 0100 ( 4 бита ) D = 0101 ( 4 бита ) F = 011 ( 3 бита ) B = 10 ( 2 бита ) E = 11 ( 2 бита ) Каждый символ изначально представлялся 8-ю битами ( один байт ), и т.к. мы умень- шили число битов,необходимых для представ- ления каждого символа, мы, следовательно, уменьшили размер выходного файла. Сжатие складывется следующим образом: ----------------------------------------------------------- Частота первоначально уплотненные биты уменьшено на ----------------------------------------------------------- C 30 30 x 8 = 240 30 x 2 = 60 180 A 10 10 x 8 = 80 10 x 3 = 30 50 D 5 5 x 8 = 40 5 x 4 = 20 20 F 10 10 x 8 = 80 10 x 4 = 40 40 B 20 20 x 8 = 160 20 x 2 = 40 120 E 25 25 x 8 = 200 25 x 2 = 50 150 ----------------------------------------------------------- Первоначальный размер файла: 100 байт - 800 бит; Размер сжатого файла:30 байт - 240 бит; 240 - 30% из 800, так что мы сжали этот файл на 70%. Все это довольно хорошо,но неприятность находится в том факте,что для восстановле- ния первоначального файла, мы должны иметь декодирующее дерево, так как деревья будут различны для разных файлов. Следовательно, мы должны сохранять дерево вместе с фай- лом. Это превращается в итоге в увеличение размеров выходного файла. В нашей методике сжатия и каждом узле находятся 4 байта указателя,поэтому полная таблица для 256 байт будет приблизительно 1 Кбайт длиной. Таблица в нашем примере имеет 5 узлов плюс 6 вершин (где и находятся наши симво- лы), всего 11. 4 байта 11 раз - 44. Если мы добавим после небольшое количество бай- тов для сохранения места узла и некоторую другую статистику -наша таблица будет при- близительно 50 байтов длины. Добавив к 30 байтам сжатой информации 50 байтов таблицы - получаем, что общая длина архивного файла вырастет до 80 байт. Учитывая, что первоначальная длина файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации. Не плохо. То что мы действительно вы- полнили - трансляция символьного ASCII на- бора в наш новый набор, требующий меньшее количество знаков по сравнению с стандарт- ным. Что мы можем получить на этом пути? Рассмотрим максимум, который мы можем получить для различных разрядных комбина- ций в оптимальном дереве, которое является несимметричным. Мы получим, что можно иметь только: 4 - 2 разрядных кода; 8 - 3 разрядных кодов; 16 - 4 разрядных кодов; 32 - 5 разрядных кодов; 64 - 6 разрядных кодов; 128 - 7 разрядных кодов; Необходимо еще два 8-разрядных кода. 4 - 2 разрядных кода; 8 - 3 разрядных кодов; 16 - 4 разрядных кодов; 32 - 5 разрядных кодов; 64 - 6 разрядных кодов; 128 - 7 разрядных кодов; -------- 254 Итак, мы имеем итог из 256 различных комбинаций,которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов, которые это представляют, то в итоге получим 1554 бит или 195 байтов. Так, в максимуме, мы сжали 256 байт к 195 или 33%, таким образом мак- симально идеализированный Huffman может достигать сжатия в 33%, когда используется на уровне байта. Все эти подсчеты производились для не префиксных кодов Хаффмана, т.е. кодов, ко- торые нельзя идентифицировать однозначно. Например,код A - 01011 и код B - 0101. Ес- ли мы будем получать эти коды побитно,то, получив биты 0101, мы не сможем сказать какой код мы получили - A или B, т.к. сле- дующий бит может быть как началом следую- щего кода, так и продолжением предыдущего. Необходимо добавить, что ключем к пост- роению префиксных кодов служит обычное би- нарное дерево, и,если внимательно рассмот- реть предыдущий пример с построением дере- ва, можно убедиться,что все получаемые ко- ды там префиксные. И последнее примечание - алгоритм Хаф- фмана требует читать входной файл дважды, один раз считая частоты вхождения символов и другой раз, производя, непосредственно, кодирование. P.S. О "ключике", дающем дорогу алгоритму Running. Прочитав обзорную информацию о Huffman-кодировании, подумайте над тем, что на нашем бинарном дереве мо- жет быть и 257 листиков. ------------------------------------------
Other articles:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Similar articles:
В этот день... 23 November