Инженерный вестник Дона №1, ч. 2 (2015)

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

Для выбора того или иного архиватора необходимо провести анализ типа данных, которые подлежат сжатию. Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная избыточность. Степень избыточности зависит от типа данных. Например, у видеоданных степень избыточности, как правило, в несколько раз больше, чем у графических данных, а степень избыточности графических данных в несколько раз больше, чем у текстовых. Кроме того, степень избыточности данных зависит от принятой системы кодирования. Так, например, можно сказать, что кодирование текстовой информации средствами русского языка дает в среднем избыточность на 20-30% больше, чем кодирование адекватной информации средствами английского языка [1].

Разумеется, определение избыточности информации [2-4] необходимо проводить программным способом, для этого нужно разработать алгоритм, по которому будет разрабатываться программное средство.

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

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

Количество информации, содержащееся в символе, которое определяется частотой его появления, равно:

Отсюда среднее количество информации на один произвольный символ равно:

Если при некотором кодировании символов i-ый символ имеет длину , то средняя длина слов равна:

Если предположить, что набор символов можно поделить на равновероятные подмножества, то . Следует иметь в виду, что на самом деле всегда (следствие теоремы кодирования Шеннона)[5].

Абсолютная избыточность кода определяется как разность двух величин: L и E (4), а относительная избыточность кода – по формуле (5).

, бит. (4)

. (5)

Избыточность связана с мерой неопределённости информации, т.е. информационной энтропией [6]. Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения. Энтропия рассчитывается по формуле (6):

где n – длина сообщения (текста).

На основе формул (2), (3) и (4) получаем общую формулу расчета избыточности информации (7):

, бит. (7)

Для того, чтобы определить предварительно коэффициент сжатия кода того или иного файла, т.е. не используя какой-либо архиватор, необходимо его вычислить по формуле (8):

где – количество кодируемых символов алфавита; – средняя длина кода; – количество символов алфавита, подлежащих кодированию.

Для проведения анализа была разработана программа «Анализ эффективности сжатия данных и архивирование» по алгоритму Хаффмана [5, 7] и по основным формулам (1)-(8). Данная программа позволяет сжимать выбранные пользователем файлы выбранными архиваторами с выводом таблиц исходных и сжатых размеров файлов, а также выводит результаты расчета абсолютных погрешностей коэффициентов сжатия [8, 9].

Программа работает по следующему алгоритму, который представлен на рис. 1: пользователь вводит следующие параметры (входные данные): , где – выбираемые файлы для архивации или анализа; – выбираемые архиваторы для сжатия; – допустимая погрешность расчетов, для получения требуемого результата; – режим 1 – анализ эффективности сжатия, 2 – сжатие файлов с последующими расчетами и анализами. Далее для каждого выбранного файла рассчитываются все параметры, такие как коэффициент сжатия по алгоритму Хаффмана, избыточность информации, длина текста, и др. Если был выбран 1 режим, то на экран выводятся результаты всех расчетов и анализируется, будет ли эффективным сжатие того или иного файла. Если выбран – 2, то происходит сжатие всех файлов () всеми выбранными архиваторами (). Затем рассчитываются: коэффициент сжатия как отношение сжатого размера файла к исходному; погрешности коэффициента сжатия относительно экспериментальных и расчетных данных, проверяется условие допустимой погрешности: . После этого на экран выводятся все результаты расчетов и экспериментальных данных.

Рис. 1.   Алгоритм работы программы «Анализ эффективности сжатия данных и архивирование»

Рис. 2.   Главное окно программы «Анализ эффективности сжатия данных и архивирование»

Производим сжатие (кнопка «Начать сжатие») всеми архиваторами. Результаты сжатия (кнопка «Результаты сжатия») представлены на рис. 3. В последних двух столбцах представлена выборка из всех архиваторов по файлу: минимальный размер архива и наименование архиватора соответственно.

Рис. 3.   Результаты сжатия файлов

Далее производится расчет данных по основным формулам (1)-(8) (кнопка «Анализ»). Результаты показаны на рис. 4.

Рис. 4.   Результаты расчета

Из рис. 4 видно, что абсолютная избыточность в выбранных файлах велика – более миллиона, кроме последнего (файл «20.doc») всего – 6,78. Это означает, что оригинальный метод Хаффмана здесь не эффективен (здесь его необходимо доработать в плане обработки разных типов данных (рис. 5)). Архиватор RAR показал наилучший результат сжатия (рис. 3).

Рис. 5.   Код Хаффмана для файла «20.doc»

Сжатие всех файлов, в том числе и «20.doc», является эффективным, что доказывает необходимость использования избыточности информации при сжатии информации (рис. 6).

Рис. 6.   Результаты расчета коэффициентов сжатия (для эксперимента)

На рис. 7 показаны результаты расчета абсолютных погрешностей коэффициентов сжатия.

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

Рассчитанные абсолютные погрешности крайне малы ­– меньше 0,3, это означает, что рассчитанные до сжатия избыточность и коэффициент сжатия соответствуют экспериментальным значениям.

Рис. 8.   Диаграмма коэффициентов сжатия для файла «5.txt»

На примере файла «5.txt» построена диаграмма коэффициентов сжатия по всем архиваторам (рис. 8) для визуального представления. Красной линией показано расчетное значение коэффициента сжатия (из рис. 4).

Вывод

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

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

Литература

1. 
   Петрянин Д.Л. Анализ систем защиты информации в базах данных / Петрянин Д.Л., Горячев Н.В., Юрков Н.К. // Труды международного симпозиума Надежность и качество. 2013. Т. 1. С. 115-121.
   
2. 
   Diniz P. Adaptive filtering: algorithms and practical implementation / P. Diniz – 3rd ed. – USA, New York City: Springer Publishing, 2008. – 656 p.
   
3. 
   Crochiere R.E., Rabiner L.R. Multirate digital signal processing / R.E. Crochiere, L.R. Rabiner. – USA, New Jersey, Upper Saddle River: Prentice-Hall, 1983. – 411 p.
   
4. 
   Haykin S. Adaptive filter theory / S. Haykin. – USA, New Jersey, Upper Saddle River: Prentice-Hall, 2001. – 936 p.
   
5. 
   Метод Хаффмана и родственные методы // Сайт по методам сжатия данных, изображений и видео URL: www.compression.ru/arctest/descript/huffmans.htm (дата обращения 20.12.2014).
   
6. 
   Линович А.Ю. Применение метода максимума энтропии к спектральному оцениванию в системах с многоскоростной обработкой сигналов // 15-я международная конференция «Цифровая обработка сигналов и её применение»: труды, Т.1. М.: РНТОРЭС им. А.С. Попова, 2013. С. 96 – 100.
   
7. 
   Левитин А.В. Алгоритмы: введение в разработку и анализ — М.: Вильямс, 2006. С. 392-398.
   
8. 
   Линович А.Ю. Динамический выбор порядка в многоскоростном адаптивном фильтре // «Инженерный вестник Дона», 2013, №4 URL: www.ivdon.ru/magazine/archive/n4y2013/2002 (дата обращения 20.12.2014).
   
9. 
   Линович А.Ю. Методы многоскоростной обработки сигналов в сетях распределённых датчиков сбора информации // «Инженерный вестник Дона», 2014, №2 URL: www.ivdon.ru/ru/magazine/archive/n2y2014/2370 (дата обращения 20.12.2014).
   
10. 
    Описание текстового формат TXT // Электронные книги для чтения URL: leeet.net/info_txt.php (дата обращения 20.12.2014).
    
11. 
    Внутренний формат документов MS WORD // Underground InformatioN Center – Компьютерная безопасность URL: uinc.ru/articles/39/ (дата обращения 20.12.2014).
    

1. Petrjanin D.L. Analiz sistem zashhity informacii v bazah dannyh. Petrjanin D.L., Gorjachev N.V., Jurkov N.K. Trudy mezhdunarodnogo simpoziuma Nadezhnost' i kachestvo. 2013. T. 1. S. 115-121.

2. Diniz P. Adaptive filtering: algorithms and practical implementation. P. Diniz – 3rd ed. USA, New York City: Springer Publishing, 2008. 656 p.

3. Crochiere R.E., Rabiner L.R. Multirate digital signal processing. R.E. Crochiere, L.R. Rabiner. USA, New Jersey, Upper Saddle River: Prentice-Hall, 1983. 411 p.

4. Haykin S. Adaptive filter theory. S. Haykin. USA, New Jersey, Upper Saddle River: Prentice-Hall, 2001. 936 p.

5. Metod Haffmana i rodstvennye metody. Sajt po metodam szhatija dannyh, izobrazhenij i video URL: www.compression.ru/arctest/descript/huffmans.htm (data obrashhenija 20.12.2014).

6. Linovich A.Ju. Primenenie metoda maksimuma jentropii k spektral'nomu ocenivaniju v sistemah s mnogoskorostnoj obrabotkoj signalov. 15-ja mezhdunarodnaja konferencija «Cifrovaja obrabotka signalov i ejo primenenie»: trudy, T.1. M.: RNTORJeS im. A.S. Popova, 2013. S. 96 – 100.

7. Levitin A.V. Algoritmy: vvedenie v razrabotku i analiz. M.: Vil'jams, 2006. S. 392-398.

8. Linovich A.Ju. Inzhenernyj vestnik Dona (Rus), 2013, №4 URL: www.ivdon.ru/magazine/archive/n4y2013/2002 (data obrashhenija 20.12.2014).

9. Linovich A.Ju. Inzhenernyj vestnik Dona (Rus), 2014, №2 URL: www.ivdon.ru/ru/magazine/archive/n2y2014/2370 (data obrashhenija 20.12.2014).

10. Opisanie tekstovogo format TXT. Jelektronnye knigi dlja chtenija URL: leeet.net/info_txt.php (data obrashhenija 20.12.2014).

11. Vnutrennij format dokumentov MS WORD. Underground InformatioN Center – Komp'juternaja bezopasnost' URL: uinc.ru/articles/39/ (data obrashhenija 20.12.2014).