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

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

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

Анализ рынка программ -  Архиваторов. В данный момент на рынке архиваторов преобладают программы, использующие словарные (LZ) методы, например: Zip, RAR, ACE, CAB, 7-Zip и многие другие клоны Zip’а. Однако, эти методы были предложены еще в конце 70-х годов прошлого столетия и, соответственно, много исследованы, что усложняет нахождение серьезных оптимизаций к ним. Поэтому, на мой взгляд, на рынке архиваторов сложился кризис, выраженный именно в том, что лидеры этого рынка не могут существенно улучшить сжатие без использования не-LZ методов, ввиду того, что словарные методы исчерпали свой потенциал. Ярким подтверждением этого является то, что даже автор WinRAR, Евгений Рошал, в версии 3 своего архиватора для улучшения сжатия не оптимизировал алгоритм, а использовал метод другого семейства. Поэтому в последнее время особое внимание разработчики ПО для сжатия данный уделяют не-LZ методам. Один из таких методов (PPM, Prediction by Partial Match) мог бы стать заменой LZ, однако, несмотря на серьезное улучшение сжатия, среди их минусов необходимо отметить: низкую скорость (она в разы меньше скорости LZ-архиваторов), а также высокие требования к ресурсам компьютеров, как при сжатии, так и при разжатии [3-5].

Другой представитель методов нового поколения – метод BWCA (Burrows-Wheeler transform based Compression Algorithm) был предложен сравнительно недавно (в 1994 году). По своим принципам этот метод более близок к PPM-семейству, то есть позволяет использовать не только избыточность, заключенную в повторах одинаковых фрагментов, но и контекстную избыточность (повторение символов при одинаковых “соседях”), а поэтому обеспечивает улучшение сжатия по сравнению c LZ, особенно на качественных данных, например, текстах или таблицах. BWCA не использует явного моделирования, следовательно требует гораздо меньше ресурсов компьютера, чем PPM, а также имеет лучшие временные характеристики. Поэтому, на наш взгляд, BWCA является компромиссным решением между медленным PPM и слабо сжимающими LZ-методами. Причем в последних исследованиях предложены методы улучшения сжатия BWCA, позволяющие вплотную приблизиться к PPM при сохранении значительного преимущества в скорости.

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

Наиболее популярные среди них это WinZip и WinRAR:

Описание BWT. Общая схема преобразования происходит так [3-5]:

1) выделяется блок из входного потока, причем размер блока является константой алгоритма.

2) формируется матрица циклических перестановок блока;

3) все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки;

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

С первого взгляда может показаться, что этот метод очень ресурсоемкий и требует как минимум O(n2) памяти. Однако это впечатление ошибочно: так как сортируется матрица циклических перестановок одной и той же строки, то для хранения каждой строки не обязательно указывать все N символов. На практике размер блока устанавливают обычно в 4 мегабайта, как оптимальное решение между сжатием и скоростью.

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

han …t (..than..)

he ….t (..the..)

he ….t (..the..)

hen …t (..then..)

hen …w (..when..)

Таким образом BWT позволяет неявно использовать контекстную избыточность, затрачивая на такое моделирование гораздо меньше времени и ресурсов, чем если бы это происходило явно. Чтобы быть точным, заметим, что неявность является и недостатком, т.к. у программиста нет возможности четко задать способ моделирования. В работе [2] автор предположил, что BWT является частным случаем CM(Context Modeling), родоначальника PPM; мы можем согласиться с этим утверждением: эмпирически видно, что BWT напоминает PPM порядка размера блока, то есть, оперирующего контекстами длины N.

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

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

Можно использовать также тот факт, что сортируемые строки есть циклические перестановки друг друга, то есть возможно, отсортировав строки по N символам использовать результаты для сортировки по 2N символам. Данное соображение легло в основу сортировок удвоением, которые используются в большинстве современных BWT-компрессорах. Наше решение – сортировка Бентли-Седжвика с использованием углубления вставками Pixar©, которое позволяет нивелировать значительное замедление BeSe на высокоизбыточных данных.

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

3. строки можно сравнивать не по одиночным символам, а по 4 байта, что позволяется современной архитектурой intel-32. При использовании 64-битных процессоров незначительная модификация позволит ускорить сортировку на 30-50%.

Скорость сортировки зависит от следующих факторов:

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

- Степень избыточности данных. BeSe-сортировка делит все строки на три группы: 1)s[k]>median[k], 2)s[k]=median[k], 3)s[k]<median[k] и вызывает себя рекурсивно на каждой из групп. В случае неоптимального выбора медианы, то есть в какой-либо группе будет большинство строк, время исполнения программы значительно увеличится. Эта проблема до некоторой степени решена использованием. Как уже указывалось, обычные методы сжатия (LZ, PPM) не дают оптимального результата на преобразованных файлах. Поэтому, эти файлы нужно сжимать специализированными методами (или связкой моделировщик + энтропийный кодер). Изучая преобразованные файлы, можно прийти к выводу, что подавляющее число фрагментов преобразованных файлов делятся на 3 группы несколько символов имеют постоянную частоту преобладание одних символов сменяется преобладанием других один символ встречается гораздо чаще других. Поэтому, специализированный метод сжатия должен удовлетворять следующим требованиям:

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

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

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

1. Заргарян Е.В., Заргарян Ю.А., Мищенко А.С., Лимарева Н.В. Проектирование автоматизированного рабочего места врача-терапевта санатория // Современная техника и технологии. 2014. № 11 [Электронный ресурс]. URL: http://technology.snauka.ru/2014/11/4881
2. Заргарян Е.В., Заргарян Ю.А., Коринец А.Д., Малышенко И.М. Проектирование автоматизированного рабочего места сотрудника регистратуры санатория // Современная техника и технологии. 2014. № 12 [Электронный ресурс]. URL: http://technology.snauka.ru/2014/12/5013
3. Новоженов Ю.В. Объектно-ориентированные технологии разработки сложных программных систем. М., 2002.
4. Гради Буч. “Объектно-ориентированный анализ и проектирование.” М.: Издательство Бином
5. Борзов Ю.В. “Методы тестирования и отладки программ ЭВМ.” Рига, ЛГУ им. П. Стучки, 1995.

Все статьи автора «Заргарян Елена Валерьевна»