Презентация - Методы сжатия информации в архиваторах

Методы сжатия информации в архиваторах
Дисциплина: «Операционные системы и среды» Преподаватель: Сосновская Т.Г. 2017г.
ГБПОУ КК Краснодарский колледж электронного приборостроения

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

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

рассмотрим следующий пример:
Упаковываемый файл занимает 15 байт (1символ-1байт) и состоит из следующей последовательности символов: B B B B B L L L L L A A A A A В шестнадцатиричной системе: 42 42 42 42 42 4C 4C 4C 4C 4C 41 41 41 41 41 Архиватор может представить этот файл в виде (16-тиричном): 01 05 42 06 05 4С 0А 05 41 Эти последовательности можно интерпретировать следующим образом: с первой позиции 5 раз повторяется знак В, с шестой позиции 5 раз повторяется знак L, с позиции 11 повторяется 5 раз знак А.

рассмотрим еще один вариант:

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

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

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

3 метод: Алгоритм Лемпела-Зива
Популярные архиваторы ARJ, PAK, LHARC, PKZIP работают на основе алгоритма Лемпела-Зива. Эти архиваторы классифицируются как адаптивные словарные кодировщики, в которых текстовые строки заменяются указателями на идентичные им строки, встречающиеся ранее в тексте.

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

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