Алгоритмы сжатия данных без потерь

Часть первая – историческая.

Введение

История

Иерархия алгоритмов:

Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.
Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.
Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.

Проблемы с правами

Рост популярности Deflate

Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивавшихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG.
Том Хендерсон придумал и выпустил первый коммерчески успешный архиватор ARC в 1985 году (компания System Enhancement Associates). ARC была популярной среди пользователей BBS, т.к. она одна из первых могла сжимать несколько файлов в архив, к тому же исходники её были открыты. ARC использовала модифицированный алгоритм LZW.
Фил Катц, вдохновлённый популярностью ARC, выпустил программу PKARC в формате shareware, в которой улучшил алгоритмы сжатия, переписав их на Ассемблере. Однако, был засужен Хендерсоном и был признан виновным. PKARC настолько открыто копировала ARC, что иногда даже повторялись опечатки в комментариях к исходному коду.
Но Фил Катц не растерялся, и в 1989 году сильно изменил архиватор и выпустил PKZIP. После того, как его атаковали уже в связи с патентом на алгоритм LZW, он изменил и базовый алгоритм на новый, под названием IMPLODE. Вновь формат был заменён в 1993 году с выходом PKZIP 2.0, и заменой стал DEFLATE. Среди новых возможностей была функция разбиения архива на тома. Эта версия до сих пор повсеместно используется, несмотря на почтенный возраст.
Формат изображений GIF (Graphics Interchange Format) был создан компанией CompuServe в 1987. Как известно, формат поддерживает сжатие изображения без потерь, и ограничен палитрой в 256 цветов. Несмотря на все потуги Unisys, ей не удалось остановить распространение этого формата. Он до сих пор популярен, особенно в связи с поддержкой анимации.
Слегка взволнованная патентными проблемами, компания CompuServe в 1994 году выпустила формат Portable Network Graphics (PNG). Как и ZIP, она использовала новый модный алгоритм DEFLATE. Хотя DEFLATE был запатентован Катцем, он не стал предъявлять никаких претензий.
Сейчас это самый популярный алгоритм сжатия. Кроме PNG и ZIP он используется в gzip, HTTP, SSL и других технологиях передачи данных.

К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году в возрасте 37 лет. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!

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

ZIP царствовал безраздельно до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас ZIP, пожалуй, самый распространённый из форматов, RAR – до недавнего времени был стандартом для распространения различного малолегального контента через интернет (благодаря увеличению пропускной способности всё чаще файлы распространяются без архивации), а 7zip используется как формат с наилучшим сжатием при приемлемом времени работы. В мире UNIX используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).

Прим. перев. Лично я, кроме перечисленных, сталкивался ещё с архиватором ARJ (Archived by Robert Jung), который был популярен в 90-х в эру BBS. Он поддерживал многотомные архивы, и так же, как после него RAR, использовался для распространения игр и прочего вареза. Ещё был архиватор HA от Harri Hirvola, который использовал сжатие HSC (не нашёл внятных объяснений — только «модель ограниченного контекста и арифметическое кодирование»), который хорошо справлялся со сжатием длинных текстовых файлов.

В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.
В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.

Будущее алгоритмов сжатия

Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.

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

Источник

Лекция 14. Архивирование и методы сжатия информации

14.1. Что такое архивирование

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

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

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

14.2. Какие существуют методы архивирования

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

14.3. Какими возможностями обладают архиваторы

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

14.4. Как сжать звуковые файлы

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

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

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

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

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

14.5. Как сжать графические файлы

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

Источник

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

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

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

Лекция 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Сжатие информации без потерь. Часть вторая

Во второй части будут рассмотрены арифметическое кодирование и преобразование Барроуза-Уилера (последнее часто незаслуженно забывают во многих статьях). Я не буду рассматривать семейство алгоритмов LZ, так как про них на хабре уже были неплохие статьи.

Итак, начнем с арифметического кодирования — на мой взгляд, одного из самых изящных (с точки зрения идеи) методов сжатия.

Введение

Как можно заметить, в случаях, когда относительные частоты не являются степенями двойки, алгоритм явно теряет в эффективности. Это легко проверить на простом примере потока из двух символов a и b с частотами 253/256 и 3/256 соответственно. В этом случае в идеале нам понадобится , то есть 24 бита. В то же время, метод Хаффмана закодирует эти символы кодами 0 и 1 соответственно, и сообщение займет 256 бит, что, конечно, меньше 256 байт исходного сообщения (напомню, мы предполагаем, что изначально каждый символ имеет размер в байт), но все же в 10 раз меньше оптимума.

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

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

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

Рассмотрим построение дроби на интервале [0,1) (такой интервал выбран для удобства подсчета), и на примере входных данных в виде слова «короб». Нашей задачей будет разбить исходный интервал на субинтервалы с длинами, равными вероятностям появления символов.

Составим таблицу вероятностей для нашего входного текста:

Здесь под «Частотой» подразумевается количество вхождений символа во входном потоке.

Будем считать, что данные величины известны как при кодировании, так и при декодировании. При кодировании первого символа последовательности (в нашем случае — «Короб»), используется весь диапазон от 0 до 1. Этот диапазон необходимо разбить на отрезки в соответствии с таблицей.
В качестве рабочего интервала берется интервал, соответствующий текущему кодируемому символу. Длина этого интервала пропорциональна частоте появления символа в потоке.
После нахождения интервала для текущего символа, этот интервал расширяется, и в свою очередь разбивается в соответствии с частотами, так же как и предыдущие (то есть, для нашего примера, на шаге 2 мы должны разбить интервал от 0.4 до 0.6 на субинтервалы так же, как сделали это на первом шаге). Процесс продолжается до тех пор, пока не будет закодирован последний символ потока.
Иными словами, i-му символу будет ставиться в соответствие интервал

где N — количество символов алфавита, p_i — вероятность i-го символа.

В нашем случае это выглядит так

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

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

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

Как же происходит декодирование? Декодирование происходит аналогичным образом (не в обратном порядке, а именно аналогичным образом).

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

Для нашего случая процесс будет выглядеть так:

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

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

Рассмотрем предложенную в начале статьи последовательность символов a и b с вероятностями 253/256 и 3/256. Длина последнего рабочего интервала для цепочки из 256 символов будет равна

В таком случае, искомое N будет равно 24 (23 дает слишком большой интервал, а 25 не будет являться минимальным), то есть мы потратим на кодирование всего 24 бита, против 256 бит метода Хаффмана.

Преобразование Барроуза — Уилера

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

Да, это возможно. Для иллюстрации, рассмотрим преобразование Барроуза Уилера, которое превращает блок данных со сложными зависимостями в блок, структура которого легче моделируется. Еслественно, это преобразование также полностью обратимо. Авторами метода являются Девид Уилер (David Wheeler) и Майк Барроуз (Michael Burrows, если верить вики, сейчас он работает в Google).

Итак, алгоритм Барроуза-Уилера (в дальнейшем для краткости я буду называть его BTW — Burrows-Wheeler Transform) преобразовывает входной блок в более удобный для сжатия вид. Однако, как показывает практика, полученный в результате преобразования блок обычные методы сжимают не так успешно, как специально для этого разработанные, поэтому для практического применения нельзя рассматривать алгоритм BWT отдельно от соответствующих методов кодирования данных, но поскольку наша цель — изучить принцип его работы, то ничего страшного в этом нет.

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

Алгоритм преобразования

BWT является блочным алгоритмом, то есть он оперирует блоками данных, и заранее знает о составе элементов блока определенного размера. Это делает затруднительным использование BWT в тех случаях, когда необходимо посимвольное сжатие, или сжатие «на лету». В принципе, такая реализация возможна, но алгоритм получится… не очень быстрым.

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

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

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

В общем-то на этом преобразование почти закончено: все что осталось сделать — это записать последний столбец, не забыв при этом запомнить номер исходной строки. Сделав это, мы получим:

Как видим, распределение символов стало значительно лучше: теперь 4 из 5 символов «а» стоят рядом, как и оба символа «б».

Обратимость

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

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

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

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

Для нашего примера первые четыре шага восстановления будут выглядеть так:

Затраты ресурсов при работе

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

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

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

Вектор преобразования формируется из значений номеров строк: <2,5,6,7,8,9,10,1,3,0,4>.

Теперь можно легко получить исходную строку. Возьмем элемент вектора обратного преобразования, который соответствует номеру исходной строки в матрице: T[2]=6. Иначе говоря, в качестве первого символа исходной строки необходимо взять шестой символ строки «рдакраааабб» — символ «а».
После этого мы смотрим, какой символ переместил найденный символ «а» на вторую позицию среди одинаковых с ним. Для этого мы берем номер из вектора преобразования строки, из которой был взят символ «а»: это номер 6.
Затем смотрим строку, имеющую номер 6 и выбираем оттуда последний символ – это символ «б». Продолжая эту процедуру для оставшихся символов, мы легко восстановим исходную строку.

Перемещение стопки книг

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

Рассмотрим строку «рдакраааабб», полученную нами по BWT в предыдущей части. В данном случае, наш алфавит состоит из 5 символов. Упорядочив их, получим
M=<а, б, д, к, р>.

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

Результатом будет последовательность

На этом этапе не совсем понятно, какой прок от этого алгоритма. На самом деле, прок есть. Рассмотрим более абстрактную последовательность:

Для начала просто закодируем ее по методу Хаффмана. Для наглядности предположим, что расходы на хранения дерева при использовании перемещения стопки книг, и без оного совпадают.
Вероятности появления всех четырех символов в нашем случае равны ¼, то есть кодирование каждого символа требует 2 бит. Легко подсчитать, что кодированная строка займет 40 бит.
Теперь проведем изменение строки алгоритмом перемещения стопки книг. В начале алфавит имеет вид

После использования алгоритма строка будет иметь вид

В этом случае частоты появления символов сильно изменятся:

В этом случае после кодирования мы получим последовательность в 15+6+3+3=27 бит, что намного меньше чем 40 бит, которые получаются без перемещения стопки книг.

Заключение

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

Источник