4. Сжатие и архивация информации
Первые теоретические разработки в области сжатия информации относятся к концу 40-х годов.
Существует несколько способов сжатия (компрессии) данных. Все их можно разделить на две группы: сжатие без потерь и с потерями. В основе процесса сжатия данных используется свойство избыточности поступающей информации. Степень избыточности зависит от метода кодирования. Алфавит любого языка – это система кодирования. Русский язык на 20-30% избыточней английского.
Методы сжатия.
-
Методы сжатия без потерь уменьшают размер файлов не очень сильно. Обычно коэффициент сжатия не превосходит 0,2…0,3.
Одним из первых появился метод сжатия текстовой информации, предложенный в 1952 году Хафманом. В этом методе наиболее часто используемому символу присваивается наиболее короткий код, а наиболее редкому - более длинный. Таблицы кодирования создаются заранее(при первом чтении ) и имеют законченный размер для кодируемого документа. Этот алгоритм обеспечивает наибольшее быстродействие и наименьшие задержки. Для получения высоких коэффициентов сжатия этот метод требует больших объемов памяти.
Пример 1. Имеем исходное выражение: A H F B H C E H E H C E A H D C E E H H H C H H H D E G H G G E H C H H. Из анализа частоты появления каждого символа составляем словарь кодов символов:
A=0010 (2 раза) |
C=000(5 раз) |
E=011(7 раз) |
G=0101(3 раза) |
B=01001(1 раз ) |
D=0011(2 раза) |
F=01000(1 раз) |
H=1. (15 раз) |
С учетом словаря кодируем исходное выражение: 0010 1 01000 01001 1 000 011 1 011 1 000 011 0010 1 0011 000 011 011 1 1 1 000 1 1 1 0011 011 0101 1 0101 0101 011 1 000 1 1.
Получаем: длинна исходного - 36*3=108 бит, закодированного - 89 бит.
Алгоритм Хаффмана в неявном (упрощенном) виде использован в программах zip, gzip, pkzip, bzip2 и др.
Пример 2. . Алгоритм RLE (Run Length Encoding) - управления размером кодирования. Для текста (без потери информации), вместо последовательности из одинаковых элементов идущих подряд, сохранять первый элемент каждой последовательности и число его повторений. AAAABBBCDDDDDDD=A4 B3 C1 D7.
Гораздо лучших результатов сжатия можно добиться, используя этот алгоритм с потерей информации. Такой подход используется для графических и мультимедийных файлщв. В этом случае на основе специальных исследований определяется, какой информацией можно пожертвовать.
Например, для одинаковых по цветности пикселей присваивается код и порядковый номер в строке. Запись может иметь вид: 5-белых(1), 8- черных(2), 3- белых(3), 2-черных(4) и т.д. Этот метод хорошо работает, когда информация содержит большие участки с однотипной информацией. Он применяется для файлов формата BMP и используется в программах-компрессорах ARJ, RAR.
5. Вопросы к защите работы
-
Что представляет собой файл, каталог, “дерево каталогов” ?
-
Поясните понятия “текущий диск” , “текущий каталог”.
-
Какие имена присваиваются дисководам компьютера?
-
Каким устройствам компьютера присваиваются имена CON, TT, LP?
-
Из каких частей состоит имя файла ? Опишите формат имени файла.
-
Какие символы-заменители используются для создания шаблонов имен файлов ? Что означают эти символы в записях имен файлов?
-
Что такое “путь к файлу” , “атрибуты файла”?
-
Как выполнить операции копирования, просмотра, переименования, поиска, удаления файлов в режиме совмещения с DOS и режиме работы с оболочкой FAR?
-
Назвать основные типы расширений файлов, нарисовать их значки.
-
Дать характеристику методам сжатия файлов.