Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Метод Шеннона-Фано (Shannon-Fano method)




Родственным методом для кодирования Хаффмана является кодирование Шеннона-Фано, которое осуществляется следующим образом:

  1. Делим множество символов на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписываем "0", для правого - "1".
  2. Повторяем шаг (1) до тех пор, пока все подмножества не будут состоять из одного элемента.

Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано - сверху вниз. Кодирование по Хаффману всегда дает оптимальные коды, по Шеннону-Фано иногда используется немного больше бит.

Алгоритмы Хаффмана и Шеннона-Фано являются одними из классических, поэтому они часто используются в графических форматах. Они берут только частоту появления одинаковых байт в изображении и сопоставляют символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требуют двух проходов по изображению. Коэффициенты сжатия алгоритмов: 1/8, 2/3, 1. Требуют записи в файл таблицы соответствия кодируемых символов и кодирующих цепочек. На практике используются их разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее адаптивно, т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.

Алгоритм Лемпеля-Зива

Агоритм сжатия основан наоборот на корреляциях между расположенными рядом символами алфавита (словами, управляющими последовательностями, заголовками файлов фиксированной структуры)

Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования, предельно прост. Он формулируется следующим образом: "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ".

Распространенный метод сжатия RLE (англ. Run Length Encoding), который заключается в записи вместо последовательности одинаковых символов одного символа и их количества, является подклассом данного алгоритма. Рассмотрим, например, последовательность "ААААААА". С помощью алгоритма RLE она будет закодирована как "(А,7)", в то же время ее можно достаточно хорошо сжать и с помощью алгоритма LZ77: "А(-1,6)". Действительно, степень сжатия именно такой последовательности им хуже (примерно на 30-40%), но сам по себе алгоритм LZ77 более универсален, и может намного лучше обрабатывать последовательности вообще несжимаемые методом RLE.

 

Задание на выполнение

1. Закодировать в двоичной форме (2-мя видами деревьев Хаффмана) предложенную информацию (см. задание к л.р.) методом Хаффмана и представить деревья Хаффмана. Подготовить результат для побайтной передачи, представив в 16-ричной форме (в случае, если в левом байте пустые разряды – побитно сдвигать влево, записывая в правый байт 0-е биты).

2. Закодировать в двоичной форме предложенную информацию (см. п.1) методом Шеннона-Фано. Подготовить результат для побайтной передачи, представив в 16-ричной форме. Сравнить эффективность сжатия методами Хаффмана (2-мя видами) и Шеннона-Фано без учета потерь на передачу таблицы кодировки.

3. Закодировать в текстовой форме предложенную информацию (см. задание к л.р.) методом Лемпеля-Зива.

4. Самостоятельно выбрать студента своей группы, представить ему результаты выполненных предыдущих пунктов 1 - 3, и получить у него аналогичные результаты. Выполнить декодирование. Представить пошаговый отчет.

 

Контрольные вопросы

 

1. Принципы и цели архивации (кодирования) данных.

2. Метод архивации Хаффмана.

3. Метод архивации Шеннона-Фано.

4. Оптимальное кодирование.

5. Классы алгоритмов архивации.

6. Принципы методов архивации без потерь.

 


Приложение 1. Программная и аппаратная реализация кодирования текстовой информации алгоритмами Хаффмана.

 

Структура данных

Для более легкой работы в дальнейшем необходимо хорошо продумать структуру данных в которой будет храниться таблица кодирования файла (дерево кодирования).

Например. Во-первых, в узле кодировки (knot-узел) храним идентификатор исходного байта ("портрет" кодируемого байта). Во-вторых, храним последовательность бит которой, заменяется исходный байт в выходном файле и ее длину:

 

Knot = record

OrigByte: byte; { байт который мы кодируем }

CodeChain: word; { кодовая последовательность бит }

Length: byte; { длинна кодовой последовательности }

end;

 

Затем, для построения статистической таблицы необходимо в каждом узле установить счетчик частоты вхождения, а после его инициализации необходимо, для более быстрого построения дерева, сцепить все узлы в список и отсортировать его по возрастанию частот вхождения байтов, а также необходимы указатели на веточки дерева. Для этого понадобятся следующие поля:

 

Counter: longint; { счетчик частоты вхождения }

ListPoint1,

ListPoint2: PKnot; { указатель на соседние узлы в списке }

TreePoint1,

TreePoint2: PKnot; { указатели на 0 и 1 -ю ветки дерева }

 

где PKnot = ^Knot;

 

В конечном итоге структура данных будет выглядеть так:

 

Type

 

PKnot = ^Knot; { тип - указатель на узел (Knot) }

Knot = record

OrigByte: byte; { байт который мы кодируем }

CodeChain: word; { кодовая последовательность бит }

Length: byte; { длинна кодовой последовательности }

Counter: longint; { счетчик частоты вхождения }

Point1,

Point2: PKnot; { указатель на соседние узлы в списке }

TreePoint1,

TreePoint2: PKnot; { указатели на 0 и 1 -ю ветки дерева }

end;

 

Для дальнейшего облегчения своей работы представим все свои 256

узлов как массив указателей на узлы:

 

Var

CodeTable: array[0..255] of PKnot;

 

Сжатие файла

Сжатие файла начнем с инициализации нашей структуры данных. Для

этого необходимо разместить в памяти наш массив узлов и установить на

каждый узел указатель из массива:

 

For I:=0 to 255 do

begin

New(CodeTable[I]);

With CodeTable[I]^ do

begin

OrigByte:=I; { инициализация узла }

Counter:=0; { обнуление счетчика вхождений }

ListPoint1:=Nil; { указатели на соседние элементы в списке}

ListPoint2:=Nil;

TreePoint1:=Nil; { и на веточки в дереве }

TreePoint2:=Nil;

end;

Рассмотрим следующие шаги:

1) Необходимо перечитать весь входной файл и подсчитать частоты

вхождения каждого из байтов в него.

2) Из массива указателей сделаем связный список узлов.

3) Отсортируем полученный список по возрастанию одним из методов

сортировок.

4) Теперь будем брать из отсортированного списка по два самых

первых элемента с начала (т.е. 2 элемента с самыми малыми частотами

вхождений). Далее будем суммировать эти частоты и включать в список

новый элемент у которого:

а) поле Counter - равно сумме частот вхождений;

б) поля TreePoint указывают на 2 первоначально взятых элемента;

Два исходных элемента из очереди удаляются, а новый элемент

вставляется за первым элементом у которого поле Counter больше.

Выполнение пункта 4 будет продолжаться до тех пор, пока в списке не

останется всего один элемент, который и будет является корнем нашего

дерева кодировок.

5) Начиная с корня дерева запустим рекурсивную процедуру, которая

будет по очереди обходить все дерево и запоминая путь к листкам

бинарного дерева, в листках (т.е. в наших первоначальных узлах),

записывать код каждого листка и длину пути к нему от корня (Root).

Процедура может выглядеть так:

 

{ ----------- глобальные переменные ------------- }

Var CounterBite: byte; { счетчик пройденных узлов при просмотре }

{ фактически - длинна кодовой последоват. }

Root: PKnote; { указатель на корень дерева }

BiteChain: word; { последовательность битов - код листа }

{ ----------- ----------- ----------- }

procedure ViewTree(P: PCodElement);

{ --- просмотр дерева частот и присваивание

кодировочных цепей листьям --- }

Var Mask,I: word;

begin

Inc(CounterBite);

If P^.TreePoint1<>Nil then ViewTree(P^.TreePoint1);

If P^.TreePoint2<>Nil then

begin

Mask:=(1 SHL (16-CounterBite));

BiteChain:=BiteChain OR Mask;

ViewTree(P^.TreePoint2);

Mask:=(1 SHL (16-CounterBite));

BiteChain:=BiteChain XOR Mask;

end;

If (P^.P0=Nil) and (P^.P1=Nil) then

begin

P^.CodeChain:=BiteChain;

P^.Length:=CounterBite-1;

end;

Dec(CounterBite);

end;

 

Но процедуру обхода дерева должна запустить другая процедура,

которая и проинициализирует глобальные переменные:

 

procedure CreateCompressCode;

{ --- обнуление переменных и

запуск просмотра дерева с вершины --- }

begin

BiteChain:=0;

CounterBite:=0;

ViewTree(Root);

end;

 

После построения кодовых последовательностей (причем префиксных)

мы можем приступать к сжатию файла.

6) Непосредственно сжатие файла:

а) Чтение из входного файла байта.

б) Получение указателя на узел с кодом исходного байта.

в) Вывод в выходной файл необходимого числа бит.

 

procedure PakOneByte;

{ --- сжатие и пересылка в выходной буфер одного байта --- }

Var Mask: word;

Tail: boolean;

begin

CRC:=CRC XOR InBuf[InCounter];

Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHR CounterBite;

OutWord:=OutWord OR Mask;

CounterBite:=CounterBite +

CodeTable[InBuf[InCounter]]^.LengthBiteChain;

If CounterBite>15 then Tail:=True else Tail:=False;

While CounterBite>7 do

begin

OutBuf[OutCounter]:=Hi(OutWord);

Inc(OutCounter);

CounterBite:=CounterBite-8;

If CounterBite<>0 then OutWord:=OutWord SHL 8 else OutWord:=0;

end;

If Tail then

begin

Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHL

(CodeTable[InBuf[InCounter]]^.LengthBiteChain-CounterBite);

OutWord:=OutWord OR Mask;

end;

Inc(InCounter);

end;

Необходимо лишь перед записью информации в выходной файл не забыть сохранить в нем имя файла, его первоначальную длину, время и дату создания, атрибуты и таблицу кодировки.

 

Разворачивание файла

Если Вы внимательно прочли предыдущий раздел, то для метод разворачивания архива в исходный файл должен быть очевиден.

Так же как и для сжатия для разархивирования необходимо вначале построить дерево кодировки (оно же и дерево раскодировки), только теперь таблица частот вхождения не строится по входному файлу, так как такового нет, а читается из архивного файла. В дальнейшем построение дерева аналогично.

После построения дерева можно начинать распаковку последовательности бит в отдельные байты. Для этого:

Начиная с корня дерева (Root) начнем отслеживать цепочку бит, которая должна привести нас к листку дерева в котором будет записан байт, который нам необходимо вывести в выходной файл. После вывода этого байта процесс опять повторяется с корня.

При этом необходимо знать первоначальную длину файла. Это необходимо для того, чтобы не считать лишние биты из архивного файла, так как при архивации могла быть ситуация, когда входной файл кончился, а цепочка бит еще не кратна 8-ми, тогда ее необходимо дополнять до числа бит кратного 8-ми.

 

Аппаратная реализация алгоритма Huffman

Представим себе прибор на вход которого поступает информация с

примерно одинаковым статистическим распределением в виде байтов, затем

этому прибору необходимо передать полученную информацию по

последовательному каналу передачи данных ко второму прибору, который

выполняет обратное преобразование.

┌──┬────┬──┐ ┌───┬────┬───┐

0 ──┤ │ Хy │ │Out In │ │ yX │ ├─── 0

1 ──┤ │ │ ├──────── ── ── ── ─────────┤ │ │ ├─── 1

2 ──┤ │ │ │ │ │ │ ├─── 2

3 ──┤ │ │ │ │ │ │ ├─── 3

4 ──┤ │ │ │ │ │ │ ├─── 4

5 ──┤ │ │ │ │ │ │ ├─── 5

6 ──┤ │ │ │ │ │ │ ├─── 6

7 ──┤ │ │ │ │ │ │ ├─── 7

│ │ │ │ │ │ │ │

└──┴────┴──┘ └───┴────┴───┘

Из приведенной схемы видно, что узким местом системы в прямом и

переноном смысле является последовательный канал передачи данных. Для

ускорения работы данной системы мы можем повысить частоту передачи

данных по последовательному каналу, но этот путь ограничивается

качеством самого канала передачи, вторым путем является... уменьшение

количества данных передаваемых за еденицу времени за счет

динамического сжатия.

 

Прямое преобразование со сжатием

Не случайно в описании вышеприведенной схемы были слова о

"информации с примерно одинаковым статистическим распределением".

Именно это " примерно одинаковое распределение " и можно вывести и

построить для этой информации кодировочное дерево аналогично тому, как

мы это делали для файла. Теперь представьте, что мы упаковали это

дерево в две микросхемы ПЗУ так, что выставив на адресной шине

необходимый байт считываем из первой длину кодовой

последовательности, а из второй - саму кодовую последовательность.

Теперь осталось лишь загрузить длину последовательности в

реверсивный счетчик, а саму кодовую последовательность в сдвиговый

регистр и запустить эту систему в работу. После того, как счетчик

досчитает до 0, снова загрузить ее новым кодом и т.д.

 

┌────────┐

вход ┌────────────────────┐ │ реверс.│

0>──────╥ │ ПЗУ с длинной ├──────\ │счетчик │

1>──────╫──\│ последовательности ├──────/ │ │

2>──────╫──/│ │ │ │

3>──────╫ └────────────────────┘ │ │

4>──────╫ └───┬┬───┘

5>──────╫ ┌───────────────────┐ \/

6>──────╫──\│ ПЗУ с самой код. │ ┌──────────┐

7>──────╨──/│последовательностью│────────\│ сдвиговый│

│ │────────/│ регистр │ выход

└───────────────────┘ │ ├────────>

│ │

└──────────┘

Обратное преобразование

 

Рассмотрим схему обратного преобразования последовательного сжатого кода в исходный байт. Представим себе цифровой автомат, работа которого описывается графом переходов практически представляющим собой аналог дерева кодировки, с тем различием, что в узле соответствующем листу дерева этот автомат будет генерировать и передавать на внешнюю шину код узла и после этого переходить в исходное состояние соответствующее корню дерева (Root).

Код узла может не обязательно быть сразу же нашим исходным байтом, он может быть промежуточным кодом, подаваемым на устройство перекодировки, откуда мы и получим уже исходный байт.

Для чего нужен промежуточный код? Все очень просто, мы можем рассчитать одно универсальное дерево кодировки и в каждом конкретном случае лишь менять коды соответствующие листочкам. Соответственно мы сможем на базе ПЛМ кристалла сделать микросхему реализующую лишь это - универсальное дерево, а конкретными кодами варьировать по разному прошивая перекодирующее ПЗУ и два ПЗУ в кодирующем приборе. Это гораздо менее трудоемко, чем для каждого конкретного случая рассчитывать и делать свой ПЛМ кристалл.

И последнее, это впрочем лишь авторская догадка и не более, но по моему мнению именно на таком принципе работает аппаратная поддержка MNP протоколов в современных модемах. Лишь с той разницей, что там должны быть не микросхемы ПЗУ, а ОЗУ, и, программная и аппаратная часть для создания и подгрузки динамической таблицы кодирования.

 

Приложение 2.

Задание к лабораторной работе №1 «Кодирование данных»

# текст для кодирования методом Хаффмана и Шеннона-Фано текст для кодирования методом Лемпеля-Зива
1 мама мыла раму в армавире мама мыла раму в армавире
2 хорошо хористкам в хоре хорошо хористкам в хоре
3 машинист снял шины у машины машинист снял шины у машины
4 лесник в темно синем лесу лесник в темно синем лесу
5 наклонить колбасу в колонну макар пошел за маком с макаровым
6 и хомячка холодный нос потерянный тир в тирасполе
7 потрогал вова чуть дыша мистический истеричный критерий
8 вот блин, да он совсем замерз карл у клары украл кораллы
9 подумал мальчик не спеша клара у карла украла кларнет
10 он вспомнил школьную столовку на траве затравленные дрова
11 чтоб разморозить бычий фарш сонная соня с сонатой
12 кладут его в микроволновку толина столовая столешница
13 так поступил и вова наш ингибированная инга на ринге
14 захлопнул дверь, нажал на кнопку макар-лекарь в мелекино
15 зашевелился хомячок киношный арлекин в мелекино
16 открыл глаза, поднял головку тамара, янка и тамянка
17 потом послышался щелчок карлсон накаркал сон
18 у вовы просто сжалось сердце ушлая каркуша каркнула
19 потом внутри как долбанет барный барабан в бане
20 мальчишка – к печке, а на дверце барабанщик и банщик в баре
21 мальчиш-кибальчиш винный раввин на траве
22 у балерины пять баллов соколиный коля и оля
23 вот билет на балет ручная ручка у ручья
24 на дворе трава ира с рисовыми ирисками

 

 

 


 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...