Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v3(3-4)/kharin-151-159.pdf Дата изменения: Fri May 8 16:53:42 2009 Дата индексирования: Mon Oct 1 23:42:22 2012 Кодировка: Windows-1251

Об одном алгоритме сжатия данных
К.В. Харин

1 Введение
Проблема сжатия данных является одной из важнейших задач теории кодирования и ее приложений. Основным теоретическим результатом в этой области является теорема Хаффмана о кодах с минимальной избыточностью (см., например, [?]). Использование этой теоремы в большинстве алгоритмов сжатия данных заключается в построении словаря повторяющихся фрагментов входной последовательности данных и последующем кодировании таких фрагментов кодовыми словами в выходном алфавите так, чтобы наиболее длинным или часто встречающимся фрагментам соответствовали более короткие кодовые слова. При этом строящийся код должен будет обладать свойством префиксности для обеспечения однозначности декодирования. Реализация этого подхода связана с решением сложных переборных задач и с большими затратами памяти для хранения словаря и кодовых слов. В настоящей работе предлагается алгоритм, основанный на другом подходе к решению задачи сжатия данных. Входная последовательность разбивается на слова определенной небольшой длины, после чего наборы таких слов записываются в виде формул в специально подобранном базисе. Информация о базисе также записывается в выходной последовательности и декодирование осуществляется путем подстановки элементов этого базиса в формулу для восстановления исходных данных. На наш взгляд предлагаемый алгоритм обладает рядом преимуществ перед традиционными, поскольку при кодировании нет необходимости в предварительном просмотре входной последовательности и решении переборных задач построения словаря, а декодирование осуществляется максимально просто без существенных затрат памяти.


Прежде чем собственно строить алгоритм сформулируем строго решаемую задачу. В терминах машин Тьюринга задача сжатия данных может быть сформулирована следующим образом. Имеется входная лента, которую можно считать ограниченной с левой стороны. На ленте могут записываться символы из алфавита {0, 1, , #}. В начальный момент времени t0 на ленте, начиная с левого конца, записана последовательность символов (, a0 , a1 , . . . , aL-1 , aL ), где a0 , . . . , aL {0, 1} - элементы входной двоичной последовательности, подлежащей сжатию. Головка машины в начальном состоянии q0 устанавливается в крайнюю левую ячейку (с символом ). Требуется построить такую машину Тьюринга (алгоритм) A, чтобы она, начав работу в описанной конфигурации, через конечное число шагов остановилась, перейдя в заключительное состояние и оставив на ленте одну из следующих последовательностей символов: а) (#, b0 , b1 , . . . , bL1 ), где b0 , . . . , bL1 {0, 1}, и L1 < L, либо б) (, a0 , a1 , . . . , aL ), то есть повторить входную последовательность, что в данном случае будет означать отказ от сжатия. Кроме того, требуемая машина Тьюринга при подаче на ее вход в начальный момент времени в начальном состоянии последовательности (#, b0 , b1 , . . . , bL1 ), записанной на ленте, начиная с левого конца, через конечное число шагов должна остановиться, перейдя в заключительное состояние, после чего на ленте должна быть записана исходная последовательность (, a0 , a1 , . . . , aL ), что и будет, собственно, означать возможность точного восстановления исходных данных по сжатой последовательности (условие "сжатия без потерь"). Вспомогательные символы алфавита '' и '#' служат только для задания "направления"работы алгоритма (сжатие или восстановление) и введены исключительно для удобства. Вместо них вполне можно использовать символы '0' и '1'. Условие на длину выходной последовательности L1 < L означает именно сжатие (уменьшение длины) входной последовательности при сохранении возможности ее восстановления. Для решения этой задачи в настоящей работе предлагается алгоритм, основная идея которого заключается в разбиении входной последовательности на слова определенной небольшой длины и записи 152


наборов таких слов в виде формул в специально подобранном базисе.

2 Основные понятия и определения
В этом разделе будут введены некоторые понятия, которые будут использоваться при описании и обосновании алгоритма. Пусть n N, n 2. На множестве En = {0, . . . , n - 1} рассмотрим произвольное отношение эквивалентности , то есть разобьем En на N непересекающихся классов эквивалентности. Эквивалентность элементов i и j множества En будем обозначать i j . Рассмотрим n теперь произвольное слово A длины n в алфавите {0, 1}, то есть A E2 . A = (a0 , . . . , an-1 ). Множество En можно рассматривать как множество индексов букв слова A. Определение 1. Отношение эквивалентности на множестве En n называется согласованным со словом A = (a0 , . . . , an-1 ) E2 , если для любых i1 , i2 En из i1 i2 следует, что ai1 = ai2 . Таким образом, буквы слова A, индексы которых эквивалентны, должны совпадать. Пример. Пусть в множестве E4 = {1, 2, 3, 4} задано отношение эквивалентности , такое что 1 2, 3 4, но 2 3, то есть классами эквивалентности относительно являются подмножества {1, 2} и {3, 4}. 4 Тогда отношение будет согласовано со следующими словами из E2 : (0000), (0011), (1100), (1111) и не будет согласовано с остальными 12 4 элементами E2 . n Пусть теперь A = A1 , . . . , Ak - набор слов из E2 . Определение 2. Отношение эквивалентности на множестве En оптимально согласовано с набором A, если: 1. согласовано с Ai для любого i {1, . . . , k }. 2. Для любого отношения эквивалентности на En , обладающего свойством 1, количество N классов эквивалентности, на которые разбивается En в соответствии с , не меньше количества N классов эквивалентности для отношения (N N ). Необходимо заметить, что отношение эквивалентности, разбивающее En на n классов (то есть отношение, при котором никакие два элемента i, j En при i = j не эквивалентны), согласовано с любым словом n A из E2 . Таким образом, свойство 2 из определения 2 действительно 153



задает в некотором смысле оптимальность выбранного отношения эквивалентности. Кроме того, любое отношение эквивалентности , согласованное со всеми элементами набора A, задает разбиение на классы эквивалентности, которое является подразбиением соответствующего разбиения для оптимально согласованного отношения эквивалентности. Учитывая сказанное, а также определения 1 и 2, можно показать истинность следующего утверждения.

A 1 , . . . , Ak n из E2 существует оптимально согласованное с A отношение эквивалентности на множестве индексов En , причем такое отношение единственно. =

Утверждение 1 Для любого набора слов A

3 Основная идея алгоритма
Пусть имеется входная последовательность данных (a0 , a1 , ..., aL ), где ai {0, 1} при i = 0, . . . , L. Выберем натуральное число n в качестве параметра алгоритма (из практических соображений n удобно выбирать из значений вида n = 2q , где q = 3, 4, 5, 6). Рассмотрим последовательно идущие слова входной последовательности длины n A1 = (a0 , . . . , an-1 ), A2 = (an , . . . , a2n-1 ), . . . Можно считать, что L + 1 = b ћ n (b N), при необходимости дополняя исходную последовательность нулями. Будем строить отношения эквивалентности 1 , 2 , ћ ћ ћ на En , такие что 1 оптимально согласовано с A1 2 оптимально согласовано с A1 , A2 . . .

k оптимально согласовано с . . .

A 1 , A2 , . . . , A

k

Обозначим количество классов эквивалентности, на которые разбивается En в соответствии с отношением эквивалентности i через Ni . Процесс построения отношений 1 , 2 , . . . можно описать с использованием индукции: а) Слову A1 в общем случае соответствует разбиение t1 на два класса индексов из En : индексы, соответствующие буквам, принимающим 154


значение 0 в A1 , и буквам, принимающим значение 1. Это разбиение выбирается в качестве разбиения T1 , соответствующего отношению эквивалентности 1 , согласованному с A1 . б) Если построено разбиение Tk множества En на классы эквивалентности для отношения k , оптимально согласованного с набором A1 , . . . , Ak , то рассмотрим слово Ak+1 , которое задает разбиение tk+1 множества En на два класса, аналогичное рассмотренному в пункте а). В качестве разбиения Tk+1 , соответствующего отношению эквивалентности k+1 выбирается подразбиение разбиения Tk , полученное его пересечением с разбиением tk+1 . Очевидно, что процесс построения отношений 1 , . . . , k . . . необходимо продолжать, пока Nk < n, и не исчерпана вся входная последовательность. Пусть l таково, что Nl < n, Nl+1 = n, либо L = ln. Для любого i {1, . . . , l} можно записать всю информацию, содержащуюся в элементах набора A1 , . . . , Ai , следующим образом. Выходная последовательность будет состоять из трех частей:

[ запись i ][ запись i][(

)(

)...(

)]

i записей, соответствующих элементам Aj (1 j i)

Занумеруем классы эквивалентности на En по отношению i числами от 0 до Ni - 1 так, чтобы первый элемент множества En принадлежал классу с номером 0. Запись i (то есть слово, кодирующее всю информацию об отношении эквивалентности i ) может быть составлена из n - 1 двоичных чисел номеров классов эквивалентности, которым принадлежат элементы 1, . . . , n - 1 множества En . Длина такой записи равна (n - 1) ћ ] log2 Ni [. Запись i представляет собой просто двоичную запись числа i. Каждая из i записей, соответствующих Aj (j = 1, . . . , i), представляет собой двоичное слово длины Ni , элементы которого являются значениями букв aj , соответствующих произвольному представителю m каждого из m Ni классов эквивалентности на множестве индексов En в соответствии с выбранной выше нумерацией. 1 Таким образом, длина всего выходного слова будет равна li = (n - 1) ћ ] log2 Ni [ + ] log2 i[ + i ћ Ni . Учитывая, что длина части входной последовательности, соответствующей набору слов A1 , . . . , Ai равна li = in, можно 155


1 вычислить коэффициент сжатия i = li /li . Если i > 1, то часть входной последовательности (a0 , . . . , ain-1 ) может быть сжата. Следует отметить, что сжатие подобным образом можно рассматривать как запись каждого из слов набора A1 , . . . , Ai в виде формулы в специально построенном для этого набора базисе (точнее, в полной системе). Для понимания этой идеи следует привести некоторые понятия и определения из работы [?]. А именно, рассмотрим функции вида f : En E2 и обозначим все множество таких функций через PEn ,E2 . Введем на PEn ,E2 операции конъюнкции, дизъюнкции и отрицания следующим образом: для любых f , g PEn ,E2 и x En положим (f &g )(x) = f (x)&g (x), (f g )(x) = f (x) g (x), (ѓf )(x) = ѓ(f (x)), где операции &, , ѓ над значениями функций f и g в точке x элементами множества E2 понимаются в традиционном смысле. Таким образом, операции на PEn ,E2 определяются поточечно. В алгебре PEn ,E2 , , где = {&, , ѓ} можно ввести понятия полной системы и базиса следующим образом. Множество B PEn ,E2 называется полной системой, если [B ] = PEn ,E2 . Базисом называется такая полная система, удаление из которой любого элемента делает ее неполной. Можно также по аналогии рассматривать полные системы и базисы для подмножеств PEn ,E2 . В данном случае для набора слов A1 , . . . , Ai по сути строится полная система, состоящая из характеристических функций классов эквивалентности по отношению i на множестве индексов En . Эти n функции можно рассматривать и как элементы PEn ,E2 , и как слова из E2 . Слова A1 , . . . , Ai строятся из элементов этой полной системы с помощью введенных выше операций дизъюнкции и отрицания в соответствии со значениями букв этих слов на каждом из классов эквивалентности. Итак, выше нами была описана процедура построения фрагмента сжатой выходной последовательности, соответствующей набору входных слов A1 , . . . , Ai . Очевидно, что таких наборов, для которых можно построить сжатую последовательность, может быть много, причем они могут пересекаться друг с другом, то есть часть одного "сжимаемого"набора может быть частью другого. В этом случае для исключения помещения лишней информации в выходную

156


последовательность, которая должна быть как можно короче, для сжатия выбирается только часть "сжимаемых"наборов, так что никакие два выбранных набора не пересекаются. Вопросы оптимизации такого выбора наборов и другие вопросы, связанные с оптимизацией описанного алгоритма, будут затронуты ниже. Остается упомянуть о полной структуре выходной сжатой последовательности с учетом наличия нескольких сжимаемых наборов входных слов. Эта структура такова:
сжатая последовательность для набора Ai1 , . . . , Ai1 +p1

[()][x1 ][a0 , . . . , a [

x1 -1

][

][x2 ][aj1 , . . . , a

j1 +x2 -1

]

сжатая последовательность для набора Ai2 , . . . , Ai2 +p2

]ћћћ

ћ ћ ћ [x ][ajp , . . . , aL ],

где () обозначает определенную последовательность символов, обозначающую, является ли данная последовательность сжатой (при отказе от сжатия выходная последовательность начинается с символов (#), после чего переписывается вся входная последовательность), xq обозначает номер буквы, с которой начинается q -й сжимаемый набор слов. Фрагменты, содержащие буквы входной последовательности ajs , соответствуют несжимаемым ее частям, x обозначает определенную последовательность символов, которая завершает последнюю сжатую подпоследовательность, после которой следует только несжимаемый фрагмент входной последовательности.

4 Возможные пути оптимизации алгоритма
В предыдущем разделе была изложена основная идея алгоритма решения задачи сжатия данных и было показано, как могут быть выделены части входной последовательности, для которых сжатие возможно. Необходимо обратить внимание на два момента, позволяющих в некоторой степени управлять процессом отбора сжимаемых наборов слов входной последовательности. 1. Рассмотрим набор A1 , . . . , Al , где l таково, что Nl < n, Nl+1 = n, либо L = ln. В этом случае обозначим через I множество I {1, . . . , l}, такое что для любого i I i > 1, где i - коэффициент сжатия, вычисленный для набора A1 , . . . , Ai . При этом если |I | > 157


1, то существует несколько наборов слов входной последовательности, начинающихся со слова A1 , для которых возможно сжатие. 2. Как уже было отмечено ранее, различные "сжимаемые"наборы слов входной последовательности могут пересекаться друг с другом. При этом, как и в предыдущем случае, различные наборы могут иметь разный коэффициент сжатия и разную длину, что может сильно влиять на общую степень сжатия всей последовательности. В обоих приведенных случаях для исключения помещения лишней информации в выходную последовательность и для обеспечения лучшего сжатия данных имело бы смысл воспользоваться каким-либо критерием оптимальности "сжимаемого"набора слов, позволяющего выделить наилучший в некотором смысле набор из всех, имеющих общие элементы. Ряд таких критериев может, например, возникнуть из содержательной сути решаемой задачи сжатия. В качестве возможных критериев можно рассмотреть следующие числовые характеристики: коэффициент сжатия i , произведение i ћ i коэффициента сжатия на длину набора и некоторые другие комбинации параметров "сжимаемого"набора. Поскольку аналитическое и даже статистическое исследование характеристик данного алгоритма представляется достаточно трудоемким из-за многостороннего влияния различных факторов и структуры входной последовательности на степень сжатия, были проведены модельные исследования алгоритма с различными критериями оптимальности. Алгоритм был реализован в виде программы на языке С++ и был испытан на реальных входных данных (текстовых, графических, файлах баз данных и т.д.). При этом чаще всего лучшие результаты демонстрировались в случае, когда в качестве критерия оптимальности набора выбиралось произведение i ћ i. В заключение автор выражает благодарность Д.Н. Бабину и А.С. Строгалову за поддержку работы и плодотворное участие в обсуждениях.

Список литературы
[1] Яблонский С.В. Введение в дискретную математику. М., Наука. 1986. 158


[2] Харин К.В. Об одной алгебре изображений // Дискретная математика. 1996. Т. 8, вып. 4. С. 149-156.

159