4.6. Обоснование методов и инструментов архивации данных
Поскольку в перспективе в АРМ по мере наращивания его возможностей могут использоваться различные виды данных (текст, видео, аудио), то целесообразно рассмотреть существующие методы их сжатия.
Дискретная форма представления информации является наиболее общей и универсальной. Текст, массивы чисел, оцифрованные звук и изображение можно представить в виде совокупности символов, принадлежащих к ограниченному алфавиту. Следовательно, должны существовать универсальные методы сжатия данных (цифровой информации), применимые ко всем ее разновидностям. В силу своей универсальности эти методы должны исключать потерю информации (такая потеря может быть допустима при передаче, например, мелкой детали изображения, но неприемлема, когда речь идет, скажем, о коде программы). С другой стороны, в ряде приложений общие методы сжатия наверняка не будут наиболее эффективными. Например, в силу особенностей зрительного и слухового восприятия некоторое «огрубление» изображения или звука может оказаться малозаметным, при этом выигрыш в объеме передаваемых данных оказывается значительным. В этих случаях уместно использовать специальные методы сжатия с потерями. В результате анализа существующей литературы [30] проведена классификация методов сжатия информации. В схематичном виде классификация которой приведена на рис. 4.5.
Из данного рисунка видно, что при кодировании со сжатием без потерь выделяются две разновидности методов - «Посимвольное кодирование» и «Кодирование цепочек». Идея посимвольного кодирования состоит в том, что символы разных типов встречаются неодинаково части и если кодировать их неравномерно, - так, чтобы короткие битовые последовательности соответствовали часто встречающимся символам, - то в среднем объем кода будет меньше. Такой метод, именуемый статистическим кодированием, реализован, в частности, в широко распространенном коде Хаффмана [30]. Однако посимвольное кодирование не использует такого важного резерва сжатия данных, как учет повторяемости последовательностей символов, так называемых цепочек.
Простейший вариант учета цепочек – так называемое «кодирование повторов» или реализация кода RLE. Суть его состоит в том, что последовательность одинаковых символов заменяется парой – "код символа + количество его повторов в цепочке". Следует отметить, что кодирование повторов достаточно часто используется как составной элемент более сложных алгоритмов сжатия.
Более универсальным является алгоритм, позволяющий эффективно кодировать повторяющиеся цепочки разных символов, имеющих при этом произвольную длину. Такой метод был предложен Лемпелем и Зивом. В настоящее время он находит широкое применение в различных архиваторах. Суть метода состоит в том, что цепочка символов, уже встречавшаяся в передаваемом сообщении, кодируется ссылкой на боле раннюю (при этом указываются «адрес» начала такой цепочки в «словаре» сообщения и ее длина).
Для графики используются специализированные методы сжатия с потерями информации.
Метод блочного сжатия изображений (JPEG) основан на независимом «огрублении» небольших фрагментов изображений (квадраты 8х8 пикселей). Установлено, что с ростом степени сжатия проявляется мозаичность изображения. Блочный метод JPEG (разработанный специальной группой международного комитета по стандартизации) получил сейчас повсеместное распространение. Средняя степень сжатия составляет десятки раз.
При волновом сжатии, в отличие от блочного, изображение как бы «размывается» (чем выше степень сжатия, тем более нечетки границы и детали). При передаче данных получаемое изображение постепенно «проявляется» в деталях. Это позволяет получателю самому выбирать необходимый компромисс между качеством и скоростью получения изображения, что очень удобно, например в Интернет. К тому же «размытость» не столь резко воспринимается глазом как потеря качества по сравнению с «мозаичностью». Так что при субъективно близком уровне качества волновой метод дает большую степень сжатия по сравнению с «блочным». Данный метод реализован в новом стандарте JPEG 2000.
Фрактальное сжатие основывается на том, что в изображении можно выделить фрагменты и повороты, масштабирование которых позволяет многократно использовать их при построении всей «картинки». Выделение и построение математического описания таких элементов-фракталов – трудоемкая в вычислительном отношении задача. Зато высокая степень сжатия (в сотни раз) и быстрота построения изображения по его фрактальному описанию делают метод очень удобным, когда не требуется быстрота компрессии.
После оценки методов сжатия данных был проведен сравнительный анализ существующих архиваторов с целью выбора наиболее эффективного из них для применения в АРМ. Были найдены данные по следующим архиваторам [30]:
7-Zip, автор Игорь Павлов (Pavlov);
АСЕ, автор Маркел Лемке (Weinke);
ARJ, автор Роберт Джанг (Jung);
ARJZ, автор Булат Зиганшин (Ziganshin);
CABARC, корпорация Microsoft;
Imp, фирма Technelysium Pty Ltd.;
JAR, автор Роберт Джанг (Jung);
PKZIP, фирма PKWARE Inc.;
RAR, автор Евгений Рошал (Roshal);
WinZip, фирма Nico Mak Computing;
1Zip, Info-ZIP group.
Данные архиваторы являются или одними из самых эффективных в классе, применяющих методы Зива - Лемпела, или пользуются популярностью, или оказали существенное влияние на развитие словарных алгоритмов, или интересны с точки зрения нескольких указанных критериев.
В табл. 4.4 представлены результаты сравнения ряда архиваторов по степени сжатия файлов, времени кодирования и декодирования на специальном наборе исходных данных CalgCC [30].
Коэффициент сжатия оценивался с помощью набора файлов, получившего название Calgary Compression Corpus2 (CalgCC). В состав CalgCC входят файлы различных типов данных. Набор состоит из 14 файлов, большая часть которых представляет собой тексты на английском языке или языках программирования [30].
При проведении исследований применялся тот алгоритм, который обеспечивал наилучшее сжатие. Следует отметить, что 7-Zip использует специальные методы препроцессинга нетекстовых данных, "отключить" которые не удалось, что до некоторой степени исказило картину. Тем не менее преимущество этого архиватора на данном тестовом наборе несомненно. В случае WinRAR и АСЕ режим мультимедийной компрессии намеренно не включался.
Полученные результаты показали, что скорость сжатия ARJ и PKZIP была примерно в 4,5 раза выше, чем у RAR и АСЕ, которые, в свою очередь, были быстрее CABARC и 7-Zip приблизительно на 30 %. Размер словаря в ARJ и PKZIP в десятки раз меньше, чем в остальных программах.
Для Ткод и Тдек за единицу принято время сжатия всего CalgCC архиватором 7-Zip. Следует отметить, что единица соответствует скорости кодирования 2 Гб/с для ПК с процессором типа Pentium IV 2,8 ГГц, объеме оперативной памяти 1ГГц, частоте шины 800 МГц, объеме жесткого диска 160 ГГб.
Таблица 4.4
Сравнительная характеристика архиваторов
по степени сжатия файлов, времени кодирования и декодирования специального набора
|
ARJ |
PKZIP |
ACE |
RAR |
CABARC |
7-Zip |
Bib |
3.08 |
3.16 |
3.38 |
3.39 |
3.45 |
3.62 |
Book1 |
2.41 |
2.46 |
2.78 |
2.80 |
2.91 |
2.94 |
Book2 |
2.90 |
2.95 |
3.36 |
3.39 |
3.51 |
3.59 |
Geo |
1.48 |
1.49 |
1.56 |
1.53 |
1.70 |
1.89 |
News |
2.56 |
2.61 |
3.00 |
3.00 |
3.07 |
3.16 |
Obj1 |
2.06 |
2.07 |
2.19 |
2.18 |
2.20 |
2.26 |
Obj2 |
3.01 |
3.04 |
3.39 |
3.38 |
3.54 |
3.96 |
Paper1 |
2.84 |
2.85 |
2.91 |
2.93 |
2.99 |
3.07 |
Paper2 |
2.74 |
2.77 |
2.86 |
2.88 |
2.95 |
3.01 |
Pic |
9.30 |
9.76 |
10.53 |
10.39 |
10.67 |
11.76 |
Progc |
2.93 |
2.94 |
3.00 |
3.01 |
3.04 |
3.15 |
Progl |
4.35 |
4.42 |
4.49 |
4.55 |
4.62 |
4.76 |
Progp |
4.32 |
4.37 |
4.55 |
4.57 |
4.62 |
4.73 |
Trans |
4.65 |
4.79 |
5.19 |
5.23 |
5.30 |
5.56 |
Итого |
3.47 |
3.55 |
3.80 |
3.80 |
3.90 |
4.10 |
Ткод |
2.60 |
1.68 |
2.73 |
2.55 |
3.77 |
1.0 |
Тдек |
2.5 |
1.90 |
2.80 |
2.97 |
3.98 |
1.0 |
Дальнейшая оценка возможностей архиваторов с целью выбора наиболее эффективного проводилась на выборке данных, непосредственно используемых в подсистеме управления финансовыми инвестициями малого предприятия. В состав выборки были включены файлы с числовыми данными, а также файлы, содержащие растровые изображения используемых графиков, диаграмм и гистограмм. Всего в состав выборки было включено 18 файлов. Данное количество файлов было определено экспериментальным путем. При меньших значениях числа файлов имел место достаточно большой разброс значений коэффициента сжатия, а при больших значениях числа файлов наступало так называемое насыщение, при котором разброс значений коэффициента сжатия имел незначительные приращения.
Среди исследуемых архиваторов рассматривались PKZIP, RAR и 7-Zip. В настоящее время они находят наибольшее распространение и являются представителями определенных диапазонов значений коэффициентов сжатия данных (табл. 4.5).
В табл. 4.5 приведены результаты сравнения архиваторов по степени сжатия файлов на реальном наборе данных, состоящем из 18 файлов фиксированного размера 1639139 байт. Анализ полученных данных показывает, что они незначительно отличаются от данных, приведенных в табл. 4.4 (в основном на десятые доли)т данных приведенных в литературе о отличаются, что повышает степень доверия к полученным результатам.
Лучшие характеристики продемонстрировал архиватор 7-Zip. Ему незначительно уступает RAR.
Таблица 4.5
Результаты сравнения архиваторов по степени сжатия файлов
на реальном наборе данных
|
PKZIP |
RAR |
7-Zip |
I1.txt |
2.94 |
3.15 |
3.55 |
I2.txt |
2.46 |
3.08 |
3.44 |
I3.txt |
2.22 |
2.93 |
3.18 |
I4.txt |
2.12 |
2.81 |
2.80 |
I5.txt |
2.08 |
2.66 |
3.40 |
R1.doc |
2.01 |
2.11 |
2.18 |
R2.doc |
2.00 |
2.05 |
2.16 |
R3.doc |
2.05 |
2.07 |
2.22 |
R4.doc |
2.00 |
2.01 |
2.15 |
R5.doc |
1.92 |
2.05 |
2.31 |
F1.bmp |
2.94 |
3.01 |
3.15 |
F2.bmp |
4.42 |
4.55 |
4.76 |
F3.bmp |
4.37 |
4.57 |
4.73 |
F4.bmp |
4.79 |
5.23 |
5.56 |
G1.jpeg |
4.01 |
4.25 |
4.75 |
G1.jpeg |
4.17 |
4.46 |
4.98 |
G1.jpeg |
4.23 |
4.29 |
5.17 |
G1.jpeg |
5.01 |
5.59 |
5.97 |
Итого |
3.09 |
3.38 |
3.69 |
Ткод |
1.60 |
1.12 |
2.55 |
Тдек |
1.8 |
1.25 |
2.68 |
В результате анализа временных характеристик при проведении экспериментов было установлено, что ценой увеличения степени сжатия является падение скорости в среднем в 2 и более раза.
По результатам проведенных экспериментов, для архивации данных при пересылке последних из оперативного хранилища в долговременное хранилище, был выбран алгоритм 7-Zip.