Реализация алгоритма анализа эффективности сжатия данных

Размещено на http://www.allbest.ru/

Реализация алгоритма анализа эффективности сжатия данных

Д.Л. Петрянин, Н.В. Горячев, И.И. Кочегаров, В.А. Трусов, Н.К. Юрков

Пензенский государственный университет, Пенза

Аннотация: в работе приводится теоретическое представление об алгоритмах сжатия информации и архиваторах, созданных на их основе. Детально описываются расчеты избыточности информации, коэффициента сжатия, количества информации, энтропии текста в выбранном пользователе файле. На основе алгоритма Хаффмана и расчетных формул разработана программа в среде разработки DELPHI «Анализ эффективности сжатия данных и архивирование», которая позволяет сжимать выбранные пользователем файлы выбранными архиваторами с выводом таблиц исходных и сжатых размеров файлов, а также проводить анализ эффективности сжатия не проводя само сжатие файлов, что позволяет сэкономить время пользователя.

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

Ключевые слова: файл, тип, сжатие, архиватор, данные, избыточность, энтропия, алгоритм, анализ, архив, Хаффман.

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

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

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

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

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

, бит. (1)

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

, бит . (2)

E называют средним количеством информации на символ или энтропией источника информации. Результатом отдельного альтернативного выбора может быть «0» или «1». Тогда всякому символу соответствует некоторая последовательность «0» и «1». Такая последовательность является кодировкой символа. Энтропия одной буквы русского языка равна примерно бит.

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

, бит. (3)

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

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

, бит. (4)

. (5)

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

, бит, (6)

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

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

, бит. (7)

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

, (8)

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

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

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

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

алгоритм сжатие файл архиватор

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

Главное окно программы представлено на рис. 2. Пользователь выбирает файлы, которые необходимо проанализировать/заархивировать. Для примера выбираем 20 случайных файлов текстового типа [10] (показаны на рис. 2).

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

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

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

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

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

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

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

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

Размещено на Allbest.ru