Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
HX M L(X) для кода Шеннона-Фэно для X следует M L 1 (X) − 1/n HX 1 M для этого же кода Таким образом, доказана основная теорема о кодировании при отсутствии помеха именно то, что с ростом длины n сообщения, при кодировании методом Шеннона-Фэно всего сообщения целиком среднее количество бит на единицу сообщения будет сколь угодно мало отличаться от энтропии единицы сообщения. Подобное кодирование практически не реализуемо из-за того, что с ростом длины сообщения трудоемкость построения этого кода становится недопустимо большой. Кроме того, такое кодирование делает невозможным отправку сообщения по частям, что необходимо для непрерывных процессов передачи данных. Дополнительным недостатком этого способа кодирования является необходимость отправки или хранения собственно полученного кода вместе сего исходной длиной, что снижает эффект от сжатия. На практике для повышения степени сжатия используют метод блокирования. По выбранному значению ε > 0 можно выбрать такое s, что если разбить все сообщение на блоки длиной s (всего будет n/s блоков, то кодированием Шеннона-Фэно таких блоков, рассматриваемых как единицы сообщения, можно сделать среднее количество бит на единицу сообщения большим энтропии менее, чем на ε. Действительно, пусть = (Y 1 , Y 2 , . . . , Y n/s ), Y 1 = (X 1 , X 2 , . . . , X s ), Y 2 = (X s+1 , X s+2 , . . . , и т. д, те. Тогда HY 1 = и sM L 1 (Y 1 ) = M L(Y 1 ) HY 1 + 1 = sHX 1 + 1, следовательно L 1 (Y 1 ) HX 1 + те. достаточно брать s = 1/ε. Минимум s по заданному ε может быть гораздо меньшим Пример. Пусть д.с.в. X 1 , X 2 , . . . X n независимы, одинаково распределены и могут принимать только два значения P (X i = 0) = p = 3/4 и (X i = 1) = q = 1/4 при i от 1 до n. Тогда 4 log 2 4 3 + 1 4 log 2 4 = 2 − 3 4 log 2 3 ≈ 0.811 бит/сим. Минимальное кодирование здесь — это коды 0 и 1 с длиной 1 бит каждый. При таком кодировании количество битв среднем на единицу сообщения равно 1. Разобьем сообщение на блоки длины 2. Закон распределения вероятностей и кодирование для мерной д. св Тогда при таком минимальном кодировании количество битв среднем на единицу сообщения будет уже L 1 (X) = 1 9 16 + 2 3 16 + 3 3 16 + 3 1 16 /2 = 27 32 = те. меньше, чем для неблочного кодирования. Для блоков длины 3 количество битв среднем на единицу сообщения можно сделать ≈ для блоков длины 4 — ≈ 0.818 и т.д. Все изложенное ранее подразумевало, что рассматриваемые д. с. в. кодируются только двумя значениями (обычно 0 и 1). Пусть д. св. кодируются значениями. Тогда для д. св и любого ее кодирования верно, что M L(X) HX/ log 2 m и M L 1 (X) HX 1 / log 2 m. Кроме того, существует кодирование такое, что M L(X) − 1 HX/ log 2 m и L 1 (X) − 1/n HX 1 / log 2 m, где n = Формулы теоретических приделов уровня сжатия, рассмотренные ранее, задают предел для средней длины кода на единицу сообщений, передаваемых много раз, те. они ничего не говорят о нижней границе уровня сжатия, которая может достигаться на некоторых сообщениях и быть меньшей энтропии д.с.в., реализующей сообщение. Простейшие алгоритмы сжатия информации Метод Шеннона-Фэно состоит в следующем, значения д.с.в. располагают в порядке убывания их вероятностей, а затем последовательно делят на две части с приблизительно равными вероятностями, к коду первой части добавляют 0, а к коду второй — Для предшествующего примера получим code(X) 00 9/16 0 01 3/16 10 10 3/16 110 11 1/16 111, M L 1 (X) = 27/32 = 0.84375 бит/сим. Еще один пример. Код составляется после сортировки, те. после перестановки значений B и C. X p code(X) A 0.4 0 B 0.2 11 C 0.4 10, M L(X) = M L 1 (X) = 1.6 бит/сим, HX = log 2 5 − 0.8 ≈ 1.523 бит/сим. Метод Хаффмена (Huffman) разработан в 1952 г. Он более практичен и никогда по степени сжатия не уступает методу Шеннона-Фэно, более того, он сжимает максимально плотно. Код строится при помощи двоичного (бинарного) дерева. Вероятности значений д.с.в. приписываются его листьям все дерево строится, опираясь на листья. Величина, приписанная к узлу дерева, называется весом узла. Два листа с наименьшими весами создают родительский узел с весом, равным сумме их весов в дальнейшем этот узел учитывается наравне с оставшимися листьями, а образовавшие его узлы от такого рассмотрения устраняются. После постройки корня нужно приписать каждой из ветвей, исходящих из родительских узлов, значения 0 или 1. Код каждого значения д. св это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению. Для методов Хаффмена и Шеннона-Фэно каждый раз вместе с собственно сообщением нужно передавать и таблицу кодов. Например, для случая из примера 2 нужно сообщить, что коду 10 соответствует символ, коду 0 — A и т.д. Построим коды Хаффмена для значений д.с.в. из двух предыдущих примеров 01 10 11 p 9 / 16 3 / 16 3 / 16 1 / 16 0 1 4 16 0 1 7 16 0 1 1 code(X) 0 10 110 111 M L 1 (X) = M L(X)/2 = 27/32 = 0.84375 бит/сим. X A B C p 0.4 0.2 0.4 0 1 0.6 0 1 1 code(X) 0 10 11 M L 1 (X) = M L(X) = 1.6 бит/сим. Упражнение Вычислить M L 1 (X) для блочного кода Хаффмена для X. Длина блока 2 бита. Д.с.в. X берется из последнего примера. Упражнение Вычислить HX и M L(X) для кодов Хаффмена и Шеннона-Фэно для X. 24 Д.с.в. X задается следующим распределением вероятностей 2 3 4 5 p 7 / 18 1 / 6 1 / 6 1 / 6 1 / 9 12. Арифметическое кодирование Алгоритм кодирования Хаффмена, в лучшем случае, не может передавать на каждый символ сообщения менее одного бита информации. Предположим, известно, что в сообщении, состоящем из нулей и единиц, единицы встречаются враз чаще нулей. При кодировании методом Хаффмена и на 0 и на 1 придется тратить не менее одного бита. Но энтропия д. св, генерирующей такие сообщения ≈ 0.469 бит/сим. Метод Хаффмена дает для минимального среднего количества бит на один символ сообщения значение 1 бит. Хотелось бы иметь такую схему кодирования, которая позволяла бы кодировать некоторые символы менее чем одним битом. Одной из лучших среди таких схем является арифметическое кодирование, разработанное в х годах XX века. По исходному распределению вероятностей для выбранной для кодирования д. св. строится таблица, состоящая из пересекающихся только в граничных точках отрезков для каждого из значений этой д.с.в.; объединение этих отрезков должно образовывать отрезок [0,1], а их длины должны быть пропорциональны вероятностям соответствующих значений д. св. Алгоритм кодирования заключается в построении отрезка, однозначно определяющего данную последовательность значений д.с.в. Затем для построенного отрезка находится число, принадлежащее его внутренней части и равное целому числу, деленному на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Всевозможные конкретные коды — это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и десятичную точку, но нужен еще один специальный код-маркер, сигнализирующий оконце сообщения. Отрезки строятся так. Если имеется отрезок для сообщения длины n−1, то для построения отрезка для сообщения длины n, разбиваем его настолько же частей, сколько значений имеет рассматриваемая д.с.в. Это разбиение делается совершенно также как и самое первое (с сохранением порядка. Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины Принципиальное отличие этого кодирования от рассмотренных ранее методов в его непрерывности, те. в ненужности блокирования. Эффективность арифметического кодирования растет с ростом длины сжимаемого сообщения (для кодирования Хаффмена или Шеннона-Фэно этого не происходит. Хотя арифметическое кодирование дает обычно лучшее сжатие, чем кодирование Хаффмена, оно пока используется на практике сравнительно редко, т.к. оно появилось гораздо позже и требует больших вычислительных ресурсов. При сжатии заданных данных, например, из файла все рассмотренные методы требуют двух проходов. Первый для сбора частот символов, используемых как приближенные значения вероятностей символов, и второй для собственно сжатия. Пример арифметического кодирования. Пусть д.с.в. X может принимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответственно. Сопоставим значению 0 отрезок [0,2/3], а 1 — [2/3,1]. Тогда для д.с.в. X, dim(X) = 3, HX = HX/3 = log 2 3 − 2/3 ≈ 0.9183 бит/сим., таблица построения кодов Интервалы и коды Вероятность Код Хаффмена 111[ 26 27 , 1] 31 32 = 0.11111 1 / 27 0000 11[ 8 9 , 1] 110[ 8 9 , 26 27 ] 15 16 = 0.1111 2 / 27 0001 101[ 22 27 , 8 9 ] 7 8 = 0.111 2 / 27 010 1[ 2 3 , 1] 10[ 2 3 , 8 9 ] 100[ 2 3 , 22 27 ] 3 4 = 0.11 4 / 27 001 011[ 16 27 , 2 3 ] 5 8 = 0.101 2 / 27 011 01[ 4 9 , 2 3 ] 010[ 4 9 , 16 27 ] 1 2 = 0.1 4 / 27 100 001[ 8 27 , 4 9 ] 3 8 = 0.011 4 / 27 101 0[0, 2 3 ] 00[0, 4 9 ] 000[0, 8 27 ] 1 4 = 0.01 8 / 27 11. M L 1 (X) = 65/81 ≈ 0.8025 бит/сим. (арифметическое L 1 (X) = 76/81 ≈ 0.9383 бит/сим. (блочный Хаффмена), M L 1 (X) = M L(X) = 1 бит/сим. (Хаффмена). Среднее количество бит на единицу сообщения для арифметического кодирования получилось меньше, чем энтропия. Это связано стем, что в рассмотренной простейшей схеме кодирования, не описан код-маркер конца сообщения, введение которого неминуемо сделает это среднее количество бит большим энтропии. Получение исходного сообщения из его арифметического кода происходит последующему алгоритму Шаг 1. В таблице для кодирования значений д. св. определяется интервал, содержащий текущий код, — поэтому интервалу однозначно определяется один символ исходного сообщения. Если этот символ — это маркер конца сообщения, то конец. Шаг 2. Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу Упражнение Вычислить среднее количество бит на единицу сжатого сообщения о значении каждой изд. св, из заданных следующими распределениями вероятностей, при сжатии методами Шеннона-Фэно, Хаффмена и арифметическим 1 2 3 4 p 1/3 1/3 1/6 1/6, X 2 1 2 5 6 7 p 0.2 0.1 0.3 0.25 0.15, X 3 1 4 9 16 25 36 49 p 0.1 0.1 0.1 0.3 0.1 0.1 0.2, X 4 −2 −1 0 1 2 p 1/3 1/4 1/5 1/6 Упражнение Вычислить длины кодов Хаффмена и арифметического для сообщения, полученного отд. св со следующим распределением вероятностей Упражнение Составить арифметический код для сообщения BAABC, полученного от д.с.в. X со следующим распределением вероятностей P (X = A) = 1/4, P (X = B) = 1/2, P (X = C) = 1/4. Каков будет арифметический код для этого же сообщения, если X распределена по закону P (X = A) = 1/3, P (X = B) = 7/15, P (X = C) = Упражнение Д. св может принимать три различных значения. При построении блочного кода с длиной блока 4 для X необходимо будет рассмотреть д. св выборку четырех значений X. Сколько различных значений может иметь X? Если считать сложность построения кода пропорциональной количеству различных значений кодируемой д. св, то во сколько раз сложнее строить блочный код для X по сравнению с неблочным? Упражнение Составить коды Хаффмена, блочный Хаффмена (для блоков длины 2 и) и арифметический для сообщения ABAAAB, вычислить их длины Приблизительный закон распределения вероятностей д.с.в., сгенериро- вавшей сообщение, определить анализом сообщения. Адаптивные алгоритмы сжатия. Кодирование Хаффмена Является практичным, однопроходным, не требующим передачи таблицы кодов. Его суть в использовании адаптивного алгоритма, т.е. алгоритма, который при каждом сопоставлении символу кода, кроме того, изменяет внутренний ход вычислений так, что в следующий раз этому же символу может быть сопоставлен другой код, те. происходит адаптация алгоритма к поступающим для кодирования символам. При декодировании происходит аналогичный процесс. В начале работы алгоритма дерево кодирования содержит только один специальный символ, всегда имеющий частоту 0. Он необходим для занесения в дерево новых символов после него код символа передается непосредственно. Обычно такой символ называют escape- символом ( ESC ). Расширенный ASCII кодируют каждый символ 8- битным числом, те. числом от 0 до 255. При построении дерева кодирования необходимо для возможности правильного декодирования как-то упорядочивать структуру дерева. Расположим листья дерева в порядке возрастания частот и затем в порядке возрастания стандартных кодов символов. Узлы собираются слева направо без пропусков. Левые ветви помечаются 0, а правые — Рассмотрим процесс построения кодов по адаптивному алгоритму Хаффмена для сообщения ACCBCAAABC, которое соответствует выборке и значений д.с.в. X из го примера на построение неадап- тивного кода Хаффмена: входные код длина № данные кода дерева 1 C 0’C’ 9 2 C 1 1 3 B 00’B’ 10 4 C 1 1 5 A 001 3 6 A 01 2 7 A 01 2 8 B 001 3 9 C 01 2 1 s s 0/ ESC 1/A s 2 s 1 s s 0/ ESC 1/A s 1/C s 3 s 1 s s 0/ ESC 1/A s 2/C s 4 s 2 s 1 s s 0/ ESC s 1/A s 1/B s 2/C 28 5 s 2 s 1 s s 0/ ESC s 1/A s 1/B s 3/C 6 s 3 s 1 s s 0/ ESC s 1/B s 2/A s 3/C 7 s 4 s 1 s s 0/ ESC s 1/B s 3/A s 3/C 8 s 4 s 1 s s 0/ ESC s 1/B s 3/C s 4/A 9 s 5 s 2 s s 0/ ESC s 2/B. s 3/C Здесь L 1 (ACCBCAAABC) = 4.1 бит/сим. Если не использовать сжатия, то L 1 (ACCBCAAABC) = 8 бит/сим. Для рассматриваемой д. св. ранее были получены значения M L 1 (X) = 1.6 бит/сим и HX ≈ 1.523 бит/сим. Нос ростом длины сообщения среднее количество бит на символ сообщения при адаптивном алгоритме кодирования будет мало отличаться от значения, полученного при использовании неадап- тивного метода Хаффмена или Шеннона-Фэно, т. к. алфавит символов ограничен и полный код каждого символа нужно передавать только один раз. Теперь рассмотрим процесс декодирования сообщения ’A’0’C’100 ’B’1001010100101. Здесь и далее символ в апостофах означает восемь бит, представляющих собой запись двоичного числа, номера символа, в таблице ASCII+. Вначале декодирования дерево Хаффмена содержит только символ с частотой 0. С раскодированием каждого нового символа дерево заново перестраивается. входные символ № данные дерева 0’C’ C 2 1 C 3 Выбранный способ адаптации алгоритма очень неэффективный, т. к. после обработки каждого символа нужно перестраивать все дерево кодирования. Существуют гораздо менее трудоемкие способы, при которых ненужно перестраивать все дерево, а нужно лишь незначительно изменять. Бинарное дерево называется упорядоченным, если его узлы могут быть перечислены в порядке неубывания веса ив этом перечне узлы, имеющие общего родителя, должны находиться рядом, на одном ярусе. Причем перечисление должно идти по ярусам снизу-вверх и слева- направо в каждом ярусе. На рис. 4 приведен пример упорядоченного дерева Хаффмена. 17 7 3 1 A ¡ ¡ ¡ e e e 2 B d d d 4 2 C ¡ ¡ ¡ e e e 2 D. ¡ ¡ ¡ e Рис. 4 19 9 4 2 D ¡ ¡ ¡ e e e 2 B d d d 5 2 C ¡ ¡ ¡ e e e 3 A ¡ ¡ ¡ e Рис. Если дерево кодирования упорядоченно, то при изменении веса существующего узла дерево ненужно целиком перестраивать — в нем достаточно лишь поменять местами два узла узел, вес которого нарушил упорядоченность, и последний из следующих за ним узлов меньшего веса. После перемены мест узлов, необходимо пересчитать веса всех их узлов-предков. Например, если в дереве на рис. 4 добавить еще две буквы A, то узлы A и D должны поменяться местами (см. рис. 5). 21 11 4 2 D ¡ ¡ ¡ e e e 2 B d d d 7 2 C ¡ ¡ ¡ e e e 5 A ¡ ¡ ¡ e e e 10 E → 21 11 5 A ¡ ¡ ¡ e e e 6 2 C ¡ ¡ ¡ e e e 4 2 D ¡ ¡ ¡ e e e 2 B ¡ ¡ ¡ e e e 10 E 21 10 E ¡ ¡ ¡ e e e 11 5 A ¡ ¡ ¡ e e e 6 2 C ¡ ¡ ¡ e e e 4 2 D ¡ ¡ ¡ e Рис. 6 31 Если добавить еще две буквы A, то необходимо будет поменять местами сначала узел A и узел, родительский для узлов D и B, а затем узел E и узел-брат E (рис. Дерево нужно перестраивать только при появлении в нем нового узла-листа. Вместо полной перестройки можно добавлять новый лист справа к листу ESC и упорядочивать, если необходимо, полученное таким образом дерево. Процесс работы адаптивного алгоритма Хаффмена с упорядоченным деревом можно изобразить следующей схемой: входные код длина № метод данные кода дерева получения добавление узла добавление узла упорядочение добавление узла не меняется не меняется упорядочение упорядочение не меняется 2 |