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


Содержание

Алгоритмы сжатия и компрессии

Опрос

Новички

Контекстное моделирование

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

Пожалуй, наиболее простой способ оценки реализуется с помощью по­луадаптивного моделирования и заключается в предварительном подсчете безусловной частоты появления символов в сжимаемом блоке. Полученное распределение вероятностей используется для статистического кодирования всех символов блока. Если, например, такую модель применить для сжатия текста на русском языке, то в среднем на кодирование каждого символа бу­дет потрачено примерно 4.5 бита. Это значение является средней длиной кодов для модели, базирующейся на использовании безусловного распределения вероятностей букв в тексте. Заметим, что уже в этом простом случае достигается степень сжатия 1.5 по отношению к тривиальному кодированию, когда всем символам назначаются коды одинаковой длины. Действительно, размер алфавита русского текста превышает 64 знака, но меньше 128 знаков (строчные и заглавные буквы, знаки препинания, пробел), что требует 7-битовых кодов.

Анализ распространенных типов данных, — например, тех же текстов на естественных языках, — выявляет сильную зависимость вероятности появ­ления символов от непосредственно им предшествующих. Иначе говоря, большая часть данных, с которыми мы сталкиваемся, порождается источни­ками с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, строка из трех только что обра­ботанных символов равна «_цы» (подчеркиванием здесь и далее обозначает­ся пробел), то текущий символ скорее всего входит в следующую группу: «г» («цыган»), «к» («цыкать»), «п» («цыпочки»), «ц» («цыц»). Или, в случае анализа фазу нескольких слов, если предыдущая строка равна «Вста-вай,_проклятьем_заклейменный,», то продолжением явно будет «весь_мир_». Следовательно, учет зависимости частоты появления символа (в общем случае — блока символов) от предыдущих должен давать более точные оценки и в конечном счете лучшее сжатие. Действительно, в случае посим­вольного кодирования при использовании информации об одном непосред­ственно предшествующем символе достигается средняя длина кодов в 3.6 бита для русских текстов, при учете двух последних — уже порядка 3.2 бита. В первом случае моделируются условные распределения вероятностей сим­волов, зависящие от значения строки из одного непосредственно предшест­вующего символа, во втором — зависящие от строки из двух предшествую­щих символов.

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

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

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

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

Если длина контекста ограничена, то такой подход будем называть кон­текстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых кон­текстов N. Например, при моделировании порядка 3 для последнего симво­ла «о» в последовательности «. молоко. » контекстом максимальной длины 3 является строка «лок». При сжатии этого символа под «текущими контек­стами» могут пониматься «лок», «ок», «к», а также пустая строка «». Все эти контексты длины от N до 0 назовем активными контекстами в том смысле, что при оценке символа может быть использована накопленная для них сть тистика.

Далее вместо «контекст длины о, о N , где q — размер алфавита обрабатываемой последовательности. КМ(0) и КМ(-1) всегда ак­тивны.

Заметим, что часто не делается различий между понятиями «контекст» и «контекстная модель». Авторы этой книги такое соглашение не поддержи­вают.

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

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

ВИДЫ КОНТЕКСТНОГО МОДЕЛИРОВАНИЯ

Пример обработки строки «абсабвбабс» иллюстрирует сразу две пробле­мы контекстного моделирования:

■ как выбирать подходящий контекст (или контексты) среди активных с целью получения более точной оценки, ведь текущий символ может лучше предсказываться не контекстом 2-го порядка «аб», а контекстом 1-го порядка «б»;

■ как оценивать вероятность символов, имеющих нулевую частоту (на­пример, «г»).

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

Если в модели используются для оценки только КМ(ЛО, то иногда такой подход называют «чистым» (pure) контекстным моделированием порядка N. Из-за вышеуказанного недостатка «чистые» модели представляют обычно только научный интерес.

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

Рассмотрим модель произвольного порядка N. Если q(si\o) есть вероят­ность, присваиваемая в активной КМ(о) символу j, алфавита сжимаемого потока, то смешанная вероятность q(si) вычисляется в общем случае как

где w(o) — вес оценки КМ(о).

Оценка q(Sj\o) обычно определяется через частоту символа s,- по триви­альной формуле

rnfiJ[si\o) — частота появления символа st в соответствующем контексте по­рядка о; До) — общая частота появления соответствующего контекста поряд­ка о в обработанной последовательности.

Заметим, что правильнее было бы писать не, скажем, Ду/|о), иДз^С^), т. е. «частота появления символа S/ в КМ порядка о с номером До)», по­скольку контекстных моделей порядка о может быть огромное количество. Но при сжатии каждого текущего символа мы рассматриваем только одну КМ для каждого порядка, так как контекст определяется непосредственно примыкающей слева к символу строкой определенной длины. Иначе говоря, для каждого символа мы имеем набор из N+1 активных контекстов длины от N до 0, каждому из которых однозначно соответствует только одна КМ, если она вообще есть. Поэтому здесь и далее используется сокращенная за­пись.

Если вес w(-l) > 0, то это гарантирует успешность кодирования любого символа входного потока, так как наличие КМ(-1) позволяет всегда получать ненулевую оценку вероятности и, соответственно, код конечной длины.

Различают модели с полным смешиванием (fully blended), когда предска­зание определяется статистикой КМ всех используемых порядков, и с час­тичным смешиванием (partially blended) — в противном случае.

Рассмотрим процесс оценки отмеченного на рисунке стрелкой символа

«л», встретившегося в блоке «молочноемолоко». Считаем, что модель рабо­тает на уровне символов.

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

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

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

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

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 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-файлы представлены только в архивах.
Рекомендуем скачать работу.

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

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

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

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

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

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

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бит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

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

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

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

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

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

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

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—) ;

Сжатие текстовых данных Текст научной статьи по специальности « Общие и комплексные проблемы естественных и точных наук»

Похожие темы научных работ по общим и комплексным проблемам естественных и точных наук , автор научной работы — Петрянин Д.Л., Юрков Н.К.,

Текст научной работы на тему «Сжатие текстовых данных»

Петрянин Д.Л., Юрков Н.К

Пензенский государственный университет

СЖАТИЕ ТЕКСТОВЫХ ДАННЫХ

Архиватор — программа, осуществляющая сжатие и/или упаковку одного и более файлов в архив или серию архивов, для удобства переноса или хранения, а также распаковку архивов.

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

Архивация все чаще используется при передаче данных через локальные сети или/и сети Интернет, для экономичности трафика и времени передачи.

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

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

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

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

Сжатие текстовых данных обычно происходит намного быстрее, чем остальных типов данных.

Проведем эксперимент: произведем сжатие 4 распространенных текстовых типов данных: TXT, DOCX, DOC и RTF. В каждый из данных файлов будет находиться один и тот же текст (малого объема — 135 слов (1054 знака), без форматирования) . Количество используемых архиваторов: 11 (RAR, 7z, ZIP, ARJ, UC2, GZ, LHA (LZH), TGZ, DST, RK и CAB) . Результаты сжатия по размерам приведены в таблице 1, а по времени сжатия — в таблице 2.

Таблица 1 Результаты сжатия по размерам (в байтах)______________________

Файл TXT DOCX DOC RTF

Размер файла 1058 10951 28160 37582

RAR 612 8443 6006 7134

7z 726 8435 5601 7402

zip 841 8623 6311 8349

ARJ 688 8466 6219 8351

UC2 1555 1041 7209 9265

GZ 592 8370 5883 7534

LZH 610 8390 6115 8294

TGZ 841 8632 6359 8592

DST 616 8350 5983 7642

RK 640 9120 5956 7684

CAB 723 8464 5979 8053

Min размер 592 1041 5601 7134

Выбранный архиватор GZ UC2 7z RAR

Таблица 2 Результаты сжатия по времени сжатия (в мс)

Файл TXT DOCX DOC RTF

Размер файла 1058 10951 28160 37582

RAR 78 469 124 93

zip 45 469 31 63

ARJ 46 108 78 46

UC2 297 312 295 282

GZ 31 61 78 124

LZH 31 78 46 46

TGZ 46 62 63 45

DST 79 124 92 141

CAB 93 218 93 110

Min время 31 47 31 45

Выбранный архиватор GZ/LZH 7z zip TGZ

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

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

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

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

Рис. 1 Распределение русских букв по их частоте использования

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

Файлы документов MS WinWord с расширением DOC представляют собой сложные объекты, организованные по правилам структурированного хранилища. Внутри составной файл состоит из следующих элементов:

«хранилища», а на самом деле это просто внутренние каталоги, описывающие состав и расположение других объектов внутри составного файла;

«потоки», а на самом деле это своего рода файлы, массивы структурированной информации, имеющие собственное имя;

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

Формат DOCX предполагает сжатие, и сам по себе является ZIP-архивом, внутри которого содержатся собственно текстовый документ в виде XML, графика и файлы, определяющие свойства документа и отношения между содержимым контейнера. Сжатие определяет и одно из основных отличий между форматами DOC и DOCX — размер файла в последнем случае несколько меньше. [4]

В RTF для обмена документами используются только представимые символами коды из ASCII-, MAC- и PC-символьного набора. Документы RTF состоят преимущественно из команд управления настройки программы чтения файлов в данном формате. Эти команды можно разделить на управляющие слова и управляющие символы (рис. 2). Конец каждой команды отмечается одним из разделяющих символов (чаще всего — точкой с запятой). [5] Так как файл состоит из данных команд и отсутствует какое-либо

внутреннее сжатие, то документ будет занимать большее физическое пространство (на носителе) .

0x0310 3530 3230 3330 347D 5469 6D65 7320 4Е65

0x0320 7720 526F 6D61 6ЕЗВ 7D0D 0А7В 5С66 6C6F

0x0330 6D69 6E6F 725С 6633 3135 3034 5С66 6269


0x0340 6469 2 05С 6672 6F6D 616Е 5С66 6368 6172

0x0350 7365 7432 3034 5С66 7072 7132 7В5С 2А5С

0x0360 7061 6E6F 7365 2030 3230 3230 3630 3330

0x0370 3530 3430 3530 3230 3330 3 47D 5469 6D65

0x0380 7320 4Е65 7720 526F 6D61 6ЕЗВ 7D7B 5С66

0x0390 6462 6D69 6E6F 725С 6633 3135 3035 5С66

ОхОЗАО 6269 6469 2 05С 6672 6F6D 616Е 5С66 6368

0x03В 0 6172 7365 7432 3034 5С66 7072 7132 7В5С

ОхОЗСО 2А5С 7061 6E6F 7365 2030 3230 3230 3 63 0

0x03D0 3330 3530 3430 3530 3230 3330 347D 5469

ОхОЗЕО 6D65 7320 4Е65 7720 526F 6D61 6ЕЗВ 7D0D

Рис. 2 Фрагмент документа RTF в шестнадцатеричной форме (HEX)

TXT-файл представляет собой последовательность символов в одной из пяти кодировок: ANSI, UTF-8, Unicode, Unicode Big Endian, OEM. Каждый символ из используемого набора символов кодируется в виде одного байта, а иногда в виде последовательности подряд идущих двух, трёх и т.д. байтов.

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

Текстовым файлам противопоставляются двоичные (бинарные) файлы, в которых информация

организована по иным принципам. [б] Поэтому данный документ имеет наименьший размер.

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

1. Батьков, В.О. Анализ проблем современных хранилищ данных / В.О. Батьков // Труды

международного симпозиума Надежность и качество. 2013. Т. 1. С. 259-260.

2. Петрянин, Д.Л. Анализ систем защиты информации в базах данных / Д.Л.Петрянин, Н.В.Горячев, Н.К. Юрков // Труды международного симпозиума Надежность и качество. 2013. Т. 1. С. 115-121.

3. Внутренний формат документов MS WORD — http://uinc.ru/articles/39/

[MS-DOCX]: Word Extensions to the Office Open XML (.docx) File Format —

Сжатие информации: как это делается

Мы каждый день пользуемся различными архиваторами: zip, rar, ace окружают нас повсюду.
Графические и звуковые файлы тоже содержат сжатые данные. Если же нам нужно использовать
сжатие в своей проге, то мы используем различные dll’ки, многие из которых платные.
Шареварность — это не единственное свойство программных компонентов, мешающих их нормальному
использованию. Если, например, сжимать waw или bmp-файл архиватором, то
он будет значительно уступать специальному методу для конкретного типа данных, т.е.
метод должен учитывать особенности конкретного типа данных. Поэтому полезно уметь реализовывать сжатие самостоятельно.
В этой статье я расскажу, как вообще сжимать информацию и рассмотрю один из методов сжатия.

Классификация методов сжатия

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

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

Методы сжатия делятся на статистические и словарные. Словарные методы заключаются в том,
чтобы в случае встречи подстроки, которая уже была найдена раньше, кодировать ссылку, которая
занимает меньше места, чем сама подстрока. Классическим словарным методом является метод
Лемпела-Зива (LZ). Все используемые на сегодняшний день словарные методы являются лишь
модификациями LZ.

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

Отметим один момент, который почему-то неочевиден для некоторых «теоретиков».
Правило кодирования определяется вероятностной структурой данных, а значит, декомпрессор
должен до начала раскодирования уже знать её. Если же мы получаем её из статистики конкретного
сообщения (так оно сжимается лучше), то её придется передать явно или неявно вместе со сжатым
сообщением, и еще неизвестно, будет ли общий размер меньше.

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

H = -Sum(p[i] * log(p[i]))

где Sum — сумма по i, p[i] — вероятность i-го сообщения, log — логарифм по основанию 2.
Энтропия сложного сообщения равна сумме энтропий входящих в него простых сообщений.

Если кодировать каждый символ отдельно, то длина кода каждого сообщения должна быть
равна -log(p). Т.е., например, если вероятность символа 0.3, то его код должен иметь длину
1.73 бита, в то время, как реальные длины целые. Можно улучшить результаты, если не сводить
задачу к кодированию отдельных символов.

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

новая_нижняя_граница = нижняя_граница + ширина * S[i]
новая_ширина = ширина * p[i]

где p[i] — вероятность i-го символа, S[i] — сумма вероятностей символов с номерами
меньше i.

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

Проект, прикрепленный к этой статье, компилируется на Visual Studio .NET.
Это реализация арифметического кодирования, сжимающая файлы, рассматривая байты как символы.
Содержимое файла рассматривается как марковский процесс 1-го порядка, т. е. распределение
вероятностей символов зависит от предыдущего символа. Класс CMarkovProcessDef обрабатывает
данные, сохраненные в ресурсе в специальном формате. Эти данные сгенерированы по результатам
обработки большого количества текстов, т. е. текстовые файлы, скорее всего, будут сжиматься
хорошо, а если попытаться сжать какой-нибудь бинарник, то размер «сжатого» файла будет больше
исходного. Для того, чтобы получить метод сжатия для своего типа данных, нужно заменить данные о
вероятностях символов. Кроме того, символ — это не обязательно байт несжатых данных. Например,
если есть столбец таблицы, где значения должны быть уникальными, то каждое значение — это
символ, а после того, как символ встречается, сбрасываем его вероятность в ноль. Нижняя граница и ширина интервала хранятся в целочисленных переменных dwBuf1 и dwBuf2.
Если после обработки очередного символа старшие байты границ окажутся равными
(заметим, что это не то же самое, что если старший байт ширины равен нулю), то
соответствующий байт окончательного результата будет равен этому значению, и его можно
записать в файл. Запишем его и сдвинем буферы на 1 байт. При распаковке кроме переменных, обрабатываемых так же, как при упаковке, нам
понадобится еще одна, где будет информация из файла. Для того, чтобы определить очередной символ, нужно
найти символ с наименьшим номером, такой, что S[n] * dwBuf2 >= dwBuf3, т.е. P[n] >= dwBuf3 / dwBuf2. При работе с целыми числами возникает проблема: мы представляем вероятности (дробные
числа от 0 до 1) целочисленными переменными (0x100000000 * p). Для умножения и деления на них нужны
особые процедуры: при умножении берем старшее 32-битное слово 64-битного результата, а при делении
делим число, умноженное на 2^32. Компилятор не может, умножитв DWORD на DWORD, поместить результат
в 64-битную переменную — это недостаток языка С++. Поэтому пришлось написать специальные процедуры
на ассемблере.

void CArithmCompressorDlg::OnBnClickedCompress()
<
CFileDialog dlg1(TRUE);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE, «compressed», 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, «*.compressed|*.compressed|All files|*.*||»);
if (dlg2.DoModal() != IDOK) return;

CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);

BYTE b;
ULONGLONG fs = file1.GetLength();

file2.Write(&fs, 8); // Запишем размер исходного файла

// m_mpd — это объект класса CMarkovProcessDef
m_mpd.ResetProcess(); // Сбросим данные о предшествующих символах

// Здесь начинается сжатие
// Начальный интервал — от 0x00000000 до 0xFFFFFFFF
DWORD dwBuf1 = 0; // Нижняя граница
DWORD dwBuf2 = 0xFFFFFFFF; // Ширина
DWORD dww; // Временная переменная

Замените эту функцию на свою реализацию и получите метод сжатия для вашего типа данных.
*/
dwBuf1 += dww;
if (b Если старший байт буфера определен
<
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем его
dwBuf1 = dwBuf1 И сдвигаем буфер
dwBuf2 = dwBuf2 PushSymbol(b, 0) перемещает внутренний указатель на распределение для следующего символа
*/
m_mpd.PushSymbol(b, 0);
>
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем последний байт
// Вот и всё
// Закрываем файлы
file1.Close();
file2.Close();
>

void CArithmCompressorDlg::OnBnClickedDecompress()
<
CFileDialog dlg1(TRUE, «compressed», 0, 0, «*.compressed|*.compressed|All files|*.*||»);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE);
if (dlg2.DoModal() != IDOK) return;

CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);

if (file1.Read(&fs, 8) != 8) return; // Читаем длину извлекаемого файла

DWORD dwBuf1 = 0, dwBuf2 = 0xFFFFFFFF, dwBuf3, dww;

// Читаем первые 4 байта
// Нужно поместить байты в переменную не в том порядке, в каком они в файле,
// поэтому читаем их по отдельности
for (int j = 3; j >= 0; j—) if (file1.Read(((LPBYTE)&dwBuf3)+j, 1) == 0) ((LPBYTE)&dwBuf3)[j] = 0xFF;

// Поиск методом половинного деления
do
<
m = (l+h)/2;
if (h Вычисляем новый интервал
if (m > 0) dww = MulHigh(m_mpd.GetDistribution(m-1), dwBuf2); else dww = 0;
dwBuf1 += dww;
dwBuf3 -= dww;
if (m Пишем символ
m_mpd.PushSymbol(m, 0);

DWORD CArithmCompressorDlg::MulHigh(DWORD dw1, DWORD dw2)
<
/*
Эта функция возвращает старшее двойное слово
произведения данных двойных слов
*/
DWORD r;
_asm
<
mov eax, dw1;
mul dw2;
mov r, edx;
>
return r;
>

DWORD CArithmCompressorDlg::DivLarge(DWORD hi, DWORD lo, DWORD dw)
<
/*
Эта функция делит 64-битное беззнаковое целое (hi;lo)
на 32-битное
*/
DWORD r;
_asm
<
mov eax, lo;
mov edx, hi;
div dw;
mov r, eax;
>
return r;
>

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

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-программы не отвечают требованиям необходимым для совершенной работы за компьютером. К тому же последнее время де-факто стало требованием, что бы в состав программного обеспечения ко всем компьютерам входили программные продукты, которые могли бы работать с архивами.

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

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

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 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. Программная реализация метода Хаффмана.

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

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

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

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

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

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

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

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

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

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

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

Илон Маск рекомендует:  Псевдоэлемент -ms-check
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL