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


Содержание

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

Вопрос 1. Количество информации и энтропия

Лекция №8. Сжатие данных

Вопросы

1. Может ли непрерывная на сегменте функция не принимать нулевого значения ни в одной точке сегмента? Ответ объяснить.

2. Может ли непрерывная на интервале функция не принимать нулевого значения ни в одной точке сегмента? Ответ объяснить.

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

4. Пусть функция определена и непрерывна на , а на концах сегмента принимает значения разных знаков. Вытекает ли из этого, что функция принимает нулевое значение в какой-то точке сегмента? Ответ объяснить.

5. Доказать первую теорему Больцано-Коши.

6. Доказать, не решая уравнение непосредственно, что уравнение обязательно будет иметь корень на сегменте .

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

8. Пусть функция определена на , а множество ее значений – это . Что можно сказать о непрерывности на ? Почему?

9. Доказать вторую теорему Больцано-Коши.

10. Доказать следствие из второй теоремы Больцано-Коши.

Вопросы:

1. Количество информации и энтропия. Методы сжатия данных.

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

Сжатие данных применяется для сокращения времени их передачи. Так как на сжатие данных передающая сторона тратит дополнительное время, к которому нужно еще прибавить аналогичные затраты времени на декомпрессию этих данных принимающей стороной, то выгоды от сокращения времени на пере­дачу сжатых данных обычно бывают заметны только для низкоскоростных кана­лов. Этот порог скорости для современной аппаратуры составляет около 64 Кбит/с. Многие программные и аппаратные средства сети способны выполнять динамичес­кое сжатие данных в отличие от статического, когда данные предварительно сжимаютмя (например, с помощью популярных архиваторов), а уже затем отсылаются в сеть.

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

Обычно применяются следующие алгоритмы сжатия данных.

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

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

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

Коды переменной длины. В этом методе кодирования используется тот факт, что не все символы в передаваемом кадре встречаются с одинаковой частотой. Поэтому во многих схемах кодирования коды часто встречающихся символов заменяют кодами меньшей длины, а редко встречающихся — кодами большей длины. Такое кодирование называется также статистическим кодированием. Из-за того, что символы имеют различную длину, для передачи кадра возможна только бит-ориентированная передача. При статистическом кодировании коды выбираются таким образом, чтобы при анализе последовательности бит можно было бы однозначно определить соответствие определенной порции бит тому или иному символу или же запрещенной комбина­ции бит. Если данная последовательность бит представляет собой запрещенную комбинацию, то необходимо к ней добавить еще один бит и повторить анализ. Например, если при неравномерном кодировании для наиболее часто встречающе­гося символа «Р» выбран код 1, состоящий из одного бита, то значение 0 однобит­ного кода будет запрещенным. Иначе можно будет закодировать только два символа. Для другого часто встречающегося символа «О» можно использовать код 01, а код 00 оставить как запрещенный. Тогда для символа «А» можно выбрать код 001, для символа «П» — код 0001 и т. п.

Неравномерное кодирование наиболее эффективно, когда неравномер­ность распределения частот передаваемых символов достаточно велика, как при передаче длинных текстовых строк. Напротив, при передаче двоичных данных, например кодов программ, оно малоэффективно, так как 8-битовые коды при этом распределены почти равномерно.

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

Многие модели коммуникационного оборудования, такие как модемы, мосты, коммутаторы и маршрутизаторы, поддерживают протоколы динамического сжатия, позволяющие сократить объем передаваемой информации в 4, а иногда и 8 раз. В таких случаях говорят, что протокол обеспечивает коэффициент сжатия 1:4 или 1:8. Существуют стандартные протоколы сжатия, например V.42bis также большое количество нестандартных, фирменных протоколов. Реальный коэффициент сжатия зависит от типа передаваемых данных, так, графические и текстовые данные обычно сжимаются хорошо, а коды программ — хуже.

Не нашли то, что искали? Воспользуйтесь поиском:

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 13.08.2013
Размер файла 118,3 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

HTML-версии работы пока нет.
Cкачать архив работы можно перейдя по ссылке, которая находятся ниже.

Подобные документы

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

курсовая работа [1,1 M], добавлен 17.03.2011

Особенности посылки сообщений в Windows и в Win32 API. Обработка состояний простоя. Маршрутизация сообщений в Windows 3.x. Основные циклы обработки сообщений. Применение многопотоковых приложений. Основные возможности редакторов WinWord 97 и Notepad.

лекция [35,9 K], добавлен 24.06.2009

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

курсовая работа [197,1 K], добавлен 20.02.2012

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

курсовая работа [1,1 M], добавлен 12.03.2009

Текстовый редактор — приложение для обработки текстовой информации. Описание текстовых процессоров как более совершенных текстовых редакторов. Типы текстовых файлов: форматированные, неформатированные. Основные правила редактирования и набора текста.

презентация [747,3 K], добавлен 26.11.2010

Технологическая схема системы. Структурно-функциональная модель обработки сообщений системой управления технологическим процессом. Поток сообщений в общем виде. Моделирование в среде GPSS и в среде C#, их результаты. Алгоритм имитационного моделирования.


курсовая работа [1,3 M], добавлен 14.12.2012

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

курсовая работа [1,0 M], добавлен 08.06.2020

Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.

практическая работа [188,5 K], добавлен 24.04.2014

Описание назначения всех команд меню WinRar. Создание и распаковывание архивов для текстовых, графических и системных файлов. Примеры создания архивов с опциями: пароль, многотомный и самораспаковывающийся архивы. Теоретические основы сжатия файлов.

контрольная работа [2,3 M], добавлен 07.07.2013

Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.

курсовая работа [487,3 K], добавлен 14.07.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

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

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

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

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

Что понимается под сжатием данных? Если говорить кратко, то сжатие устраняет из данных избыточность; в терминах же теории информации сжатие увеличивает энтропию сжатого текста. Однако оба этих утверждения по существу по существу верны в силу определения самих понятий. Избыточность может быть выражена в самых разных формах. Одним типом является последовательности повторяющихся битов ( 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).

Модели и алгоритмы контекстно-словарного сжатия текстовых данных : Применительно к системам электронного обучения

Содержимое

Оглавление
ВВЕДЕНИЕ.
ГЛАВА 1. АНАЛИЗ МЕТОДОВ СЖАТИИ ИНФОРМАЦИИ.
1.1. Предварительные замечания
1.2. Модели словарного сжатия.
1.3. Модели контекстного сжатия.
1.3.1. Модели с фиксированным контекстом
1.3.2. Контекстуальносмешанные модели
1.3.3. Вероятность ухода
1.3.4. Исключения.
1.3.5. Алфавиты.
1.4. Другие методы статистического моделирования.
1.4.1. Динамическое сжатие Маркова
1.4.2. Г рамматические модели.
1.4.3. Модели новизны.
1.4.4. Выводы по первой главе.
ГЛАВА 2. КОНТЕКСТНОСЛОВАРНЫЕ МОДЕЛИ СЖАТИЯ
2.1. Предварительные замечания
2.2. Сжатие текстовых файлов
2.3. Структурная модель представления сжатия текстовой информации .
2.4. Постановка задачи приведения к предложенной схеме
структурированного вида.
2.5. Модель сжатия использующий контекстнословарный метод
2.5.1. Модель хранения сжатого текста.
2.5.2. Древовидная модель словаря.
2.5.3. Модель словаря морфем
2.6. Выводы по второй главе.
ГЛАВА 3. АЛГОРИТМЫ КОНТЕКСТНОСЛОВАРНОГО СЖАТИЯ ДАННЫХ НА ОСНОВЕ ПРЕДЛОЖЕННЫХ МОДЕЛЕЙ.
3.1. Предварительные замечания
3.2. Приведение информации к структурированному виду
. 3.3. Преобразование словаря.
3.3.1. Разбиение слова на слоги
3.3.2. Разбиение на составные части слова
3.3.3. Древовидное представление структуры словаря.
3.4. Оценка построение структуры словаря от способа разложения слов.
3.5. Кодирование текста с использованием полученного словаря
3.5.1. Построение кодов переменной длины.
3.5.2. Применение кодирования контекстных индексов арифметического
кодирования
3.6. Оценка эффективности полученных кодов алгоритма кодирования с
помощью словаря
3.6.1. Стоимость кодирования текста
3.6.2. Оценка объема необходимой памяти
3.7. Управление распределением памяти.
3.8. Выводы по третьей главе
ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС КОНТЕКСТНОСЛОВАРНОГО СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ V I
4.1. Основные требования к техническому облику программного
комплекса V i .
4.2. Область применения программного комплекса
4.3. Проблемы существующих систем.
4.4. Задачи разработки программного комплекса.
4.5. Этапы разработки программного комплекса
4.6. Реализация блока сжатия файлов.
4.6.1. Реализация блока .
4.6.2. Реализация блока .
4.7. Сравнительная оценка эффективности.
4.7.1. Тестовые данные
4.7.2. Методика сравнения.
4.7.3. Результаты сравнения
4.8. Пример преобразования и кодирования слов.
4.9. Выводы по четвертой главе
ПРИЛОЖЕНИЕ 1
Листинг V.
ПРИЛОЖЕНИЕ 2.
Акт внедрения
Иллюстрации
Рис. 1 Модель сжатия реляционным словарем
Рис. 2 Модель сжатия динамическим словарем.
Рис. 3 Модель контекстного сжатия
Рис. 4 Операция клонирования в .
Рис. 5. Начальная модель ДМС с одним состоянием
Рис. 6. Более сложная начальная модель.
Рис. 7. Вероятностная грамматика для круглых скобок
Рис. 8 Структурная модель представления сжатия текстовой информации
Рис. 9 Модель сжатия контекстнословарного метода
Рис. Сравнение представления словарей.
Рис. Улучшенная модель представления словаря
Рис. . Модель сжатия текстового файла
Рис. Модель представления текста в естественных языках
Рис. Модель представления словаря после разбиения слов на слоги.
Рис. Модель программного комплекса V i .
Рис. Реализация блока сжатия текстового файла.
Рис. Реализация распаковки тестового файла
Рис. Результаты сравнения программ сжатия для тестового набора файлов.
Рис. График сравнения коэффициента сжатия от языковых особенностей
Введение
Актуальность

Доставим любую диссертацию от 2002 г. Для заказа напишите нам интересующую Вас тему и год защиты на почту: dissertation.com.ua@gmail.com

Поздравляем Вас с праздником весны.

Желаем чтобы в каждой ситуации вы чувствовали себя женщиной!

Желаем всем здоровья , счастья , творческих успехов!

Определения. Аббревиатуры и классификации методов сжатия

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

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

ASCII (American Standard Code for Information Interchange — Американский Стандартный Код для Обмена Информацией) каждому значению байта ставит в соответствие символ. Но чтобы построить однозначное соответствие для всех необходимых символов из множества национальных алфавитов народов мира, требуется больше: по крайней мере 16 битов на символ (что и обеспечивает стандарт Unicode ).

Множество всех различных символов, порождаемых некоторым источником, называется алфавитом, а количество символов в этом множестве — размером алфавита. Источники данных порождают только элементы, но физические источники информации — символы или элементы.

Размер алфавита таблицы ASCII равен , а Unicode — . Это две самые распространенные таблицы символов .

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

Можно говорить, что источник без памяти порождает «элементы», а источник данных с памятью — «слова», поскольку во втором случае

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

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

Кавычки показывают, что это условные названия способов интерпретации входных данных : «слова», «элементы», «биты».

По традиции бинарный источник без памяти называют обычно «источник Бернулли», а важнейшим частным случаем источника данных с памятью является «источник Маркова» (N-го порядка): состояние на i-ом шаге зависит от состояний на N предыдущих шагах: i-1, i-2,…, i-N .

Третья важнейшая применяемая при сжатии данных математическая модель — «аналоговый сигнал»:

  • данные считаются количественными;
  • источник данных считается источником Маркова 1-го порядка.

Если использовать модель » аналоговый сигнал » с N > 1 , то при малых N эффективность сжатия неизменна или незначительно лучше, но метод существенно сложнее, а при дальнейшем увеличении N эффективность резко уменьшается.

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

Еще две важных характеристики алгоритма сжатия — объемы памяти, необходимые для сжатия и для разжатия (для хранения данных, создаваемых и/или используемых алгоритмом).

Названия и аббревиатуры методов

CM (Context Modeling) — Контекстное моделирование

DMC (Dynamic Markov Compression) — Динамическое марковское сжатие (является частным случаем CM)

PPM (Prediction by Partial Match) — Предсказание по частичному совпадению (является частным случаем CM)

LZ-методы — методы Зива-Лемпела, в том числе LZ77, LZ78, LZH и LZW

PBS (Parallel Blocks Sorting) — Сортировка параллельных блоков

ST (Sort Transformation) — Частичное сортирующее преобразование (является частным случаем PBS)

BWT (Burrows-Wheeler Transform) — Преобразование Барроуза-Уилера (является частным случаем ST )

RLE (Run Length Encoding) — Кодирование длин повторов

HUFF (Huffman Coding) — кодирование по методу Хаффмана

SEM (Separate Exponents and Mantissas) — Разделение экспонент и мантисс ( Представление целых чисел)

UNIC (Universal Coding) — Универсальное кодирование (является частным случаем SEM )


ARIC (Arithmetic Coding) — Арифметическое кодирование

RC (Range Coding) — Интервальное кодирование (вариант арифметического)

DC (Distance Coding) — Кодирование расстояний

IF (Inverted Frequences) — «Обратные частоты» (вариант DC)

MTF (Move To Front) — «Сдвиг к вершине», «Перемещение стопки книг»

ENUC (Enumerative Coding) — Нумерующее кодирование

FT (Fourier Transform) — Преобразование Фурье

Илон Маск рекомендует:  Все про HyperText Transfer Protocol

DCT (Discrete Cosine Transform) — Дискретное Косинусное Преобразование, ДКП (является частным случаем FT)

DWT (Discrete Wavelet Transform) — Дискретное Вэйвлетное Преобразование, ДВП

LPC (Linear Prediction Coding) — Линейно-Предсказывающее Кодирование , ЛПК (к нему относятся Дельта- кодирование , ADPCM , CELP и MELP)

SC (Subband Coding) — Субполосное кодирование

VQ (Vector Quantization) — Векторное квантование

Алгоритмы сжатия: описание, основные приемы, характеристики

Сжатие является частным случаем кодирования, основной характеристикой которого является то, что результирующий код меньше исходного. Процесс основан на поиске повторений в информационных рядах и последующем сохранении только одного рядом с количеством повторений. Таким образом, например, если последовательность появляется в файле, как «AAAAAA», занимая 6 байтов, он будет сохранен, как «6A», который занимает только 2 байта, в алгоритме сжатия RLE.

История возникновения процесса

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

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

В 1977 году, Авраам Лемпель и Джейкоб Зив издали свой инновационный метод LZ77, использующий более модернизированный словарь. В 1978 году, та же команда авторов, издала усовершенствованный алгоритм сжатия LZ78. Который использует новый словарь, анализирующий входные данные и генерирующий статический словарь, а не динамический, как у 77 версии.

Формы исполнения компрессии

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

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

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

Преимущество алгоритмов сжатия:

  1. Значительно уменьшает объем памяти. При степени сжатия 2:1 файл в 20 мегабайт (МБ) займет 10 МБ пространства. В результате администраторы сети тратят меньше денег и времени на хранение баз данных.
  2. Оптимизирует производительность резервного копирования.
  3. Важный метод сокращения данных.
  4. Практически любой файл может быть сжат, но важно выбрать нужную технологию под конкретный тип файла. Иначе файлы могут быть «уменьшены», но при этом общий размер не изменится.

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

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

Алгоритм сжатия Хаффмана

Этот процесс, который можно использовать для «уменьшения» или шифрования.

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

Порядок создания алгоритмы сжатия данных:

  1. Просчитывают, сколько раз каждый символ повторяется в файле для «уменьшения».
  2. Создают связанный список с информацией о символах и частотах.
  3. Выполняют сортировку списка от наименьшего к наибольшему в зависимости от частоты.
  4. Преобразуют каждый элемент в списке в дерево.
  5. Объединяют деревья в одно, при этом первые два образуют новое.
  6. Добавляют частоты каждой ветви в новый элемент дерева.
  7. Вставляют новое в нужное место в списке, в соответствии с суммой полученных частот.
  8. Назначают новый двоичный код каждого символа. Если берется нулевая ветвь, к коду добавляется ноль, а если первая ветвь, добавляется единица.
  9. Файл перекодируется в соответствии с новыми кодами.
  10. Например характеристики алгоритмов сжатия для короткого текста:»ata la jaca a la estaca»
  11. Подсчитывают, сколько раз появляется каждый символ и составляют связанный список:» (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
  12. Заказывают по частоте от низшей к высшей: e (1), j (1), s (1), c (2), l (2), t (2), » (5), a (9)

Как видно, корневой узел дерева создан, далее назначаются коды.

И осталось только упаковать биты в группы по восемь, то есть в байты:

Всего восемь байтов, а исходный текст был 23.

Демонстрация библиотеки LZ77

Алгоритм LZ77 рассмотрим на примере текста«howtogeek». Если повторить его три раза, то он изменит его следующим образом.

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

Это идеальный пример, когда большая часть текста сжимается с помощью нескольких символов. Например, слово «это» будет сжато, даже если оно встречается в таких словах, как «этом», «их» и «этого». С повторяющимися словами можно получить огромные коэффициенты сжатия. Например, текст со словом «howtogeek», повторенным 100 раз имеет размер три килобайта, при компрессии займет всего 158 байт, то есть с 95% «уменьшением».

Это, конечно, довольно экстремальный пример, но наглядно демонстрирует свойства алгоритмов сжатия. В общей практике он составляет 30-40% с текстовым форматом ZIP. Алгоритм LZ77, применяется ко всем двоичным данным, а не только к тексту, хотя последний легче сжать из-за повторяющихся слов.

Дискретное косинусное преобразование изображений

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

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

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


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

Сжатие аудио работает очень похоже на сжатие текста и изображений. Если JPEG удаляет детали из изображения, которое не видны человеческим глазом, сжатие звука делает, то же самое для звуков. MP3 использует битрейт, в диапазоне от нижнего уровня 48 и 96 кбит/с (нижний предел) до 128 и 240 кбит/с (довольно хороший) до 320 кбит/с (высококачественный звук), и услышать разницу можно только с исключительно хорошими наушниками. Существуют кодеки сжатия без потерь для звука, основным из которых является FLAC и использует кодирование LZ77 для передачи звука без потерь.

Форматы «уменьшения» текста

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

Прогоны значений кодируются, как символ, за которым следует длина прогона. Можно правильно восстановить оригинальный поток. Если длина серии 15 января, 2020

Методы максимального неискажающего сжатия Текст научной статьи по специальности « Автоматика. Вычислительная техника»

Аннотация научной статьи по автоматике и вычислительной технике, автор научной работы — Богатов Роман Николаевич

В статье приводится обзор методов сжатия с точки зрения достижения наибольшей степени сжатия «типичных» даншх. Особое внимание уделено контекстному моделированию (КМ) и методам, использующим PPM (Prediction by Partial Match — предсказание по частичному совпадению), которые достигают наибольшей известной степени сжатия. Рассмотрены наиболее существенные недостатки КМ. Предложены три возможных пути повышения эффективности КМ: ассоциативное КМ, использование удаленных контекстов и двустороннее КМ.

Похожие темы научных работ по автоматике и вычислительной технике , автор научной работы — Богатов Роман Николаевич,

Текст научной работы на тему «Методы максимального неискажающего сжатия»

0 ж S s i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

— объем оперативной памяти, необходимой для разжатия.

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

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

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

При многопроходном сжатии производится пред1 варительный анализ всего объема данных с целью выявления их внутренней структуры, осуществления возможной декомпозиции, выбора модели для сжатия и настройки параметров модели. На последнем проходе на основе собранной статистики осуществляется сжатие данных с предварительным кодированием информации, необходимой для осуществления разжатия. Однопроходные методы сжатия не используют предварительного анализа всего объема данных. Сжатие осуществляется из априорного предположения о природе данных, и на основе уже обработанной части подстраиваются параметры модели (производится адаптация).В1981 годуй. Й. РиссанениГ. Г. Лангдон предложили называть такой подход универсальным кодированием и выделять в нем две функциональные составляющие, моделирование и кодирование, осуществляемые последовательно для сжатия каждого сообщения источника [ 1 ]. Модель, в конечном счете, является способом оценки вероятностей возможных значений следующего ожидаемого сообщения источника. Задачей кодера является, используя полученные от модели вероятности, построить для очередного сообщения сжатый код, максимально приближенный по числу бит к энтропии этого сообщения. После кодирования модель производит необходимую адаптацию, оценивает вероятности возможных значений следующего» сообщения, новое сообщение вместе с априорными оценками модели передается кодеру и кодируется, после чего цикл повторяется для каждого кодируемого сообщения. Такая последовательность обновления модели позволяет осуществить аналогичные действия при разжатии: на основании текущих оценок модели декодер производит восстановление значения сжатого сообщения, модель адаптируется и подготавливает декодер для принятия следующего сообщения. Только небольшая часть современных методов сжатия, обеспечивающих высокую степень сжатия типичных данных, не использует явного моделирования как функционально отделимого элемента, К ним относятся, в частности, методы, использующие ВШТ (см. далее в статье).

Для достижения максимальной степени сжатия требуется построение модели, адекватной источнику входных данных. Выбор способа кодирования промоделированных данных влияет на степень сжатия в меньшей степени. Так, например, в связке со словарным моделированием для повышения быстродействия часто используется равномерное кодирование (схемы 1X77, ЬгББ и др.). Разница в степени

сжатия по сравнению с методами, использующими оптимизированное кодирование (ЬХН, ЬгРв, 12С и др.), является гораздо меньшей величиной, чем в случае использования различных типов моделирования и одного метода кодирования [2,3].

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

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

■^Большинство методов КМ являются стохастическими, оценивающими вероятности значений следующего элемента данных на основе статистики по обработанной части и текущего контекста. Исключение составляют методы, использующие преобразование Барроуза-Уиллера (BWT, сокр. от англ. Burrows-Wheeler Transform), которое избавляет данные от контекстной избыточности с помощью сортировки. Среди стохастических методов могут быть выделены использующие явное взвешивание оценок текущих (активных) контекстов (взвешивание контекстного дерева или CWTöt англ. Context Tree Weighting, динамическое Марковское сжатие или DMC от англ. Dynamic Markov Compression и др.) и методы, использующие неявное взвешивание с помощью техники предсказания по частичному совпадению (РРМ, сокр. от англ. Prediction by Partial Match), обеспечивающие наибольшую известную степень сжатия типичных данных и получившие наибольшее распространение.

Суть классического РРМ, предложенного в 1984г. Дж. Г. Клэари (Cleary) и И. X. Уиттеном (Witten) [4), заключается в следующем. Пусть последними символами источника были. sk_3sk2sk, и имеется М контекстных моделей, предсказывающих значение следующего символа sk на основе статистики, накопленной по контекстам разной длины. Контекстная модель порядка т содержит словарь контекстов (цепочек символов) длины т, встречавшихся ранее более одного раза, и для каждого контекста — счетчики символов, которые ранее встречались следующими за ним. Для данного случая я!-тая модель обеспечит статистику по цепочкам вида sk_m. sk_2sk fx, встречавшимся ранее, отличающимися значением х. Кроме М контекстных моделей используются две условных модели нулевого и минус первого порядка. Модель нулевого порядка предсказывает значение sk на основе накопленных частот встретившихся символов; модель минус первого порядка полагает все возможные значения sk равновероятными.

Для оценки значения sk выбирается одна из М + 2 моделей, обладающая статистикой по текущему контексту, и предпринимается попытка закодировать sk на основе ее распределения вероятностей. В классическом варианте модели просматриваются, начиная со старших порядков. Если выбранная модель не может закодировать sk (такое значение в данном контексте не ожидалось), то кодируется код ухода, означающий необходимость использования другой модели. Если все М контекстных моделей и модель нулевого порядка выдадут код ухода, s, кодируется равномерным кодом в модели минус первого порядка.

Оценка вероятности ухода (ОВУ) является одной из ключевых проблем сжатия с использованием РРМ. Большинство известных методов априорной ОВУ (методы А, В [4], С, D [5], Р, X, ХС [3]) используют только три величины: С — частоту появления данного контекста ранее; S — кол-во различных символов, появлявшихся ранее после данного контекста и S»1 — кол-во различных символов, появлявшихся ранее после данного контекста только / раз. Большую точность дают адаптивные методы ОВУ, использующие повторную оценку ухода (SEE, сокр. от англ. Secondary Es-

cape Estimation), основанную на текущей статистике уходов. Адаптивные методы Z [6] Ч. Блума (Bloom) с вариациями,SEE-dl hSEE- i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

— специальная обработка кода конца строки (EOL removing; ЕОЕотангл. End Of Line);

— грамматический и лексический разбор (LIPT и StarNT [13], Lexical Attraction [14]).

Другой полезной дополнительной техникой является использование разреженных контекстов (sparse contexts), которые представляют собой последовательности сообщений, чередующихся с пустыми позициями в различных комбинациях, например, имеющих вид sm □ sm_2. s6 □ □ s3 □ s.1sv где m — длинна контекста; s. — фиксированные значения сообщений; символом □ отмечены свободные позиции. Разреженный контекст считается наступившим при совпадении всех фиксированных значений сообщений с сообщениями источника в тех же позициях. Статистика по разреженному контексту является суммарной статистикой по обыкновенным контекстам, попадающим подданный шаблон. Разреженные контексты используются в большинстве современных архиваторов, основанных на КМ, и позволяют «перешагивать» через сообщения-исключения, нарушающие текущие контекстные зависимости (например, коды EOL).

Однако древовидно-контекстные Марковские модели, лежащие в основе всех существующих методов стохастического КМ, имеют два существенных ограничения:

— условные вероятности учитывают влияние только непосредственно прилегающих к оцениваемому сообщению контекстов;

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

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

Илон Маск рекомендует:  Свойство flex-basis 0

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

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

ru.knowledgr.com

Динамическое сжатие Маркова (DMC) — алгоритм сжатия данных без потерь, развитый Гордоном Кормакком и Найджелом Хорспулом. Это использует прогнозирующую арифметику, кодирующую подобный предсказанию частичным соответствием (PPM), за исключением того, что вход предсказан один бит за один раз (а не один байт за один раз). DMC имеет хорошую степень сжатия и умеренную скорость, подобную PPM, но требует несколько большей памяти и широко не осуществлен. Некоторые недавние внедрения включают экспериментальный крюк программ сжатия Нанией Франческо Антонио, ocamyd Франком Швеллингером, и как подмодель в paq8l Мэттом Махони. Они основаны на внедрении 1993 года в C Гордоном Кормакком.

Алгоритм

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

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

bitwise арифметического кодера, такого как DMC есть два компонента, предсказатель и арифметический кодер. Предсказатель принимает строку ввода n-долота x = xx... x и назначает ему вероятность p (x), выраженный как продукт серии предсказаний, p (x) p (xx) p (xxx). p (xxx... x). Арифметический кодер поддерживает два высоких двоичных числа точности, p и p, представляя возможный диапазон для полной вероятности, что модель назначила бы на все последовательности лексикографически меньше, чем x учитывая части x, замеченного до сих пор. Сжатый кодекс для xp, самая короткая битовая строка, представляющая число между p и p. Всегда возможно найти число в этом диапазоне не больше, чем на один бит дольше, чем Шаннонский предел, зарегистрировать 1/p (x&#39). Одно такое число может быть получено из p, пропустив все тянущиеся биты после первого бита, который отличается от p.

Сжатие продолжается следующим образом. Начальный диапазон установлен в p = 0, p = 1. Для каждого бита предсказатель оценивает p = p (x = 0|xx. x) и p = 1 − p, вероятность 0 или 1, соответственно. Арифметический кодер тогда делит текущий диапазон, (p, p) в две части в пропорции к p и p. Тогда поддиапазон, соответствующий следующему биту x, становится новым диапазоном.

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

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

Модель DMC

Предсказатель DMC — стол, который наносит на карту (bitwise) контексты паре количества, n и n, представляя число нолей и, ранее наблюдаемых в этом контексте. Таким образом это предсказывает, что следующий бит будет 0 с вероятностью p = n/n = n / (n + n) и 1 с вероятностью p = 1 − p = n/n. Кроме того, у каждой записи в таблице есть пара указателей на контексты, полученные, прилагая или 0 или 1 направо от текущего контекста (и возможно пропуская биты слева). Таким образом никогда не необходимо искать текущий контекст в столе; достаточно поддержать указатель на текущий контекст и пройти по ссылкам.

В оригинальном внедрении DMC начальный стол — набор всех контекстов длины 8 — 15 битов, которые начинаются на границе байта. Начальное состояние — любой из 8-битных контекстов. Количество — числа с плавающей запятой, инициализированные к маленькой константе отличной от нуля такой как 0,2. Количество не инициализировано к нолю, чтобы позволить ценностям быть закодированными, даже если они не были замечены прежде в текущем контексте.


Моделирование — то же самое для сжатия и декомпрессии. Для каждого бита вычислены p и p, x долота закодирован или расшифрован, модель обновлена, добавив 1 количеству, соответствующему x, и следующий контекст найден, пересекая связь, соответствующую x.

Добавление новых контекстов

DMC, как описано выше эквивалентен модели контекста приказа 1. Однако нормально добавить более длинные контексты, чтобы улучшить сжатие. Если бы текущий контекст — A, и следующий контекст B пропустил бы биты слева, то DMC может добавить (клонируют) новый контекст C от B. C представляет тот же самый контекст как после добавления одного бита справа как с B, но не пропуская битов слева. Связь от A будет таким образом перемещена от B, чтобы указать на C. B и C и сделает то же самое предсказание, и оба укажут той же самой паре следующих состояний. Полное количество, n = n + n для C будет равно пункту обвинения n для (для входного x долота), и то количество будет вычтено из B.

Например, предположите, что штат A представляет контекст 11111. На входном бите 0, это переходит в государство Б, представляющее контекст 110, полученный, понижаясь на 3 бита слева. В контексте A, было 4 нулевых бита и некоторое число одного бита. В контексте B, было 3 ноля и 7 (n = 10), который предсказывает p = 0.7.

C клонирован от B. Это представляет контекст 111110. И B и C предсказывают, что p = 0.7, и оба идут в те же самые следующие состояния, E и F. Счет C является n = 4, равный n для A. Это оставляет n = 6 для B.

Государства клонированы только до того, чтобы переходить им. В оригинальном DMC условие для клонирования государства состоит в том, когда переход от до B является по крайней мере 2, и счет B является еще по крайней мере 2, чем это. (Когда второй порог будет больше, чем 0, он гарантирует, что другие государства все еще перейдут к B после клонирования). Некоторые внедрения, такие как крюк позволяют этим порогам быть установленными как параметры. В paq8l увеличиваются эти пороги, поскольку память израсходована, чтобы замедлить темп роста новых государств. В большинстве внедрений, когда память исчерпана, от модели отказываются и повторно инициализировала назад к оригинальной bytewise модели приказа 1.

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

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

  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 ; Просмотров: 1585 ; Нарушение авторских прав? ;

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

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

  • повторить и обобщить понятие о кодировании текстовой информации.

1. Организационный момент, проверка домашнего задания

2. Ознакомление учащихся с понятие «сжатие информации» на примерах (см. слайды №2 и №3).

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

3. Метод Шеннона-Фано (по презентации Приложение 2, см. слайды №№ 4-9)

Как мы уже видели при решении задач, информацию нельзя сжимать до бесконечности. То есть в какой-то момент должна появиться своего рода граница, при сжатии дальше которой восстановление информации неоднозначно или просто невозможно. То есть хотелось бы, чтобы выбранный нами способ кодирования был оптимальным: с одной стороны, чтобы обеспечивалось максимально возможное сжатие, с другой стороны, чтобы записанная таким образом информация не теряла свою полноту. Одним из методов, обеспечивающих такое оптимальное кодирование отдельных символов является метод Шеннона-Фано.
Суть метода состоит в следующем: пусть дан некоторый алфавит (конечный набор символов, который будет использован для написания текста). Пусть также дано сообщение. Какие-то символы в сообщении обычно встречаются чаще, какие-то – реже. Для часто используемых символов создадим более короткие коды, для реже используемых – длинные (слайд №4 – частота использования букв русского языка).
Для начала, в качестве повторения, оценим (например, по формуле Хартли) сколько бит необходимо отвести для записи кода одного символа, и создадим «обычные» коды равной длины (слайд №5).

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

Далее, разделим таблицу на две части, чтобы сумма долей всех символов в одной была как можно ближе к сумме долей всех символов другой. Пусть коды всех символов из первой части начинаются на 0, коды всех символов из второй – на 1 (слайд №7). Если в какой-то части находится более одного символа, то повторим для нее процесс деления, находя вторую, третью и так далее цифры кода. Как только для всех символов найдены коды – процесс завершен (слайды №8 и №9)
Осталось только подчитать количество бит, которые необходимы для представления сообщения в новом коде (слайд №10).

4. Закрепление пройденного материала, решение задач (слайд №11)

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL