Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
1. Методы сжатия данных;
2. Сжатие изображений без потерь;
3. Сжатие изображений с потерями.
Ниже вы можете ознакомиться с первым постом серии.

На текущий момент существует большое количество алгоритмов сжатия без потерь, которые условно можно разделить на две большие группы:
1. Поточные и словарные алгоритмы. К этой группе относятся алгоритмы семейств RLE (run-length encoding), LZ* и др. Особенностью всех алгоритмов этой группы является то, что при кодировании используется не информация о частотах символов в сообщении, а информация о последовательностях, встречавшихся ранее.
2. Алгоритмы статистического (энтропийного) сжатия. Эта группа алгоритмов сжимает информацию, используя неравномерность частот, с которыми различные символы встречаются в сообщении. К алгоритмам этой группы относятся алгоритмы арифметического и префиксного кодирования (с использованием деревьев Шеннона-Фанно, Хаффмана, секущих).
В отдельную группу можно выделить алгоритмы преобразования информации. Алгоритмы этой группы не производят непосредственного сжатия информации, но их применение значительно упрощает дальнейшее сжатие с использованием поточных, словарных и энтропийных алгоритмов.

Поточные и словарные алгоритмы

Кодирование длин серий

Кодирование длин серий (RLE - Run-Length Encoding) - это один из самых простых и распространённых алгоритмов сжатия данных. В этом алгоритме последовательность повторяющихся символов заменяется символом и количеством его повторов.
Например, строку «ААААА», требующую для хранения 5 байт (при условии, что на хранение одного символа отводится байт), можно заменить на «5А», состоящую из двух байт. Очевидно, что этот алгоритм тем эффективнее, чем длиннее серия повторов.

Основным недостатком этого алгоритма является его крайне низкая эффективность на последовательностях неповторяющихся символов. Например, если рассмотреть последовательность «АБАБАБ» (6 байт), то после применения алгоритма RLE она превратится в «1А1Б1А1Б1А1Б» (12 байт). Для решения проблемы неповторяющихся символов существуют различные методы.

Самым простым методом является следующая модификация: байт, кодирующий количество повторов, должен хранить информацию не только о количестве повторов, но и об их наличии. Если первый бит равен 1, то следующие 7 бит указывают количество повторов соответствующего символа, а если первый бит равен 0, то следующие 7 бит показывают количество символов, которые надо взять без повтора. Если закодировать «АБАБАБ» с использованием данной модификации, то получим «-6АБАБАБ» (7 байт). Очевидно, что предложенная методика позволяет значительно повысить эффективность RLE алгоритма на неповторяющихся последовательностях символов. Реализация предложенного подхода приведена в Листинг 1:

1. type
2. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
3. MatchFl: boolean ;
4. MatchCount: shortint ;
5. EncodedString: TRLEEncodedString;
6. N, i: byte ;
7. begin
8. N : = 0 ;
9. SetLength(EncodedString, 2 * length(InMsg) ) ;
10. while length(InMsg) >= 1 do
11. begin
12. MatchFl : = (length(InMsg) > 1 ) and (InMsg[ 1 ] = InMsg[ 2 ] ) ;
13. MatchCount : = 1 ;
14. while (MatchCount <= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount : = MatchCount + 1 ;
16. if MatchFl then
17. begin
18. N : = N + 2 ;
19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] ) ;
21. else
22. begin
23. if MatchCount <> length(InMsg) then
24. MatchCount : = MatchCount - 1 ;
25. N : = N + 1 + MatchCount;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. for i : = 1 to MatchCount do
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
29. end ;
30. delete(InMsg, 1 , MatchCount) ;
31. end ;
32. SetLength(EncodedString, N) ;
33. RLEEncode : = EncodedString;
34. end ;

Декодирование сжатого сообщения выполняется очень просто и сводится к однократному проходу по сжатому сообщению см. Листинг 2:

1. type
2. TRLEEncodedString = array of byte ;
3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
4. RepeatCount: shortint ;
5. i, j: word ;
6. OutMsg: ShortString;
7. begin
8. OutMsg : = "" ;
9. i : = 0 ;
10. while i < length(InMsg) do
11. begin
12. RepeatCount : = InMsg[ i] - 128 ;
13. i : = i + 1 ;
14. if RepeatCount < 0 then
15. begin
16. RepeatCount : = abs (RepeatCount) ;
17. for j : = i to i + RepeatCount - 1 do
18. OutMsg : = OutMsg + chr (InMsg[ j] ) ;
19. i : = i + RepeatCount;
20. else
21. begin
22. for j : = 1 to RepeatCount do
23. OutMsg : = OutMsg + chr (InMsg[ i] ) ;
24. i : = i + 1 ;
25. end ;
26. end ;
27. RLEDecode : = OutMsg;
28. end ;

Вторым методом повышения эффективности алгоритма RLE является использование алгоритмов преобразования информации, которые непосредственно не сжимают данные, но приводят их к виду, более удобному для сжатия. В качестве примера такого алгоритма мы рассмотрим BWT-перестановку, названную по фамилиям изобретателей Burrows-Wheeler transform. Эта перестановка не изменяет сами символы, а изменяет только их порядок в строке, при этом повторяющиеся подстроки после применения перестановки собираются в плотные группы, которые гораздо лучше сжимаются с помощью алгоритма RLE. Прямое BWT преобразование сводится к последовательности следующих шагов:
1. Добавление к исходной строке специального символа конца строки, который нигде более не встречается;
2. Получение всех циклических перестановок исходной строки;
3. Сортировка полученных строк в лексикографическом порядке;
4. Возвращение последнего столбца полученной матрицы.
Реализация данного алгоритма приведена в Листинг 3.

1. const
2. EOMsg = "|" ;
3. function BWTEncode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: word ;
7. begin
8. InMsg : = InMsg + EOMsg;
9. N : = length(InMsg) ;
10. ShiftTable[ 1 ] : = InMsg;
11. for i : = 2 to N do
12. begin
13. LastChar : = InMsg[ N] ;
14. InMsg : = LastChar + copy(InMsg, 1 , N - 1 ) ;
15. ShiftTable[ i] : = InMsg;
16. end ;
17. Sort(ShiftTable) ;
18. OutMsg : = "" ;
19. for i : = 1 to N do
20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
21. BWTEncode : = OutMsg;
22. end ;

Проще всего пояснить это преобразование на конкретном примере. Возьмём строку «АНАНАС» и договоримся, что символом конца строки будет символ «|». Все циклические перестановки этой строки и результат их лексикографической сортировки приведены в Табл. 1.

Т.е. результатом прямого преобразования будет строка «|ННАААС». Легко заметить, что это строка гораздо лучше, чем исходная, сжимается алгоритмом RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв.
Подобного эффекта можно добиться и с помощью других преобразований, но преимущество BWT-преобразования в том, что оно обратимо, правда, обратное преобразование сложнее прямого. Для того, чтобы восстановить исходную строку, необходимо выполнить следующие действия:
Создать пустую матрицу размером n*n, где n-количество символов в закодированном сообщении;
Заполнить самый правый пустой столбец закодированным сообщением;
Отсортировать строки таблицы в лексикографическом порядке;
Повторять шаги 2-3, пока есть пустые столбцы;
Вернуть ту строку, которая заканчивается символом конца строки.

Реализация обратного преобразования на первый взгляд не представляет сложности, и один из вариантов реализации приведён в Листинг 4.

1. const
2. EOMsg = "|" ;
3. function BWTDecode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. ShiftTable: array of ShortString;
6. N, i, j: word ;
7. begin
8. OutMsg : = "" ;
9. N : = length(InMsg) ;
10. SetLength(ShiftTable, N + 1 ) ;
11. for i : = 0 to N do
12. ShiftTable[ i] : = "" ;
13. for i : = 1 to N do
14. begin
15. for j : = 1 to N do
16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
17. Sort(ShiftTable) ;
18. end ;
19. for i : = 1 to N do
20. if ShiftTable[ i] [ N] = EOMsg then
21. OutMsg : = ShiftTable[ i] ;
22. delete(OutMsg, N, 1 ) ;
23. BWTDecode : = OutMsg;
24. end ;

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

После сортировки таблицы, полученной на седьмом шаге, необходимо выбрать из таблицы строку, заканчивающуюся символом «|». Легко заметить, что это строка единственная. Т.о. мы на конкретном примере рассмотрели преобразование BWT.

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

Словарное сжатие (алгоритмы LZ)

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

Ниже описан простейший вариант словарного алгоритма:
Инициализировать словарь всеми символами, встречающимися во входной строке;
Найти в словаре самую длинную последовательность (S), совпадающую с началом кодируемого сообщения;
Выдать код найденной последовательности и удалить её из начала кодируемого сообщения;
Если не достигнут конец сообщения, считать очередной символ и добавить Sc в словарь, перейти к шагу 2. Иначе, выход.

Например, только что инициализированный словарь для фразы «КУКУШКАКУКУШОНКУКУПИЛАКАПЮШОН» приведён в Табл. 3:

В процессе сжатия словарь будет дополняться встречающимися в сообщении последовательностями. Процесс пополнения словаря приведён в Табл. 4.

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

Для начала определим словарь как запись, хранящую не только встречавшиеся подстроки, но и количество хранящихся в словаре подстрок:

Встречавшиеся ранее подпоследовательности хранятся в массиве Words, а их кодом являются номера подпоследовательностей в этом массиве.
Также определим функции поиска в словаре и добавления в словарь:

1. const
2. MAX_DICT_LENGTH = 256 ;
3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
4. r: integer ;
5. i: integer ;
6. fl: boolean ;
7. begin
8. r : = - 1 ;
9. if D. WordCount > 0 then
10. begin
11. i : = D. WordCount ;
12. fl : = false ;
13. while (not fl) and (i >= 0 ) do
14. begin
15. i : = i - 1 ;
16. fl : = D. Words [ i] = str;
17. end ;
18. end ;
19. if fl then
20. r : = i;
21. FindInDict : = r;
22. end ;
23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
24. begin
25. if D. WordCount < MAX_DICT_LENGTH then
26. begin
27. D. WordCount : = D. WordCount + 1 ;
28. SetLength(D. Words , D. WordCount ) ;
29. D. Words [ D. WordCount - 1 ] : = str;
30. end ;
31. end ;

Используя эти функции, процесс кодирования по описанному алгоритму можно реализовать следующим образом:

1. function LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TDictionary;
5. i, N: byte ;
6. begin
7. SetLength(OutMsg, length(InMsg) ) ;
8. N : = 0 ;
9. InitDict(D) ;
10. while length(InMsg) > 0 do
11. begin
12. tmpstr : = InMsg[ 1 ] ;
13. while (FindInDict(D, tmpstr) >= 0 ) and (length(InMsg) > length(tmpstr) ) do
14. tmpstr : = tmpstr + InMsg[ length(tmpstr) + 1 ] ;
15. if FindInDict(D, tmpstr) < 0 then
16. delete(tmpstr, length(tmpstr) , 1 ) ;
17. OutMsg[ N] : = FindInDict(D, tmpstr) ;
18. N : = N + 1 ;
19. delete(InMsg, 1 , length(tmpstr) ) ;
20. if length(InMsg) > 0 then
21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
22. end ;
23. SetLength(OutMsg, N) ;
24. LZWEncode : = OutMsg;
25. end ;

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

Единственная проблема возможна в следующей ситуации: когда необходимо декодировать подпоследовательность, которой ещё нет в словаре. Легко убедиться, что это возможно только в случае, когда необходимо извлечь подстроку, которая должна быть добавлена на текущем шаге. А это значит, что подстрока удовлетворяет шаблону cSc, т.е. начинается и заканчивается одним и тем же символом. При этом cS – это подстрока, добавленная на предыдущем шаге. Рассмотренная ситуация – единственная, когда необходимо декодировать ещё не добавленную строку. Учитывая вышесказанное, можно предложить следующий вариант декодирования сжатой строки:

1. function LZWDecode(InMsg: TEncodedString) : ShortString;
2. D: TDictionary;
3. OutMsg, tmpstr: ShortString;
4. i: byte ;
5. begin
6. OutMsg : = "" ;
7. tmpstr : = "" ;
8. InitDict(D) ;
9. for i : = 0 to length(InMsg) - 1 do
10. begin
11. if InMsg[ i] >= D. WordCount then
12. tmpstr : = D. Words [ InMsg[ i - 1 ] ] + D. Words [ InMsg[ i - 1 ] ] [ 1 ]
13. else
14. tmpstr : = D. Words [ InMsg[ i] ] ;
15. OutMsg : = OutMsg + tmpstr;
16. if i > 0 then
17. AddToDict(D, D. Words [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
18. end ;
19. LZWDecode : = OutMsg;
20. end ;

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

Энтропийное кодирование

Кодирование с помощью деревьев Шеннона-Фано

Алгоритм Шеннона-Фано - один из первых разработанных алгоритмов сжатия. В основе алгоритма лежит идея представления более частых символов с помощью более коротких кодов. При этом коды, полученные с помощью алгоритма Шеннона-Фано, обладают свойством префиксности: т.е. ни один код не является началом никакого другого кода. Свойство префиксности гарантирует, что кодирование будет взаимно-однозначным. Алгоритм построения кодов Шеннона-Фано представлен ниже:
1. Разбить алфавит на две части, суммарные вероятности символов в которых максимально близки друг к другу.
2. В префиксный код первой части символов добавить 0, в префиксный код второй части символов добавить 1.
3. Для каждой части (в которой не менее двух символов) рекурсивно выполнить шаги 1-3.
Несмотря на сравнительную простоту, алгоритм Шеннона-Фано не лишён недостатков, самым существенным из которых является неоптимальность кодирования. Хоть разбиение на каждом шаге и является оптимальным, алгоритм не гарантирует оптимального результата в целом. Рассмотрим, например, следующую строку: «ААААБВГДЕЖ». Соответствующее дерево Шеннона-Фано и коды, полученные на его основе, представлены на Рис. 1:

Без использования кодирования сообщение будет занимать 40 бит (при условии, что каждый символ кодируется 4 битами), а с использованием алгоритма Шеннона-Фано 4*2+2+4+4+3+3+3=27 бит. Объём сообщения уменьшился на 32.5%, но ниже будет показано, что этот результат можно значительно улучшить.

Кодирование с помощью деревьев Хаффмана

Алгоритм кодирования Хаффмана, разработанный через несколько лет после алгоритма Шеннона-Фано, тоже обладает свойством префиксности, а, кроме того, доказанной минимальной избыточностью, именно этим обусловлено его крайне широкое распространение. Для получения кодов Хаффмана используют следующий алгоритм:
1. Все символы алфавита представляются в виде свободных узлов, при этом вес узла пропорционален частоте символа в сообщении;
2. Из множества свободных узлов выбираются два узла с минимальным весом и создаётся новый (родительский) узел с весом, равным сумме весов выбранных узлов;
3. Выбранные узлы удаляются из списка свободных, а созданный на их основе родительский узел добавляется в этот список;
4. Шаги 2-3 повторяются до тех пор, пока в списке свободных больше одного узла;
5. На основе построенного дерева каждому символу алфавита присваивается префиксный код;
6. Сообщение кодируется полученными кодами.

Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-Фано. Дерево Хаффмана и коды, полученные для сообщения «ААААБВГДЕЖ», представлены на Рис. 2:

Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано. Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес родительских узлов постоянно растёт, рано или поздно возникает переполнение. Т.о., несмотря на простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно для больших алфавитов.

Кодирование с помощью деревьев секущих функций

Кодирование с помощью секущих функций – разработанный авторами алгоритм, позволяющий получать префиксные коды. В основе алгоритма лежит идея построения дерева, каждый узел которого содержит секущую функцию. Чтобы подробнее описать алгоритм, необходимо ввести несколько определений.
Слово – упорядоченная последовательность из m бит (число m называют разрядностью слова).
Литерал секущей – пара вида разряд-значение разряда. Например, литерал (4,1) означает, что 4 бит слова должен быть равен 1. Если условие литерала выполняется, то литерал считается истинным, в противном случае - ложным.
k-разрядной секущей называют множество из k литералов. Если все литералы истинны, то и сама секущая функция истинная, в противном случае она ложная.

Дерево строится так, чтобы каждый узел делил алфавит на максимально близкие части. На Рис. 3 показан пример дерева секущих:

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

Арифметическое кодирование

Арифметическое кодирование – один из наиболее эффективных способов сжатия информации. В отличие от алгоритма Хаффмана арифметическое кодирование позволяет кодировать сообщения с энтропией меньше 1 бита на символ. Т.к. большинство алгоритмов арифметического кодирования защищены патентами, далее будут описаны только основные идеи.
Предположим, что в используемом алфавите N символов a_1,…,a_N, с частотами p_1,…,p_N, соответственно. Тогда алгоритм арифметического кодирования будет выглядеть следующим образом:
В качестве рабочего полуинтервала взять = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 > 2){ s1 = MinK(); m1 = m; s2 = MinK(); m2 = m; kk2++; k = s1 + s2; a = m1; b = m2; Free = true; kk1--; } } //описание функции формирования префиксных кодов void BuildBits(){ strcpy(bits,"1"); Free = false; strcpy(bits],bits); strcat(bits] , "0"); strcpy(bits],bits); strcat(bits] , "1"); i = MinK(); strcpy(bits[m],"0"); Free[m] = true; strcpy(bits],bits[m]); strcat(bits] , "0"); strcpy(bits],bits[m]); strcat(bits] , "1"); for (i = kk2 - 1; i > 0; i--) if (!Free[i]) { strcpy(bits],bits[i]); strcat(bits] , "0"); strcpy(bits],bits[i]); strcat(bits] , "1"); } } //описание функции вывода данных void OutputResult(char **Result){ (*Result) = new char; for (int t = 0; i < 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

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

"Сжатие данных"

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

Для человека избыточность данных часто связана с качеством информации, поскольку избыточность, как правило, улучшает понятность и восприятие информации. Однако, когда речь идет о хранении и передаче информации средствами компьютерной техники, то избыточность играет отрицательную роль, поскольку она приводит к возрастанию стоимости хранения и передачи информации. Особенно актуальной эта проблема стает в случае обработки огромных объемов информации при незначительных объемах носителей данных. В связи с этим, постоянно возникает проблема уменьшения избыточности или сжатия данных. Если методы сжатия данных применяются к готовым файлам, то часто вместо термина "сжатие данных" употребляют термин "архивация данных", сжатый вариант данных называют архивом , а программные средства, которые реализуют методы сжатия называются архиваторами .

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

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

Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым , то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть:

JPEG - для графических данных;

MPG - для для видеоданных;

MP3 - для аудиоданных.

Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым . В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:

GIF, TIFF - для графических данных;

AVI - для видеоданных;

ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

алгоритм RLE (Run Length Encoding);

алгоритмы группы KWE(KeyWord Encoding);

алгоритм Хаффмана.

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:

где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

Алгоритмы группы KWE

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

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

Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).

Алгоритм Хаффмана

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

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

Пусть задан текст, в котором бурва "А" входит 10 раз, буква "В" - 8 раз, "С"- 6 раз, "D" - 5 раз, "Е" и "F" - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.

Таблица 1.

	Частота вхождения	Битовый код

Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

На практике программные средства сжатия данных синтезируют эти три "чистых" алгоритмы, поскольку их эффективность зависит от типа и объема данных. В таблице 2 приведены распространенные форматы сжатия и соответствующие им программыи-архиваторы, использующиеся на практике.

Таблица 2.

Формат сжатия	Операционная система MS DOS		Операционная система Windows
	Программа архивации	Программа разархивации	Программа архивации	Программа разархивации

Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:

создание нового архива;

добавление файлов в существующий архив;

распаковывание файлов из архива;

создание самораспаковающихся архивов (self-extractor archive);

создание распределенных архивов фиксированного размера для носителей маленькой емкости;

защита архивов паролями от несанкционированного доступа;

просмотр содержимого файлов разных форматов без предварительного распаковывания;

поиск файлов и данных внутри архива;

проверка на вирусы в архиве к распаковыванию;

выбор и настройка коэффициента сжатия.

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

1. Какие факторы влияют на степень избыточности данных? 2. Что такое архив? Какие программные средства называются архиваторами? 3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми? 4. Приведите примеры форматов сжатия с потерями информации. 5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток? 6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия? 7. В чем состоит основная идея алгоритма RLE? 8. В чем состоит основная идея алгоритмов группы KWE? 9. В чем состоит основная идея алгоритма Хаффмана? 10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.

Информатика. Базовый курс. / Под ред. С.В.Симоновича. - СПб., 2000 г.

А.П.Микляев, Настольная книга пользователя IBM PC 3-издание М.:, "Солон-Р", 2000, 720 с.

Симонович С.В., Евсеев Г.А., Мураховский В.И. Вы купили компьютер: Полное руководство для начинающих в вопросах и ответах. - М.: АСТ-ПРЕСС КНИГА; Инфорком-Пресс, 2001.- 544 с.: ил. (1000 советов).

Ковтанюк Ю.С., Соловьян С.В. Самоучитель работы на персональном компьютере - К.:Юниор, 2001.- 560с., ил.

Из книги Компьютер на 100. Начинаем с Windows Vista автора Зозуля Юрий

Сжатие файлов NTFS При использовании разделов с файловой системой NTFS вы можете задействовать ее возможности для сжатия файлов. При этом происходит более слабое сжатие, чем при использовании архивов ZIP или RAR, но выполняется оно гораздо быстрее. Файлы, сжатые с помощью NTFS,

Из книги Sound Forge 9 автора Квинт Игорь

Сжатие звука Формат WAVE достаточно точно сохраняет данные исходного аналогового сигнала, но является очень расточительным в отношении объема, занимаемого информацией. Тем не менее этот формат предпочтителен для первоначальной записи звуковых данных, которые

Из книги Microsoft Windows SharePoint Services 3.0. Русская версия. Главы 9-16 автора Лондер Ольга

Экспорт данных из базы данных Access 2007 в список SharePoint Access 2007 позволяет экспортировать таблицу или другой объект базы данных в различных форматах, таких как внешний файл, база данных dBase или Paradox, файл Lotus 1–2–3, рабочая книга Excel 2007, файл Word 2007 RTF, текстовый файл, документ XML

Из книги Реферат, курсовая, диплом на компьютере автора Баловсяк Надежда Васильевна

Форматы графических файлов. Сжатие изображения Работая с изображениями в Photoshop, можно хранить файл в одном из нескольких графических форматов. Наиболее популярными из них являются JPEG, TIFF и PSD.JPEG – это формат, позволяющий создать минимальный по размерам файл с наименьшей

Из книги Новейший самоучитель работы на компьютере автора Белунцов Валерий

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

Из книги TCP/IP Архитектура, протоколы, реализация (включая IP версии 6 и IP Security) автора Фейт Сидни М

4.7.1 Сжатие в PPP Может показаться не очень разумным включение одних и тех же октетов адреса и управления в каждый кадр. Партнеры на каждом конце связи PPP могут работать в режиме сжатия (compression) для исключения этих полей.Значения в поле протокола указывают, является ли

Из книги Программирование на языке Ruby [Идеология языка, теория и практика применения] автора Фултон Хэл

Из книги Этюды для программистов [неполностью, главы 1–24] автора Уэзерелл Чарлз

11. Меньше copy - меньше и вздору, или Избыточность текста и сжатие файла Все знают, что большинству людей свойственно излишнее многословие. Гораздо менее широко известно, что даже самые лаконичные высказывания можно было бы значительно сократить. Вообще, естественные

Из книги Macromedia Flash Professional 8. Графика и анимация автора Дронов В. А.

Сжатие видео во Flash. Кодеки On2 VP6 и Sorenson Spark В главе 1 мы уже говорили о видео. Давайте кратко повторим все, что уже успели узнать и, возможно, уже забыли.Итак, видеоинформация, хранящаяся в файле, практически всегда сжимается. Иначе и не получится: данные, содержащие

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

Глава 11. Сжатие данных. Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных.

Из книги Компьютерная обработка звука автора Загуменнов Александр Петрович

Сжатие данных Думая о данных, обычно мы представляем себе ни что иное, как передаваемую этими данными информацию: список клиентов, мелодию на аудио компакт-диске, письмо и тому подобное. Как правило, мы не слишком задумываемся о физическом представлении данных. Заботу об

Из книги Цифровая фотография. Трюки и эффекты автора Гурский Юрий Анатольевич

Сжатие с минимальной избыточностью Теперь, когда в нашем распоряжении имеется класс потока битов, им можно воспользоваться при рассмотрении алгоритмов сжатия и восстановления данных. Мы начнем с исследования алгоритмов кодирования с минимальной избыточностью, а затем

Из книги автора

Сжатие с использованием словаря Вплоть до 1977 года, основные усилия в области исследования алгоритмов сжатия концентрировались вокруг алгоритмов кодирования с минимальной избыточностью, подобных алгоритмам Шеннона-Фано или Хаффмана, и были посвящены либо

Из книги автора

Из книги автора

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

Из книги автора

3.2. Размеры и сжатие файлов Для чего нужно сжимать изображение Картинка, полученная с помощью шестимегапиксельной камеры, должна занять 18 Мбайт памяти. Если изображение записывать в память в таком виде, то даже в запоминающее устройство большой емкости удастся уместить

Важнейшей задачей современной информатики является кодирование информации наиболее оптимальным способом.

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

Один из подходов к решению проблемы сжатия информации заключался в отказе от одинаковой длины кодовых слов: часто встречающиеся символы кодировать более короткими кодовыми словами по сравнению с реже встречающимися символами.

Принцип неравномерного кода для уменьшения информационного объема сообщения был реализован в азбуке Морзе. Однако, применение кода переменной длины создавало трудности разделения сообщения на отдельные кодовые слова. Эта проблема была решена Морзе путем применения символа-разделителя – паузы.

Префиксные коды

Теоретические исследования К. Шеннона и Р. Фано показали, что можно построить эффективный неравномерный код без использования разделителя. Для этого он должен удовлетворять условию Фано : ни одно кодовое слово не является началом другого кодового слова . Коды, удовлетворяющие условию Фано называются префиксными.

Префиксный код - это код, в котором ни одно кодовое слово не является началом другого кодового слова.

Шеннон и Фано предложили алгоритм построения эффективных сжимающих кодов переменной длины (алгоритм Шеннона – Фано). Однако, в некоторых случаях алгоритм давал неоптимальное решение.

Код Хаффмана

В 1952 году Дэвид Хаффман, ученик Фано, предложил новый алгоритм кодирования и доказал оптимальность своего способа. Улучшение степени сжатия Хаффман достиг за счет кодирования часто встречающихся символов короткими кодами, реже встречающихся – длинными.

Построим код Хаффмана для текста «ОКОЛО КОЛОКОЛА КОЛ»

1. Строим список свободных узлов, упорядоченных по убыванию частоты появления буквы.
2. Выберем две наименее вероятные буквы и построим для них узел-предок («псевдобуква») с частотой, равной сумме частот узлов-потомков.
3. Менее вероятной букве ставим в соответствие 1, более вероятной – 0 (в следующем проходе соблюдаем порядок расстановки 0 и 1).
4. Удаляем обе буквы из списка, оставив их узел-предок.
5. Повторяем шаги, начиная с пункта 2, до тех пор, пока не останется один узел («метабуква»). Этот узел будет считаться корнем дерева.

Для получения кода каждого символа движемся от корня дерева до данного символа, выписывая по ходу нули и единицы. В нашем примере символы имеют следующие коды:

• О – 00
• К – 01
• Л – 10
• Пробел – 110
• А - 111