Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Розв'язання. Процес декодування ілюструється таблицею 1, відповідні зміни кодового дерева – рис

⇐ ПредыдущаяСтр 14 из 30Следующая ⇒

Процес декодування ілюструється таблицею 1, відповідні зміни кодового дерева – рис. 1.

Таблиця 1

Вхідний код Символ Довжина Коду Номер дерева
‘ B ’ B   1
0‘ D ’ D   2
00‘ C ’ C   3
  D   4
  B   5
  B   6
  C   7
  B   8
  C   9
  D   10
  C   11
  D   12
  B   13
  B   14
  D    
å=53  

1)

 

 


2)

 

 


3) 4)

 

           
   
 
   
 
 

 

 


5) 6)

 

 

               
   
   
 
 
   

 

 


7) 8)

 

       
   
 
 

 

 


9)

 

           
     

 


 

 

10) 11)

 

 

 


 

 

 
 


12) 13) 14)

 

 

 
 
Рисунок 1

 


Отже, закодоване повідомлення BDCDBBCBCDCDBBD.

Довжина стиснутого повідомлення L (X)= 53 (біти).

Довжина нестиснутого повідомлення в коді ASCII+

L (X)= 15×8=120 (бітів).

Задачі до розділу 6

 

1 Закодувати повідомлення AABCDAACCCCDBB за адаптивним алгоритмом Хаффмена. Обчислити довжину у бітах стиснутого повідомлення і його ASCII+ -коду.

2 Закодувати повідомлення КИБЕРНЕТИКИ за адаптивним алгоритмом Хаффмена. Обчислити довжини в бітах стиснутого повідомлення і його ASCII+ - коду.

3 Розкодувати повідомлення ‘ A ’0‘ F ’00‘ X ’01111101010110111101 00101, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжини кодів стиснутого і нестиснутого повідомлення в бітах.

4 Розкодувати повідомлення ‘D ’0‘ B ’0100‘ C ’000‘ A ’11010 11111110, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжини кодів стиснутого і нестиснутого повідомлення в бітах.

5 Закодувати повідомлення МАТЕМАТИКА за адаптивним алгоритмом Хаффмена. Обчислити довжини стиснутого повідомлення і вхідного повідомлення в коді ASCII+.

6 Розкодувати повідомлення ‘ B ’0‘ D ’00‘ C ’01111101010110111101 00101, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжини кодів стиснутого і нестиснутого повідомлення.

7 Розкодувати повідомлення ‘ К ’0‘ Р ’00‘ А ’100‘ С ’000‘ Н ’011100‘ Я ’ 0100‘ ’1100101001011110, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжини кодів стиснутого і нестиснутого повідомлення в бітах.

8 Закодувати повідомлення ПРОГРАММА за адаптивним алгоритмом Хаффмена. Обчислити довжини стиснутого повідомлення і вхідного повідомлення в коді ASCII+.

9 Закодувати повідомлення ТЕОРИЯ ИНФОРМАЦИИ за адаптивним алгоритмом Хаффмена. Обчислити довжини стиснутого повідомлення і вхідного повідомлення в коді ASCII+.

10 Розкодувати повідомлення ‘ В ’0‘ О ’00‘’100‘ Д ’1010000‘ Р ’0100‘ Е ’ 01011001010010000‘ Н ’10000‘ И ’111100‘ К ’, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжини кодів стиснутого і нестиснутого повідомлення.

11 Розкодувати повідомлення ‘ X ’0‘ F ’00‘ Z ’1111101100‘ A ’11101011, закодоване за адаптивним алгоритмом Хаффмена. Обчислити довжини кодів стиснутого і нестиснутого повідомлення.

 

Розділ 7 СЛОВНИКОВІ МЕТОДИ СТИСНЕННЯ ЗІВА-ЛЕМПЕЛА

Раніше нами розглядалися статистичні методи стиснення інформації. Словникові алгоритми мають менш математичне обґрунтування, але більш практичний характер. Майже усі словникові методи розроблені ізраїльськими вченими Якобом Зівом (Ziv) та Абрамом Лемпелем (Lempel) і були вперше опубліковані у 1977 році.

Суть словникових методів полягає в тому,що повторювані підрядки у повідомленні замінюються покажчиками на місце у повідомленні, де ці підрядки вже раніше з'являлися. Декодування стиснутого повідомлення здійснюється заміною покажчика готовою фразою із словника, на яку цей покажчик вказує. LZ-методи забезпечують високий степінь стиснення даних, і їхньою важливою перевагою є швидка робота декодера.

Всі словникові методи можна поділити на дві групи.

До першої групи належать алгоритми з використанням «ковзного» за повідомленням вікна, розділеного на дві нерівні за об'ємом частини: перша, більша за розміром, включає фрагмент повідомлення, що вже проглянуто, – ця частина використовується як словник, друга частина вікна, набагато менша, виступає як буфер, що містить ще незакодовані символи вхідного потоку. Звичайно розмір ковзного вікна займає декілька кілобайтів, а розмір буфера - не більше 100 байтів. Алгоритми цієї групи відшукують у словнику (більшій частині вікна) ланцюжки символів, що збігаються із вмістом буфера, і замінюють ці ланцюжки покажчиками на їхнє попереднє входження у повідомлення, тобто на вміст словника. Словник в неявному вигляді міститься у закодованих даних, а зберігаються покажчики на повторювані ланцюжки символів (підрядки), що зустрічаються у повідомленні.


Усі алгоритми першої групи словникових методів базуються на алгоритмі, що має назву за іменами його авторів і роком розроблення – LZ77. Найдосконаліший представник цієї групи –алгоритм LZSS, опублікований у 1982 році Сторером (Storer) та Шиманські (Szimanski).

Алгоритми другої групи доповнюють початковий словник джерела словником фраз, що є повторюваними у повідомленні комбінаціями символів початкового словника. При цьому розмір словника збільшується, і для його кодування потрібне більше число бітів, але значна частина словника представлятиме вже не окремі букви, а сполучення букв або цілі слова. Якщо кодер знаходить фразу, що раніше зустрічалася, він замінює її індексом цієї фрази у словнику. При цьому довжина коду індексу виходить менше або набагато менше довжини коду незакодованого підрядка.

Базовий алгоритм другої групи словникових методів – алгоритм LZ78,розроблений Зівом і Лемпелем у 1978 році. Найдосконаліший представник цієї групи словникових методів – алгоритм LZW, запропонований у 1984 році Тері Уелчем.

 

 

7.1 Алгоритм LZ77

 

Основна ідея алгоритму LZ77 полягає в тому, що друге і подальші входження деякого підрядка символів у повідомленні замінюються покажчиками на його перше або попереднє входження. Алгоритм використовує частину повідомлення, що вже проглянуто, як словник. Щоб добитися стиснення, він намагається замінити наступну фразу повідомлення покажчиком на вміст словника.

Позначимо через N розмір «ковзного» вікна; F - розмір буфера. Тоді перші N-F символів - це вже закодовані символи, що містить словник, а останні F символів – вміст випереджуючого буфера.

При кодуванні вмісту буфера серед попередніх N-F символів, тобто у словнику, шукається найдовший підрядок, що збігається з початком буфера. Знайдений найбільший збіг кодується тріадою <i, j, a>, де i - зсув у словнику підрядка, що збігається із початком буфера; j - довжина підрядка, що збігається; а - перший символ, що йде за підрядком, що збігається. Далі алгоритм зсовує увесь вміст вікна на j+1 символів і водночас зчитує стільки ж символів вхідного потоку у буфер.

Об ' єм пам'яті, що потребує алгоритм-кодер або декодер, визначається розміром вікна N. Довжина коду обчислюється так: довжина підрядка, що співпав із вмістом словника, не може бути більше розміру буфера F, а зсув цього підрядка у словнику не може бути більше розміру словника мінус 1. Отже, довжина двійкового коду зсуву i буде округлений до більшого цілого , а довжина коду довжини підрядка j буде округлений у більшу сторону , а символ а кодується 8 бітами за таблицею ASCII +.


При декодуванні виконується той же самий порядок роботи з вікном, що й при кодуванні, але на відміну від пошуку підрядків, що збігаються, вони, навпаки, копіюються декодером з вікна згідно з черговою тріадою коду.

Приклад 1 (а) Закодуємо за алгоритмом LZ77 рядок «КРАСНАЯ КРАСКА»; розмір словника 8 байтів, буфера – 5 байтів.

Кодування повідомлення подається табл. 2.13.

В останньому рядку таблиці буква «А» береться не із словника, оскільки вона остання.

Таблиця 2.13

Словник (8 Бт) Буфер (5 Бт) Код
                         
. . . . . . . . К Р А С Н <0, 0, ‘ К ’>
. . . . . . . К Р А С Н А <0, 0, ‘ Р ’>
. . . . . . К Р А С Н А Я <0, 0, ‘ А ’>
. . . . . К Р А С Н А Я   <0, 0, ‘ С ’>
. . . . К Р А С Н А Я   К <0, 0, ‘ Н ’>
. . . К Р А С Н А Я   К Р <5, 1, ‘ Я ’>
. К Р А С Н А Я   К Р А С <0, 0, ‘ ’>
К Р А С Н А Я   К Р А С К <0, 4, ‘ К ’>
А Я   К Р А С К А . . . . <0, 0, ‘ А ’>
                                   

 

Довжина отриманого коду Lcode =9×(3+3+8)=126 (бітів) проти LASCII+ =14×8=112 (бітів) коду нестисненого рядка.

Приклад 1 (б) Розпакуємо повідомлення, закодоване за алгоритмом LZ77, довжина словника 8 байтів. Код стисненого повідомлення: <0,0,‘ K ’> <0,0,‘ P ’> <0,0,‘ A ’> <0,0,‘ C ’> <0,0,‘ H ’> <5,1,‘ Я ’> <0,0,‘ ’> <0,4,‘ K ’> <0,0,‘ A ’>.

Розпаковування повідомлення показано у табл. 2.14.

Таблиця 2.14

Вхідний код Вихід Словник
               
<0, 0, ‘ K ’> «К» . . . . . . . К
<0, 0, ‘ P ’> «Р» . . . . . . К Р
<0, 0, ‘ A ’> «А» . . . . . К Р А
<0, 0, ‘ C ’> «С» . . . . К Р А С
<0, 0, ‘ H ’> «Н» . . . К Р А С Н
<5, 1, ‘ Я ’> «АЯ» . К Р А С Н А Я
<0, 0, ‘ ’> «» К Р А С Н А Я  
<0, 4, ‘ K ’> «КРАСК» А Я   К Р А С К
<0, 0, ‘ A ’> «А» Я   К Р А С К А
                       

 


Наведемо процедури кодування та декодування за алгоритмом LZ77.

Кодер:

While (lookAheadBuffer not empty)

get a pointer(position, match) to the longest match

in the window for the lookahead buffer;

if (lehgth>Minimum_Match_Length)

output a(position, length) pair;

shift the window length characters along;

else

output the first character in the lookaheadbuffer;

shift the window 1 character along.

Декодер:

Whenever a(position, length) pair is encountered,

go to that (position) in the window and copy (length) bytes to the output.

Недоліки алгоритму LZ77:

1) із збільшенням розміру словника швидкість роботи алгоритму кодера пропорційно сповільнюється;

2) кодування поодиноких символів дуже неефективне.

7.2 Алгоритм LZSS

 

Алгоритм LZSS є модифікацією алгоритму LZ77. Код алгоритму починається однобітовим префіксом, що відділяє код підрядка, що збігається, від незакодованого символу. Код складається з пари <i, j> - зсуву i у словнику підрядка, що збігається з початком буфера, і довжини j цього підрядка, як і для LZ77. Вікно зсовується рівно на довжину знайденого підрядка або на 1, якщо входження підрядка буфера у словнику не знайдено.

Довжина підрядка у алгоритмі LZSS завжди більше 0 і не може перевищувати розмір буфера F, тому довжина двійкового коду довжини підрядка, що збігається, j - це округлений до більшого цілого , а довжина коду зсуву i – округлений до більшого цілого .

Приклад 2 (а) Закодуємо за алгоритмом LZSS рядок «КРАСНАЯ КРАСКА», розмір словника 8 байтів, буфера – 5 байтів.

Кодування повідомлення подане у табл. 2.15.

Таблиця 2.15

Словник (8 Бт) Буфер (5 Бт) Код li
                         
. . . . . . . . К Р А С Н 0‘ К ’  
. . . . . . . К Р А С Н А 0‘ Р ’  
. . . . . . К Р А С Н А Я 0‘ А ’  
. . . . . К Р А С Н А Я   0‘ С ’  
. . . . К Р А С Н А Я   К 0‘ Н ’  
. . . К Р А С Н А Я   К Р 1<5,1>  
. . К Р А С Н А Я   К Р А 0‘ Я ’  
. К Р А С Н А Я   К Р А С 0‘ ’  
К Р А С Н А Я   К Р А С К 1<0,4>  
Н А Я   К Р А С К А . . . 1<4,1>  
А Я   К Р А С К А . . . . 1<0,1>  
                               

Довжина отриманого коду Lcode = =7×9+4×7=91 (біт).

Довжина нестиснутого повідомлення LASCII+ =14×8=112 (бітів).

Приклад 2 (б) Розпакуємо повідомлення 0‘ K ’0‘ P ’0‘ A ’0‘ C ’ 0‘ H ’1<5, 1>0‘ Я ’0‘ ’1<0, 4>1<4, 1>1<0, 1>, закодоване за алгоритмом LZSS, довжина словника 8 байтів.

Розпакування повідомлення подане у табл. 2.16.

Таблиця 2.16

Вхідний код Вихід Словник
               
0‘ K ’ «К» . . . . . . . К
0‘ P ’ «Р» . . . . . . К Р
0‘ A ’ «А» . . . . . К Р А
0‘ C ’ «С» . . . . К Р А С
0‘ H ’ «Н» . . . К Р А С Н
1<5, 1> «А» . . К Р А С Н А
0‘ Я ’ «Я» . К Р А С Н А Я
0‘ ’ «» К Р А С Н А Я  
1<0, 4> «КРА» Н А Я   К Р А С
1<4, 1> «К» А Я   К Р А С К
1<0, 1> «» Я   К Р А С К А

 

Алгоритми LZ77, LZSS мають такі очевидні недоліки:

1) неможливість кодування повторюваних підрядків, що знаходяться на відстані, більшій за довжину словника;

2) довжина підрядка, який можна закодувати, обмежується розміром буфера.

Якщо набагато збільшити розміри словника і буфера, то це призведе до зростанням довжини кодів для зсуву і довжини підрядка, що зробить загальний код повідомлень з короткими підрядками неприпустимо великим. Крім того, різко зросте час роботи алгоритму кодера.

 

 

7.3 Алгоритм LZ78

 

Авторами LZ77 був розроблений алгоритм LZ78, позбавлений недоліків LZ77 і LZSS. Цей алгоритм не використовує вікно, а зберігає словник із фраз повідомлення, що вже проглянуто.

При старті алгоритму словник містить тільки один порожній рядок. Алгоритм зчитує символи повідомлення до того часу, поки накопичуваний підрядок повністю збігається з однією із фраз словника. Як тільки зчитаний підрядок перестає відповідати фразі словника, алгоритм генерує код з індексу фрази у словнику, що до останнього зчитаного символу містила вхідний підрядок, і символу, що порушив збіг. Потім зчитаний новий підрядок заноситься у словник, і пошук збігу наступного підрядка з однією із фраз словника починається знову. Якщо словник вже заповнений, то з нього видаляють фразу, що найменше використовується у порівняннях.

Для визначення розміру кодів ключовим є розмір словника, оскільки кожний код за алгоритмом LZ78 містить номер фрази у словнику. Звідси випливає, що коди алгоритму мають постійну довжину, яка дорівнює округленому до більшого цілого +8, де 8 - кількість бітів для кодування наступного символу, що йде за підрядком, що збігається, за таблицею ACSII+.

Приклад 3 (а) Закодуємо за алгоритмом LZ78 рядок «КРАСНАЯ КРАСКА», використовуючи словник довжиною 16 фраз.

Кодування повідомлення ілюструється табл. 2.17.

Таблиця 2.17

Вхідна фраза (словник) Код Індекс фрази
«»    
«К» <0, ‘ К ’>  
«Р» <0, ‘ Р ’>  
«А» <0, ‘ А ’>  
«С» <0, ‘ С ’>  
«Н» <0, ‘ Н ’>  
«АЯ» <3, ‘ Я ’>  
«» <0, ‘ ’>  
«КP» <1, ‘ Р ’>  
«АС» <3, ‘ С ’>  
«КА» <1, ‘ А ’>  

Покажчик на будь-яку фразу словника розміром 16 фраз – це ціле число від 0 до 15, для кодування якого двійковим рівномірним кодом потрібно 4 біти. Отже, довжина отриманого коду повідомлення Lcode =10×(4+8) = 120 (бітів).

Приклад 3 (б) Розкодуємо повідомлення <0,‘ К ’><0,‘ P ’> <0,‘ A ’><0,‘ C ’><0,‘ H ’><3,‘ Я ’><0,‘ ’><1,‘ P ’><3,‘ C ’><1,‘ A ’>, закодоване за алгоритмом LZ78; довжина словника 16 фраз.

Розкодування повідомлення подане в табл. 2.18.

Таблиця 2.18

Вхідний код Вихід (словник) Індекс фрази
  «»  
<0, ‘ К ’> «К»  
<0, ‘ Р ’> «Р»  
<0, ‘ А ’> «А»  
<0, ‘ С ’> «С»  
<0, ‘ Н ’> «Н»  
<3, ‘ Я ’> «АЯ»  
<0, ‘ ’> «»  
<1, ‘ Р ’> «КP»  
<3, ‘ С ’> «АС»  
<1, ‘ А ’> «КА»  

 

 

7.4 Алгоритм LZW

 

Алгоритм LZW є модифікацією LZ78. Алгоритм починає роботу зі словника розміром 4К, що містить за адресами від 0 до 255 посилання на окремі символи (таблиця ASCII+), а від 256 до 4095 - посилання на підрядки завдовжки більше одного символу. У процесі кодування текст розбивається на підрядки, де кожний новий підрядок є найдовшою фразою, що збігається, що вже проглянуто, плюс один символ. Новий підрядок кодується індексом його префікса (фрази словника) і символом, що порушив збіг,після чого нова фраза заноситься у словник(таблицю рядків). При переповнюванні словника з нього видаляється або найменш уживана фраза, або усі підрядки завдовжки більше одного символу.

Наведемо покроковий опис алгоритму кодування.

Крок 1 Ініціалізація словника усіма можливими односимвольними фразами (звичайно це 256 символів ASCII+). Ініціалізація вхідної фрази w першим символом повідомлення.

Крок 2 Зчитування наступного символу K повідомлення.

Крок 3 Якщо це символ-КІНЕЦЬ_ПОВІДОМЛЕННЯ

Видати код для w

КІНЕЦЬ.

Якщо фраза wK вже є у словнику

Привласнити вхідній фразі w значення wK

Перейти до кроку 2

Інакше

Видати код w

Додати wK у словник

Привласнити вхідній фразі w значення символу K

Перейти до кроку 2.

LZW -коди мають постійну довжину, що визначається округленим до більшого цілого .

Приклад 4 (а) Закодуємо за алгоритмом LZW рядок «КРАСНАЯ КРАСКА». Розмір словника 500 фраз.

Процес кодування повідомлення показаний у табл. 2.19.

Таблиця 2.19

Вхідна фраза wK (словник) Код w Індекс фрази
ASCII+   0 – 255
«КP» 0‘ К ’  
«РА» 0‘ Р ’  
«АС» 0‘ А ’  
«СН» 0‘ С ’  
«НА» 0‘ Н ’  
«АЯ» 0‘ А ’  
«Я» 0‘ Я ’  
«К» 0‘ ’  
«КРА» <256>  
«АСК» <258>  
«КА» 0‘ К ’  
«А» 0‘ А ’  

Довжина отриманого коду Lcode =12× =108 (б).

Наведемо процедуру кодування за алгоритмом LZW:

Read a character K

Set w=K

Loop

read a character K

if wK exists in the dictionary

w=wK

Else

output the code for w

add wK to the string table

w=K

End loop.

LZW-декодер також, як і кодер, заносить нові фрази у словник кожного разу, якщо знаходить у вхідному потоці новий код. Наприкінці декодування декодер має такий самий словник фраз, що був накопичений кодером при кодуванні.

При декодуванні за алгоритмом LZW потрібно дотримуватися такого правила: словник поповнюється тільки після зчитування першого символу фрази, що розкодовується із наступного за поточним коду.

Приклад 4 (б) Розпакуємо повідомлення 0' К '0' Р '0' А '0' С ' 0' Н '0' А '0' Я '0' '<256><258>0' К '0' А ', закодоване за алгоритмом LZW; довжина словника 500 фраз.

Розпаковування повідомлення подане у табл. 2.20.

Таблиця 2.20

Вхідний код Вихід Словник Індекс фрази
    ASCII+ 0 – 255
0‘ К ’ «К» «КP»  
0‘ Р ’ «Р» «РА»  
0‘ А ’ «А» «АС»  
0‘ С ’ «С» «СН»  
0‘ Н ’ «Н» «НА»  
0‘ А ’ «А» «АЯ»  
0‘ Я ’ «Я» «Я»  

Продовження табл. 2.20

Вхідний код Вихід Словник Індекс фрази
0‘ ’ «» «К»  
<256> «КР» «КРА»  
<258> «АС» «АСК»  
0‘ К ’ «К» «КА»  
0‘ А ’ «А» «А»  

 

Відмітною рисою словникових способів стиснення є те, що увесь словник нових фраз передається декодеру власне без самої передачі, іншими словами, словник фраз у неявному вигляді міститься у вироблюваних кодах.

 

 

Зразки розв'язування задач до розділу 7

Приклад 1 Закодувати повідомлення СИНЯЯ СИНЕВА СИНИ, використовуючи словникові алгоритми LZ77, LZSS, розмір словника – 12 байтів, буфера – 4 байти. Обчислити довжини кодів.


⇐ Предыдущая9101112131415161718Следующая ⇒





Date: 2015-11-15; view: 583; Нарушение авторских прав


mydocx.ru - 2015-2024 year. (0.071 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию