МЕТОДЫ СЖАТИЯ ИНФОРМАЦИИ. Методические указания Рекомендовано Научнометодическим советом университета для студентов, обучающихся по направлению Фундаментальная информатика и информационные технологии
 Скачать 0.87 Mb.
|
|
Построение дерева Хаффмана к примеру со с. 13) 15 о Уз1 Уз2 О В Уз3 4 2 2 1 1 7 6 5 р 0 2 1 11 т Уз1 Уз2 О Уз3 В 5 3 2 2 1 9 8 7 6 5 р Уз4 Т ξ 1 1 1 0 4 3 2 к од1(т) а Уз 1 Уз 2 О Уз 3 Уз 4 6 4 2 2 2 11 10 9 8 р в Т Уз5 а 1 1 1 1 1 6 5 4 3 2 ξ 0 1 к од1(а) Рис. 4-и Рис. 4-л Рис. 4-к Рис. 4-з Рис. 4-н Рис. м 16 2.1.2. Код Шеннона Описание алгоритма приведено по работе Исходными данными алгоритма являются алфавит A = {a 1 ,…, a n }, состоящий из n символов p(a i ) – вероятность появления каждого символа алфавита в рассматриваемом сообщении. Алгоритм Шеннона состоит из нескольких шагов. Шаг 1. Инициализация) выстраиваем все символы текущего алфавита в порядке убывания вероятностей. Будем считать, что выполняется условие p 1 ≥ … ≥ p i ≥ … ≥ p n ; 2) для каждого a i вводим вспомогательную переменную d i ; 3) будем считать, что d 1 = Шаг 2. Работа алгоритма for i = 2 to |A| do ∑ - = = 1 1 i k k i p d ; 2) в качестве кодового слова для каждого символа a i берем первые- разрядов после запятой в двоичной записи числа Алгоритм окончен. Пример. Дан алфавит A = без, "мл, "ь, для каждого символа из алфавита А задана вероятность его появления в тексте. символ б е з м л ь вероятность 10 1 10 4 10 2 10 1 10 1 10 Закодировать алфавит с помощью алгоритма Шеннона. Решение Процесс работы алгоритма можно описать следующей таблицей. символ е з б м л ь вероятность 10 4 10 2 10 1 10 1 10 1 10 1 d i 0 0,4 0,6 0,7 0,8 0,9 i p log - 2 3 4 4 4 кодовое слово 011 1001 1011 1100 1110 10 10 10 10 10 10 10 10 10 10 10 10 Следовательно, слово безземелье будет закодировано в последовательность Пример окончен. Код Гилберта–Мура Описание алгоритма приведено по работе Исходными данными алгоритма являются алфавит A = {a 1 ,…, a n }, состоящий из n символов p(a i ) – вероятность появления каждого символа a i в со- общении. Алгоритм Гилберта–Мура состоит из нескольких шагов. Шаг 1. Инициализация) для каждого элемента алфавита a i введем вспомогательные переменные d i , δ i ; 2) будем считать d 1 = 0, 2 Шаг 2. Работа алгоритма) for i = 2 to |A| do { ∑ - = = 1 1 i k k i p d ; 2 i i i p d + = δ } 2) в качестве кодового слова для каждого символа a i берем первые 1 log + - i p разрядов после запятой в двоичной записи числа Алгоритм окончен. Пример. Дан алфавит A = без, "мл, "ь, для каждого символа из алфавита A задана вероятность его появления в тексте. символ б е з м л ь вероятность 10 1 10 4 10 2 10 1 10 1 10 Закодировать алфавит с помощью алгоритма Гилберта–Мура. 10 10 10 10 10 10 18 Решение Процесс работы алгоритма можно описать следующей таблицей. символ б е з м л ь вероятность 0,1 0,4 0,2 0,1 0,1 0,1 i d 0 0,1 0,5 0,7 0,8 0,9 i δ 0,05 0,3 0,6 0,75 0,85 0,95 1 log + - i p 5 3 4 5 5 кодовое слово 010 1001 11000 11011 Пример окончен. Словарные методы Идея словарных методов рассматриваем входную последовательность как последовательность строк, содержащих произвольное количество символов при кодировании заменяем строки символов на кода (индексы строк в некотором словаре при декодировании осуществляется замена индексов на соответствующие им фразы словаря. Словарь – это набор строк, которые предположительно будут встречаться в обрабатываемой последовательности. Индексы строк должны быть построены таким образом, чтобы в среднем их представление занимало меньше места, чем требуют замещаемые строки. За счет этого и происходит сжатие. Алгоритм Впервые алгоритм был опубликован в 1984 г. Он применяется, например, для сжатия данных при записи их на жесткий диск компьютера в форматах ARJ, ZIP; а также при записи файлов изображений в форматах TIFF и При кодировании вводится поток символов и выводится поток кодов. Перед описанием алгоритма кодирования введем несколько обозначений и определений 19 K – символ простейший элемент данных (в тексте – это может быть элемент алфавита, а при рассмотрении изображений это может быть числовое значение цвета в палитре – строка, несколько непрерывных символов от одного и более – операция конкатенации строки и символа; код – число, помещаемое в выходной файл. Алгоритм кодирования состоит из нескольких шагов. Шаг 1. Инициализация словаря всеми возможными одно- символьными фразами. Инициализация входной фразы w первым символом сообщения. Шаг 2. Считать очередной символ K из кодируемого со- общения. Шаг 3. Если конец_сообщения, Выдать код для w. Конец. Если фраза wK уже есть в словаре, Присвоить входной фразе значение wK, то есть w = Перейти к шагу 2. Иначе Выдать код Добавить wK в словарь Присвоить входной фразе значение K, то есть w = Перейти к шагу Алгоритм окончен. При декодировании вводится поток кодов и выводится поток символов. Перед описанием алгоритма декодирования введем несколько обозначений и определений строка (b) – функция, которая по коду b выдает из словаря связанную с ним строку строка) – функция, которая по коду b выдает первый символ из связанной с ним строки Алгоритм декодирования состоит из нескольких шагов. Шаг 1. Инициализация. Инициализация словаря всеми возможными односимволь- ными фразами. Ввести переменные w – текущий код, s – старый код, t – строка символов и K – символ. Считать w – первый код из сжатого файла. Вывести строку (w) в поток символов = Шаг 2. Работа алгоритма = следующий код в потоке кодов. Если код w существует в словаре { вывести строка (w) в поток символов = строка (s); K = строка' добавить фразу tK в словарь = Иначе = строка (s); K = строка' вывести tK в поток символов; добавить фразу tK в словарь = Повторить шаг 2 нужное количество раз. Алгоритм окончен. Пример. Рассмотрим работу алгоритма LZW с помощью кодирования фразы «abcdabce_abcd_abceabcabcabcd». Размер словаря не ограничен. Решение Процесс кодирования можно описать таблицей вход текущая фраза фраза, помещаемая в словарь) позиция в сл ов аре ко ммент арии ко ды на выходе b c d e 0 1 2 3 4 Инициализация словаря всеми возможными односимвольными фразами a 3 b ab фрагмента «ab» нет в словаре фрагмент «a» есть в словаре 4 с bc фрагмента «bc» нет в словаре 5 d cd cd 8 -//- 3 6 a da da 9 -//- 4 7 b ab фрагмент «ab» есть в словаре с abc abc 10 фрагмента «abc» нет в словаре 9 e ce ce 11 фрагмента «ce» нет в словаре 10 _ e_ e_ 12 -//- 5 11 a _a _a 13 -//- 0 12 b ab фрагмент «ab» есть в словаре c abc фрагмент «abc» есть в словаре d abcd abcd 14 фрагмента «abcd» нет в словаре 15 _ d_ d_ 15 -//- 4 16 a _a фрагмент «_a» есть в словаре b _ab _ab 16 фрагмента «_ab» нет в словаре 18 c bc фрагмент «bc» есть в словаре e bce bce 17 фрагмента «bce» нет в словаре 20 a ea ea 18 фрагмента «ea» в словаре нет 21 b ab фрагмент «ab» есть в словаре c abc фрагмент «abc» есть в словаре 22 23 a abca abca 19 фрагмента «abca» в словаре нет 24 b ab фрагмент «ab» есть в словаре c abc фрагмент «abc» есть в словаре a abca фрагмент «abca» есть в словаре b abcab abcab 20 фрагмента «abcab» в словаре нет 28 c bc фрагмент «bc» есть в словаре d bcd bcd 21 фрагмента «bcd» в словаре нет 30 d получили конец файла выдали код строки Таким образом на выходе мы получим строку (1, 2, 3, 4, 6, 3, 5, 0, 10, 4, 13, 7, 5, 10, 19, 7, Процесс декодирования можно описать таблицей. вх од кода текущая фраза фраза, по мещ ае мая в словарь) позиция в сл ов аре ко ммент арии вых од 1 _ a b c d e 0 1 2 3 4 Инициализация словаря всеми возможными односимвольными фразами а код 1 есть в словаре выводим в потока код 2 есть в словаре, выводим в поток «b», s = 1, t = строка (s) = «a», K = строка' (w) = «b», помещаем фразу tK = в словарь, s = w = 2 b 4 3 c bc 7 код 3 есть в словаре, выводим в поток «c», помещаем фразу «bc» в словарь c 5 4 d cd 8 код 4 есть в словаре, выводим в поток «d», помещаем фразу «cd» в словарь d 23 6 6 ab da 9 код 6 есть в словаре, выводим в поток «ab», s = 4, t = «d», K = «a», помещаем фразу «da» в словарь, s = 6 ab 7 3 c abc 10 код 3 есть в словаре, выводим в поток «c», s = 6, t = «ab», K = «c», помещаем фразу «abc» в словарь, s = 3 c 8 5 e ce 11 код 5 есть в словаре, помещаем фразу «ce» в словарь 0 _ e_ 12 код 0 есть в словаре, помещаем фразу «e_» в словарь 10 abc _a 13 код 10 есть в словаре, выводим в поток «abc», s = 0, t = «_», K = «a», помещаем фразу «_a» в словарь, s = 10 abc 11 4 d abcd 14 код 4 есть в словаре, помещаем фразу «abcd» в словарь d 12 13 _a d_ 15 код 13 есть в словаре, помещаем фразу «d_» в словарь 7 bc _ab 16 код 7 есть в словаре, помещаем фразу «_ab» в словарь bc 14 5 e bce 17 код 5 есть в словаре, помещаем фразу «bce» в словарь e 15 10 abc ea 18 код 10 есть в словаре, s = 5, t = «e», K = «a», помещаем фразу «ea» в словарь. s = 10 abc 16 19 abca 19 кода нет в словаре, s = 10, t = строка (s) = «abc», K = строка' (s) = «a», вывести tK = «abca» в поток символов, добавить фразу tK = «abca» в словарь, s = w = 19 abca 17 7 bc abcab 20 код 7 есть в словаре, s = 19, t = «abca», K = «b», помещаем фразу «abcab» в словарь. s = 7 bc 18 4 d bcd 21 код 4 есть в словаре, помещаем фразу «bcd» в словарь d Таким образом, на выходе мы получим фразу Пример окончен. Монотонные коды Определение.Монотонным кодом назовем префиксный код 4 множества натуральных чисел, который удовлетворяет следующему условию если для любых i, j ∈ N и i ≤ j то для длин соответствующих кодовых слови выполняется неравенство l i ≤ Монотонные коды можно использовать, например для кодирования индексов строк словаря в алгоритме LZW. 2.3.1. Унарный код Унарный код сопоставляет натуральному числу m двоичную комбинацию вида 1 m – 1 0 5 , альтернативной записью унарного кода является 0 m – 1 1 [9, 2]. Приведем несколько унарных кодов унарный код альтернативный унарный код m унарный код альтернативный унарный код 0 1 5 11110 00001 2 10 01 6 111110 000001 3 110 001 7 1111110 0000001 4 1110 0001 8 11111110 Легко заметить, что длина кодового слова числа i для унарного кода равна l i = i. 2.3.2. Код Голомба Код является параметризированным префиксным кодом. Код особенно полезен в тех случая, когда удается подобрать хорошие значения параметра T. Код Голомба для натурального числа m 4 Напомним, что кодирование f называется префиксным, если никакое кодовое слово f (a i ) не является префиксом (началом) другого кодового слова f (a j ). Примером префиксного кода является код Хаффмана. 5 Запись вида 1 m или 0 m означает последовательность из m единиц или нулей соответственно и параметра T 6 состоит из двух частей и может быть получен после выполнения следующих шагов [12, 2]: › вычисляем величины , = T m q r = m – qT и T b 2 log = ; › строим первую часть кода (кодируем число q + 1 с помощью унарного кода второй частью кода является двоичное представление числа r: – если r < 2 b – T, то двоичная запись числа r размещается в b –1 битах остальные числа кодируются в b битах. Код Голомба для натурального числа m и параметра T 7 состоит из двух частей и может быть получен после выполнения следующих шагов вычисляем величины = T m q и r = m – qT; › строим первую часть кода (кодируем число q + 1 с помощью унарного кода второй частью кода является двоичное представление числа, состоящее избит. Приведем несколько кодов Голомба. m 1 2 3 4 5 6 7 8 9 T 2 (0)1 (10)0 (10)1 (110)0 (110)1 (1110)0 (1110)1 (11110)0 (11110)1 3 (0)10 (0)11 (10)0 (10)10 (10)11 (110)0 (110)10 (110)11 (1110)0 4 (0)01 (0)10 (0)11 (10)00 (10)01 (10)10 (10)11 (110)00 (110)01 5 (0)01 (0)10 (0)110 (0)111 (10)00 (10)01 (10)10 (10)110 (10)111 6 (0)01 (0)100 (0)101 (0)110 (0)111 (10)00 (10)01 (10)100 (Пусть входной поток данных состоит из натуральных чисел и вероятность числа равна P(m) = (1 – p) m – 1 , (где p – некоторый параметр 0 ≤ p ≤ 1). Коды Голомба будут оптимальными кодами для этого потока данных, если T выбрать из условия (1 – p) T + (1 – p) T + 1 ≤ 1< (1 – p) T – 1 + (1 – Легко заметить, что длина кодового слова числа i для кода Голомба равна T T i l i 2 log 1+ + = 6 Пусть T не является степенью 2. 7 Пусть T является степенью 2, то есть T = 2 b 26 2.3.3. Код Левенштейна Введем обозначения › bin(i) – двоичная запись натурального числа i; › bin' (i) – двоичная запись натурального числа i без первой единицы › | bin(i) | – длина двоичной последовательности bin(i); › λ | bin' (i) | – длина двоичной последовательности bin' Студенты могут заметить, что непосредственно использовать двоичные представления натуральных чисел при кодировании нельзя, ибо такой код не будет префиксным. Например, bin(2) = 10 является префиксом bin(5) = 101. Простейший способ преобразования двоичной записи числа в префиксный код состоит в том, что в начало можно записать префикс, например указывающий на длину двоичной записи числа. Учитывая, что в двоичной записи старший разряд всегда 1, его можно не передавать, если декодер знает длину двоичной записи (следовательно, число i можно, например, закодировать ( unar ( | bin' (i)| + 1 ), bin' (Чтобы сделать запись еще короче, с длиной двоичной записи можно поступить также, как и с самим числом, то есть заменим на | bin' | bin' (i) | | , bin' | bin'(i) | итак далее. Итерации продолжаются, пока не останется один значащий разряд. Чтобы декодирование было однозначным, достаточно приписать префикс, содержащий закодированное префиксным кодом число итераций. Заметим, что минимальное число итераций равно 0 при кодировании числа 1). Поэтому в качестве префиксного кода можно выбрать унарный код числа t (где t равно увеличенному на единицу числу итераций. Полученное кодовое слово будет кодовым словом кода Левенштейна. Пример: построим код Левенштейна для числа m = 17. Решение) =10001 ⇒ bin' (17) = 0001 ⇒ | bin' (17) | = 4; bin(4) =100 ⇒ bin' (4) = 00 ⇒ | bin' (4) | = 2; bin(2) =10 ⇒ bin' (2) = 0 ⇒ | bin' (2) | = 1. 8 Другими словами, | bin' (i) | можно представить bin' (λ k –2 (i))… bin' (λ(i)), где λ 2 (i) = | bin' ((λ(i)) | итак далее. Число итераций равно 3, следовательно в качестве префикса можно взять unar(4) = 1110. lev(17) = (Декодер кода Левенштейна сначала узнает, что число итераций равно 3. Прочитав значащий разряди дописав к нему в начало 1, получаем последовательность 10, то есть на предпоследней итерации длина числа была 2. Прочитав два разряда и дописав слева 1, получим 100. Теперь считываем четыре разряда и дописываем слева 1. Получаем последовательность 10001, ей соответствует число m = Пример окончен. Приведем несколько кодов Левенштейна. Введем обозначения - bin (m) 4 - bin ( | bin' (m)| ) | 7 - bin ( | bin' ( | bin' (m)| ) | ) 2 - bin' (m) 5 - bin' ( | bin' (m)| ) 8 - bin' ( | bin' ( | bin' (m)| ) | ) 3 - | bin' (m)| 6 - | bin' ( | bin' (m)| ) | 9 - | bin' ( | bin' ( | bin' (m)| ) | )| m 1 2 3 4 5 6 7 8 число итераций 10101 0101 4 100 00 2 10 0 1 3 (1110)(0)(00)(0101) 25 11001 1001 4 100 00 2 10 0 1 3 (1110)(0)(00)(1001) 30 11110 1110 4 100 00 2 10 0 1 3 (1110)(0)(00)(1110) 40 101000 01000 5 101 01 2 10 0 1 3 (1110)(0)(01)(01000) 60 111100 11100 5 101 01 2 10 0 1 3 (1110)(0)(01)(11100) 80 1010000 010000 6 110 10 2 10 0 1 3 (1110)(0)(10)( Другим похожим кодом может служить монотонный код mon(i) = ( unar ( | bin'(i) | + 1 ) , Студенты могут легко заметить, что согласно определению | bin'(i) | = i i n bi log ) ( = ′ и значит длинна кодового слова числа i (монотонный код) равна 1 log 2 + = i l i 28 2.3.4. Код Элайеса Код является упрощенным кодом Левенштейна. Числу m = 1 припишем кодовое слово elias(1) = 0. Для чисел m > 1 кодовые слова вычисляются по формуле) = ( unar (| bin' ( | bin' (m)| ) | + 2 ) , bin' ( | bin' (m)| ) , bin' (Приведем несколько кодов Элайеса. m bin (m ) s = bin' (m ) |s| bin ( |s| ) bin' ( |s| ) s 1 = |bin' ( |s| )| unar (s 1 + 2) elias (m ) 21 10101 0101 4 100 00 2 1110 (1110)(00)(0101) 25 11001 1001 4 100 00 2 1110 (1110)(00)(1001) 30 11110 1110 4 100 00 2 1110 (1110)(00)(1110) 40 101000 01000 5 101 01 2 1110 (1110)(01)(01000) 60 111100 11100 5 101 01 2 1110 (1110)(01)(11100) 80 1010000 010000 6 110 10 Длинна кодового слова числа i для кода Элайеса равна 2 log log 2 log 1 ,1 i i i i l i 29 |