Моделирование при сжатии текстовых данных сравhеhие


Содержание

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

Читайте также:

  1. II.Численные методы решения нормальных краевых задач для уравнений параболического типа. №13
  2. V. Основные методы проектирования ИС
  3. Административно-правовые методы управления
  4. Административные методы мотивации
  5. Административные методы мотивации
  6. Адсорбционные и хемосорбционные методы очистки отходящих газов
  7. Анализ» и «синтез» как общенаучные методы познания, их роль и особенности
  8. Антивирусные методы и программные средства.
  9. Аудиторская выборка. Виды и методы выборки
  10. Бесконтактные методы оценки
  11. Биологические методы борьбы с вредителями
  12. БИОЛОГИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОБЪЕКТОВ СУДЕБНОЙ ЭКСПЕРТИЗЫ

Современные архиваторы

Специальные программы

Лекция 6

Архиваторы – это программы для создания архивов. Архивы предназначены для хранения данных в удобном компактном виде. В качестве данных обычно выступают файлы и папки. Как правило, данные предварительно подвергаются процедуре сжатия или упаковки. Поэтому почти каждый архиватор одновременно является программой для сжатия данных. С другой стороны, любая программа для сжатия данных может рассматриваться как архиватор. Эффективность сжатия является важнейшей характеристикой архиваторов. От нее зависит размер создаваемых архивов. Чем меньше архив, тем меньше места требуется для его хранения. Для передачи нужна меньшая пропускная способность канала передачи или затрачивается меньшее время. Преимущества архивов очевидны, если учесть, что данные уменьшаются в размере и в 2 раза, и в 5 раз.

Сжатие данных используется очень широко. Можно сказать, почти везде. Например, документы PDF, как правило, содержат сжатую информацию. Довольно много исполняемых файлов EXE сжаты специальными упаковщиками. Всевозможные мультимедийные файлы (GIF, JPG, MP3, MPG) являются своеобразными архивами.

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

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

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

Кодирование длин серий (RLE — сокращение от run-length encoding — кодирование длин серий)

Очень простой метод. Последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный метод. В качестве самостоятельного метода применяется, например, в графическом формате BMP.

Словарный метод (LZ — сокращение от Lempel Ziv — имена авторов)

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

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

Энтропийный метод (Huffman — кодирование Хаффмена, Arithmetic coding — арифметическое кодирование)

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

Широко используется как дополнительный метод. В качестве самостоятельного метода применяется, например, в графическом формате JPG.

Метод контекстного моделирования (CM — сокращение от context modeling — контекстное моделирование)

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

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

PPM (PPM — Prediction by Partial Matching — предсказание по частичному совпадению)

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

Предварительные преобразования или фильтрация

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

Метод сортировки блока данных (BWT — сокращение от Burrows Wheeler Transform — по имени авторов)

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

Непрерывные блоки или непрерывный режим (Solid mode — непрерывный режим)

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

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

Во всех методах сжатия при изменении типа данных собственно сам переход кодируется очень плохо. Словарь становится не актуальным, модель настроена на другие данные. В этих случаях применяется сегментирование. Это предварительная разбивка на однородные части. Затем эти части кодируются по отдельности или группами.

| следующая лекция ==>
Формат PDF | Антивирусы

Дата добавления: 2014-01-06 ; Просмотров: 1590 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Сжатие данных в примерах

Теория и стратегия представления данных

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

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

Что понимается под сжатием данных? Если говорить кратко, то сжатие устраняет из данных избыточность; в терминах же теории информации сжатие увеличивает энтропию сжатого текста. Однако оба этих утверждения по существу по существу верны в силу определения самих понятий. Избыточность может быть выражена в самых разных формах. Одним типом является последовательности повторяющихся битов ( 11111111 ). Вторым – последовательности повторяющихся байтов ( XXXXXXXX ). Однако чаще избыточность проявляется в более крупном масштабе и выражается либо закономерностями в наборе данных, взятом как единое целое, либо последовательностями различной длины, имеющими общие признаки. По существу, цель сжатия данных заключается в поиске алгоритмических преобразований представлений данных, которые позволят получить более компактные представления «типовых» наборов данных. Это описание может показаться несколько туманным, но мы постараемся раскрыть его суть на практических примерах.

Сжатие без потерь и с потерями

Фактически существуют два в корне различающихся подхода к сжатию данных: сжатие с потерями и без потерь. Эта статья, в основном, посвящена методам сжатия без потерь, но для начала полезно изучить различия. Сжатие без потерь предусматривает преобразование представления набора данных таким образом, чтобы затем можно было в точности воспроизвести первоначальный набор данных путем обратного преобразования (распаковки). Сжатие с потерями – это представление, которое позволяет воспроизводить нечто «очень похожее» на первоначальный набор данных. Преимущество использования методов сжатия с потерями заключается в том, что они зачастую позволяют получать намного более компактные представления данных по сравнению с методами сжатия без потерь. Чаще всего методы сжатия с потерями применяются для обработки изображений, звуковых файлов и видео. Сжатие с потерями в этих областях может оказаться уместным благодаря тому, что человек воспринимает битовую комбинацию цифрового изображения/звука не с «побитовой» точностью, а скорее оценивает музыку или изображение в целом.

С точки зрения «обычных» данных сжатие с потерями – неудачный вариант. Нам не нужна программа, которая делает «примерно» то, а не точно то, что было запрошено в действительности. То же касается и баз данных, которые должны хранить именно те данные, которые были в них загружены. По крайней мере, это не подойдет для решения большинства задач (и мне известно очень мало практических примеров использования сжатия с потерями за пределами тех данных, которые сами по себе описывают чувственное восприятие реального мира (например, изображений и звуков)).

Пример набора данных

В данной статье будет использоваться специально подготовленное гипотетическое представление данных. Приведем простой для понимания пример. В городе Гринфилд (штат Массачусетс, США) используются префиксы телефонных номеров 772- , 773- и 774- . (К сведению читателей за пределами США: в США местные телефонные номера являются семизначными и традиционно представляются в виде ###-####; префиксы назначаются в соответствии с географическим местоположением). Также предположим, что из всех трех префиксов чаще всего используется первый. Частями суффикса могут быть любые другие цифры с приблизительно равной вероятностью. Набор интересующих нас данных находится в «списке всех телефонных номеров, которые в настоящее время находятся в активном пользовании». Можно попробовать подобрать причину, почему это могло бы быть интересным с точки зрения программирования, но в данном случае это не важно.

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

Таблица 1. Многоколоночный отчет

Сжатие пустых мест

Сжатие пустых мест может быть охарактеризовано в более общем смысле как «удаление того, что нас не интересует». Даже несмотря на то, что этот метод с технической точки зрения представляет собой метод сжатия с потерями, он все равно полезен для многих типов представлений данных, с которыми мы сталкиваемся в реальном мире. Например, даже несмотря на то, что HTML намного удобнее читать в текстовом редакторе при добавлении отступов и междустрочных интервалов, ни одно из этих «пустых мест» никак не влияет на визуализацию HTML-документа в Web-браузере. Если вам точно известно, что конкретный документ HTML предназначается исключительно для Web-браузера (или для какого-либо робота/поискового агента), то, возможно, будет неплохо убрать все пустые места, чтобы документ передавался быстрее и занимал меньше места в хранилище. Все то, что мы удаляем при сжатии пустых мест, в действительности не несет никакой функциональной нагрузки.

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

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

Групповое кодирование

Групповое кодирование (RLE) является простейшим из широко используемых методов сжатия без потерь. Подобно сжатию пустых мест, оно не требует особых затрат, особенно для декодирования. Идея, стоящая за данным методом, заключается в том, что многие представления данных состоят большей частью из строк повторяющихся байтов. Наш образец отчета является одним из таких представлений данных. Он начинается со строки повторяющихся символов «=» и имеет разбросанные по отчету строки, состоящие только из пробелов. Вместо того чтобы представлять каждый символ с помощью его собственного байта, метод RLE предусматривает (иногда или всегда) указание количества повторений, за которым следует символ, который необходимо воспроизвести указанное число раз.

Если в обрабатываемом формате данных преобладают повторяющиеся байты, то может быть уместным и эффективным использование алгоритма, в котором один или несколько байтов указывают количество повторений, а затем следует повторяемый символ. Однако если имеются строки символов единичной длины, для их кодирования потребуются два (или более) байта. Другими словами, для одного символа ASCII «X» входного потока мог бы потребоваться выходной битовый поток 00000001 01011000 . С другой стороны, для кодирования ста следующих друг за другом символов «X» использовалось бы то же самое количество битов: 01100100 01011000 , что весьма эффективно.

В различных вариантах RLE часто применяется избирательное использование байтов для указания числа повторений, в то время как остальные байты просто представляют сами себя. Для этого должно быть зарезервировано как минимум одно однобайтовое значение, которое в случае необходимости может удаляться из выходных данных. Например, в нашем образце отчета по телефонным номерам известно, что вся информация во входном потоке состоит из простых символов ASCII. В частности, у всех таких символов первый бит ASCII-значения равен 0. Мы могли бы использовать этот первый бит ASCII для указания на то, что байт указывает число повторений, а не обычный символ. Следующие семь битов байта итератора могли бы использоваться для указания числа повторений, а в следующем байте мог бы содержаться повторяющийся символ. Так, например, мы могли бы представить строку «YXXXXXXXX» следующим образом:

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

Кодирование по методу Хаффмана

Кодирование по методу Хаффмана рассматривает таблицу символов как целый набор данных. Сжатие достигается путем нахождения «весовых коэффициентов» каждого символа в наборе данных. Некоторые символы используются чаще других, поэтому кодирование по методу Хаффмана предполагает, что частые символы должны кодироваться меньшим количеством бит, чем более редкие символы. Существуют различные варианты кодирования по методу Хаффмана, но исходный (и чаще всего применяемый) вариант включает поиск самого распространенного символа и кодирование его одним битом, например, 1. И если в закодированной последовательности встречается 0, это значит, что на этом месте находится другой символ, закодированный большим количеством бит.

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

Таблица 2. Результаты кодирования по методу Хаффмана

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

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

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

Сжатие по алгоритму Лемпеля-Зива

Вероятно, самым значимым методом сжатия без потерь является алгоритм Лемпеля-Зива. В этой статье речь пойдет о варианте LZ78, но LZ77 и другие варианты работают схожим образом. Идея, заложенная в алгоритме LZ78, заключается в кодировании потоковой последовательности байтов с использованием некоторой динамической таблицы. В начале сжатия битового потока таблица LZ заполняется фактическим набором символов, наряду с несколькими пустыми слотами. В алгоритме применяются таблицы разных размеров, но в данном примере с телефонными номерами (со сжатием пустых мест) используется таблица из 32 элементов (этого достаточно для данного примера, но может оказаться мало для других типов данных). Вначале мы заполняем первые десять слотов символами используемого алфавита (цифрами). По мере поступления новых байтов сначала выводится значение из таблицы, соответствующее самой длинной подходящей последовательности, а затем в следующий доступный слот записывается последовательность длиной N+1. В наихудшем случае мы используем 5 битов вместо 4 для отдельного символа, однако в большинстве случаев мы сможем обойтись 5 битами на несколько символов. Рассмотрим пример работы этого алгоритма (слот таблицы указан в квадратных скобках):

До сих пор мы не извлекли из этого никакой пользы, но давайте перейдем к следующему телефонному номеру:

Приведенных операций должно быть достаточно для демонстрации работы модели. Хотя никакого заметного сжатия пока не достигнуто, уже видно, что мы повторно использовали слоты 11 и 16, закодировав по два символа одним выходным символом. Кроме того, мы уже накопили крайне полезную последовательность байтов 772 в слоте 18, которая впоследствии неоднократно будет встречаться в потоке.

Алгоритм LZ78 заполняет одну таблицу символов полезными (предположительно) записями, затем записывает эту таблицу, очищает ее и начинает новую. В такой ситуации таблица из 32 символов может оказаться недостаточной, так как будет очищена прежде, чем нам удастся неоднократно воспользоваться такими последовательностями, как 772 и ей подобные. Однако с помощью небольшой таблицы проще проиллюстрировать работу алгоритма.

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

Правильная постановка задачи

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

Необходимо еще раз взглянуть на проблему, которую представляют данные. Так как это не общий набор данных и для него существуют четкие предварительные требования, то проблему можно переформулировать. Известно, что существует максимум 30000 телефонных номеров (от 7720000 до 7749999), некоторые из которых являются активными, а некоторые – нет. Перед нами не стоит задача вывести полное представление всех активных номеров. Нам просто требуется указать с помощью логического значения, активен данный номер или нет. Размышляя о проблеме подобным образом, мы можем просто выделить 30000 битов в памяти и в системе хранения и использовать каждый бит для индикации активности («да» или «нет») соответствующего телефонного номера. Порядок битов в битовом массиве может соответствовать телефонным номерам, отсортированным по возрастанию (от меньшего к большему).

Подобное решение на основе битового массива идеально со всех точек зрения. Оно требует ровно 3750 байт для представления набора данных; различные методы сжатия будут использовать меняющийся объем в зависимости от количества телефонных номеров в наборе и эффективности сжатия. Однако если 10000 из 30000 возможных телефонных номеров являются активными и если даже самому эффективному методу сжатия требуется несколько байтов на один телефонный номер, то битовый массив однозначно выигрывает. С точки зрения потребностей в ресурсах ЦП битовый массив не только превосходит любой из рассмотренных методов сжатия, но и оказывается лучше, чем обычный метод представления телефонных номеров в виде строк (без сжатия). Проход по битовому массиву и увеличение счетчика текущего телефонного номера могут эффективно выполняться даже во встроенном кэше современных процессоров.

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

Посвящается памяти Клода Шеннона (Claude Shannon).

Алгоритмы сжатия данных (стр. 2 из 6)

Энтропия набора данных, а значит и максимально возможная степень сжатия, зависит от модели. Чем адекватнее модель (чем качественнее мы можем предсказать распределение вероятности значений следующего элемента), тем ниже энтропия и тем лучше максимально достижимая степень сжатия. Таким образом, сжатие данных разбивается на две самостоятельные задачи — моделирование и кодирование.

Моделирование обеспечивает предсказание вероятности наступ­ления возможных событий, кодирование обеспечивает представление события в виде -log2 pбит, где р — предсказанная вероятность наступ­ления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия исполь­зуемый кодер при необходимости может быть легко заменен другим.

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

Алгоритм LZ77 является родоначальником целого семейства словарных схем — так называемых алгоритмов со скользящим словарем, или скользящим окном. Действительно, в LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно меняется, словарь «скользит» по входному потоку данных.

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

■ последовательности длины W=N-nуже закодированных символов, которая и является словарем;

■ упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.

Пусть к текущему моменту времени мы уже закодировали tсимволов S1 , S2 , . St . Тогда словарем будут являться Wпредшествующих символов St -( W -1) , St -( W -1)+1, …, St . Соответственно, в буфере находятся ожидающие кодирования символы St +1 , St +2 , …, St + n . Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St +1 , и всеми фразами словаря. Эти фразы могут начинаться с любого символа St -( W -1) , St -( W -1)+1, …, St выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St +1 . поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St -( i -1) , St -( i -1)+1, …, St -( i -1)+( j -1) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (matchlength), j;

Смещение и длина соответствия играют роль указателя (ссылки), одно­значно определяющего фразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s(литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax | строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции posисходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

2. В выходной файл помещается номер найденного слова в словаре positionи следующий символ из входного текста В (на котором обнаружилось различие) —

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |strB|=|str|+l байт дальше к символу, следующему за В.

В таком варианте алгоритм почти не нашел практического применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax ] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииposисходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |str| байт дальше к символу В.

Алгоритм PPM (predictionbypartialmatching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «tobeornott» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

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

Модели и алгоритмы контекстно-словарного сжатия текстовых данных Максимов Сергей Владимирович

480 руб. | 150 грн. | 7,5 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Диссертация — 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников

Автореферат — бесплатно , доставка 10 минут , круглосуточно, без выходных и праздников

Максимов Сергей Владимирович. Модели и алгоритмы контекстно-словарного сжатия текстовых данных : 05.13.11 Максимов, Сергей Владимирович Модели и алгоритмы контекстно-словарного сжатия текстовых данных (Применительно к системам электронного обучения) : Дис. . канд. техн. наук : 05.13.11 Уфа, 2006 133 с. РГБ ОД, 61:06-5/2212

Содержание к диссертации

ГЛАВА 1. Анализ методов сжатии информации 14

1.1. Предварительные замечания 14

1.2. Модели словарного сжатия 18

1.3. Модели контекстного сжатия 20

1.3.1. Модели с фиксированным контекстом 21

1.3.2. Контекстуально-смешанные модели 22

1.3.3. Вероятность ухода 22

1.3.4. Исключения 22

1.3.5. Алфавиты 24

1.4. Другие методы статистического моделирования 24

1.4.1. Динамическое сжатие Маркова 24

1.4.2. Грамматические модели 27

1.4.3. Модели новизны 28

1.4.4. Выводы по первой главе 29

ГЛАВА 2. Контекстно-словарные модели сжатия 30

2.1. Предварительные замечания 30

2.2. Сжатие текстовых файлов 34

2.3. Структурная модель представления сжатия текстовой информации 35

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

структурированного вида 36

2.5. Модель сжатия использующий контекстно-словарный метод 38

% 2.5.1. Модель хранения сжатого текста 39

2.5.2. Древовидная модель словаря 40

2.5.3. Модель словаря морфем 44

2.6. Выводы по второй главе 44

ГЛАВА 3. Алгоритмы контекстно-словарного сжатия данных на основе предложенных моделей 46

3.1. Предварительные замечания 46

3.2. Приведение информации к структурированному виду 48

3.3. Преобразование словаря 50

3.3.1. Разбиение слова на слоги 50

3.3.2. Разбиение на составные части слова 55

3.3.3. Древовидное представление структуры словаря 57

3.4. Оценка построение структуры словаря от способа разложения слов. 58

3.5. Кодирование текста с использованием полученного словаря 61

3.5.1. Построение кодов переменной длины 61

3.5.2. Применение кодирования контекстных индексов арифметического кодирования 61

3.6. Оценка эффективности полученных кодов алгоритма кодирования с

помощью словаря 63

3.6.1. Стоимость кодирования текста 63

3.6.2. Оценка объема необходимой памяти 65

3.7. Управление распределением памяти 67

3.8. Выводы по третьей главе 68

ГЛАВА 4. Программный комплекс контекстно-словарного сжатия текстовых данных msv quick reader 69

4.1. Основные требования к техническому облику программного комплекса MSV Quick Reader 69

4.2. Область применения программного комплекса 70

4.3. Проблемы существующих систем 71

4.4. Задачи разработки программного комплекса 72

4.5. Этапы разработки программного комплекса 72

4.6. Реализация блока сжатия файлов 75

4.6.1. Реализация блока Compress 78

4.6.2. Реализация блока Decompress 79

4.7. Сравнительная оценка эффективности 80

4.7.1. Тестовые данные 81

4.7.2. Методика сравнения 81

4.7.3. Результаты сравнения 82

4.8. Пример преобразования и кодирования слов 84

4.9. Выводы по четвертой главе 88

Введение к работе

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

Под хорошо структурированной понимается информация, представленная в виде информационных объектов (символьных конструкций). Эти объекты состоят из некоторой совокупности связанных определенным образом элементов, имеющих ярко выраженную структуру. Примером подобной структуры является информация фактографического типа. Например: числа, математические выражения (формулы), компьютерные программы, алгоритмы и др. Для структурированных объектов характерным является наличие четких правил получения различных структур на основе базовых элементов: цифр, символов и др. В этом случае говорят, что представляемые информационные объекты имеют «жесткую» структуру подобную структуре данных в хранилищах информации.

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

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

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

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

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

7.^ — исключает повторную упаковку встречаемого объекта; — сокращает затраты на преобразование сжимаемого объекта.

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

Ы позволяет выбрать наиболее эффективные правила ее упаковки в базу данных.

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

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

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

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

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

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

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

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

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

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

При решении поставленной задачи автор опирался на труды Д. Ватолина, А. Ратушняка, А. Смирнова, М. Смирнова, В. Юкина, И. Ножова,

9 И.В. Павлова, А.В. Кадача, Д. Мастрюков, Д.Сэломона, Д.Е.Кнута и других ученых.

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

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

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

Цель диссертационной работы

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

Для достижения цели поставлены следующие задачи:

1. Разработка контекстно-словарных моделей сжимающих текстовые данные.

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

Разработка алгоритмов контекстно-словарного сжатия текстовых данных на основе предложенных моделей.

Создание программного обеспечения, реализующего разработанные алгоритмы.

Проверка эффективности разработанного программного обеспечения на примере организации хранения и передачи учебной информации.

10^ Результаты исследований, выполненных в работе, базируются на методах математической статистики, теории информации, теории цепей Маркова, теории исследования операций, принципах морфемного и словообразовательного анализа состава. На защиту выносятся:Ш 1. Объектно-когнитивная модель контекстно-словарного сжатия.

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

Контекстно-словарные алгоритмы сжатия текстовых данных с использованием элементов статистического прогнозирования.

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

Щ Научная новизна работы заключается в следующем:

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

2. Новизна предложенных алгоритмов, реализующих сжатие текстовой информации, заключается в использовании тезаурусных моделей ее сжатия, основанных на раздельном сжатии элементов текстовой информации: слов, ссылок на них, хранящихся в словаре, самого словаря, морфем, служебных символов. ^\ 3. Новизна предложенного способа кодирования текстовой информации на основе статистических прогнозирующих моделей заключается во взаимосвязанном (контекстном) сжатии следующих классов символьных конструкций: слов, ссылок на них, хранящихся в словаре, самого словаря, морфем, служебных символов. Это позволяет более точно ^ определить условные вероятности появления символов. ^ 4. Новизна предложенного способа коррекции условных вероятностей появления символов заключается в использовании бинарного арифметического кодирования. Это позволяет обеспечить высокую степень сжатия текстовой информации в условиях возможного изменения условных вероятностей появления символов.

Ш Практическая значимость работы:

1. Разработан программный комплекс MSV Quick Reader, использующий реализованные алгоритмы сжатия. Экспериментальная проверка эффективности предложенных алгоритмов контекстно-словарного сжатия текстовых данных с помощью данного комплекса показала, что они обеспечивают увеличение степени сжатия для текстовых данных по сравнению с известными его вариантами и как следствие, снижение трафика ^Р компьютерных сетей на 5 — 7 %.

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

Программный комплекс MSV Quick Reader внедрен в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. Программное обеспечение данного комплекса имеет открытую архитектуру, что позволяет развивать данный программный комплекс с помощью добавления соответствующих модулей.

Связь темы с плановыми исследованиямим± Диссертационная работа выполнялась в рамках госбюджетного финансирования кафедре информатики Уфимского государственного авиационного технического университета и кафедре программирования и вычислительной математики Башкирского государственного педагогического университета, а также в рамках внутривузовского гранта «05.02. Информационные технологии в образовании» (БГПУ).

12 Объем и структура работы

Диссертация состоит из введения, четырех глав, заключения, библиографии и 2 приложения. Работа содержит 96 страницы машинописного текста, 46 страниц приложения и 79 наименований библиографических источников.

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

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

Во второй главе показана целесообразность использования системной формы (типа «сущность — связь») представления при сжатии текстовой данных на естественных языках. На основе использования системной формы предложены модели реализации контекстно-словарного сжатия текстовых данных.

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

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

13 Заключение содержит основные результаты и выводы по диссертационной работе.

Апробация работа и публикации

Основные положения, представленные в диссертационной работе, докладывались всероссийских и международных конференциях (VI международный симпозиум Intels»2004 (г. Саратов, 2004), V международная научная техническая конференция «Проблемы Техники и Технологий Телекоммуникаций» (г. Самара, 2004); 7-й Международная конференция по проблемам информатики и информационных технологий CSIT’2005 (г. Уфа, 2005)), обсуждались и получили положительную оценку. Достоверность основных результатов работы подтверждена корректным использованием методов поиска информации в иерархических (древовидных) моделях представления данных, теории цепей Маркова, методов математической статистики, правил словообразования в естественных языках, а также результатами проведенных экспериментов.

Основные материалы, представленные в диссертационной работе опубликованы в 7 работах.

Результаты диссертационной работы внедрены в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. ф Глава 1. Анализ методов сжатии информации

1.1. Предварительные замечания

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

2. Появление новых методов сжатия позволяет улучшить количественное качество хранения существующей информации

Существуют три основных направления исследований в данной области: повышение эффективности сжатия; убыстрение работы алгоритма; ф осуществление сжатия на основании новой системы контекстов.

В настоящее время лучшие схемы достигают сжатия в 2.3 — 2.5 битов/символ для английского текста. Показатель иногда может быть немного улучшен за счет использования больших объемов памяти, но преодолеть рубеж в 2 бита/символ еще не удавалось. Обычные люди достигали результата в 1.3 бита/символ при предсказании символов в іл английском тексте [36]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или системы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия Щ> к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуровневой связности. Однако необходимо иметь в виду, что очень большое количество слов обычного ‘Щ английского текста в обычном английском словаре может быть не найдено. ^ Данный факт касается и остальных языков. Например, Уолкер и Эмслер [73] проверили 8 миллионов слов из New York Times News Service для Webster’s Seventh New Collegiate Dictionary [58] и обнаружили, что в словаре отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них -грамматические формы слов, еще 1/4 — собственные существительные, 1/6 —

Илон Маск рекомендует:  Прочие функции

Щ слова, написанные через дефис, 1/12 — напечатаны с орфографическими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содержат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в расчете на лингвистическую информацию более высокого уровня будут, несомненно, зависеть от системной сферы. Вероятно, что

Щ поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование.

Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности ^| системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод построения моделей состояний; показанный метод DMC -лишь форма контекстно-ограниченной модели [27]. Тонкости роста этих сжимаемых данных, вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [74], этот вопрос еще не был исследован систематично.

It Другой актуальной темой для исследований являются методы выделения кодов ухода в частично соответствующих контекстуальных моделях. В итоге, преобразование систем, определяемых состояниями, таких как скрытые модели Маркова [63], может дать новые идеи моделям состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей ф Маркова [26] в последнее время был вновь открыт в области распознавания речи [57]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига [38]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний. ‘Щ Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут, несомненно, продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными системами данных, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [51], разными путями воздействует на баланс между хранением и выполнением. Будет ^ развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, тогда как Гонзалес-Смит и Сторер [43] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. Увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

Последняя область — это разработка и реализация новых систем, ki включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных программ разных областей применения, включая текст-процессор MaxWrite [79], цифровой факсимильный аппарат [49], сетевую почту и новости (например, UNIX «net-news») и архивацию файлов (например, программы ARC и PKARC для IBM PC, которые часто применяются для распределяемого ПО из электронных бюллетеней). Для Щ увеличения скорости и сокращения стоимости большинство этих систем используют удивительно простые методы сжатия. Все они представляют собой потенциальные сферы применения для более сложных методов моделирования.

17 Актуальным является объединение адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные системные проблемы, частично которые заключаются в сглаживании взрывного характера вывода алгоритмов сжатия, но в основном в согласовании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие имеет значительные преимущества для конечного движения — некоторые высокоскоростные модемы (например, Racal-Vadic’s Scotsman) и конечные эмуляторы уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования определенно будут давать преимущество в скорости реализации.

Еще одной сферой применения является шифрование и защита данных [75]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретности. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредством удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистический порядок. В-третьих, что самое важное, модель действует как очень большой ключ, без которого расшифровка невозможна. Применение адаптивной модели означает, что ключ зависит от всего текста, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, определяющий модель для дальнейшего раскодирования [52].

Сжатие текстов является настолько же нужной областью исследований, как и 40 лет назад, когда ресурсы ЭВМ были скудны. Его применение продолжает изменяться вместе с улучшением технологии, постоянно увеличивая выигрыш за счет машинного времени, скорости передачи данных, первичного и вторичного хранения.

1.2. Модели словарного сжатия

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

Выходной поток Рис. 1 Модель сжатия реляционным словарем

Такой способ сжатия файла имеет как положительные, так и отрицательные стороны.

К положительной стороне такого метода сжатия необходимо отнести:

1. Размер сжатого файла получается компактный.

2. Словарь хранится отдельно от сжатого файла и входит в комплект программного обеспечения.

3. Нет необходимости строить модель и подсчитывать статистику.

4. Декодирование выполняется быстро, так как файл содержит ссылки на место положения слова в словаре.

Необходимо также отметить и отрицательные стороны:

1. Скорость распаковки зависит от размера словаря.

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

Плохо сжимает разнородные данные, подходит для сжатия текстовых файлов.

Использование динамического словаря позволяет решить некоторые из этих проблем.

Динамический словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается добавлять и удалять эти последовательности по мере чтения из входного файла. Примером модели сжатия динамическим словарем является модель со скользящим окном. [1,2, 77, 78]

Скользящее окно rz.

Динамический словарь содержит последовательности, ранее поступившие (1 АД) (1,0,и) О Ан) (1 Да) (1 Дм) (4,1,4) (1 Де) (1 Де) (1 Дк) (5,1,й) (1,0, « » ) (5)1,л)

Рис. 2 Модель сжатия динамическим словарем

Отметим положительные стороны: нет необходимости сохранять словарь; алгоритмы универсальны; высокая скорость распаковки;

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

1.3. Модели контекстного сжатия

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

Под моделированием понимается построение модели информационного источника, породившего сжимаемые данные, а под кодированием — отображение обрабатываемых данных в сжатую форму представленную на основе построенной модели [1].

Кодирование на основании вероятности

Рис. 3 Модель контекстного сжатия

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

1.3.1. Модели с фиксированным контекстом

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

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

22 контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [33], а использована для сжатия в [68, 69].

1.3.2. Контекстуально-смешанные модели

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

1.3.3. Вероятность ухода

Этот подход, который сначала может показаться совсем не похожим на перемешивание, выделяет каждой модели некоторое кодовое пространство, учитывая при этом возможность доступа к моделям низшего порядка для предсказания следующего символа [34, 67]. Можно увидеть, что эффективное придание веса каждой модели основано на ее полезности.

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

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

23 устраняет указанные проблемы посредством преобразования вероятности символа в более простые оценки.

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

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [62]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков. Значит, выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть

24 исключены. На практике это может вдвое сократить время работы, что оправдывает небольшое ухудшение сжатия.

Принцип контекстно-ограниченного моделирования, может быть, применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования, несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [59]. В этом случае необходимы только маленькие контексты — обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [61] и [52] даются эффективные алгоритмы на эту тему.

1.4. Другие методы статистического моделирования 1.4.1. Динамическое сжатие Маркова

Единственный метод, из приводимых в литературе, работающий достаточно быстро, чтобы его можно было применять на практике, метод моделирования с конечным числом состояний, называется динамическим сжатием Маркова (ДМС) [36, 46]. ДМС адаптивно работает, начиная с простой начальной модели, и добавляет по мере необходимости новые состояния. К сожалению, оказывается, что выбор эвристики и начальной модели обеспечивает создаваемой модели контекстно-ограниченный характер [30], из-за чего возможности модели с конечным числом состояний


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

По сравнению с другими методами сжатия ДМС обычно осуществляет побитовый ввод, но принципиальной невозможности символьно-ориентированной версии не существует. Однако на практике такие модели зачастую требуют много оперативной памяти, особенно если используется простая статистическая данная. Модели с побитовым вводом не имеют проблем с поиском следующего состояния, поскольку в зависимости от значения следующего бита существуют только два перехода из одного состояния в другое. Еще важно, что работающая с битами модель на каждом шаге осуществляет оценку в форме двух вероятностей р(0) и р(1) (в сумме дающих 1). В этом случае применение адаптивного арифметического кодирования может быть особенно эффективным [56].

Основная идея ДМС состоит в поддержании счетчиков частот для каждого перехода в текущей модели с конечным числом состояний, и «клонировании» состояния, когда соответствующий переход становится достаточно популярным. Рисунок 4 демонстрирует операцию клонирования, где показан фрагмент модели с конечным числом состояний, в которой состояние / — целевое. Из него осуществляется два перехода (для символов О и 1), ведущие к состояниям, помеченным как X и Y. Здесь может быть несколько переходов к t, из которых на показано рисунке 4: из U, V и W, каждый из которых может быть помечен 0 или 1 (хотя они и не показаны). 3-| „г>И дГ

Рис. 4 Операция клонирования в DMC. ^i Предположим, что переход из U имеет большее значение счетчика частот. Из-за высокой частоты перехода U—*t, состояние / клонирует добавочное состояние t’. Переход U—*t изменен на U—*t\ при этом другие переходы в f не затрагиваются этой операцией. Выходные переходы t передаются и Ґ, следовательно, новое состояние будет хранить более

0 і присущие для этого шага модели вероятности. Счетчики выходных переходов старого t делятся между t и Ґ в соответствии с входными переходами из U и V/W.

Для нахождении готовности перехода к клонированию используются два фактора. Опыт показывает, что клонирование происходит очень медленно. Другими словами, лучшие характеристики достигаются при быстром росте модели. Обычно t клонируется для перехода U—*t, когда этот переход уже однажды имел место и из других состояний также имеются переходы в t. Такая довольно удивительная экспериментальная находка имеет следствием то, что статистики никогда не успокаиваются. Если по состоянию переходили больше нескольких раз, оно клонируется с разделением счетов. Можно сказать, что лучше иметь ненадежные статистики, основанные на длинном, специфичном контексте, чем надежные и основанные на коротком ь. и менее специфичном.

Для старта ДМС нужна начальная модель. Причем простая, поскольку процесс клонирования будет изменять ее в соответствии со спецификой встреченной последовательности. Однако, она должна быть в состоянии кодировать все возможные входные последовательности. Простейшим случаем является модель с 1 состоянием, показанная на рисунке 5, которая W, является вполне удовлетворительной. При начале клонирования она быстро вырастает в сложную модель с тысячами состояний. Немного лучшее сжатие может быть достигнуто для 8-битового ввода при использовании начальной модели, представляющей 8-битовые последовательности в виде цепи, как показано на рисунке 6, или даже в виде двоичного дерева из 255 узлов.

Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспосабливается к требованиям кодируемого текста.

Рис. 5. Начальная модель ДМС с одним состоянием -> х1—- ХІ—> х1—> xl—^ xl—> xl—^ xL— xl— pf Х|—у Xj—^ Х|—у Xi—^ Хі—У Xi—У X,—)> Х|— 1_1 о LJ о I—I п I—JQl_lnl—IqI—I q L_l n

Рис. 6. Более сложная начальная модель

1.4.2. Грамматические модели

Даже более искусные модели с конечным числом состояний не способны отразить некоторые моменты должным образом. В особенности ими не могут быть охвачены рекуррентные структуры — для этого нужна модель, основанная на грамматике. Рисунок 7 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка разбирается message seeing string substring substring = string «.» < 1 >= substring string < 0.6 ) = empty-string < 0.4 ) = "a" < 0.5 >— «(» string «)» і 0.5 > string ( ( parse

I— 5: П.5 —’ « S: 0.5 -J

1: 1.0 probabilities 0.5 0.5 0.5 0.5 0.4 0.6 0.6 0.5 1.0 combined probability = 0.0045 [ 7.80 bits )

Рис. 7. Вероятностная грамматика для круглых скобок.

28 согласно грамматике, то терминалы кодируются согласно своим вероятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [31,53]. Вероятностные грамматики изучались также Озеки [63, 64, 65]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их грамматики. Конструирование ее вручную будет утомительным и ненадежным, поэтому в идеале грамматика должна выводиться механически из образца текста. Но это невозможно, поскольку построение грамматики для выяснения ограничений изучаемого языка требует анализа не принадлежащих ему примеров [24, 43].

1.4.3. Модели новизны

Они работают по принципу, что появление символа во входном потоке делает более вероятным его новое появление в ближайшем будущем. Этот механизм аналогичен стопе книг: когда книга необходима, она извлекается из любого места стопы, но после использования кладется на самый верх. Наиболее популярные книги будут ближе к вершине, что позволяет их быстрее находить. Многие авторы разрабатывали варианты этого алгоритма [31, 38, 47, 52, 70]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые используются как символы.

Символ кодируется своей позицией в обновляемом списке (стопке книг). Применяются коды переменной длины, наподобие предложенного Элиасом [39], в котором слова, расположенные ближе к вершине имеют более короткий код (такой метод подробно рассматривается в [59]). Существует несколько способов организации списка. Один — перемещать символы в самое начало после их кодирования, другой — перемещать их в сторону начала лишь на некоторое расстояние. Джонс в [52] применяет символьно-ориентированную модель, где код каждого символа определяется его глубиной в расширяемом дереве. После очередного своего кодирования символы при помощи расширения перемещаются вверх по дереву.

29 Практическая реализация и характеристика некоторых моделей новизны приводится в [60].

1.4.4. Выводы по первой главе

Существуют три направления исследований в данной области: повышение эффективности сжатия; убыстрение работы алгоритма; осуществление сжатия на основании новой системы контекстов.

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

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

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

Работа по исследованию по этим трем направлениям позволит получить наиболее лучшие результаты

Модели с фиксированным контекстом

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

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

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

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [62]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков. Значит, выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть m исключены. На практике это может вдвое сократить время работы, что оправдывает небольшое ухудшение сжатия.

Принцип контекстно-ограниченного моделирования, может быть, применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования, несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [59]. В этом случае необходимы только маленькие контексты — обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [61] и [52] даются эффективные алгоритмы на эту тему.

Структурная модель представления сжатия текстовой информации

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

Учитывая, что сжатие предусматривает замену часто используемых символов короткими кодами, объем информации можно уменьшить до 30-50%. » Как известно текст на естественных языках является слабоструктурированной информацией. Исследования сжатия текстов показало, что обычными приемами сжатия высокую степень сжатия для текстовых файлов невозможно получить по следующим причинам:

Редко встречаются повторяющиеся последовательности вида «аааааааааа». Необходимо рассматривать не только отдельный символ, но группу символов образующие слова. Для текстов на естественных языках длина повторяющихся последовательностей обычно не превышает 20 символов.

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

Пусть A= — некоторый алфавит. Имеется последовательность символов х єАк: О lN-\

Пусть существует некоторый поток текстовых данных Г. Под текстовыми данными Т понимаем последовательность символов х разделенных знаками препинаниями, которые определили в начальном этапе в группе G. Элементы группы G данной последовательности разделят текстовый поток на подгруппу GS, состоящую из строк xt , концевыми элементами являются элементы группы G.

Приведение информации к структурированному виду

Приводя файл к структурированному виду, создаем словарь слов и список ссылок на индексы в словаре, точно повторяющий преобразованный текст, что позволяет исключать из словаря повторяющиеся слова, а в тексте будет храниться только ссылка на это слово. Обычно для сохранения индекса ссылок используют код фиксированной длины. Но если объем словаря будет слишком большой, то такой способ хранения не подходит. Поэтому лучше всего воспользоваться кодами ссылок переменной длины. Часто встречаемому слову присваиваем короткий код индекса, а редко встречающимся словам длинный код, если код оказывается длиннее, чем слово, то в этом случае сохраняем слово, а не индекс. Индексом служит место нахождение слова в словаре. Полученный словарь используем для кодирования заданного текста, заменяя слова, встречающиеся в тексте, их индексами. Так как словарь является упорядоченной последовательностью, существует возможность дальнейшего уменьшения его размера. Преобразование словаря, может, проведено двумя способами, используем особенности словообразования: Текст на естественных языках Слова Слоги Корни, приставки, суффиксы, окончания Буквы, символы, знаки Рис. 13 Модель представления текста в естественных языках. Приведение структурированному виду текстового файла проводится в 2 этапа: 1) выявление структуры и построение модели; 2) построение и проведение кодирования на основе выявленных структур. В блоке выявление структур и построение моделей производится первичная обработка.

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

Можно заметить, что существует возможность уменьшения объема словаря, при его создании: 1. Разбиение слова на слоги 2. Разбиение на составные части слова (морфемы) 3. Представление словаря древовидной форме на основе приведенных ранее разбиений. Выбранный нами метод обусловлен тем, что язык обладает рядом особенностей.

Известно, что слова делятся на слоги. Слог — это один гласный звук или несколько звуков в слове, которые произносятся одним толчком воздуха: я -ма, до — ро — га, шос — се. Слова делятся по правилу: в слове столько слогов, сколько в нем гласных букв. На основе этого, слова в словаре делятся на слоги, и создается словарь слогов. Затем кодируется словарь, заменяя слог в слове на полученный индекс.

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

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

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

Например: слово «информация» закодируется, применяя нами предлагаемый метод, как «1234» (длина слова 10 символов, закодированного 4 символа), слово «информатика» — «12378»(5 символов к 11), слово «политика» — «5678»(4 символа к 8), слово «полиформа» — «5623»(4 символа к 9) и т.д. Для кодирования 38 символов нами было потрачено всего 17 символов.

Область применения программного комплекса

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

Предлагаемый нами программный продукт один из этого класса программный средств, который позволит решить назревшую проблему и облегчить работу за компьютером.

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

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

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

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

Достаточно большое количество ссылок на bookreader имеется на сайтах http://www.mi.ru/ zserge/bv_simil.html и http://read.textory.ru. Для , большей объективности была также предпринята попытка найти и зарубежные аналоги. Удалось найти несколько таких программ, однако часть оказалась выполнена с интерфейсом лишь в виде раскрытой книги, а остальные были не слишком удачными, да и с чтением русских текстов в кодировках отличных от кодировки Windows проблемы были у всех.

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

Алгоритм сжатия текстовых файлов

Рубрика: Технические науки

Дата публикации: 05.11.2020 2020-11-05

Статья просмотрена: 215 раз

Библиографическое описание:

Череданова Е. М., Мамченко Е. А. Алгоритм сжатия текстовых файлов // Молодой ученый. — 2020. — №44. — С. 24-26. — URL https://moluch.ru/archive/178/46279/ (дата обращения: 12.11.2020).

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

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

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

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

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

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

Предложенная методика Шеннона — Фано логически не замкнута, т. е. не всегда приводит к однозначному построению кода. Действительно, при разбиении на подгруппы, когда разбить на точно равные по вероятности подгруппы невозможно, имеется неопределенность, какую подгруппу сделать большей по вероятности, а какую меньшей. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием а > 2 неопределенность становится еще больше.

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

Задача построения оптимального неравномерного кода (ОНК) основания a для некоррелированных алфавитов исходной дискретной последовательности (сообщения) m, состоящий из m символов, формулируется следующим образом:

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

где Аср — средняя длина кодовой комбинации, — вероятность i-го символа алфавита, — число кодовых знаков кодовой комбинации i -го символа алфавита, минимально возможна.

Для того, что бы предложенный ОНК удовлетворял соотношению (1) необходимо выполнение условий:

  1. Если выписать символы в порядке убывания вероятности:

где i>j, то длительность соответствующих кодовых комбинаций должна удовлетворять соотношению:

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

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

Задача построения оптимального неравномерного кода основания a для некоррелированных алфавитов m с учетом положения символа на различных позициях в слове формулируется следующим образом:

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

где Аср — средняя длина кодовой комбинации, — вероятность i-го символа алфавита находящегося на k-й позиции в слове, — число кодовых знаков кодовой комбинации i -го символа алфавита на k-ой позиции в слове, n- максимальная длина слова.

Что бы предложенный ОНК, удовлетворял соотношению (5) необходимо выполнение условий:

  1. Для каждой позиции символов в слове k є [1…n] если выписать символы в порядке убывания вероятностей:

где i> j, то длительность соответствующих кодовых комбинаций должна удовлетворять соотношению:

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

Оценка эффективности

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

Возьмем для алфавита текстовых сообщений на русском языке m = 53 (32 буквы, 10 цифр, 11 служебных знаков). Тогда для равномерного распределения частот символов алфавита печатного текста, построенное по данным [2] получим:

– для соответствующего этому распределению частот первого приближения к энтропии:

– информационная емкость сообщения:

– максимально достижимый выигрыш при кодировании

Для предложенной методики эффективного кодирования с учетом распределения вероятностей символов на различных позициях в словах:

= 4,02 дв. ед./симв. и

Заключение

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

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

1. Новик Д. А. Эффективное кодирование. М.-Л. “Энергия”,1965 г., 236

2. Котов А. П. и др., Основы телеграфии, ВКАС, л.,1958

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

Данный материал представлен в виде лекции. Дано определение, назначение сжатия информации, а так же виды и алгоритмы. Приведены примеры.

Содержимое разработки

Лекция №4. Сжатие информации

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

Цель сжатия данных — обеспечить компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного — запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

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

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

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

Методы сжатия этого класса не могут допустить утрату информа­ции, поэтому они основаны только на устранении ее избыточности, а информация имеет избыточность почти всегда (правда, если до этого кто-то ее уже не уплотнил). Если бы избыточности не было, нечего было бы и сжимать.

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» (• • — -) и «Ц» (- • — •), кодиру­ются четырьмя знаками. Неэффективная кодировка — второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

Наличие повторяющихся фрагментов — третье основание для избыточности. В текстах это встречается редко, но в таблицах и в графике повторение кодов — обычное явление. Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20. Такие алгоритмы, основанные на выявлении повторов, называют методами RLE (Run Length Encoding).

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

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

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

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

В то же время, существуют материалы, в которых стоит пожерт­вовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотографические иллюстрации, видеоматериалы и музыкальные композиции. Потеря информации при сжатии и последующей распаковке в таких материалах воспринимается как появление некоторого дополнительного «шума». Но поскольку при создании этих мате­риалов определенный «шум» все равно присутствует, его неболь­шое увеличение не всегда выглядит критичным, а выигрыш в раз­мерах файлов дает огромный (в 10-15 раз на музыке, в 20-30 раз на фото- и видеоматериалах).

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG исполь­зуется при сжатии фотоизображений. Графические файлы, сжа­тые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются .MPG для видео и .МРЗ для музыки.

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

Алгоритмы сжатия без потери информации

Для дальнейших рассуждений будет удобно представить наш исходный файл с текстом как источник символов, которые по одному появляются на его выходе. Мы не знаем заранее, какой символ будет следующим, но мы знаем, что с вероятностью p1 появится буква «а», с вероятностью p2 -буква «б» и т.д.

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

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

0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов — двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой — цифрой 1.

Снова разобьем первую группу (А-В) на две подгруппы таким образом, чтобы их суммарные вероятности были как можно ближе друг к другу. Добавим к коду первой подгруппы цифру 0, а к коду второй — цифру 1.

Будем повторять эту операцию до тех пор, пока на каждой вершине нашего «дерева» не останется по одному символу. Полное дерево для нашего алфавита будет иметь 31 узел.

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

Итак, принцип очевиден — часто встречающиеся символы кодируются меньшим числом бит, редко встречающиеся — большим. В результате среднестатистическое количество бит на символ будет равно

где ni — количество бит, кодирующих i-й символ, pi — вероятность появления i-го символа.

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

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо — 1, налево — 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

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

Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.

Еще один недостаток кодов — это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

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

Групповое кодирование — Run Length Encoding (RLE) — один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары «счетчик, значение». («красный, красный, . красный» записывается как «N красных»).

Одна из реализаций алгоритма такова: ищут наименнее часто встречающийся байт, называют его префиксом и делают замены цепочек одинаковых символов на тройки «префикс, счетчик, значение». Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару «префикс, 1» или «префикс, 2». Остается одна неиспользованная пара «префикс, 0», которую можно использовать как признак конца упакованных данных.

Илон Маск рекомендует:  Result - Переменная Delphi

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt. которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат — GIF — более примитивен — он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF — файла находится палитра — таблица, устанавливающая соответствие между индексом цвета — числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

Алгоритмы сжатия с потерей информации

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия — например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

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

Фрактальное сжатие изображений — это алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (IFS, как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры — до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил.

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

Строго говоря, IFS — это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость).

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

Идея заключается в следующем: предположим, что исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда можно вместо самого изображения запомнить каким-либо образом это отображение, а для восстановления достаточно многократно применить это отображение к любому стартовому изображению.

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

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

Наиболее известны два изображения, полученных с помощью IFS: треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе — пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

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

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

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

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравним его с фрактальной компрессией.

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

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

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

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

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

Моделирование при сжатии текстовых данных сравhеhие

Разработано большое количество разнообразных методов, их модификаций и подвидов для сжатия данных. Современные архиваторы, как правило, одновременно используют несколько методов сжатия[7]. Можно выделить некоторые основные.

Кодирование длин серий (RLE- сокращение от run- length encoding- кодирование длин серий). Последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный метод. Программные реализации алгоритмов RLE отличаются простотой, высокой скоростью работы, но в среднем обеспечивают недостаточное сжатие[16].

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

Словарный метод (LZ- сокращение от Lempel Ziv -имена авторов). Наиболее распространенный метод. Используется словарь, состоящий из последовательностей данных или слов. При сжатии эти слова заменяются на их коды из словаря. В наиболее распространенном варианте реализации в качестве словаря выступает сам исходный блок данных. Основным параметром словарного метода является размер словаря. Чем больше словарь, тем больше эффективность. Однако для неоднородных данных чрезмерно большой размер может быть вреден, так как при резком изменении типа данных словарь будет заполнен неактуальными словами. Для эффективности работы данного метода при сжатии требуется дополнительная память. Приблизительно на порядок больше, чем нужно для исходных данных словаря. Существенным преимуществом словарного метода является простая и быстрая процедура распаковки. Дополнительная память при этом не требуется. Такая особенность особенно важна, если необходим оперативный доступ к данным[16].

Энтропийный метод (Huffman- кодирование Хаффмана, Arithmetic coding- арифметическое кодирование). В основе этого метода лежит кодирование не байтами, а битовыми группами:

· Перед началом кодирования производится частотный анализ кода документа и выявляется частота повтора каждого из встречающихся символов;

· Чем чаще встречается тот или иной символ, тем меньшим количеством битов он кодируется (соответственно, чем реже встречается символ, тем длиннее его кодовая битовая последовательность);

· Образующая в результате кодирования иерархическая структура прикладывается к сжатому документу в качестве таблицы соответствия.

В связи с тем, что к сжатому архиву необходимо прикладывать таблицу соответствия, на файлах малых размеров алгоритм Хаффмана малоэффективен. Практика также показывает, что его эффективность зависит и от заданной предельной длины кода (размера словаря). В среднем, наиболее эффективными оказываются архивы с размером словаря от 512 до 1024 единиц (длина кода до 18-20 бит). Широко используется как дополнительный метод. В качестве самостоятельного метода применяется, например, в графическом формате JPG.

Метод контекстного моделирования (CM- сокращение от context modeling- контекстное моделирование). В этом методе строится модель исходных данных. При сжатии очередного элемента данных эта модель выдает свое предсказание или вероятность. Согласно этой вероятности, элемент данных кодируется энтропийным методом. Чем точнее модель будет соответствовать исходным данным, тем точнее она будет выдавать предсказания, и тем короче будут кодироваться элементы данных. Для построения эффективной модели требуется много памяти. При распаковке приходится строить точно такую же модель. Поэтому скорость и требования к объему оперативной памяти для упаковки и распаковки почти одинаковы. В данный момент методы контекстного моделирования позволяют получить наилучшую степень сжатия, но отличаются чрезвычайно низкой скоростью.

PPM (PPM- Prediction by Partial Matching- предсказание по частичному совпадению). Это особый подвид контекстного моделирования. Предсказания выполняется на основании определенного количества предыдущих элементов данных. Основным параметром является порядок модели, который задает это количество элементов. Чем больше порядок модели, тем выше степень сжатия, но требуется больше оперативной памяти для хранения данных модели. Если оперативной памяти недостаточно, то такая модель с большим порядком показывает низкие результаты. Метод PPM особенно эффективен для сжатия тестовых данных.

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

Метод сортировки блока данных (BWT- сокращение от Burrows Wheeler Transform- по имени авторов). Это особый вид или группа преобразований, в основе которых лежит сортировка. Такому преобразованию можно подвергать почти любые данные. Сортировка производится над блоками, поэтому данные предварительно разбиваются на части. Основным параметром являются размер блока, который подвергается сортировке. Для распаковки данных необходимо проделать почти те же действия, что и при упаковке. Поэтому скорость и требования к оперативной памяти почти одинаковы. Архиваторы, которые используют данный метод, обычно показывают высокую скорость и степень сжатия для текстовых данных.

Непрерывные блоки или непрерывный режим (Solid mode- непрерывный режим). Во многих методах сжатия начальный участок данных или файла кодируется плохо. Например, в словарном методе словарь пуст. В методе контекстного моделирования модель не построена. Когда количество файлов большое, а их размер маленький, общая степень значительно ухудшается за счет этих начальных участков. Чтобы этого не происходило при переходе на следующий файл, используется информация, полученная исходя из предыдущих файлов. Аналогичного эффекта можно добиться простым представлением исходных файлов в виде одного непрерывного файла. Этот метод используется во многих архиваторах и имеет существенный недостаток. Для распаковки произвольного файла необходимо распаковать и файлы, которые оказались в начале архива. Это необходимо для правильного заполнения словаря и построения модели. Существует и промежуточный вариант, когда используются непрерывные блоки фиксированного размера. Потери сжатия получаются минимальными, но для извлечения одного файла, который находится в конце большого архива, необходимо распаковать только один непрерывный блок, а не весь архив[5].

Сегментирование. Во всех методах сжатия при изменении типа данных собственно сам переход кодируется очень плохо. Словарь становится не актуальным, модель настроена на другие данные. В этих случаях применяется сегментирование. Это предварительная разбивка на однородные части. Затем эти части кодируются по отдельности или группами.

Программные средства сжатия данных.«Классическими» форматами сжатия данных, широко используемыми в повседневной работе с компьютером, являются форматы .ZIP, .RAR и .ARJ. В связи с широким распространением нескольких форматов сжатия многие программные средства для сжатия данных начинают приобретать универсальный характер, позволяя упаковывать и распаковывать сжатые архивы разных типов. Программные средства для WINDOWS обычно имеют один «предпочтительный» тип архива, но также справляются с распаковкой данных при работе с архивами других типов. Наиболее распространен формат .ZIP, который является стандартом для архивов, распространяемых через Интернет. Немаловажную роль в этом играет открытость этого формата. Этот формат является полностью открытым- его использование не требует никаких лицензионных отчислений. Операционная система Windows XP позволяет рассматривать ZIP- архивы как сжатые папки. Это предлагает полностью прозрачную работу с такими архивами- все файловые операции можно выполнять в сжатой папке так же, как в обычной. Однако специализированные средства работы с архивами обеспечивают более широкий набор функций. Формат архивного файла, а следовательно, и его расширение зависят от выбранного архиватора[21]. Примеры популярных архивов и их расширение представлены в таблице 3.

Таблица 3 Примеры архиваторов

Расширение архивного файла

Некоторые архиваторы поддерживают создание самораспаковывающихся архиваторов. Такие архиваторы имеют расширение .exe и распаковываются при запуске этого файла[19].

Существует два режима работы с архиваторами: режим командной строки и диалоговый с использованием интерфейса программы. Среди приведенных выше архиваторов диалоговый режим поддерживает, например, архиватор RAR. При работе в режиме командной строки каждая команда вводится клавишей . Для вывода на экран справки о командах архиватора обычно достаточно набрать в командной строке имя архиватора, символ «/» и «?». Например: arj/? Или rar/?. В ОС Windows программы- архиваторы устанавливаются в систему. Их можно автоматически вызвать по контекстному меню (правая клавиша мыши при выделении файла или группы файлов). Программа- архиватор WinRar (рисунок 12).

Рисунок12. Архиватор WinRAR

WinRAR — это 32-разрядная версия архиватора RAR для Windows, мощного средства создания архивов и управления ими. Существует несколько версий RAR для разных операционных систем. Количество файлов, которое можно добавить в архив, зависит от объёма доступной памяти и длины имён файлов. Для добавления одного файла в архив RAR требуется ориентировочно 128 байт памяти. Максимальный размер архива RAR, равно как и любого файла в архиве RAR, практически не ограничен — он составляет 8 эксабайт (что равнозначно 8 589 934 591 Гбайт или 9 223 372 036 854 775 807 байт). В целом архивный формат RAR значительно лучше оптимизирован для сложных задач с использованием большого количества файлов и гигабайтных дисковых пространств. Меню WinRAR содержит следующие пункты: «Файл», «Команды», «Избранное», «Параметры» и «?».

Ещё один элемент интерфейса — панель инструментов. Она находится ниже меню и выше списка файлов. Кнопки на панели инструментов повторяют пункты из меню «Команды» (у всех пунктов в этом меню есть «горячие клавиши» для быстрого доступа). Во время просмотра содержимого архива некоторые кнопки могут быть отключены, если их функции неприменимы к архиву. Под панелью инструментов находится маленькая кнопка со стрелкой вверх и строка списка дисков. При нажатии кнопки «Вверх» происходит переход в родительскую папку. Список дисков служит для выбора текущего диска или, например, сети. Этот список также можно открыть нажатием клавиши . При желании кнопку «Вверх» и список дисков можно перетащить в правый угол панели инструментов. Текущий диск также можно изменить нажатием сочетания клавиш или щелчком мыши на маленьком значке диска в строке состояния. Ниже панели инструментов расположено файловое окно. В нём отображается содержимое текущей папки или, если в WinRAR открыт архив, содержимое архива. Эти режимы называются режимом управления файлами и режимом управления архивами. Для каждого файла выводится следующая информация: имя, размер, тип и дата изменения. Для файлов в архиве показываются ещё два параметра — упакованный размер и значение CRC32. CRC32 — это особая контрольная сумма, вычисляемая на основании данных файла, с помощью неё можно сразу определить, одинаковы ли упакованные в архиве файлы, не прибегая к их распаковке. Файлы с одинаковым содержимым всегда имеют одинаковые CRC32. Все параметры представлены в виде колонок. Порядок сортировки файлов можно поменять щелчком на заголовке колонки (там же синей стрелкой указывается направление сортировки). Кроме того, можно изменить ширину колонок, перетаскивая мышью разделители заголовков колонок. Несколько дополнительных параметров списка можно изменить в диалоге «Список файлов». Если находящийся в архиве файл зашифрован, то после его имени будет стоять звездочка («*»). Если файл продолжается в следующем томе, то после его имени будут стоять символы «». Если файл продолжается из предыдущего тома, то после имени будут стоять символы « ».

Следующие комбинации клавиш можно использовать для навигации по списку файлов. Чтобы перейти в родительскую папку, необходимо нажать клавиши (BS), или дважды щелкнуть мышью на папке «..» в списке файлов. Если сделать это в корневой папке архива, то этим закроется архив и осуществится переход в ту папку на диске, где он находится. Для перехода в другую папку можно нажать , или дважды щелкнуть левой кнопкой мыши на этой папке. То же действие на файле архива приведет к открытию архива. Для перехода в корневую папку служит комбинация клавиш . Если щелкнуть правой кнопкой мыши на списке файлов, то появится меню с командами интерфейса и управления файлами. Эти команды доступны также из обычных меню WinRAR, с панели инструментов и с помощью сочетаний клавиш, поэтому можно использовать наиболее удобный для себя способ. Если включена опция «Показывать комментарий» в диалоге общих параметров, а в открытом архиве есть комментарий, он будет показан в специальном окне справа от списка файлов. Ширину окна комментария можно изменять, перетаскивая мышью его левый край. Внизу окна WinRAR (под списком файлов) находится строка состояния. В её левой части расположены два маленьких значка: «диск» и «ключ». Щелчком по значку «диск» можно изменить текущий диск, а щелчком по «ключу» — текущий пароль. Две соответствующие команды также есть в меню «Файл». По умолчанию значок «ключ» жёлтого цвета, но если введён пароль, то он становится красным. В средней части строки состояния выводится информация об общем размере выделенных файлов или о текущем состоянии. В правой части строки состояния отображаются общее количество файлов в текущей папке и их размер. Оболочка WinRAR имеет два основных режима: режим управления файлами и режим управления архивами. В режиме управления файлами в окне WinRAR отображается список файлов и папок в текущей папке. Можно выделить эти файлы и папки, как обычно в Windows, с помощью мыши или клавиатуры, и произвести с выделенными файлами различные операции, например, заархивировать их или удалить. В этом режиме также можно протестировать группу архивов и извлечь из них файлы. В режиме управления архивами в окне WinRAR отображается список файлов и папок в открытом архиве. Здесь также можно выделить файлы и папки и выполнить с ними различные действия, специфичные для архива, например, распаковать, протестировать или добавить комментарий. В обоих режимах можно изменить текущую папку (на диске или в архиве). Для перехода в родительскую папку необходимо нажать клавишу (BS) или , либо дважды щелкнуть мышью на папке «..» в списке файлов. Если сделать это в корневой папке архива, то закроется архив и осуществится переход в ту папку на диске, в которой он находится. Для перехода в другую папку необходимо нажать , или дважды щелкнуть мышью на этой папке. Аналогичное действие на файле архива приведет к открытию архива. Для перехода в корневую папку диска служит комбинация клавиш . Для входа в режим управления файлами запускается WinRAR двойным щелчком на его значке или вводится в командной строке «WinRAR» без параметров. Для входа в режим управления архивами запускается WinRAR в режиме управления файлами, помещается курсор на выбранный архив и нажимается (это же действие выполняется при выборе пункта «Открыть архив» в меню «Файл» или при двойном щелчке мышью на имени архива). Кроме того, вход в режим управления архивами происходит при нажатии на архиве или двойном щелчке мышью в оболочке Windows (в Проводнике или на Рабочем столе), но только в том случае, если WinRAR ассоциирован с архивами (что делается по умолчанию во время установки). Связать WinRAR с архивами несложно и после установки — для этого служит диалог «Параметры интеграции»[20].

Программа- архиватор ARJ (рисунок 13).

Рисунок 13. Архиватор ARJ

Программа ARJ (разработчик — Robert K. Jung) относится к числу наиболее известных продуктов своего класса. Она выполняет все функции по обслуживанию своих, архивов, может помещать файлы в архив, извлекать файлы из архива, и делать «самоизвлекающиеся» файлы.

Программа ARJ позволяет:

· создавать архивные файлы из отдельных или всех файлов текущего каталога и его подкаталогов, загружая в один архив до 32000 файлов;

· добавлять и заменять файлы в архиве;

· извлекать и удалять файлы из архива;

· просматривать содержимое архива;

· создавать многотомный архив;

· защищать каждый из помещенных в архив файлов 32-битовым циклическим кодом, тестировать архив, проверяя сохранность в нем информации;

· получать помощь по работе на 3 международных языках;

· вводить в архив комментарии к файлам;

· запоминать в архиве пути к файлам;

· сохранять в архиве несколько поколений (версий) одного и того же файла;

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

· осуществлять поиск строк в архивированных файлах;

· восстанавливать файлы из разрушенных архивов;

· создавать самораспаковывающиеся архивы как на одном томе, так и на нескольких томах;

· просматривать содержимое текстовых файлов, содержащихся в архиве;

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

Для получения на экране краткой помощи по работе достаточно в командной строке ввести имя программы: arj. Для получения развернутой помощи и примеров задания команд следует ввести: «arj -?» или «arj /?» Для загрузки программы и выполнения ею необходимых функций используется формат командной строки, где имя программы и параметры разделяются пробелами

Обязательные параметры командной строки — это два параметра: и

В качестве списка имен файлов можно использовать шаблон (маску). Параметр записывается в виде одного символа вслед за именем программы и задает функцию архивации. Параметр задает имя архивного файла и записывается по общим правилам MS DOS, но без указания расширения, которое при создании нового файла присваивается автоматически. Имя архива может быть записано с указанием пути к файлу. Архиватор по умолчанию обрабатывает архивные файлы, имеющие расширение .arj. Самораспаковывающийся архивный файл создается с расширением .exe. Такой файл содержит в себе программный модуль распаковки, и для извлечения из него файлов не требуется программа arj. Ключи уточняют действие команды архивации, и их может быть несколько. Каждый ключ начинается с символа «-» и может быть помещен в любом месте командной строки после команды. Признаком ключа кроме символа «-» может быть символ «/»[20].

Программа- архиватор ZIP(рисунок 14).

Рисунок 14. Архиватор ZIP

ZIP(разработан Филом Кацем)- популярный формат сжатия данных и архивации файлов. Файл в этом формате обычно имеет расширение .zip и хранит в сжатом или несжатом виде один или несколько файлов, которые можно из него извлечь путём распаковки с помощью специальной программы.

Существует два основных файла программы :

· PKZIP- программа помещающая файлы в архив;

· PKUNZIP- программа извлекающая файлы из архива.

Программы PKZIP/PKUNZIP имеют большое количество функций, выбор нужных функций выполняется в командной строке при вызове программ. Задание функций программ PKZIP/PKUNZIP осуществляется только с помощью указания режимов. Режимы могут указываться в любом месте командной строки после имени программы, они задаются либо с предшествующим знаком “-”, либо с предшествующим знаком “/”

При помещении файла в архив используется следующий формат:

«PKZIP режимы имя архива (имена файлов)»

Режимы- указываются с предшествующим знаком “-” или “/”, они задают или уточняют требуемые от программы архивации действия;

Имена файлов- задают файлы, включаемые в архив. При задании имен файлов можно использовать символы * и ?. Если имена файлов не заданы, то подразумевается все файлы из текущего каталога. После ввода команды программы-упаковщики начинают выполнять запрошенные действия. На экране изображаются имена помещаемых в архив файлов. При сжатии каждого файла выводиться процент обработанной части файла. После окончания сжатия каждого файла напротив его имени сообщается о степени сжатия. Например, при упаковке файла pkzip.exe на экране появляется надпись: «Adding: PKZIP.EXE Deflating (36%), done.» По умолчанию программа PKZIP обеспечивает достаточно большую скорость работы и близкую к максимальной степень сжатия. Но при желании можно получить максимальную (на несколько процентов большую) и наименьшую (быструю) степень сжатия. С ключом максимальной степени сжатия программа работает медленнее обычной, а при ключе наименьшей степени сжатия файлов наоборот, быстрее.

· “-ex” — максимальная степень;

· “-en” — средняя (обычная) степень;

· “-es” — наименьшая степень.

Программа PKZIP имеет три основных режима помещения файлов в архив:

· Add — добавление в архив всех файлов;

· Update — добавление в архив новых файлов;

· Freshen — добавление новых версий имеющихся в архиве файлов.

Эти режимы имеют следующие особенности:

в режиме добавления (Add) в архивный файл добавляются все указанные в команде файлы;

в режиме добавления новых файлов (Update) в архивный файл добавляются те файлы, у которых либо нет копий в архиве, либо эти копии имеют более раннюю дату, чем у файла. Задание этого режима позволяет предотвратить затирание более новых версий в архиве;

в режиме обновления версий файлов (Freshen) в архив добавляются новые версии тех файлов, которые уже имеются в архиве. Иначе говоря, в архив добавляются те файлы, копии которых уже находятся в архиве, но имеют более раннюю дату, чем у соответствующего файла на диске. Этот режим позволяет добиться того, чтобы архивный файл содержал наиболее свежие версии своих файлов. Как упоминалось ранее, для извлечения файлов из архивов, созданных программой PKZIP, используется программа PKUNZIP. После ввода команды программы архивации начинают извлечение файлов из архива. На экране изображаются имена извлекаемых из архива файлов. При извлечении файлов из архива может возникнуть ситуация, когда в том каталоге, в который извлекается файл, уже имеется файл с таким же именем. По умолчанию программа PKUNZIP при этом выполняет следующие действия: на экран выводиться запрос: «PKUNZIP: (W18) Warning! PKUNZIP.EXE already exists. Overwrite (y/n/a/r)? (Файл существует. Перезаписать?)». При нажатии на одну из клавиш : Y — заместить имеющийся файл на диске, N — не извлекать файл из архива, A — всегда замещать имеющиеся на диске файлы(больше запросов не будет), R — присвоить извлекаемому из архива файлу другое имя. Здесь извлечение новой версии файла — ситуация, когда для извлекаемого из архива файла в том каталоге, куда он должен быть помещен, имеется файл с тем же именем, но файл в архиве имеет более позднюю дату последней модификации, чем файл с тем же именем на диске; извлечение нового файла- ситуация, когда для извлекаемого из архива файла в том каталоге, куда он должен быть помещен, нет файла с тем же именем; запрос- запрос — предупреждение, делаемый перед “затиранием” файла на диске. Для каждого файла из архива в оглавлении архива запоминается его код циклического контроля (СRC). Этот код — специальная функция всего содержимого файла, составленная таким образом, что изменить файл так, чтобы его код циклического контроля остался неизменным, практически невозможно. Наличие кода циклического контроля позволяет проверить целостность архивного файла. При извлечении файлов из архива вычисляется код циклического контроля для каждого файла и сообщают пользователю, если этот код не совпадает с записанным в оглавлении архива. Проверить целостность архива можно с помощью команды тестирования: «Pkunzip -t имя-архива». Хранение информации в архиве более надежно из-за того, что данные хранятся в сжатом виде, меньше вероятность их случайного повреждения, например из-за дефектов магнитного покрытия диска. Но в некоторых случаях архивные файлы с большой вероятностью могут быть повреждены. Вот наиболее типичные из таких ситуаций:

· запись архива на дефектную дискету или чтение его с такой дискеты;

· передача архива по телефонной сети через модем;

· повреждения из-за воздействия вирусов, неосторожных действий пользователей, неправильно работающих программ и т.д.

Курсовая работа: Алгоритмы сжатия данных

Алгоритмы сжатия данных

Энтропия и количество информации

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

Моделирование и кодирование

Некоторые алгоритмы сжатия данных

BWT — преобразование и компрессор

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

Реализация алгоритма арифметического кодирования

Доказательство правильности декодирования

Приращаемая передача и получение

Переполнение и завершение

Адаптивная модель для арифметического кодирования

Приложение 1. Программный код

Приложение 2. Интерфейс программы

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

Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив­ному кодированию символов. Словарные алгоритмы позволяли кодир­овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, aLZW давно уже не встраивается в новые приложения (однако широко используется в старых).

Будущее алгоритмов сжатия тесно связано с будущим компью­терных технологий. Современные алгоритмы уже вплотную приблизи­лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия.

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

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

Количество нужной человеку информации неуклонно растет. Объемы устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее. У этой проблемы есть три решения. Первое — ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Второе — увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными. Третье решение — использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избы­точность информации и возможность установки специального програм­много обеспечения либо аппаратуры как вблизи источника, так и вблизи приемника информации. Как правило, оба эти условия удовлетворяются.

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

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

При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

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

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

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

Таким образом, для передачи состояния объекта достаточно I=log2 Nбит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

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

Обозначим через р(у|х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi |х) будет

Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 pбит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).


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

Энтропия набора данных, а значит и максимально возможная степень сжатия, зависит от модели. Чем адекватнее модель (чем качественнее мы можем предсказать распределение вероятности значений следующего элемента), тем ниже энтропия и тем лучше максимально достижимая степень сжатия. Таким образом, сжатие данных разбивается на две самостоятельные задачи — моделирование и кодирование.

Моделирование обеспечивает предсказание вероятности наступ­ления возможных событий, кодирование обеспечивает представление события в виде -log2 pбит, где р — предсказанная вероятность наступ­ления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия исполь­зуемый кодер при необходимости может быть легко заменен другим.

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

Алгоритм LZ77 является родоначальником целого семейства словарных схем — так называемых алгоритмов со скользящим словарем, или скользящим окном. Действительно, в LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно меняется, словарь «скользит» по входному потоку данных.

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

■ последовательности длины W=N-nуже закодированных символов, которая и является словарем;

■ упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.

Пусть к текущему моменту времени мы уже закодировали tсимволов S1 , S2 , . St . Тогда словарем будут являться Wпредшествующих символов St -( W -1) , St -( W -1)+1, …, St . Соответственно, в буфере находятся ожидающие кодирования символы St +1 , St +2 , …, St + n . Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St +1 , и всеми фразами словаря. Эти фразы могут начинаться с любого символа St -( W -1) , St -( W -1)+1, …, St выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St +1 . поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St -( i -1) , St -( i -1)+1, …, St -( i -1)+( j -1) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (matchlength), j;

Смещение и длина соответствия играют роль указателя (ссылки), одно­значно определяющего фразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s(литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax | строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции posисходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

2. В выходной файл помещается номер найденного слова в словаре positionи следующий символ из входного текста В (на котором обнаружилось различие) —

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |strB|=|str|+l байт дальше к символу, следующему за В.

В таком варианте алгоритм почти не нашел практического применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax ] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииposисходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |str| байт дальше к символу В.

Алгоритм PPM (predictionbypartialmatching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «tobeornott» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

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

BWT — преобразование и компрессор

BWT-компрессор (Преобразование Барроуза – Уиллера) — сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г.. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых,даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической» последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V=»БАРАБАН» и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

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

Фактический «выход» преобразования состоит из строки L=»РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

Название: Алгоритмы сжатия данных
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 02:50:21 26 июля 2009 Похожие работы
Просмотров: 1052 Комментариев: 14 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно Скачать
15 7 6 6 5
А Б В Г Д

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 2.

Рис. 2. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

Рис. 3. Окончательное дерево кодирования Хаффмана

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

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

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтений их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д — наибольшим.

Классический алгоритм Хаффмана имеет один существенный недостаток. Дня восстановления содер­жимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования.

Арифметическое сжатие — достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварная корова»). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Символ Частота Вероятность Диапазон
О 3 0.3 [0.0; 0.3)
К 2 0.2 [0.3; 0.5)
В 2 0.2 [0.5; 0.7)
Р 1 0.1 [0.7; 0.8)
А 1 0.1 [0.8; 0.9)
“.” 1 0.1 [0.9; 1.0)

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д.

Используя исходную таблицу диапазонов, кодируем текст «КОВ.КОРОВА»:

Исходный рабочий интервал [0,1).

Символ «К» [0.3; 0.5) получаем [0.3000; 0.5000).

Символ «О» [0.0; 0.3) получаем [0.3000; 0.3600).

Символ «В» [0.5; 0.7) получаем [0.3300; 0.3420).

Символ «.» [0.9; 1.0) получаем [0,3408; 0.3420).

Графический процесс кодирования первых трех символов можно представить так, как на рис. 4.

Рис. 4. Графический процесс кодирования первых трех символов

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Можно обозначить диапазон символа с как [а[с]; b[с]), а интервал для i-го кодируемого символа потока как [li , hi ).

Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале [/i , hi ). Для последовательности «КОВ.», состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только «К», поскольку только его диапазон включает это число. В качестве интервала берется диапазон «К» — [0.3; 0.5) и в нем находится диапазон [а[с]; b[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для «О», включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т. д.

Ниже показан фрагмент псевдокода процедур кодирования и декодирования. Символы в нем нумеруются как 1,2,3. Частотный интервал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] возрастает так, что cum_freq[0] = 1. (Причина такого «обpатного» соглашения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализующий множитель, котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика.

С каждым символом текста обpащаться к пpоцедуpе encode_symbol(). Пpовеpить, что «завеpшающий» символ закодиpован последним. Вывести полученное значение интеpвала [low; high).

range = high — low

high = low + range*cum_freq[symbol-1]

low = low + range*cum_freq[symbol]

Value — это поступившее на вход число. Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит «завеpшающий» символ.

//поиск такого символа, что

Из выражения (1) имеем:

В отличие от псеводокода, программа представляет low и high целыми числами. В псевдокоде текущий интеpвал пpедставлен чеpез [low; high), а в пpогpамме это [low; high] — интеpвал, включающий в себя значение high. Hа самом деле более пpавильно, хотя и более непонятно, утвеpждать, что в пpогpамме пpедставляемый интеpвал есть [low; high + 0.1111. ) по той пpичине, что пpи масштабитовании гpаниц для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high.

По меpе сужения кодового интеpвала, стаpшие биты low и high становятся одинаковыми, и поэтому могут быть пеpеданы немедленно, т.к. на них будущие сужения интеpвала все pавно уже не будут влиять. Поскольку мы знаем, что low≤high, это воплотится в следующую пpогpамму:

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

гаpантиpующую, что после ее завеpшения будет спpеведливо неpавенство: low Half)

value = 2 * (value — Half) + input_bit();

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

Как показано в псевдокоде, арифметическое кодирование работает при помощи масштабирования накопленных вероятностей, поставляемых моделью в интервале [low; high] для каждого передаваемого символа. Пpедположим, что low и high настолько близки дpуг к дpугу, что опеpация масштабиpования пpиводит полученные от модели pазные символы к одному целому числу, входящему в [low; high]. В этом случае дальнейшее кодиpование пpодолжать невозможно. Следовательно, кодиpовщик должен следить за тем, чтобы интеpвал [low; high] всегда был достаточно шиpок. Пpостейшим способом для этого является обеспечение шиpины интеpвала не меньшей max_frequency — максимального значения суммы всех накапливаемых частот.

Как можно сделать это условие менее стpогим? Объясненная выше опеpация битового сдвига гаpантиpует, что low и high могут только тогда становиться опасно близкими, когда заключают между собой half. Пpедположим, они становятся настолько близки, что

first_qtr ≤low 14 — 1 и top_value = 2 16 — 1.

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

Теперь рассмотрим возможность переполнения при целочисленном умножении. Переполнения не произойдет, если произведение range*max_frequency вмещается в целое слово, т.к. накопленные частоты не могут превышать max_frequency. range имеет наибольшее значение в top_value + 1, поэтому максимально возможное произведение в программе есть 2 16 *(2 14 — 1), которое меньше 2 30 .

При завершении процесса кодирования необходимо послать уникальный завершающий символ (EOF-символ), а затем послать вслед достаточное количество битов для гарантии того, что закодированная строка попадет в итоговый рабочий интервал. Т.к. пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либо выpажением (1a), либо (1b), ему нужно только пеpедать 01 или 10 соответственно, для удаления оставшейся неопpеделенности. Удобно это делать с помощью пpоцедуpы bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанять заполнение нижнего конца буфеpа. Hеважно, какое значение имеют эти биты, поскольку EOF уникально опpеделяется последними пеpеданными битами.

Программа должна работать с моделью, которая предоставляет пару перекодировочных таблиц index_to_char[] и char_to_index[], и массив накопленных частот cum_freq[]. Причем к последнему предъявляются следующие требования:

никогда не делается попытка кодиpовать символ i, для котоpого

cum_freq[0] — 4 битов/символ.

Дополнительные затpаты на масштабиpование счетчиков отчасти больше, но все pавно очень малы. Для коpотких текстов (меньших 2 14 байт) их нет. Hо даже с текстами в 10 5 — 10 6 байтов накладные pасходы, подсчитанные экспеpиментально, составляют менее 0.25% от кодиpуемой стpоки.

Адаптивная модель, пpи угpозе пpевышения общей суммой накопленных частот значение max_frequency, уменьшает все счетчики. Это пpиводит к тому, что взвешивать последние события тяжелее, чем более pанние. Т.о. показатели имеют тенденцию пpослеживать изменения во входной последовательности, котоpые могут быть очень полезными.

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

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

Для реализации использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. В результате программное обеспечение очень компактно, интуитивно понятно и эффективно в работе.

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2002. — 384 с.

2. Сэломон Д. Сжатие данных, изображений и звука. Data Compression Methods. Серия: Мир программирования. Издательство: Техносфера, 2004. — 368 с.

3. Артюшенко В. М., Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука. Издательство: Дашков и Ко, 2004. — 426 с.

4. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. Издательство: ДиаСофт, 2002. — 688 с.

// Количество бит для кода

// Максимально возможное значениекода

const int top_value = (int)(((long)1 = 0; i—)

freq[i] = (freq[i] + 1) / 2;

/* Обновление перекодировочных таблиц в случае перемещения символа */

for (i = symbol; freq[i] == freq[i — 1]; i—) ;

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему: Эффективные алгоритмы неискажающего сжатия текстовой информации

Автореферат диссертации по теме «Эффективные алгоритмы неискажающего сжатия текстовой информации»

российская академия наук

Р ИНСТИТУТ СИСТЕМ ИНФОРМАТИКИ П 0 иЦ им. А. II. Ершова

Иа правах рукописи

Кадач Андрей Викторович

Эффективные алгоритмы неискажающего сжатия текстовой информации

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

диссертации иа соискание ученой степени кандидата физико-математических наук

Работа выполнена в Институте систем информатики имени А.П. Ершова Сибирского отделения Российской академии наук (ИСИ СО РАН).

Научный руководитель: доктор физико-математических наук,

профессор И.В. Поттосин

Официальные оппоненты: академик МАИ, доктор технических нау

профессор Б.Я. Рябко

кандидат физико-математических наук, старший научный сотрудник П.А. Ким

Ведущая организация: Институт математики СО РАН

Защита состоится «» февраля 1998 г. в 14 час. 30 мин. на заседании специализированного совета К0003.93.01 в Институте систем информатики им. А.II. Ершова Сибирского отделения РАН по адресу: 630090, Новосибирск, пр. ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (пр. ак. Лаврентьева, 6).

Автореферат разослан « » января 1998 г.

Ученый секретарь специализированного совета К0003.93.01

к.ф.-м.н. А ‘ М.А. Бульонков

Общая характеристика работы

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

Основные параметры метода сжатия — качество сжатия (отношение длин сжатых и исходных данных), скорость сжатия (объем исходных данных, обрабатываемых в единицу времени) и объем требуемой памяти. При практической реализации имеются жесткие ограничения на объем доступной памяти (не более 20 Мб, для встроенных систем — не более 1 Мб ввиду ограниченного объема ОЗУ) и скорость сжатия (не менее 50 Кб/с). Скорость особенно важна, т. к. пропускная способность даже обычных телефонных линий — 3-10 Кб/с сжатых данных, поэтому (с уче том коэффициента сжатия) необходимо обрабатывать не менее 10-30 Кб/с исходных данных; типичный объем жесткого диска — 2-5 Гб. поэтому при скорости сжатия менее 50 Кб/с (180 Мб/с) время резервного копирования превысит 1224 часов, что не приемлемо.

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

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

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

Научная новизна работы состоит в том, что были предложены, изучены и обоснованы новые методы и алгоритмы сжатия, способы их реализации, новые решения известных проблем:

• предложены и исследованы новые методы построения и декодирования канонических кодов Хаффмана; доказано, что эти методы почти оптимальны по скорости и на порядок эффективнее известных при таком же объеме требуемой памяти;

• разработаны и изучены новый методы сжатия текстов и гипертекстов на естественных языках (английском, русском, немецком и т. д.); доказано, что они близки к оптимальным;

• предложены и изучены новые алгоритмы поиска подстрок в алгоритмах словарного сжатия семейства 1^77 (обладающих высокой скоростью сжатия, приемлемым качеством и требующих мало — 300-500 Кб — оперативной памяти), разработаны новые эффективные варианты таких методов сжатия и предложены новые однопроходные алгоритмы построения оптимальной последовательности кодирования; доказано, что большинство вышеперечисленных методов сжатия близки к оптимальным по всем или почти по всем параметрам, и показано, что при таком же качестве сжатия и меньшем объеме требуемой памяти предложенные методы в несколько раз быстрее известных;

• разработана новая методика построения алгоритмов сжатия сортировкой блоков (обладающих высокой скоростью и очень хорошим качеством сжатия, но требующих достаточно больших — 5-20 Мб — объемов оперативной памяти):

— предложены и исследованы новые эффективные методы реализации полной сортировки блоков; доказано, что

они оптимальны в своем классе, и показано, что при таком же объеме требуемой памяти по скорости1 (ISOISO Кб/с) они-превосходят (иногда в тысячи раз) используемые в настоящее время эвристические методы; — разработан и изучен новый класс алгоритмов сжатия частичной сортировкой блоков и доказано, что скорость таким методов сжатия (‘250 300 Кб/с) вдвое выше, чем при полной сортировке, и не зависит от сжимаемых данных (что является достаточно редким и очень важным свойством), а качество сжатия незначительно хуже сжатия полной сортировкой блоков;

разработаны и исследованы новые методы кодирования выхода преобразования сортировкой блока (полной или частичной) и предложены эффективные методы их реализации; доказано, что по скорости такие методы кодирования оптимальны, и показано, что [в сочетании с преобразованием сортировкой блоков] по качеству сжатия они не уступают наилучшим известным методам сжатия (будучи в 5-20 раз быстрее), а по скорости — алгоритмам семейства LZ77 (превосходя последние по качеству в 1.3 1.7 раза).

Практическая ценность работы подтверждается фактом их использования рядом коммерческих компаний, занимающихся созданием программного обеспечения самого различного профиля от систем автоматизации машиностроения до разработки сильно оптимизирующих компиляторов для встроенных систем (ProPro Group inc., XDS Ltd., AIP NL и др.).

Разработанные и реализованные A.B. Кадачом системы сжатия исполняемых файлов (PRSEXE и UXECE) получили широкое международное признание; согласно регулярно проводимым канадской группой ACT тестам, они уверенно занимают лидирующее положение среди более десяти аналогичных продуктов, разработанных известными производителями программного обеспечения .Microsoft, Symantec и др.

Апробация работы и публикации. Результаты работы неоднократно докладывались и обсуждались на объединенном се-

1 Скорость сжатия указана для процессора, исполняющего 100 млн. команд типа регистр-регистр в секунду.

минаре ИСИ СО РАН и НГУ «Системное программирование», семинарах Новосибирского института связи (СибГАТИ) и Института математики СО РАН с участием ведущих специалистов. По теме диссертации опубликовано семь печатных работ (все — без соавторов).

Структура и объем работы. Диссертационная работа состоит из пяти частей (12 глав) и списка литературы из 203 наименований. Общий объем работы — 184 страницы. К работе прилагаются акты внедрения разработанных и реализованным автором систем сжатия.

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

Вторая часть работы состоит из главы 3 и посвящена префиксным кодам, которые лидируют по скорости кодирования и декодирования (но не являются наилучшими по качеству); особое внимание уделено кодам Хаффмана, оптимальным по качеству сжатия среди префиксных кодов.

Кодом называется отображение / : £ —» <0,1>*, а кодовым словом символа2 а £ Е — значение /(о). Код называется префиксным, если ни одно кодовое слово не является префиксом (полным началом) какого-либо другого кодового слова. Код называется полным, если из того, что битовая строка 5 € <0,1>* — префикс некоторого кодового слова, отличный от него, следует, что строки «0 и «1 — также префиксы некоторых кодовых слов. Можно показать, что для каждого однозначно-декодируемого кода /’ существует псудлиняющий полный префиксный код /, т. е.

2 В дальнейшем предполагается, что £ — алфавит конечной мощности, что позволяет занумеровать все символы алфавита и задать на них полный порядок, который индуцирует естественный полный порядок на строках символов алфавита

такой, что |/(а)| 0 появления символов Е, то возникает задача построение оптимального кода /, средняя стоимость кодирования которого минимальна:

известно, что С(р, /) не меньше энтропии

‘R(p) = C(]>. f) — £(;■>) > 0 называется избыточностью кода /.

Задача построения оптимального кода была решена Хафф-маном в 1952 г. следующим образом: создадим ¡ü¡ деревьев, состоящих из одной вершины, помеченной очередным символом, и припишем каждому дереву вес, равный вероятности появления соответствующего символа. Пока существует более одного дерева, будем сливать два дерева с минимальным весом в одно (в качестве потомков новой вершины), которому припишем вес, равный сумме весов его поддеревьев. Оставшееся дерево и будет деревом Хаффмана. По построению, соответствующий ему код будет полним и префиксным; можно показать, что его избыточность меньше единицы, а средняя стоимость кодирования — минимальна.

Поскольку на практике вероятности появления символов заранее не известны, требуется предварительно просмотреть сообщение длины .V и подсчитать п(а) количество появлений символа гу в сообщении:

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

Заметим, что на практике длина кодируемого сообщения N заведомо ограничена сверху (хотя бы потому, что суммарный объем всех существующих носителей информации не превышает 2128 битов, так что N , где ( — длина предыдущего идентичного вхождения подстроки, а р Ь или аа Ь и т. д.

В главе 4 предложен способ кодирования текстов на естественных языках (русском, английском, немецком и т. д.) заменой слов и последовательностей разделителей (пробелов, запятых, точек и т. д.) их номерами в словаре. Используя известный закон Ципфа о том, что вероятность появления г-го по частоте использования слова обратно пропорциональна г, доказано. что стоимость оптимального кодирования не меньше

битов на слово, где N — количество различных использованных в тексте слов (обычно 10-40 тыс., на очень длинных тек-

стах — 2-5 Гб — до 1 млн.), а 8 е [0.82,0.96] при N > 2048. Для кодирования номеров слов было предложено отсортировать все слова по частоте появления и разбить на \l0g2N] групп, так что слово с номером п € [2т, 2т+1 — 1] кодируется парой , причем первый элемент кодируется по Хаффману, а второй — равномерно п битами. Было доказано, что избыточность такого кодирования (с учетом избыточности кода Хаффмана) не превышает 2%. Автором было предложено использовать единый словарь для всех лексем (и слов, и разделителей) и вообще не кодировать самую часто используемую лексему (как правило, одиночный пробел); если при декодировании встречаются две идущие подряд лексемы одного класса, то между ними нужно вставить удаленную. Был также предложен эффективный метод сжатия словаря, способы построения модифицируемых словарей, сжатия изменяемых текстов, хранения словаря в сжатом виде и во время декодирования и т. д. Показано, что, в отличие от известных, предложенный метод кодирования допускает доступ к сжатых данным в почти произвольном порядке (что важно для работы с гипертекстами) и обладает в 1.5-2 раза лучшим качеством сжатия.

В главе 5 изучены методы построения оптимального по стоимости Ь277-кода: т. к. каждая строка может быть закодирована многими способами, возникает проблема построения 1^77-кода минимальной длины. При прямолинейном кодировании строка просматривается слева направо, и если в текущей позиции г в окне ширины Ш существует подстрока, являющаяся началом незакодированной части, порождается указатель и кодировщик сдвигается на £ символов (если таких подстрок несколько, то выбирается самая правая и наиболее длинная подстрока); если же подстроки не найдено, то порождается литерал (текущий символ) и кодировщик смещается на один символ вправо. Прямолинейное кодирование не оптимально; длина такого кода может быть в раз больше оптимальной (Р — стоимость передачи указателя, а С — литерала). Для построения оптимального 1^77-кода можно применить известный алгоритм динамического программирования Миллера — Вег-мана, что потребует 3|5| слов дополнительной памяти, где ]5| — длина кодируемой строки; на практике это не приемлемо.

Кроме того, для алгоритма Миллера — Вегмана необходимо для каждой позиции осуществить поиск подстроки, тогда как при прямолинейном кодировании поиск осуществляется гораздо реже, поскольку при кодировании указателя поиск подстроки в следующих — 1) позициях не требуется. Таким образом, алгоритм Миллера — Вегмана в /аие

4 6 раз медленнее прямолинейного и поэтому никогда не используется; вместо этого применяются всевозможные эвристики. Автором были разработаны и обоснованы новые однопроходные методы построение почти оптимального 1^77-кода, требующие 5М слов дополнительной памяти при относительной избыточности менее

(при М = кодирование оптимально). Показано, что они минимизируют количество требуемых поисков подстрок и линейны по количеству неоднозначностей кодирования, а их скорость (с учетом количества необходимых поисков подстрок) близка к скорости прямолинейного кодирования. Более того, показано, что все используемые методы кодирования и эвристики — частные случаи предложенных при Р — 2С и М = 0,1,2. Важным свойством предложенных алгоритмов является, что при каждом поиске подстрок заранее известна минимальная длина интересующей подстроки (тт > т е- процедура поиска может пропускать совпадающие подстроки длины меньше (тгп.

В главе 6 описаны предложенные автором эффективные методы поиска подстрок и новые варианты [/¿77. Поскольку поиск осуществляется относительно редко, асимптотически оптимальные методы поиска подстрок, использующие деревья суффиксов. не являются наилучшими для 1^77: процесс вставки новой подстроки не отличается от поиска; удаление подстрок, не попадающих в окно, чрезвычайно нетривиально; вычислительная сложность алгоритма и объем требуемой памяти очень большие; средняя производительность очень низкая. Вместо этого было предложено осуществлять поиск прямым перебором хэш-списка подстрок с одинаковым значением хэш-суммы, построенной по первым п — яа 3 -г 4 символам;

доказано, что для источников Берпулли в среднем требуется перебирать не более \¥0″ подстрок, где 0 = (обычно в « 0.05 -г 0.075), поэтому при ограниченной ширине окна (IV на 0, 1, . (Аг — 1) символов; отсортировав строки М в лексикографическом порядке (индуцированном естественным полным порядком на Е), получим матрицу М’. Утверждается, что если известен последний столбец Ь матрицы М’ и номер в М’ исходной строки, то ее можно восстановить за 0(Аг) операций с использованием 0(№) слов дополнительной памяти. Поскольку длина общего начала двух соседних строк отсортированной матрицы М’, скорее всего, значительна, предшествующие символы с высокой вероятностью совпадают, а т. к. строки М’ — циклические вращения 5, то символы последнего столбца Ь предшествуют первым символам строк М’. Таким образом, Ь обладает ярко выраженной избыточностью, выражающейся в наличии большого количества серий повторов одного и того же символа, и может быть эффективно закодирована достаточно простыми методами.

Матрица М Матрица М’

а ъ с ь с а Ъ а ь с а Ь 0 а Ь а Ъ с а Ь . а Ь с Ь с

Ь с Ъ с а Ь а Ь с а Ъ а 1 а Ь с а Ь . а Ъ с Ь с а Ъ

с Ъ с а Ь а Ъ с а Ь а Ъ 2 ==> а Ь с Ъ с а Ь а Ъ с а Ъ

Ъ с а ь а Ь с а Ъ а Ъ с 3 а Ъ . а Ъ с Ь с а Ъ а Ъ с

а Ъ а ъ с а Ъ . а ъ с Ъ с 4 Ъ а Ъ с а Ь . а Ъ с Ъ с а

Ъ а Ъ с а Ь . а Ь с Ь с а 5 Ъ с а Ъ а Ь с а Ъ а Ь с

а Ь с а Ъ . а Ь с Ъ С а Ъ 6 ь с а Ь . а Ъ с ъ с а Ъ а

Ь с а Ь . а Ь с Ь с а Ъ а 7 ь с Ъ с а Ь а Ь с а Ъ . а

с а Ъ а Ь с Ь с а Ъ а Ъ 8 с а Ъ . а Ь с Ь с а Ь а Ъ

а Ъ а Ь с Ь с а Ь а Ъ с 9 с Ь с а Ь а Ь с а Ъ а Ъ

а Ъ с Ь с а Ь а Ъ с а Ъ 10 а Ъ с Ь с а Ь а ь с а Ъ

В главе 8 описывается разработанный автором алгоритм блочной сортировки матрицы циклических вращений М, который является центральной частью одноименного метода сжа-

тил данных и во многом (на 80-90%) определяет скорость сжатия и объем требуемой памяти. Известные асимптотически оптимальные непрямые методы решения этой задачи (основанные на применении деревьев суффиксов) требуют слишком много оперативной памяти — 8N-10N слов (32-64 Мб при N = 1-^-2 Мб) —- и обладают очень низкой средней производительностью, поэтому используются всевозможные эвристические методы сортировки, требующие (2N + |£|) слов памяти и обладающие высокой средней скоростью (0(N log log N) операций); к сожалению, в наихудшем случае время сортировки увеличивается в тысячи раз, достигая 0(N\/N log N). Таким образом, известные методы сортировки не пригодны для практического использования. Алгоритм, разработанный автором, требует (2N -f |£|) слов памяти; доказано, он оптимален в классе алгоритмов сортировки удвоением, поэтому среднее время сортировки равно 0(iVloglog N) и в наихудшем случае не превышает 0(N log N), оставаясь приемлемым. Показано, что реальная производительность этого алгоритма лучше всех известных.

В главе 9 автором предложен новый класс алгоритмов сжатия частичной сортировкой блоков. Вместо того, чтобы полностью сортировать исходную матрицу М, отсортируем ее по первым F символам устойчивым образом, что может быть сделано с помощью известного алгоритма сортировки расстановкой за 0((N -f |£|)F) операций с использованием (2N + |£|) слов дополнительной памяти; важно отметить, что время такой сортировки не зависит от сортируемых данных. Автором доказано, что если сортировка устойчива, т. е. сохраняет исходный порядок следования строк М при совпадении первых F символов, преобразование частичной сортировкой блоков, равно как и полной, обратимо. Доказано, что предложенные способы реализации обратного преобразования восстанавливают исходные данные за C>(|£| + iVlogF) операций при Bp ф 0 и за 0(N + Y.) при Bp = 0 с использованием (2N+ |£|) слов дополнительной памяти. Доказано, что преобразование Барроуза — Уилера является частным случаем преобразования частичной сортировкой. Показано, что при F = 4 скорость такого сжатия вдвое выше, чем при полной сортировке, а качество хуже лишь на 1-5%.

В главе 10 предложены новые методы кодирования резуль-

татов преобразования сортировкой блоков (полной или частичной) и эффективные способ!,i их реализации. Поскольку кодируемая последовательность содержит много повторений символов. иногда перемежаемых другими символами (например, типичная последовательность выглядит как aaaabaababbbabbb-beb), применяется локально-адаптивное, кодирование. Было показано, что наилучшие результаты получаются использованием Inverted Frequency Coding (IF-преобразования): просматривая строк>1, при обнаружении символа а будем генерировать число, равное количеству символов, лексикографически больших а, ртделяющих текущее и предыдущее вхождение а; затем это проделывается для следующего за су символа и т. д.; например, строка aabaebba будет преобразована в (а : 0013,6 : 010, с : 0); полученная последовательность целых сжимается с применением кодов Хаффмана, групповых и шаговых кодов и т. п. Так как и при кодировании, и при декодировании требуется |£| проходов по строке, то при |£| > 100 время IF-преобразования очень значительно и равняется 1j). Автором был предложен алгоритм прямого и обратного IF-преобразования с временной сложностью 0(.Y log которые быстрое на порядок. Кроме того, были предложены эффективные способы построения моделей высоких порядков (4-5-го) для кодирования результата 1 К-преобразования. Было показало, что при использовании 5-50 Кб дополнительной памяти скорость такого кодирования очень высокая, а качество на 10-25% выше, чем у применявшихся ранее методов кодирования, и не уступает качеству сжатия лучших известных методов статистического моделирования.

Пятая часть работы — заключительная и состоит из двух г л а в

В главе 11 приводятся результаты экспериментов по сжатию данных из стандартных наборов тестов Calgary и Canterbury Data Compression Corpus(es). Методы сжатия, разработанные и реализованные автором, представлены программой PRS: при опциях L1-L7 используется LZ77 с «прыгающим» окном в 3264 Кб при различной максимальной глубине перебора и различных методах построения ЬХ77-кода (об ьем требуемой памяти — 300 Кб), при опции F — сжатие полной сортировкой блоков размером в 1 Мб, а при Р4 и Р8 — частичной сортировкой по пер-

вым 4 и 8 символам (объем требуемой памяти — 9 Мб). Кроме того, рассмотрены наиболее эффективные современные архиваторы, реализующие LZ77 со «скользящим» окном в 32-64 Кб и требующие 300—500 Кб памяти (PKZIP 2.04G, RAR 2.02, ARJ 2.41, LHA4), алгоритмы сжатия сортировкой блоков размером в 1 Мб, требующие 6-10 Мб памяти, (BRED, BRED3, XI 0.94L -аш7), методы статистического моделирования, требующие 16-20 Мб памяти: АСВ (АСВ 1.23С), DMC (DMC1 в авторской реализации, коротая вдвое быстрее оригинальной версии при прочих равных параметрах), PPM (XI 0.94L -ашЗ и -am4, RKIVE 1.4, НА 0.999С). Из приведенного сравнения видно, что авторская реализация LZ77 при таком же или лучшем качестве сжатия в 2-5 раз быстрее и требует вдвое меньше памяти (300 Кб), а разработанные методы сжатия сортировкой блоков при таком же или меньшем объеме используемой памяти (9 Мб) превосходят другие реализации сжатия сортировкой блоков по качеству на 10-20% и не уступают по скорости, опережая по скорости методы сжатия статистическим моделированием 4-20 раз на текстовых данных и в 20-30 раз на двоичных при таком же и часто лучшем качестве сжатия.

В таблице на стр. 17 приведены результаты сжатия файлов bookl и book2 из Calgary Data Compression Corpus. Тесты проводились на IBM PC с процессором Intel Pentium при тактовой частотой 100 МГц, 32 Мб оперативной памяти, под операционной системой Microsoft Windows 95. Время сжатия определялось с точностью до 0.001 с и усреднялось по И запускам; наихудшее время не учитывалось.

В главе 12 перечисляются основные результаты работы.

4 ЬНА заметно уступает другим рассмотренным архиваторам по всем параметрам, т. к. это единственная [из рассмотренных] реализация \Л77 со «скользящим» окном [всего] в 8 Кб, использующая для поиска подстрок дерево суффиксов. Этот пример наглядно показывает, что асимптотически оптимальные алгоритмы — не всегда наилучшие на практике.

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

bookl (768771 байтов) Ьоок2 (610856 байтов)

Архиватор и опции Время. с Длина сжатых данных, байтов Л рхи-ватор и опции Время, с Длина сжатых данных, байтов

prs Р8 4.648 219905 prs Р8 3.480 152616

prs F 5.753 219708 prs F 4.450 152465

xl ат4!9 18.265 219688 xl am419 13.815 152539

xl атпЗШ 19.250 219821 xl ат319 14.500 152832

rkive -mt 29.880 219672 rkive -mt 19.880 149881

rkive -mtx 48.610 219913 rkive -mtx 32.300 149682

prs P4 2.896 227652 acb b 51.250 150591

acb b 86.830 226609 acb u 82.280 149743

acb u 142.150 224525 prs P4 2.181 158853

dmcl с 9.650 235619 ha a2 13.210 163566

ba a2 17.245 235764 rkive -mb 15.190 164570

ach В 40.200 241260 acb В 24.500 159133

bred:) -All 5.355 24997т bred3 -Alf 3.827 167255

xl аш7 7.413 250121 xl am7 5.313 167422

bred -Ml 7.633 250086 bred -Ml 5.492 167387

rkive -mb 23.780 252317 drnc 1 с 7.507 167244

prs 1/1 3.947 304737 prs L4 2.603 200965

prs L5 5.013 301107 prs L5 3.310 198574

prs L6 5.945 299393 prs Lö 3.928 197589

prs L7 6.960 296524 prs L7 4.482 195879

rar -шЗ 7.377 305906 rar -m3 4.712 199440

rar -mi) 14.115 301298 rar -rnö 8.183 196803

prs LI г» 2.011 330325 prs LI 1.407 220968

prs L2 2.794 314942 prs L2 1.884 208465

prs L3 3.327 311627 prs L3 2.270 206029

pkzip -en 4.020 316107 pkzip -en 2.547 209169

rar -ni2 4.132 319837 rar -iu2 2.808 208902

arj -ш2 5.315 322381 pkzip -ex 3.990 206621

pkzip -ex 6.015 312598 arj -ш2 3.397 212659

arj -ml 7.890 319166 arj -ml 4.756 210431

1ha а 8.970 339107 1ha а 6.753 228475

1. Разработаны, изучены и обоснованы новые методы построения и декодирования кодов Хаффмана, которые в 3-6 раз быстрее известных алгоритмов.

2. Предложены и обоснованы новые алгоритмы сжатия текстов на естественных языках, которые в 5—50 раз быстрее известных при лучшем в 1.5-2 раза качестве сжатия.

3. Разработаны, исследованы и обоснованы новые варианты алгоритма \IL77, новые методы управления поиском, новые способы реализации поиска подстрок для 1^77-схем со «скользящим» окном, применение которых позволило в 25 раз увеличить скорость сжатия (до 250-450 Кб/с) и на 3-5% — качество, при таком же и часто меньшем объеме требуемой памяти (300 Кб при ширине окна 64 Кб).

4. Разработана новая методика сжатия данных сортировкой блоков:

• предложены, изучены и обоснованы алгоритмы сжатия полной сортировкой блоков, которые по средней производительности (130-150 Кб/с.) превосходят почти все другие известные реализации (при таком же объеме требуемой памяти), в отличие от них обеспечивая приемлемую скорость сжатия и в наихудшем случае, при лучшем на 15-20% качестве, не уступающем качеству сжатия методов статистического моделирования;

• разработан и изучен новый класс алгоритмов сжатия частичной сортировкой блоков, которые скорости сжатия (250-300 Кб/с) вдвое опережают алгоритмы сжатия полной сортировкой блоков и часто быстрее алгоритмов семейства Ь277] показано, что скорость такого сжатия не зависит от сжимаемых данных, а качество лишь на 15% хуже, чем при полной сортировке, и в 1.3-1.7 раза лучше, чем у \ЛП1.

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

Публикации по теме диссертации

1. Кадач A.B. Оптимизация качества сжатия в LZ77-cxeMax // В сб. «Средства и инструменты окружений программирования». — Новосибирск, 1995. — С. 127-142.

2. Кадач A.B. Поиск подстрок в LZ77-cxeMax // В сб. «Средства и инструменты окружений программирования». — Новосибирск, 1995. ■ — С. 143-160.

1. Кадач A.B. Эффективные алгоритмы нгискажающего сжатия данных сортировкой блоков. Ч. I: Преобразование Барроуза — Уилера и его модификации. — Новосибирск, 1997. — 43 с. — (Преир. / Сиб. отд-ние РАН; Институт систем информатики им. А.П. Ершова; N 42/1).

4. Кадач A.B. Эффективные алгоритмы нсискажающгго сжатия данных сортировкой блоков. Ч. II: Кодирование выхода преобразования Барроуза — Уилера. — Новосибирск, 1997. — 39 с. — (Препр. / Сиб. отд-ние РАН; Институт систем информатики им. А.П. Ершова; N 42/2).

5. Кадач A.B. Эффективные методы создания и передачи префиксных кодов. — Новосибирск, 1997. — 27 с. — (Препр. / Сиб. отд-ние РАН; Институт систем информатики им. А.П. Ершова; N 44).

S. Кадач A.B. Свойства кодов Хаффмана и эффективные алгоритмы декодирования префиксных кодов. — Новосибирск, 1997. — 44 с. — (Препр. / Сиб огд-нис РАИ; Институт систем информатики им. А.П. Ершова:

7 Кадач A.B. Сжатие текстов и гипертекстов // Программирование. —

1997 — X 4. С. 47-57.

Подписано в печать 29.12.1997 Объем 1.1 Формат бумаги 60×84 1/16

Объем 1.1 уч.-изд.л., 1.2 п.л.

Отпечатано на ризографе «AL Group» 330090, г. Новосибирск, пр. ак. Лаврентьева, 3.

Алгоритмы сжатия данных

Цель лекции: изучить основные виды и алгоритмы сжатия данных и научиться решать задачи сжатия данных по методу Хаффмана и с помощью кодовых деревьев.

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0,6 – 1,3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение .

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

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

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

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

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт , но он может быть битом, тритом <0,1,2>, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины), а если же допускаются слова разной длины, то – неравномерным (переменной длины).

Код – полное множество слов.

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

Фраза – фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – процесс сжатия данных.

Декодирование – обратный кодированию процесс, при котором осуществляется восстановление данных.

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.

Коэффициент сжатия – величина, обратная отношению сжатия.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

где – вероятности кодовых слов;

Существуют два основных способа проведения сжатия.

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

Словарное сжатие – это методы сжатия, хранящие фрагменты данных в «словаре» (некоторая структура данных ). Если строка новых данных, поступающих на вход, идентична какому-либо фрагменту, уже находящемуся в словаре, в выходной поток помещается указатель на этот фрагмент. Лучшие словарные методы применяют метод Зива-Лемпела.

Рассмотрим несколько известных алгоритмов сжатия данных более подробно.

Метод Хаффмана

Этот алгоритм кодирования информации был предложен Д.А. Хаффманом в 1952 году. Хаффмановское кодирование (сжатие) – это широко используемый метод сжатия, присваивающий символам алфавита коды переменной длины, основываясь на вероятностях появления этих символов.

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код , имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

  1. Определение вероятности появления символов в исходном тексте.

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

Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x , который имеет вероятность появления, равную сумме вероятностей появления символов a и b . Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x ). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Коды Хаффмана имеют уникальный префикс , что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Пример 1. Программная реализация метода Хаффмана.

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

Илон Маск рекомендует:  Как изменить цвет маркеров в списке
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL