###
  • Программы
  • Безопасность
  • Новости
  • Интересное
  • Советы 
  • Новости 
  • Обзоры 

    • Методы сжатия данных. Сжатие информации

    29.10.2023 Безопасность

    Цель урока: развивать внимательность, сообразительность, воспитывать интерес к предмету.
    Оборудование: компьютеры, лабораторные диски, соответствующее программное обеспечение, карты с тестовым заданием.

    Ход урока

    1. Организационная часть.
    2. Актуализация опорных знаний.
    3. Изучение нового материала
    4. Закрепление нового материала.
    5. Домашнее задание.
    6. Подведение итогов урока.

    Изучение нового материала

    1. Что такое архивирование. Понятие о сжатии данных.
    2. Основные виды программ-архиваторов.
    3. Программа-архиватор WIN-RAR.
    4. Как добавлять файл в архив, а также извлекать его из архива.

    С развитием информационных технологий остро встал вопрос о способах хранения данных. Начиная с 40-х годов ХХ в., Ученые разрабатывают методы представления данных, при которых пространство на носителях информации использовался бы экономнее. Результатом этого стала технология сжатия данных и архивации данных (backup).

    Архивация данных - это слияние нескольких файлов или каталогов в единый файл-архив.

    Сжатие данных - сокращение объема исходных файлов путем устранения избыточной информации.

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

    Степень сжатия зависит от типа файлов и от программы - архиватора. Более всего сжимаются текстовые файлы, менее всех – звуковые и видеофайлы.

    Архивирование файлов. Задачи

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

    3. Архивация при шифровании данных с целью уменьшения вероятности взлома криптосистемы.

    Процесс записи информации в архивный файл называется - архивирование.
    Извлечение файлов из архива - разархивирование.

    Первые программы-архиваторы появились в середине 80-х годов. Они были ориентированы на работу в MS-DOC и поддерживали популярные архивные форматы: ARC, ICE, ARJ, ZIP и RAR и др. Существовала также группа архиваторов, которые упаковывали данные в самораспаковывающиеся архивы - файлы с расширениями. eхе,. cоm. Для сжатия всего диска были созданы резидент архиваторы. Они позволяли поднять эффективность использования дискового пространства путем создания крупных архивных файлов - «сжатий» дисков.

    Значительно более удобной стала работа с архивами при появлении Windows и Windows-версий архиваторов. Из бывших архивных форматов среди пользователей Windows по-настоящему прижились ARJ, ZIP - программы которые распаковывают файлы. Большие по объему архивные файлы могут быть размещены на нескольких дискетах (томах). Такие архивы называются многотомными.

    Том - это составная часть многотомного архива.

    Сейчас используется десятки программ-архиваторов, которые отличаются перечнем функций и параметрами работы, однако лучшие из них имеют примерно одинаковые характеристики. Мы знаем, что упаковка и распаковки файлов выполняется одной и той же программе, но в некоторых случаях это осуществляется разными программами, например, программа РКZIP упаковывает файлы, а РКUNZIP - распаковку файлов.
    Программы-архиваторы позволяют создавать такие архивы, для извлечения из которых не нужны какие-либо программы, так как архивные файлы содержат в себе программу самораспаковки. Такие архивы называются SFX-архивами.

    Помещение файлов в архив: Пуск Программы WINRAR или в виде ярлыка на Рабочем столе.

    Универсальный архиватор WINRAR

    Архиватор WINRAR также предназначен для архивирования файлов. Он имеет удобную графическую оболочку и поддерживает технологию Drag and Drop. Программа WINRAR позволяет работать не только с архивными файлами rar, но и с другими архивными форматами: zip, cab, arj, lzh. Запускается WINRAR любым из возможных способов, предусмотренных в Windows. Запуск программы с помощью Главного меню кнопки Пуск Программы WINRAR WINRAR или с помощью ярлыка на Рабочем столе.

    Тестовый опрос по основам работы с дисками.
    Домашнее задание.
    Самоанализ урока.

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

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


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

    Зачем сжимать информацию?

    На сегодняшний день сжатие информации является достаточно важной процедурой, которая необходима каждому пользователю ПК. Сегодня любой пользователь может позволить себе приобрести современный накопитель данных, в котором предусмотрена возможность использования большого объема памяти. Подобные устройства, как правило, оснащаются высокоскоростными каналами для транслирования информации. Однако, стоит отметить, что с каждым годом объем необходимой пользователям информации становится все больше и больше. Всего десять лет назад объем стандартного видеофильма не превышал 700 Мегабайт. Сегодня объем фильмов в HD-качестве может достигать нескольких десятков гигабайт.

    Когда необходимо сжатие данных?

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

    1. Передача по электронной почте.

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

    2. Публикация данных на интернет-сайтах и порталах.

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

    3. Экономия свободного места на диске.

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

    Кроме перечисленных выше ситуаций, возможно еще огромное количество случаев, в которых процесс сжатия данных может оказаться очень полезным. Мы перечислили только самые распространенные.

    Способы сжатия информации

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

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

    Сжатие с потерями информации

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

    Сжатие без потери информации

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

    Универсальные методы

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

    1. Преобразование потока.

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

    2. Статистическое сжатие.

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

    3. Преобразование блока.

    В процессе сжатия вся преобразовываемая информация распределяется на несколько отдельных блоков. Происходит целостное трансформирование информации.

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

    Сжатие информации при копировании

    Одним из важнейших компонентов при осуществлении резервного копирования информации является то устройство, на котором будет перемещаться информация. Чем больший объем имеет нужная вам информация, тем более объемное устройство придется использовать. Решить проблему нехватки свободного пространства можно путем использования процесса сжатия информации.

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

    Это позволит вам сэкономить деньги, необходимые для покупки более объемного накопителя. Кроме того, подвергая нужную вам информацию дополнительному сжатию вы сокращаете время, затрачиваемое на транспортировку используемых данных на сервер. Это же относится и к копированию информации по сети. Для резервного копирования сжатие информации можно проводить в один или несколько файлов.

    Все будет зависеть только от программы, которую вы используете для сжатия информации. При выборе утилиты для сжатия, обязательно обратите внимание на то, как выбранная вами программа способна сжимать данные. Эффективность сжатия также будет зависеть от типа преобразуемой вами информации. Так, например, эффективность сжатия текстовых файлов и документов может достигать 90%. А вот при сжатии изображений удается достичь эффективности всего в несколько процентов.

    Заключение

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

    АРХИВАТОРЫ

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

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

    Степень сжатия : K c =V c /V o *100%

    K c – коэффициент сжатия, V c – объем сжатого файла, V o – исходный объем файла.

    Степень сжатия зависит от:

    1) используемой пограммы – архиватора,

    2) метода сжатия,

    3) типа исходного файла: текстового, графического, видео, звукового и т.д.

    Программы, осуществляющие упаковку и распаковку файлов называются архиваторами. Наиболее распространенными являются: ARJ, ZIP, RAR. Расширение архивных файлов совпадает с названием использованного для их создания архиватора.

    Архиваторы позволяют создавать самораспаковывающиеся архивные файлы, т.е. для их распаковки не требуется запуска программы-архиватора, т.к. они сами содержат программу распаковки. Эти архивы называются SFX-архивы
    (SelF-eXtracting). Расширение таких файлов *.EXE.


    Принципы сжатия информации

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

    Если в тексте используются не все символы алфавита ПК, то для их кодирования можно использовать в место одного байта, 8-ми бит, меньше число. Этот принцип используется в телеграфном аппарате, где используются только русские заглавные буквы, для их представления достаточно 5 бит, что позволяет записать в два байта три символа.

    3. В следующим принципе используется закономерность что в тексте буквы встречаются с разной частотой. Например в этом тексте пробел самый распространенный символ, очень часто встречаются символы «а», «и». Эти часто встречающиеся символы можно представлять короткой комбинацией битов, остальные символы возможно кодировать более длинной последовательностью. Например:

    4. Физически ПК выделяет место для размещения файлов на диске по кластерам - блоками по 4 кБ. Меньше выделить невозможно. Например если файл имеет размер 8193 байта (8 кБ и 1 байт), физически он будет занимать 16 кБ или 16384 байта. Объединение группы файлов в один позволяет сэкономить на этих остатков. При упаковки маленьких файлов это дает большую экономию.

    Итого, при отдельном размещении файлов не используются 6 кБ, что составляет 100% от содержания файлов. Во втором случае неиспользуемыми остается 2 кБ, 33%.


    Архиватор zip

    Запаковка файлов pkzip [ключи] <имя архива> [пути файлов]

    Ключи: -rp архивация с подкаталогами с сохранением структуры

    SPWD защита архива паролем (PWD)

    A добавить файлы в архив

    M переместить файлы в архив

    V просмотр содержимого архива

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

    Распаковка файлов pkunzip [ключи] <имя архива> [имена файлов]

    Ключи: -d распаковка с подкаталогами с сохранением структуры

    SPWD пароль архива (PWD)


    Архиватор arj

    arj <команда> [ключи] <имя архива> [имена файлов]

    Для архиватора arj один файл выполняет операции и распаковки и запаковки.

    Команды: a архивация

    e распаковка без сохранения структуры каталогов

    x распаковка с сохранением структуры

    l просмотр содержимого архива

    m переместить файлы в архив

    d удалить файлы из архива

    Ключи: -r упаковка с подкаталогами с сохранением структуры

    V разбивка архива на тома с объемом vol(если указан)

    размер для стандартных дискет (360, 720, 1200, 1440) указывается в килобайтах, размер нестандартных дискет указывается в байтах

    V указывается при распаковке многотомного архива

    GPWD пароль архива (PWD )

    Запаковка файлов

    Распаковка файлов

    ©2015-2019 сайт
    Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
    Дата создания страницы: 2016-08-08

    Зачем нужно сжимать информацию и какие существуют способы это сделать.

    А действительно, зачем? Посчитаем, к примеру, сколько займет памяти изображение, по качеству близкое к телевизионному. Пусть его разрешение -- 800х6009 пиксел, а число оттенков цвета около 16 тысяч (High Color), т. е. цвет каждого пиксела представляется двухбайтовым кодом. 800x600=480000 элементов. 480000x2 байт = 960000 байт -- это чуть меньше 1 мегабайта. Кажется, не так много -- на лазерном диске поместится больше 650 таких картинок. Ну, а если речь идет о фильме? Стандартная скорость кинопроекции -- 24 кадра в секунду. Значит на компакт-диске можно записать фрагмент длительностью 650:24=27 секунд. Куда это годится?! А ведь это далеко не единственный случай, когда информации "слишком много". Таким образом, одна из причин использования сжатия данных -- желание поместить больше информации в память того же объема. Есть и вторая причина. Сжатие информации ускоряет ее передачу. Но об этом -- в следующей главе.

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

    Практически все методы сжатия без потерь основаны на одной из двух довольно простых идей.

    Одна из них впервые появилась в методе сжатия текстовой информации, предложенном в 1952 году Хафманом. Вы знаете, что стандартно каждый символ текста кодируется одним байтом. Но дело в том, что одни буквы встречаются чаще, а другие реже. Например, в тексте, написанном на русском языке, в каждой тысяче символов в среднем будет 90 букв "о", 72 -- "е" и только 2 -- "ф". Больше же всего окажется пробелов: сто семьдесят четыре. Если для наиболее распространенных символов использовать более короткие коды (меньше 8 бит), а для менее распространенных -- длинные (больше 8 бит), текст в целом займет меньше памяти, чем при стандартной кодировке.

    Несколько методов сжатия основаны на учете повторяющихся байтов или последовательностей байт. Простейший из них -- RLE11 -- широко используется при сжатии изображений. В файле, сжатом таким методом, записывается, сколько раз повторяются одинаковые байты. Например, вместо "RRRRRGGGBBBBBBRRRBBRRRRRRR" будет храниться "5R3G6B3R2B7R"12. Очевидно, что такой метод лучше всего работает, когда изображение содержит большие участки с однотонной закраской.

    Другие методы основаны на том, что если некоторая последовательность байт встречается в файле многократно, ее можно записать один раз в особую таблицу, а потом просто указывать: "взять столько-то байт из такого-то места таблицы"13.

    Методы сжатия без потерь уменьшают размер файлов не очень сильно. Обычно коэффициент сжатия не превосходит 1/3-1/4. Гораздо лучших результатов можно добиться, используя сжатие с потерями. В этом случае на основе специальных исследований определяется, какой информацией можно пожертвовать.

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

    Естественно, сжатие с потерями может использоваться только программами, предназначеными для обработки конкретных видов данных (например, графическими редакторами). А вот методы сжатия без потерь применяются и для любых произвольных файлов (широко известны программы-компрессоры ARJ, ZIP, RAR, StuffIt и др).

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

    Примечания

    На самом деле, в телевизионном изображении 625 строк.

    Compressus (лат.) -- сжимание.

    Run-Length Encoding (англ.) -- кодирование длины последовательности.

    На самом деле, конечно, используются коды цветов и коды, указывающие либо сколько раз повторяется следующий байт, либо сколько следующих байтов -- неповторяющиеся.

    На этой идее основан широко использующийся для сжатия различных данных метод LZW, названный так по первым буквам фамилий его разработчиков: Lempel, Ziv и Welch.

    Joint Photographic Experts Group (англ.) -- Объединенная группа экспертов по фотографии, разработавшая одноименный метод сжатия изображений.

    Moving Picture Experts Group (англ.) -- Группа экспертов по движущимся изображениям

    GORKOFF 24 февраля 2015 в 11:41

    Методы сжатия данных

    • Алгоритмы

    Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
    1. Методы сжатия данных;
    2. Сжатие изображений без потерь;
    3. Сжатие изображений с потерями.
    Ниже вы можете ознакомиться с первым постом серии.

    На текущий момент существует большое количество алгоритмов сжатия без потерь, которые условно можно разделить на две большие группы:
    1. Поточные и словарные алгоритмы. К этой группе относятся алгоритмы семейств RLE (run-length encoding), LZ* и др. Особенностью всех алгоритмов этой группы является то, что при кодировании используется не информация о частотах символов в сообщении, а информация о последовательностях, встречавшихся ранее.
    2. Алгоритмы статистического (энтропийного) сжатия. Эта группа алгоритмов сжимает информацию, используя неравномерность частот, с которыми различные символы встречаются в сообщении. К алгоритмам этой группы относятся алгоритмы арифметического и префиксного кодирования (с использованием деревьев Шеннона-Фанно, Хаффмана, секущих).
    В отдельную группу можно выделить алгоритмы преобразования информации. Алгоритмы этой группы не производят непосредственного сжатия информации, но их применение значительно упрощает дальнейшее сжатие с использованием поточных, словарных и энтропийных алгоритмов.

    Поточные и словарные алгоритмы

    Кодирование длин серий

    Кодирование длин серий (RLE - Run-Length Encoding) - это один из самых простых и распространённых алгоритмов сжатия данных. В этом алгоритме последовательность повторяющихся символов заменяется символом и количеством его повторов.
    Например, строку «ААААА», требующую для хранения 5 байт (при условии, что на хранение одного символа отводится байт), можно заменить на «5А», состоящую из двух байт. Очевидно, что этот алгоритм тем эффективнее, чем длиннее серия повторов.

    Основным недостатком этого алгоритма является его крайне низкая эффективность на последовательностях неповторяющихся символов. Например, если рассмотреть последовательность «АБАБАБ» (6 байт), то после применения алгоритма RLE она превратится в «1А1Б1А1Б1А1Б» (12 байт). Для решения проблемы неповторяющихся символов существуют различные методы.

    Самым простым методом является следующая модификация: байт, кодирующий количество повторов, должен хранить информацию не только о количестве повторов, но и об их наличии. Если первый бит равен 1, то следующие 7 бит указывают количество повторов соответствующего символа, а если первый бит равен 0, то следующие 7 бит показывают количество символов, которые надо взять без повтора. Если закодировать «АБАБАБ» с использованием данной модификации, то получим «-6АБАБАБ» (7 байт). Очевидно, что предложенная методика позволяет значительно повысить эффективность RLE алгоритма на неповторяющихся последовательностях символов. Реализация предложенного подхода приведена в Листинг 1:

    1. type
    2. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
    3. MatchFl: boolean ;
    4. MatchCount: shortint ;
    5. EncodedString: TRLEEncodedString;
    6. N, i: byte ;
    7. begin
    8. N : = 0 ;
    9. SetLength(EncodedString, 2 * length(InMsg) ) ;
    10. while length(InMsg) >= 1 do
    11. begin
    12. MatchFl : = (length(InMsg) > 1 ) and (InMsg[ 1 ] = InMsg[ 2 ] ) ;
    13. MatchCount : = 1 ;
    14. while (MatchCount <= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
    15. MatchCount : = MatchCount + 1 ;
    16. if MatchFl then
    17. begin
    18. N : = N + 2 ;
    19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
    20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] ) ;
    21. else
    22. begin
    23. if MatchCount <> length(InMsg) then
    24. MatchCount : = MatchCount - 1 ;
    25. N : = N + 1 + MatchCount;
    26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
    27. for i : = 1 to MatchCount do
    28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
    29. end ;
    30. delete(InMsg, 1 , MatchCount) ;
    31. end ;
    32. SetLength(EncodedString, N) ;
    33. RLEEncode : = EncodedString;
    34. end ;

    Декодирование сжатого сообщения выполняется очень просто и сводится к однократному проходу по сжатому сообщению см. Листинг 2:
    1. type
    2. TRLEEncodedString = array of byte ;
    3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
    4. RepeatCount: shortint ;
    5. i, j: word ;
    6. OutMsg: ShortString;
    7. begin
    8. OutMsg : = "" ;
    9. i : = 0 ;
    10. while i < length(InMsg) do
    11. begin
    12. RepeatCount : = InMsg[ i] - 128 ;
    13. i : = i + 1 ;
    14. if RepeatCount < 0 then
    15. begin
    16. RepeatCount : = abs (RepeatCount) ;
    17. for j : = i to i + RepeatCount - 1 do
    18. OutMsg : = OutMsg + chr (InMsg[ j] ) ;
    19. i : = i + RepeatCount;
    20. else
    21. begin
    22. for j : = 1 to RepeatCount do
    23. OutMsg : = OutMsg + chr (InMsg[ i] ) ;
    24. i : = i + 1 ;
    25. end ;
    26. end ;
    27. RLEDecode : = OutMsg;
    28. end ;

    Вторым методом повышения эффективности алгоритма RLE является использование алгоритмов преобразования информации, которые непосредственно не сжимают данные, но приводят их к виду, более удобному для сжатия. В качестве примера такого алгоритма мы рассмотрим BWT-перестановку, названную по фамилиям изобретателей Burrows-Wheeler transform. Эта перестановка не изменяет сами символы, а изменяет только их порядок в строке, при этом повторяющиеся подстроки после применения перестановки собираются в плотные группы, которые гораздо лучше сжимаются с помощью алгоритма RLE. Прямое BWT преобразование сводится к последовательности следующих шагов:
    1. Добавление к исходной строке специального символа конца строки, который нигде более не встречается;
    2. Получение всех циклических перестановок исходной строки;
    3. Сортировка полученных строк в лексикографическом порядке;
    4. Возвращение последнего столбца полученной матрицы.
    Реализация данного алгоритма приведена в Листинг 3.
    1. const
    2. EOMsg = "|" ;
    3. function BWTEncode(InMsg: ShortString) : ShortString;
    4. OutMsg: ShortString;
    5. LastChar: ANSIChar;
    6. N, i: word ;
    7. begin
    8. InMsg : = InMsg + EOMsg;
    9. N : = length(InMsg) ;
    10. ShiftTable[ 1 ] : = InMsg;
    11. for i : = 2 to N do
    12. begin
    13. LastChar : = InMsg[ N] ;
    14. InMsg : = LastChar + copy(InMsg, 1 , N - 1 ) ;
    15. ShiftTable[ i] : = InMsg;
    16. end ;
    17. Sort(ShiftTable) ;
    18. OutMsg : = "" ;
    19. for i : = 1 to N do
    20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
    21. BWTEncode : = OutMsg;
    22. end ;

    Проще всего пояснить это преобразование на конкретном примере. Возьмём строку «АНАНАС» и договоримся, что символом конца строки будет символ «|». Все циклические перестановки этой строки и результат их лексикографической сортировки приведены в Табл. 1.

    Т.е. результатом прямого преобразования будет строка «|ННАААС». Легко заметить, что это строка гораздо лучше, чем исходная, сжимается алгоритмом RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв.
    Подобного эффекта можно добиться и с помощью других преобразований, но преимущество BWT-преобразования в том, что оно обратимо, правда, обратное преобразование сложнее прямого. Для того, чтобы восстановить исходную строку, необходимо выполнить следующие действия:
    Создать пустую матрицу размером n*n, где n-количество символов в закодированном сообщении;
    Заполнить самый правый пустой столбец закодированным сообщением;
    Отсортировать строки таблицы в лексикографическом порядке;
    Повторять шаги 2-3, пока есть пустые столбцы;
    Вернуть ту строку, которая заканчивается символом конца строки.

    Реализация обратного преобразования на первый взгляд не представляет сложности, и один из вариантов реализации приведён в Листинг 4.

    1. const
    2. EOMsg = "|" ;
    3. function BWTDecode(InMsg: ShortString) : ShortString;
    4. OutMsg: ShortString;
    5. ShiftTable: array of ShortString;
    6. N, i, j: word ;
    7. begin
    8. OutMsg : = "" ;
    9. N : = length(InMsg) ;
    10. SetLength(ShiftTable, N + 1 ) ;
    11. for i : = 0 to N do
    12. ShiftTable[ i] : = "" ;
    13. for i : = 1 to N do
    14. begin
    15. for j : = 1 to N do
    16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
    17. Sort(ShiftTable) ;
    18. end ;
    19. for i : = 1 to N do
    20. if ShiftTable[ i] [ N] = EOMsg then
    21. OutMsg : = ShiftTable[ i] ;
    22. delete(OutMsg, N, 1 ) ;
    23. BWTDecode : = OutMsg;
    24. end ;

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

    После сортировки таблицы, полученной на седьмом шаге, необходимо выбрать из таблицы строку, заканчивающуюся символом «|». Легко заметить, что это строка единственная. Т.о. мы на конкретном примере рассмотрели преобразование BWT.

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

    Словарное сжатие (алгоритмы LZ)

    Группа словарных алгоритмов, в отличие от алгоритмов группы RLE, кодирует не количество повторов символов, а встречавшиеся ранее последовательности символов. Во время работы рассматриваемых алгоритмов динамически создаётся таблица со списком уже встречавшихся последовательностей и соответствующих им кодов. Эту таблицу часто называют словарём, а соответствующую группу алгоритмов называют словарными.

    Ниже описан простейший вариант словарного алгоритма:
    Инициализировать словарь всеми символами, встречающимися во входной строке;
    Найти в словаре самую длинную последовательность (S), совпадающую с началом кодируемого сообщения;
    Выдать код найденной последовательности и удалить её из начала кодируемого сообщения;
    Если не достигнут конец сообщения, считать очередной символ и добавить Sc в словарь, перейти к шагу 2. Иначе, выход.

    Например, только что инициализированный словарь для фразы «КУКУШКАКУКУШОНКУКУПИЛАКАПЮШОН» приведён в Табл. 3:

    В процессе сжатия словарь будет дополняться встречающимися в сообщении последовательностями. Процесс пополнения словаря приведён в Табл. 4.

    При описании алгоритма намеренно было опущено описание ситуации, когда словарь заполняется полностью. В зависимости от варианта алгоритма возможно различное поведение: полная или частичная очистка словаря, прекращение заполнение словаря или расширение словаря с соответствующим увеличением разрядности кода. Каждый из этих подходов имеет определённые недостатки. Например, прекращение пополнения словаря может привести к ситуации, когда в словаре хранятся последовательности, встречающиеся в начале сжимаемой строки, но не встречающиеся в дальнейшем. В то же время очистка словаря может привести к удалению частых последовательностей. Большинство используемых реализаций при заполнении словаря начинают отслеживать степень сжатия, и при её снижении ниже определённого уровня происходит перестройка словаря. Далее будет рассмотрена простейшая реализация, прекращающая пополнение словаря при его заполнении.

    Для начала определим словарь как запись, хранящую не только встречавшиеся подстроки, но и количество хранящихся в словаре подстрок:

    Встречавшиеся ранее подпоследовательности хранятся в массиве Words, а их кодом являются номера подпоследовательностей в этом массиве.
    Также определим функции поиска в словаре и добавления в словарь:

    1. const
    2. MAX_DICT_LENGTH = 256 ;
    3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
    4. r: integer ;
    5. i: integer ;
    6. fl: boolean ;
    7. begin
    8. r : = - 1 ;
    9. if D. WordCount > 0 then
    10. begin
    11. i : = D. WordCount ;
    12. fl : = false ;
    13. while (not fl) and (i >= 0 ) do
    14. begin
    15. i : = i - 1 ;
    16. fl : = D. Words [ i] = str;
    17. end ;
    18. end ;
    19. if fl then
    20. r : = i;
    21. FindInDict : = r;
    22. end ;
    23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
    24. begin
    25. if D. WordCount < MAX_DICT_LENGTH then
    26. begin
    27. D. WordCount : = D. WordCount + 1 ;
    28. SetLength(D. Words , D. WordCount ) ;
    29. D. Words [ D. WordCount - 1 ] : = str;
    30. end ;
    31. end ;

    Используя эти функции, процесс кодирования по описанному алгоритму можно реализовать следующим образом:
    1. function LZWEncode(InMsg: ShortString) : TEncodedString;
    2. OutMsg: TEncodedString;
    3. tmpstr: ShortString;
    4. D: TDictionary;
    5. i, N: byte ;
    6. begin
    7. SetLength(OutMsg, length(InMsg) ) ;
    8. N : = 0 ;
    9. InitDict(D) ;
    10. while length(InMsg) > 0 do
    11. begin
    12. tmpstr : = InMsg[ 1 ] ;
    13. while (FindInDict(D, tmpstr) >= 0 ) and (length(InMsg) > length(tmpstr) ) do
    14. tmpstr : = tmpstr + InMsg[ length(tmpstr) + 1 ] ;
    15. if FindInDict(D, tmpstr) < 0 then
    16. delete(tmpstr, length(tmpstr) , 1 ) ;
    17. OutMsg[ N] : = FindInDict(D, tmpstr) ;
    18. N : = N + 1 ;
    19. delete(InMsg, 1 , length(tmpstr) ) ;
    20. if length(InMsg) > 0 then
    21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
    22. end ;
    23. SetLength(OutMsg, N) ;
    24. LZWEncode : = OutMsg;
    25. end ;

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

    Единственная проблема возможна в следующей ситуации: когда необходимо декодировать подпоследовательность, которой ещё нет в словаре. Легко убедиться, что это возможно только в случае, когда необходимо извлечь подстроку, которая должна быть добавлена на текущем шаге. А это значит, что подстрока удовлетворяет шаблону cSc, т.е. начинается и заканчивается одним и тем же символом. При этом cS – это подстрока, добавленная на предыдущем шаге. Рассмотренная ситуация – единственная, когда необходимо декодировать ещё не добавленную строку. Учитывая вышесказанное, можно предложить следующий вариант декодирования сжатой строки:

    1. function LZWDecode(InMsg: TEncodedString) : ShortString;
    2. D: TDictionary;
    3. OutMsg, tmpstr: ShortString;
    4. i: byte ;
    5. begin
    6. OutMsg : = "" ;
    7. tmpstr : = "" ;
    8. InitDict(D) ;
    9. for i : = 0 to length(InMsg) - 1 do
    10. begin
    11. if InMsg[ i] >= D. WordCount then
    12. tmpstr : = D. Words [ InMsg[ i - 1 ] ] + D. Words [ InMsg[ i - 1 ] ] [ 1 ]
    13. else
    14. tmpstr : = D. Words [ InMsg[ i] ] ;
    15. OutMsg : = OutMsg + tmpstr;
    16. if i > 0 then
    17. AddToDict(D, D. Words [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
    18. end ;
    19. LZWDecode : = OutMsg;
    20. end ;

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

    Энтропийное кодирование

    Кодирование с помощью деревьев Шеннона-Фано

    Алгоритм Шеннона-Фано - один из первых разработанных алгоритмов сжатия. В основе алгоритма лежит идея представления более частых символов с помощью более коротких кодов. При этом коды, полученные с помощью алгоритма Шеннона-Фано, обладают свойством префиксности: т.е. ни один код не является началом никакого другого кода. Свойство префиксности гарантирует, что кодирование будет взаимно-однозначным. Алгоритм построения кодов Шеннона-Фано представлен ниже:
    1. Разбить алфавит на две части, суммарные вероятности символов в которых максимально близки друг к другу.
    2. В префиксный код первой части символов добавить 0, в префиксный код второй части символов добавить 1.
    3. Для каждой части (в которой не менее двух символов) рекурсивно выполнить шаги 1-3.
    Несмотря на сравнительную простоту, алгоритм Шеннона-Фано не лишён недостатков, самым существенным из которых является неоптимальность кодирования. Хоть разбиение на каждом шаге и является оптимальным, алгоритм не гарантирует оптимального результата в целом. Рассмотрим, например, следующую строку: «ААААБВГДЕЖ». Соответствующее дерево Шеннона-Фано и коды, полученные на его основе, представлены на Рис. 1:

    Без использования кодирования сообщение будет занимать 40 бит (при условии, что каждый символ кодируется 4 битами), а с использованием алгоритма Шеннона-Фано 4*2+2+4+4+3+3+3=27 бит. Объём сообщения уменьшился на 32.5%, но ниже будет показано, что этот результат можно значительно улучшить.

    Кодирование с помощью деревьев Хаффмана

    Алгоритм кодирования Хаффмана, разработанный через несколько лет после алгоритма Шеннона-Фано, тоже обладает свойством префиксности, а, кроме того, доказанной минимальной избыточностью, именно этим обусловлено его крайне широкое распространение. Для получения кодов Хаффмана используют следующий алгоритм:
    1. Все символы алфавита представляются в виде свободных узлов, при этом вес узла пропорционален частоте символа в сообщении;
    2. Из множества свободных узлов выбираются два узла с минимальным весом и создаётся новый (родительский) узел с весом, равным сумме весов выбранных узлов;
    3. Выбранные узлы удаляются из списка свободных, а созданный на их основе родительский узел добавляется в этот список;
    4. Шаги 2-3 повторяются до тех пор, пока в списке свободных больше одного узла;
    5. На основе построенного дерева каждому символу алфавита присваивается префиксный код;
    6. Сообщение кодируется полученными кодами.

    Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-Фано. Дерево Хаффмана и коды, полученные для сообщения «ААААБВГДЕЖ», представлены на Рис. 2:

    Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано. Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
    Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес родительских узлов постоянно растёт, рано или поздно возникает переполнение. Т.о., несмотря на простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно для больших алфавитов.

    Кодирование с помощью деревьев секущих функций

    Кодирование с помощью секущих функций – разработанный авторами алгоритм, позволяющий получать префиксные коды. В основе алгоритма лежит идея построения дерева, каждый узел которого содержит секущую функцию. Чтобы подробнее описать алгоритм, необходимо ввести несколько определений.
    Слово – упорядоченная последовательность из m бит (число m называют разрядностью слова).
    Литерал секущей – пара вида разряд-значение разряда. Например, литерал (4,1) означает, что 4 бит слова должен быть равен 1. Если условие литерала выполняется, то литерал считается истинным, в противном случае - ложным.
    k-разрядной секущей называют множество из k литералов. Если все литералы истинны, то и сама секущая функция истинная, в противном случае она ложная.

    Дерево строится так, чтобы каждый узел делил алфавит на максимально близкие части. На Рис. 3 показан пример дерева секущих:

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

    Арифметическое кодирование

    Арифметическое кодирование – один из наиболее эффективных способов сжатия информации. В отличие от алгоритма Хаффмана арифметическое кодирование позволяет кодировать сообщения с энтропией меньше 1 бита на символ. Т.к. большинство алгоритмов арифметического кодирования защищены патентами, далее будут описаны только основные идеи.
    Предположим, что в используемом алфавите N символов a_1,…,a_N, с частотами p_1,…,p_N, соответственно. Тогда алгоритм арифметического кодирования будет выглядеть следующим образом:
    В качестве рабочего полуинтервала взять }