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


Содержание

АЛГОРИТМЫ СЖАТИЯ

Методы сжатия данных можно разделить на два типа:

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

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

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

Кроме того, можно выделить:

  • методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
  • специальные (special) методы сжатия, которые ориентированны на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

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

Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма сжатия данных являются:

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

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

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

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

Надежность программ и сложность алгоритмов

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

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

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

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

Современные методы сжатия

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

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

Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.

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

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

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

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

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

Обычно для ускорения поиска совпадающих подстрок и ограничения объема требуемой памяти область поиска ограничивается определенным количеством последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).

Алгоритмы семейства LZ77 в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.

Огромное преимущество алгоритмов семейства LZ77 – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда Декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).

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

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

Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.

По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ77, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.

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

Методы энтропийного кодирования

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

Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.

Префиксные коды

Префиксные коды называются так потому, что ни одно кодовое слово не является полным началом (т. е. префиксом) никакого другого слова, что гарантирует однозначность декодирования.

Известно много способов построения префиксных кодов: коды Шеннона и Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.

Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах малой мощности (2-8 символов) или при наличии символов с очень большой (более 30-50%) вероятностью появления и по качеству сжатия могут уступать арифметическим.

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

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

Арифметические коды

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

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

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

Арифметические коды обычно применяются в сочетании с методами статистического моделирования для кодирования символов в соответствии с предсказанными вероятностями.

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

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

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

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

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

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

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

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

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

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

Сравнение степени сжатия популярных архиваторов

Эта работа была прислана на наш «бессрочный» конкурс статей и является значительно переработанным вариантом статьи «Краткое сравнение архиваторов» того же автора. Работа получила приз — видеокарту Chaintech GeForce FX 5600XT 128 МБ>, предоставленную для нашего призового фонда компанией Chaintech.

реклама

Главной целью этой статьи является выбор наиболее оптимального архиватора с высокой степенью сжатия различных реальных данных большого объёма. В тестировании принимали участие: самый распространенный и один из старейших ZIP, популярные архиваторы ACE, RAR, 7-zip. Кроме того, были протестированы некоторые перспективные архиваторы. Большинство из них являются экспериментальными, обладают низкой скоростью архивирования и разархивирования, требуют много оперативной памяти, имеют ошибки. Например, не удалось сжать все тестовые данные при помощи Slim 0.021 (ошибка приложения), показавшего очень хорошие результаты, скорость PAQ6 v2 достигала 15 КБ/с. В итоге были выбраны Compressia 1.0b, EPM r9, PAQ6 v2, RKC 1.02, которые на данный момент являются одними из лучших.

реклама

Каждый из протестированных архиваторов обладает рядом настроек, изменяя которые, можно управлять степенью сжатия и скоростью в широких пределах. Тестирование производилось в режимах norm и max. RAR дополнительно тестировался в режиме fastest (максимальной скорости). Compressia, EPM, RKС, PAQ6 — только в режиме max. Для режима norm выбирались предлагаемые средние установки, для режима max – дающие максимальную степень сжатия. Все дополнительные настройки устанавливались в значения, дающие в среднем лучшее сжатие на тестовой системе, или, если возможно, в авто. В частности, 7-zip, EPM r9, RKC 1.02, PAQ6 v2 настраивались на использование около 400 МБ оперативной памяти в max режимах. Для режима fastest все настройки устанавливались на максимальную скорость, фильтры отключались, параметр Sol >

реклама

В качестве тестовых данных использовались большие объемы реальных неоднородных данных. Исключение составляет «Документы Word, Excel». Больше 9 МБ реальных «средних» документов найти не удалось, а тестировать документы по 13 МБ, в основном состоящие из отсканированных и несжимаемых изображений, неправильно. Дополнительно была добавлена книга TICSharp.DOC (11 МБ) с небольшими иллюстрациями.

реклама

Тестировались следующие архиваторы:

реклама

Использовался встроенный в Total Commander 6.0 архиватор. Несмотря на то, что Total Commander является shareware, сам формат ZIP бесплатный. Существует много бесплатных программ, которые архивируют в формат ZIP, например 7-zip. Стоит отметить, что каждая реализация ZIP может иметь скорость и степень сжатия, отличающуюся от реализации ZIP в Total Commander 6.0. Например, 7-zip архивирует в ZIP с более высокой степенью сжатия, но значительно медленнее.

В Total Commander 6.0 также есть поддержка формата TGZ (настройка Packer TGZ) который является своеобразным Solid (непрерывным архивом) вариантом ZIP (GZIP). Использование TGZ может дать значительное улучшение сжатия на большом количестве небольших файлов (на тестовых данных «Текст в формате HTML» — 60% от ZIP norm), но обладает таким недостатком — Total Commander 6.0 видит архив TGZ как заархивированный TAR, в результате для распаковки необходимо сначала распаковать TAR, а затем уже содержимое архива. По скорости и степени сжатия одного файла TGZ равен ZIP norm.

Настройки для тестирования:

  • ZIP norm – настройка normal compression (6).
  • ZIP max – настройка maximum compression (9).

ACE 2 www.winace.com . До выхода RAR 2.9 был существенно лучше RAR 2.0. Преимущества – высокая функциональность, степень сжатия и скорость. Недостатки – платный.

Использовался WinACE 2.5. Настройки для тестирования:

    ACE norm – настройка Level=normal, Sol >RAR 2.9www.rarlab.com. Преимущества – высокая функциональность, степень сжатия и скорость, распространённость. Недостатки – платный.

Использовался WinRAR 3.30 beta 5. По сравнению с предыдущей версией 3.11 степень сжатия незначительно увеличилась на всех видах данных, для текста прирост немного больше (вероятно, из-за улучшения в автоматическом определении параметров сжатия).

Настройки для тестирования:

    RAR fastest – настройка Compression method=fastest, Sol >7-zip 3.12 www.7-zip.org . Преимущества – высокая степень сжатия, бесплатность. Недостатки – низкая функциональность по сравнению с RAR. Для 7zip PPMd скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования.

Использовался 7-zip 3.12. Настройки для тестирования:

    7zip norm – настройка Compression level=normal, Compression method=LZMA, Dictionary=2 МБ, Word size=32, Sol >Compressiawww.compressia.com. Преимущества – один из самых лучших по степени сжатия архиваторов. Недостатки – сильно ограниченная функциональность, только GUI версия, низкая скорость, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования, платный.

Использовался Compressia v1.0 beta. Настройки для тестирования:

    Compressia – настройки Use sol >EPM www.thepipe.kiev.ua . Преимущества – один из самых лучших по степени сжатия архиваторов. Недостатки – низкая скорость, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования, для высокой степени сжатия необходимо относительно много оперативной памяти.

Использовался EMP r9. EMP r9 — это не полноценный архиватор, а экспериментальная версия для отработки алгоритмов, сжимает только один файл. Для тестирования использовались тестовые данные, скомпонованные в один файл при помощи 7-zip store. Из-за этого степень сжатия могла немного ухудшиться по сравнению с полноценной реализацией Solid режима (в пределах пары процентов).

Настройки для тестирования:

  • EMP max – параметры командной строки -m420.

RKC www.msoftware.co.nz. Преимущества – один из самых лучших по степени сжатия архиваторов. Недостатки – низкая скорость, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования, для высокой степени сжатия необходимо относительно много оперативной памяти. В конце февраля 2004 ожидается выход полноценного архиватора WinRK.

Использовался RKC 1.02. RKC 1.02 — это не полноценный архиватор, а экспериментальная версия для отработки алгоритмов, сжимает только один файл. Для тестирования использовались тестовые данные, скомпонованные в один файл при помощи 7-zip store. Из-за этого степень сжатия могла немного ухудшиться по сравнению с полноценной реализацией Solid режима (в пределах пары процентов). Опция analysis выключена, т.к. при её включении на некоторых данных программа не работает.

Настройки для тестирования:

  • RKC max – параметры командной строки -M420m -mxx -o16 -n+ -r+ -a-.

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

Использовался PAQ6 v2. PAQ6 v2 — это не полноценный архиватор, а экспериментальная версия для отработки алгоритмов, может сжимать несколько файлов. Для тестирования использовались тестовые данные, скомпонованные в один файл при помощи 7-zip store. Из-за этого степень сжатия могла немного ухудшиться по сравнению с полноценной реализацией Solid режима (в пределах пары процентов).

Настройки для тестирования:

  • PAQ6 max – параметры командной строки -7.

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

  • Документы Word, Excel – набор небольших документов (договоры, акты – 9 МБ) и книга TICSharp (11 МБ). Книга TICSharp является «неудобной» для архиваторов. Это обусловлено характерной структурой DOC файла — текстовые блоки чередуются с несжимаемыми картинками. Всего 20 МБ, 138 файлов.
  • Текст в формате HTML – содержимое JAVA SDK 1.3.1. Представляет собой большое количество небольших файлов HTML, поэтому ZIP, не поддерживающий Solid режим, показал почти в 2 раза худший результат. Этот набор данных не является полноценным текстом, т. к. содержит много тэгов HTML и пару мегабайт несжимаемых файлов. Всего 109 МБ, 6226 файлов.
  • Инсталляция Office XP – содержимое инсталляционного файла CAB. Около 120 МБ занимают файлы EXE, DLL, OCX. Всего 391 МБ, 1865 файлов
  • Игра Counter-Strike – содержимое папки Half-Life с установленным Counter-Strike. Всего 770 МБ, 3113 файлов.
  • База данных 1С: Предприятие – содержимое резервной копии базы данных (DBF-формат без индексов, с конфигурацией). Всего 189 МБ, 340 файлов.

Тестирование производилось на системе: CPU Athlon 2000 МГц, MB nForce2, RAM 512 МБ, HDD WD400JB, OS Windows 2000. Следует учитывать, что на аналогичных Pentium системах скорость сжатия может сильно отличаться.

Что можно архивировать?

Хорошо сжимаются почти все предварительно не сжатые данные, например, программные файлы, тексты, базы данных, простые несжатые изображения. Ограниченно сжимаются несжатый звук (WAV), сложные несжатые изображения (BMP). Не сжимаются (сжатие в пределах пары процентов за счет служебных тэгов и, возможно, небольшой избыточности) почти все уже сжатые данные, например, архивы (ZIP, CAB), сжатая графика и видео (JPG, GIF, AVI, MPG), сжатый звук (MP3).

Для примера можно рассмотреть папку с игрой Prince Of Persia. Из общего объема 1400 МБ, 550 МБ — это несжимаемое видео, 330 МБ — ограниченно сжимаемый звук. Игра сжимается до 1008 МБ. При сжатии разными архиваторами, разница будет только за счет сжимаемых 520 МБ, в меньшей степени за счет 330 МБ звука. Таким образом, относительные результаты будут «смазаны» несжимаемым видео.

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

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

RAR и ACE приблизительно равны, с небольшим преимуществом у RAR. Их можно рекомендовать только из-за дополнительной функциональности (например, разбивка архива на части, запись дополнительной информации для восстановления при повреждении архива). По степени сжатия они уступают 7-zip. На некоторых наборах данных разница значительна. В max режиме размер архива RAR больше 7-zip от 5% до 34%, в среднем на 18%.

7-zip не является лидером в степени сжатия и имеет низкую скорость в max режиме. По сравнению с PAQ6, размер архива 7-zip больше от 2% до 23%, в среднем на 13%. Разница с результатами Compressia, EPM, RKC незначительна или даже отличается в лучшую сторону. В отличие от этих архиваторов, скорость разархивирования 7-zip (за исключением режима PPMd) значительно выше скорости архивирования. Требования к оперативной памяти во время разархивирования небольшие. Низкая скорость в max режиме все же значительно выше, чем скорость PAQ6 (в 10 раз). 7-zip может работать, используя 2 потока, что даёт значительное повышение скорости на мультипроцессорных системах или на системах с Hyper-Threading. С учетом регулярного обновления и бесплатности, 7-zip является наиболее оптимальным выбором для современных систем. В списке ближайших его изменений – разбивка архива на части, запись дополнительной информации для восстановления при повреждении архива.

Из перспективных архиваторов стоит отметить RKC, точнее WinRK www.msoftware.co.nz, который выйдет в конце февраля 2004 года. Он должен обладать не только лучшей степенью сжатия по сравнению с 7-zip, но и удобной графической оболочкой. Главный недостаток — для хорошего сжатия необходимо много оперативной памяти, скорость и требования к оперативной памяти одинаковы во время архивирования и разархивирования.

PAQ6 показал самую лучшую степень сжатия со значительным отрывом от конкурентов. Но практически использовать его могут только экстремалы из-за очень низкой скорости (17 КБ/с). Несмотря на хорошие результаты на больших объёмах неоднородных данных, проведенное мини-тестирование по сжатию одного файла (1Cv7.MD.rpk, 7 МБ) показало, что RKC справился со сжатием на 1%, EPM на 4%, а Slim 0.021 slim-fb.by.ru на 8% лучше PAQ6 (7-zip на 20% хуже).

Дальнейшее увеличение степени сжатия архиваторов сильно ограничено возможностью современных компьютеров. Даже успехи 7-zip на фоне RAR достигнуты за счет уменьшения скорости. Более того, практическая реализация эффективных PPM алгоритмов, используемых RKC, PAQ, EPM, была обусловлена существенным повышением производительности компьютеров в последние годы. Поэтому не следует в ближайшее время ждать появления архиваторов, которые при высокой скорости показывали бы степень сжатия значительно выше рассмотренных.

Лучшие алгоритмы сжатия текста

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

Вопрос:

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

  • текст будет представлять себя наборы символов латиницы, кириллицы, знаков препинания — из ASCII (cp866 или win-1251), возможно еще псевдографика будет
  • те же наборы символов, но представленные в кодировке ru_RU.UTF-8

Пока на слуху, но это уже относительно давно, алгоритм PPMd, PPMz. Есть что-то более совершенное?

2 ответа 2

Лучший ответ на этот вопрос — спросите на форуме encode.ru. Я лично не слежу за этим совсем уж пристально, поэтому навскидку: paq8px, emma, cmix (у каждого есть своя ветка на форуме). Кроме этого, препроцессинг — словарная замена (xml-wrt), трюки Grabowski. Имейте в виду, что тексты должны быть достаточно велики (ну хотя бы сотни килобайт) и скорость сжатия/распаковки может быть в районе нескольких кб/с, а многопоточность невозможна без ухудшения сжатия.

Собственно приведённая вами же ссылка http://mattmahoney.net/dc/text.html даёт достаточно исчерпывающий ответ на ваш вопрос. Все алгоритмы такого уровня получают ветки на форуме encode.ru и тестируются Маттом на тексте английской википедии.

Да, язык/кодировка (при условии что она 8-битная) имеют значение только для словарных препроцессоров — они обычно работают только с латиницей. Остальные алгоритмы хорошо работают с любыми языками.

Если же вам на самом деле нужно не максимальное сжатие, а оптимальное сочетание скорости и степени сжатия, то для текстов я предпочитаю bsc, тем более что это единственная библиотека сжатия общего назначения, способная использовать GPU.

Алгоритмы сжатия данных (стр. 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

Илон Маск рекомендует:  Что такое код pg_lo_unlink


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

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

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

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

Дата добавления: 2013-12-23 ; просмотров: 64451 ; Нарушение авторских прав

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

Другим фактором, влияющим на степень избыточности, является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую, чем кодирование аналогичных данных средствами английского языка.

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

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию, различают:

· Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

· Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

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

· первый способ состоит в изменении содержимого данных,

· второй — в изменении структуры данных,

· третий — в одновременном изменении как структуры, так и содержимого данных.

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

· JPEG — для графических данных;

· MPG — для для видеоданных;

· MP3 — для аудиоданных.

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

· GIF, TIFF — для графических данных;

· AVI — для видеоданных;

· ZIP, ARJ, RAR, CAB, LH — для произвольных типов данных.

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

· алгоритм RLE (Run Length Encoding);

· алгоритмы группы KWE(KeyWord Encoding);

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел — это код данных, а второе — коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, вычисляется по формуле.

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

Алгоритмы группы KWE

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

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

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

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

Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования.

Влияние ntfs-сжатия на скорость чтения файлов

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

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

В очередной раз я обратился к ntfs сжатию когда переносил операционную систему Windows 7 на твердотельный накопитель небольшого размера. В своем исходном виде загрузочный раздел Windows категорически не мог поместиться на маленьком 60 (55,8) гигабайтном SSD.

Для решения этой задачи пришлось предварительно выполнить целый комплекс мероприятий. Почитать о них можно в цикле статей под общим названием “Перенос Windows 7 на твердотельный диск небольшого объема”. Первая публикация цикла находится здесь.

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

Забегая вперед, так как статья на эту тему еще только готовится к публикации, скажу, что вслед за Windows 8 и Windows 8.1 в Windows 7 буквально два дня назад наконец появились средства для обслуживания содержимого WinSxS. Следите за публикациями блога. Для этого достаточно подписаться на обновления.

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

Сжатие файлов в папке WinSxS позволило высвободить больше 2 ГБ дискового пространства. Вместе с этим захотелось оценить как повлияла компрессия на скорость дисковых операций. Тем более, что твердотельный накопитель, ради которого все это делалось, уже и так использует встроенное сжатие данных (Intel SSD 520 Series).

Методика измерения скорости чтения диска

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

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

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

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

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

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

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

Для оценки скорости чтения данных с механического HDD в качестве целевого диска в принципе можно было бы использовать твердотельный накопитель. Но как измерить скорость чтения с самого SSD?

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

В повседневной практике Dataram RAMDisk может с успехом использоваться в компьютерах с большой оперативной памятью и 32-разрядной операционной системой Windows. Если в незадействованной операционной системой части RAM создать такой быстрый диск и перенести на него некоторые критичные для скорости чтения/записи файлы, то поведение компьютера можно заметно оживить.

После создания RAM-диска, для измерения времени считывания (копирования) файлов из некоторой заданной папки, можно воспользоваться, например, командой:

robocopy X:\Testfiles\ R:\Testfiles\ /E /XJ X: – буква исследуемого диска;
R: – буква, присвоенная RAM-диску;
Testfiles – папка с тестовыми файлами.

Команда robocopy самостоятельно подсчитает объем данных Vfiles, затраченное время Tread и среднюю скорость операций копирования Cread.

Для сравнения использовались команды copy и xcopy:

@echo off
format R: /FS:NTFS /Q
@echo %time%
for /R «X:\Testfiles» %%i in (*) do (
copy /Y %%i «R:\»
rem xcopy %%i R:\ /Y
)
@echo %time%
pause>nul

Зная общий объем файлов Vfiles в тестовой папке вычислялась скорость чтения данных с диска:

Cread = Vfiles / Tread

Все достаточно очевидно. Кроме того можно отметить, что результаты, полученные при использовании разных команд, оказались одинаковыми.

Тестовое оборудование, тестируемые накопители, наборы данных

Компьютер

Тестирование скорости накопителей проводились на компьютере следующей конфигурации:

Процессор: Intel I7 950, 3,07 GHz
Системная плата: Intel DX58SO
Системная память: 6 Gb (3 x 2 Gb DDR3-1080 MHz)
Видеоадаптер: AMD ATI Radeon HD 5700 Series (1024 Мb)
Операционная система: Microsoft Windows 7 Корпоративная SP1

Тестируемые накопители

Всего в тестах участвовали четыре жестких диска: два полноразмерных (3,5”) диска Seagate Barracuda, быстрый диск для ноутбука (2,5”) Seagate Momentus и твердотельный накопитель Intel 520 Series. Основные параметры дисков представлены в следующей таблице:

ST3500418AS Seagate Barracuda 7200.12

ST31000528AS Seagate Barracuda 7200.12

ST9250410AS Seagate Momentus 7200.4

SSDSC2CW060A Intel 520 Series

Скорость вращения шпинделя 7200 7200 7200 — Объем накопителя, Гб 500 1000 250 60 Формат накопителя 3,5” 3,5” 2,5” 2,5” Буфер, Мб 16 16 16 — Интерфейс SATA-II 3 Гб/с SATA-II 3 Гб/с SATA-II 3 Гб/с SATA-III 6 Гб/с Поддержка NCQ Есть Есть Есть Есть

Тестовые наборы данных

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

Books

Photo

WinSxS

ISO

Количество файлов 616 399 3684 1 Несжатый объем, Мб 166 642 616 691 Сжатый объем, Мб 121 640 428 686 Коэффициент сжатия 1,37 1 1,44 1

Как видно из представленной таблицы, половина из выбранных для тестирования данных практически не меняет свой размер после ntfs-компрессии. К ним относятся форматы файлов со сжатием, такие как фотографии в форматах jpg и raw (nef) и образ диска iso.

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

Данные, обозначенные как WinSxS, представляют собой файлы, произвольно выбранные в папке C:\Windows\winsxs. Как понятно из предисловия к статье, выбор содержимого этой папки для тестирования совершенно не случаен.

Результаты измерения скорости чтения ntfs-сжатых данных

Еще несколько слов о процедуре тестирования.

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

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

Все измерения повторялись 5 раз. Опять же для исключения влияния кеша, во всех последовательных измерениях использовались разные данные.

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

Dataram RAMDisk

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

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

При измерении таким способом влияние ntfs-сжатия оказалось весьма существенным и отличающимся для разных типов данных. Наибольшая деградация скорости чтения (40% и 54% от первоначальной) получилась, соответственно, для файлов электронных книг и фалов из папки winsxs. То есть для «сжимающихся» в результате ntfs-компрессии файлов.

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

ST3500418AS Seagate Barracuda 7200.12 (500 Гб)

По сравнению с другими механическими дисками, участвовавшими в тестировании, 500 гигабайтный однодисковый Seagate Barracuda ST3500418AS неожиданно показал удивительные результаты в смысле его отношения к ntfs-сжатым данным. Падение скорости чтения компрессированных данных имело место лишь при копировании файлов фотографий (64% от первоначальной).

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

ST31000528AS Seagate Barracuda 7200.12 (1 Тб)

Следующим протестированным представителем семейства Seagate Barracuda явился вдвое более “толстый” ST31000528AS. Особенностью этого диска явилось то, что он очень хорошо справился с несжимаемыми файлами (“photo”, “iso”), однако “провалился” на сжимаемых (“books”, “winsxs”).

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

ST9250410AS Seagate Momentus

Третьим номером был протестирован быстрый HDD для ноутбуков Seagate Momentus ST9250410AS (250 Гб). Главной особенностью этого диска является скорость вращения шпинделя 7200 об/мин. Этот накопитель продемонстрировал удивительно ровное, за исключение “photo” (как и в случае с ST3500418AS), отношение к сжатым данным.

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

Еще одной совершенно необъяснимой особенностью всех полученных результатов явилось увеличение скорости чтения несжимаемого файла большого размера (“iso”) у всех механических дисков. Возможно, что в данном случае имеет место некое несовершенство принятой методики измерения, но найти его я не смог. Буду крайне признателен, если кто-то предложит свое объяснение этого феномена.

SSDSC2CW060A Intel 520 Series

Последним протестированным жестким диском, который на самом деле и инициировал проведение тестирования, явился твердотельный накопитель Intel 520 Series SSDSC2CW060A.

Особенностью этого накопителя является то, что установленный в нем контроллер SandForce SF-2281 уже использует сжатие данных и можно предположить, что этот диск должен хуже всех остальных справиться с ntfs-сжатием.

Как видно из полученных результатов, чтение плохо сжимаемых данных (“photo”, “iso”) действительно осуществляется медленнее (соответственно 80% и 66% от скорости чтения несжатых файлов). А вот сжимаемые ntfs-сжатые файлы (“books”, “winsxs”) вопреки ожиданиям читаются даже быстрее. Учитывая, что на практике именно последние, как мы уже говорили, скорее всего будут подвергнуты ntfs-компрессии, это обстоятельство не может не радовать.

Выводы

Так сжимать, или не сжимать? Можно ли на основании полученных данных дать однозначный ответ на этот вопрос? Однозначный, видимо, не получится.

Во-первых, тестирование проводилось на одном единственном компьютере с достаточно быстрым процессором.

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

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

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

Три из четырех протестированных накопителей, включая и SSD, продемонстрировали очень хорошие результаты при чтении ntfs-компрессированных сжимаемых данные, представленных наборами “books” и “winsxs”. Имело место или незначительное снижение скорости чтения или даже ее увеличение.

Как это ни странно, хуже всех с этой задачей справился накопитель большой емкости ST31000528AS Seagate Barracuda 7200.12 (1 Тб). С другой стороны, включать ntfs-сжатие на жестком диске такой емкости вряд ли кому-то потребуется, так как в этом случае справится с проблемой нехватки свободного места на загрузочном разделе Windows можно другими способами. Например, простым увеличением размера соответствующего раздела.

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

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

Дело в том, что так как ntfs-сжатие осуществляется сегментами по 64 килобайта, оно заметно фрагментирует данные. В сжимаемых файлах появятся «разреженные» кластеры. По данным самой Microsoft ntfs-сжатие создает в среднем один «разреженный» кластер на каждые 64 кБ. Нетрудно подсчитать, что после ntfs-сжатия на каждый гигабайт будет приходиться 16384 «разреженных» кластера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

Илон Маск рекомендует:  Что такое код pathinfo

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

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

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

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] даются эффективные алгоритмы на эту тему.

Илон Маск рекомендует:  Что такое код pdf_add_thumbnail

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

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

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

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

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

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

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

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

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

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

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

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

Сжатие способом кодирования серий

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем — это кодирование серий последовательностей (Run Length Encoding — RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других — некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п.. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF:), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже — с малым числом повторяющихся байтов в сериях.

Сжатие без применения метода RLE

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

Процесс кодирования и его методы

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

Первый заключается в просмотре входного потока и построении кодирования на основании собранной статистики (при этом требуется два прохода по файлу — один для просмотра и сбора статистической информации, второй — для кодирования, что несколько ограничивает сферу применения таких алгоритмов, т.к., таким образом, исключается возможность однопроходного кодирования «на лету», применяемого в телекоммуникационных системах, где и объем данных, под час не известен, а их повторная передача или разбор может занять неоправданно много времени). В таком случае, в выходной поток записывается статистическая схема использованного кодирования. Данный метод известен как статическое кодирование Хаффмена [Huffman].

Второй метод — метод адаптивного кодирования (adaptive coder method). Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. Данный метод известен как динамическое кодирование Хаффмена [Huffman], [Gallager], [Knuth], [Vitter].

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

Пусть входной алфавит состоит из четырех символов: a, b, c, d, частоты которых во входном потоке равны, соответственно, 1/2, 1/4, 1/8, 1/8. Кодирование Хаффмена для этого алфавита задается следующей таблицей:

Например, кодом цепочки abaaacb, представленной на входе как 00 01 00 00 00 10 01, будет 0 10 0 0 0 110 10, соответственно — 14 бит на входе дали 11 бит на выходе. Кодирование по Хаффмену обычно строится и хранится в виде двоичного дерева, в «листьях» которого находятся символы, а на «ветвях» — цифры 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 «собираются» в одну уникальную последовательность.

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

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

Однако, кодирование Хаффмена имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит — <0, 1>. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит. Так при кодировании потока с двухсимвольным алфавитом сжатие всегда отсутствует, т.к. несмотря на различные вероятности появления символов во входном потоке алгоритм фактически сводит их до 1/2.

Данная проблема, как правило, решается путем введения в алфа-вит входного потока новых символов вида ‘ab’, ‘abc’,. . . и т.п., где a, b, c — символы первичного исходного алфавита. Такой процесс называется сегментацией или блокировкой входного потока. Однако, сегментация не позволяет полностью избавиться от потерь в сжатии (они лишь уменьшаются пропорционально размеру блока), но приводит к резкому росту размеров дерева кодирования, и, соответственно, длине кода символов вторичных алфавитов. Так, если, например, символами входного алфавита являются байты со значениями от 0 до 255, то при блокировании по два символа мы получаем 65536 символов (различных комбинаций) и столько же листьев дерева кодирования, а при блокировании по три — 16777216! Конечно, при таком усложнении, соответственно возрастут требования и к памяти и ко времени построения дерева, а при адаптивном кодировании — и ко времени обновления дерева, что приведет к резкому увеличению времени сжатия. Напротив, в среднем, потери составят 1/2 бита на символ при отсутствии сегментации, и 1/4 или 1/6 бита соответственно при ее наличии, для блоков длиной 2 и 3 бита.

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

Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является «цифрой» с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и макси-мальной вероятностям появления символа в потоке. Поясним работу метода на примере.

Пусть алфавит состоит из двух символов: a и b с вероятностями соответственно 3/4 и 1/4. К ак уже говорилось выше, кодирование Хаффмена не может упаковывать слова в данном алфавите, т.к. не справляется без сегментации с двухсимвольным алфавитом.

Рассмотрим наш интервал вероятностей [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В на-шем случае это [0, 3/4) и [3/4, 1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из интервала [0, 1) а пустому слову соответствует весь интервал [ 0, 1). После получения каждого следующего символа интервал уменьшается с выбором той его части, которая соответствует новому символу. Кодом цепочки является интервал, выделенный после обработки всех ее сим-волов, точнее, двоичная запись любой точки из этого интервала, а длина полученного интервала пропорциональна вероятности появления кодируемой цепочки.

Применим данный алгоритм для цепочки «aaba»:

Cимвол Частота

[27/64, 36/64) = [0.011011, 0.100100)

[108/256, 135/256) = [0.01101100, 0.10000111)

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

Алгоритм декодирования работает синхронно с кодирующим: начав с интервала [0, 1), он последовательно определяет символы входной цепочки. В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал [0, 1) на [0, 0.11) и [0.11, 1). Поскольку число 0.0111 (код цепочки «aaba») находится в первом из них, можно получить первый символ: «a». Затем делим первый подынтервал [0, 0.11) на [0, 0.1001) и [0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0

При разработке этого метода возникают две проблемы: во-первых, необходима арифметика с плавающей точкой, теоретически, неограниченной точности, и, во-вторых, — результат кодирования становится известен лишь при окончании входного потока. Однако, дальнейшие исследования показывают [Rubin], что можно практически без потерь обойтись целочисленной арифметикой небольшой точности (16-32 разряда), а также добиться инкрементальной работы алгоритма: цифры кода могут выдаваться последовательно по мере чтения входного потока при ограничении числа символов входной цепочки какам либо разумным числом.

Модели входного потока

Кодирование представляет собой лишь часть процесса упаковки. Как было показано, арифметическое кодирование имеет минимальную избыточность при заданном распределении символов входного потока. Но какой алфавит выбрать и каким соответствующим распределением воспользоваться? Ответы на эти вопросы дает построение модели входного потока, представляющей собой (см. [Rissanen], [Witten]) некоторый способ определения возможного распределения вероятностей появления каждого очередного символа в потоке. Каждого, поскольку статические модели (в которых распределение принимается неизменным), в большинстве случаев, не дают максимального качества сжатия. Гораздо больший интерес представляют так называемые адаптивные модели, учитывающие текущий контекст потока. Такие модели позволяют строить быстрые однопроходные алгоритмы сжатия, не требующие априорных знаний о входном потоке данных и строящие распределение «на лету». В отдельную группу выделяют также класс «локально адаптивных» алгоритмов, отдающих при построении распределения предпочтение некоторым особенным, например, последним поступившим символам.

Возможны различные подходы к этой проблеме: простейший из них — сбор статистики появления каждого символа независимо от других (моделирование источником Бернулли, при котором вероятность появления последующего символа не зависит от того, какие символы встретились перед ним). Возможно, также и использование марковских моделей: сбор статистики появления каждого символа в которых про-изводится с учетом некоторого количества предыдущих появлявшихся символов (в марковском источнике первого порядка вероятность по-вления символа зависит только от одного последнего символа, второго — от двух и т. д.) . Марковские модели могут давать более точную картину источника, однако число состояний в них больше, соответственно большим будет объем хранимых таблиц частот. Кроме того, при использовании кодирования Хаффмена они могут даже ухудшить качество сжатия, поскольку порождаемые ими вероятности обычно хуже приближаются степенями 1/2.

Здесь нельзя не упомянуть простой и достаточно эффективный метод кодирования источника с неизвестным распределением частот, известный как сжатие при помощи «стопки книг» или как сжатие сортировкой или хешированием. Метод был впервые открыт и исследован Рябко в 1980г. (см. [Рябко]), а затем переоткрыт Бентли, Слейтером, Тарьяном и Веи в 1986г. (см. [Bentley]). Идея метода состоит в следующем: пусть алфавит источника состоит из N символов с номерами 1, 2. N. Кодирующий алгоритм сохраняет последовательность символов, представляющую собой некоторую перестановку символов в последовательности первичного входного алфавита. При поступлении на вход некоторого символа c, имеющего в этой переставленной последовательности номер i, кодирующий алгоритм записывает код этого символа (например, монотонный код: [Кричевский], стр. 69-73). Затем поступивший символ переставляется в начало последовательности и номера всех символов, стоящих перед c, увеличиваются на 1. Таким образом, наиболее часто встречающиеся символы будут переходить в начало списка и иметь более короткие коды, что в свою очередь снизит объем выходного потока при их записи в качестве символов выходного потока.

Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

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

В простейшем случае для кодирования в качестве входного алфавита можно использовать именно эти символы (байты) входного потока. Именно так работает метод squashing программы PKPAK (использовано статическое кодирование Хаффмена и двухпроходный алгоритм). Степень сжатия при этом относительно невелика — для текстовых файлов порядка 50%. Гораздо большей степени сжатия можно добиться при выделении из входного потока повторяющихся цепочек — блоков, и кодирования ссылок на эти цепочки с построением хеш-таблиц от первого до n-го уровня.

Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву (см. [Lempel), и обычно называется LZ-compression. Суть его состоит в следующем: упаковщик постоянно хранит некоторое количество последних обработанных символов в буфере. По мере обработки входного потока вновь поступившие символы попадают в конец буфера, сдви-гая предшествующие символы и вытесняя самые старые. Размеры этого буфера, называемого также скользящим словарем (sliding dictionary), варьируются в разных реализациях кодирующих систем. Экспериментальным путем установлено, что программа LHarc использует 4-килобайтный буфер, LHA и PKZIP — 8-ми, а ARJ — 16-килобайтный.

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

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

Таким образом, алгоритм Лемпеля-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таблице (length + distance). Очевидно, что эти потоки являются потоками символов с двумя новыми алфавитами, и к ним можно применить один из упоминавшихся выше методов (RLE, кодирование Хаффмена или арифметическое кодирование). Так мы приходим к схеме двухступенчатого кодирования — наиболее эффективной из практически используемых в настоящее время. При реализации этого метода необходимо добиться согласованного вывода обоих потоков в один файл. Эта проблема обычно решается путем поочередной записи кодов символов из обоих потоков.

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch — LZW)

Данный алгоритм отличают высокая скорость работы как при упаковке, так и при распаковке, достаточно скромные требования к памяти и простая аппаратная реализация. Недостаток — низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Предположим, что у нас имеется словарь, хранящий строки текста и содержащий порядка от 2-х до 8-ми тысяч пронумерованных гнезд. Запишем в первые 256 гнезд строки, состоящие из одного символа, номер которого равен номеру гнезда. Алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые гнезда в конец словаря. Прочитаем несколько символов в строку s и найдем в словаре строку t — самый длинный префикс s. Пусть он найден в гнезде с номером n. Выведем число n в выходной поток, переместим указатель входного потока на length(t) символов вперед и добавим в словарь новое гнездо, содержащее строку t+c, где с — очередной символ на входе (сразу после t). Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. При размере словаря в 4096 гнезд можно передавать 12 бит на каждый индекс. Каждая распознанная цепочка добавляет в словарь одно гнездо. При переполнении словаря упаковщик может либо прекратить его заполнение, либо очистить (полностью или частично).

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

От алгоритмов сжатия к форматам файлов, программам паковщикам и архиваторам

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

В настоящий момент на рынке программных продуктов и серверах программного обеспечения можно встретить достаточно большое число архивирующих и сжимающих утилит, большинство из которых доступны для некоммерческого использования. Такая доступность, прежде всего, связана с тем, что каждая, даже коммерческая, программа нуждается в обширном рынке пользователей. А, поскольку, форматы файлов архиваторов и паковщиков, даже использующих ожин и тот же алгоритм, не одинаковы, то такие программы невольно конкурируют за рынок пользователей. С этим также связано и то, что поддержка более популярных форматов файловых архивов начинает включаться в другие утилиты и программы и используемые форматы становятся стандартными форматами архивов (zip, arj, rar, ha, pak, cab и др..). Стандартный формат подразумевает исключительную легкость при поиске программы, необходимой для извлечения файлов из сжатого состояния и поддержку их другими программами (например браузерами, командными оболочками, файловыми менеджерами и т.п.).

Нами были проанализированы более 300 архиваторов и паковщиков и отобраны наиболее интересные. Тесты сжатия производились на ПК Intel Pentium 233MHz с RAM 64Mb под управлением ОС MS-Windows 95 (4.0.1111). Для тестирования использовались 7 файлов с совокупным размером 8646421 байт. В архиве содержались как текстовые (txt 643830), графические (bmp 2233560, psd 959170), двоичные (exe 4014592, dll 352256) и мультимедийные (avi 342420, mid 100593) файлы. Архивация производилась при работе в фоновом режиме из под оболочки far 1.52. Для измерения времени использовалась команда time. Файлы сжимались с жесткого диска на жесткий диск. Необходимо отметить, что в качестве опций для сжатия использовались параметры для наилучшего сжатия каждого файла, а в случае наличия у программы специальных параметров, определяющих сжатие файлов строго определенного формата, при его тестировании они также использовались. Результаты лучших экземпляров сведены нами в таблицу. Данные в нашей таблице отсортированы в порядке ухудшения коэффициента сжатия, а ratio показывает, сколько процентов объема осталось после сжатия:

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