WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 8 |

«СЕНФА (СЖАТ! Q Q A A D D QO OOD УСТРОЙСТВО АРХИВАТОРОВ, СЖАТИЕ ИЗОБРАЖЕНИЙ И ВИДЕО МОСКВА • ДИАЛОГ-МИФИ • 2003 Книга написана коллективом ...»

-- [ Страница 5 ] --

Не является обязательным и другое применение R L E - кодирование длин повторов после преобразования Барроуза - Уилера. Оно довольно эффективно реализовано в szip [33] и ВА, но известны архиваторы, в которых RLE не требуется, например такие, которые используют кодирование расстояний (DC, YBS). Ряд архиваторов использует некую разновидность кодирования длин повторов - 1-2 кодирование, описанное ниже. В любом Методы сжатия данных случае, если не воспользоваться каким-нибудь из перечисленных методов сокращения количества выходных символов, скорость работы будет оставлять желать лучшего, особенно в случае архиваторов, в которых используется арифметическое кодирование.

УСОВЕРШЕНСТВОВАНИЕ МЕТОДА ПЕРЕМЕЩЕНИЯ СТОПКИ КНИГ

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

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

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

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

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

Рис. 5.13. Модифицированное MTF-преобразование строки "рдакраааабб" http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) Преимущество такой модификации видно на примере MTF-преобразования типичной для английских текстов последовательности "ttttTtttwtt", полученной из части последнего столбца матрицы перестановок:




Предположив, что упорядоченный список содержит символы в порядке {"t", "w", "T"...}, в результате применения метода перемещения стопки книг получаем следующие результаты:

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

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

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

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

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

Упражнение. Какой из методов MTF-преобразования будет эффективнее для последовательности символов "aaacbaaa"? Предположим, что начальный упорядоченный список символов выглядит как {"a", "b, "с"}.

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

Рис. 5.14. Статистика рангов MTF-преобразования для файла bookl 1-2-КОДИРОВАНИЕ При кодировании длин повторов символов применительно к преобразованию Барроуза - Уилера стоят две задачи:

• обеспечить кодирование чисел любой величины;

• адаптироваться к изменению величины избыточности данных.

Данные задачи успешно решает алгоритм, нашедший применение в ряде архиваторов (bzip2, IMP, BWC) и названный 1-2-кодированием. Суть его заключается в том, что число, соответствующее количеству повторов, кодируется посредством двухсимвольного алфавита.

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) При использовании 1-2 кодирования в связке с MTF мы отводим под нулевой ранг не один, а два символа (назовем их Z] и z 2 ), увеличивая таким образом алфавит до 257 символов. Символ, отличный от Z\ и z 2, является признаком окончания записи числа повторов.





Число повторов кодируется так, как это представлено на рис. 5.15.

Упражнение. Закодируйте посредством описанного алгоритма число 30. Какому числу соответствует последовательность z2z2ZiZiZ2?

Как можно видеть, данный способ обеспечивает кодирование чисел в любом диапазоне. Этот метод соответствует и второму из предъявляемых требований. Увеличение избыточности данных, приводящее к возрастанию концентрации нулевых рангов MTF, приводит к увеличению частот символов Z] и z 2. Причем если преобладают короткие последовательности MTF-0, то частота символа zj превосходит частоту символа Z2.

Предвидя возможное замечание о том, что, например, число 7 приводит к большему возрастанию частоты символа Z\, чем число 1, отметим следующее. Как правило, распределение частот чисел повторов в среднем убывает с ростом числа, а частоты появлений близких по значению чисел близки. Причем обычно с ростом чисел различие частот уменьшается. Поэтому:

• частота числа 7 больше частоты числа 1 только в редких, скорее вырожденных случаях;

• увеличение частоты числа 7 за счет преобладания над частотами чисел 8, 9 и 10 приводит к более интенсивному использованию символа Z\, так Методы сжатия данных как число символов zt в коде, соответствующем числу 7, максимально среди всех трехсимвольных кодов.

В целом преобладание частоты символа Z| над частотой символа z 2 определяется преобладанием частоты одной группы символов над другой (рис. 5.16).

После двух преобразований строка "абракадабра" выглядела как {4,3,2,4,3,2,0,0,0,4,0}. Подвергнем ее 1-2-кодированию. Воспользовавшись рис. 5.16, получим {4,3,2,4,32,z,,zi,4,zi}.

Упражнение. Как будет выглядеть исходная строка в результате указанных двух преобразований и 1-2-кодирования, если вместо обычного применить модифицированный MTF? Для справки: после BWT и модифицированного MTF была получена последовательность {4,3,0,4,2,0,0,0,0,4,1}.

РЕАЛИЗАЦИЯ 1-2-КОДИРОВАНИЯ // Функция 1-2-кодирования.

// Выводит последовательность символов zl и // z2, соответствующую числу count.

void zlz2( int count ) { // длина последовательности int len=0;

// число 0 не кодируется iff !count ) return;

// находим длину последовательности { int. t = count+1;

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) // кодирование последовательности putc ((count S (l«len))? z2:zl, output ) ;

// кодирование // использует функцию zlz2() void encode( void ) { unsigned char c;

while( !feof( input ) ) { if ( с == 0 ) count++; // считаем MTF- // вводим число MTF- // выводим символ, отличный от MTF_ // декодирование void decode( void ) { unsigned char c;

while( !feof( input ) ) { // чтение последовательности zlz // вывод MTF-0, заданные числом count while ( count-- ) putc( 0, output ) ;

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

КОДИРОВАНИЕ РАССТОЯНИЙ

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

Одним из наиболее распространенных был подход, при котором отдельно строилась модель для наиболее часто используемых символов. Для таких символов вероятности просчитывались отдельно. Впервые этот подход был описан Петером Фенвиком [18], но автору не удалось превзойти результаты модели, использующей традиционный подход. Более удачным было применение кеширования наиболее частых символов в архиваторе szip, разработанном Шиндлером [33].

Самым поздним из методов, пришедших на смену MTF, является метод кодирования расстояний (Distance Coding). Первый же из архиваторов, использующих этот метод, сумел превзойти своих конкурентов по степени сжатия большинства типовых данных. Теперь, помимо архиватора DC, кодирование расстояний используют YBS и SBC.

Были публикации, посвященные родственному методу, названному Inversion Frequencies авторами одной из работ [5,1]. Помимо метода кодирования расстояний, ниже мы рассмотрим и его.

Возьмем для примера ту же строку "рдакраааабб", полученную в результате преобразования Барроуза - Уилера.

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

Для удобства добавим в конец строки символ, означающий конец блока.

При ссылке на этот символ мы можем распознать окончание цепочки символов, от которых эта ссылка сделана. Обозначим символ конца блока как "$".

Итак, после этих приготовлений наша строка выглядит как "абдкррдакраааабб$". Причем при декодировании нам на этом подготовительном этапе известны первые символы строки, "абдкр", и последний, "$".

Теперь займемся собственно кодированием расстояний. Для этого берем первый символ, "а", и ищем ближайший такой же. Расстояние до него равно шести - это число иных символов между "а". Но из этих шести символов http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) нам уже известны 4 и при декодировании мы заранее знаем, что очередной символ "а" никак не может попасть в эти позиции. Наша задача - закодировать номер той вакантной позиции, на которую выпадает этот символ. Это номер 6 - 4 = 2.

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

известные символы:

расстояние:

известные символы:

известные символы:

расстояние:

известные символы:

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

известные символы:

расстояние:

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

известные символы:

расстояние:

Методы сжатия данных Кодируя символ "д", мы сделали ссылку на конец строки. При декодировании такая ссылка позволит понять, что символы "д" закончились (рис. 5.17).

расстояние:

В итоге получаем последовательность { 2,8,1,1,0,5,0,4,4,1 }.

Упражнение. Вычислите расстояния для строки "брраааакаакдрр".

ОБРАТНЫЕ ЧАСТОТЫ

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

Авторы данного алгоритма, названного Inversion Frequencies (IF), исходили из того, что расстояние между одинаковыми символами характеризует частоту использования этих символов на данном отрезке символьной последовательности. Чем расстояние меньше, тем выше частота. Поясним работу алгоритма на примере.

Предположим, нам нужно определить IF для строки "рдакраааабб", а расчет расстояний будем проводить в соответствии с положением символов в алфавите "абдкр".

Сначала запишем для символа "а" положение первого из таких символов в исходной строке и их количество.

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

После того как все позиции символа "а" определены, мы можем удалить их из исходной строки и продолжить обработку строки, как будто их и не было (рис. 5.18).

Символ Первая В кодировании символа "р" нет необходимости, так как заведомо известно, что он занимает оставшиеся позиции в строке. Таким образом, мы получили такую последовательность: {{2,5,2,0,0,0}, {4,2,0}, {1,1}. {U}}Легко заметить, что способ и эффективность кодирования зависят от того порядка, в котором мы будем обрабатывать символы. Еще одно важное отличие данного метода от кодирования расстояний заключается в том, что он не освобождает от необходимости кодирования длинных последовательностей нулевых значений обратных частот.

"(Эч Упражнение. Определите обратные частоты для строки "брраааакаакдрр".

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

Рассмотрим фрагмент данных, типичный для текста, преобразованного посредством BWT. Для примера взят файл bookl из набора "Calgary Corpus" (рис. 5.19).

Методы сжатия данных eteksehendeynkrtdserttnregenskngsgsedeneyswmessrne xgynystslgyegsgstssrhmsstetehselxtptneessthndesddy htksthwtpfdttegedmmhysyresprssneenselgetdemsetse,t reehsetrtteseeeeeesssdeedmnlendeedgtdgttdsgtteeysy tddentnrxsltshtghnteeernsdpwlttensedehsteeswekheee teneeeeseslteenestrngsthsdgeyeyrteetklrdtetteyodth eegeercesyttesedenrtresnyssgttsslsawssygsssrewmsht gt,etssgehnehessssehneesesdnrnekhtrsslthdsseestste nbgeeessesdesyndtrdhpeesehesetsrerhyesdnwtlrrhoses hsetdrptttsdhaynenetyntpgstesknhysftsgssdftgteeedu Можно заметить, что распределение символов на этом фрагменте (рис. 5.19) меняется незначительно. Совсем другую картину м ы можем наблюдать на рис. 5.20, когда преобладание одних символов сменяется преобладанием других.

ygeldsd,,ttyogdodgdedndygnmotedgwkgodoowtdoddtotet tndmeggkrdsgtohtdegteddrsttttegtddewdddoootdgdntet ststttstt!uetttdtte-elttetny,hettltgrlttylttnttyrt rtttttttetttttdtttstottttttttttntttttttn,ddtkgnde;

ed,d,stefoefssfrsnsstyslw,fnoeadere,rteeynsfofhynn nyoytted,yfnedhddtoldtnyhnnhyrtyryttmeryesfoyedney oymd,sedesgnrrsysnssmydsspdyt'-dssehs,gynsdydgee'о defddeynt,,tdnd,os;sttyysofy-nnetognfetdnyldlewheodsttemshsdtsyteny,ngdefs,-offsnntettseyesgleay:es dtsdgllredksyryes,rldosts;dtdeefgghsfrergkdgngkenw Также бывают случаи, когда на протяжении всего фрагмента явно превалирует один определенный символ (рис. 5.21).

edeeeeeleydeyeeet'eeeleeeeeeeeeeeeeeeeeeeeeeleeeee еееееее!eeeeleeeeeeeeeeeeeeeeeeeeeeeyedeeereeeleee eeeeeeeeeeslyadeeeeeeeeeyeeeeeeeeeeeeeedyereseeeee elueeeeeeyeeeeeelsseseell'eeletenhyalehcesyyseessn s'dlesffao,dffeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeTeeee eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeteeeeeeeeeeeeeeee eeeeeeeeeeaerre,see,eywesldsysdhedeeetaeeesaeeyedo Puc. 5.21. Фрагмент с преобладанием одного символа Итак, выделим 3 вида данных:

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

2) промежуток в фрагменте, когда преобладание одних символов сменяется преобладанием других;

3) один из символов встречается намного чаще других.

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) Одна из задач выбираемой модели заключается в том, чтобы позволить оперативно настроиться на текущий вид данных.

СЖАТИЕ ПРИ ПОМОЩИ КОДИРОВАНИЯ ПО АЛГОРИТМУ ХАФФМАНА

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

После преобразований BWT и MTF блок данных делится на равные 50символьные куски. Полученные куски объединяются в группы по степени близости распределений MTF-рангов. Количество групп зависит от размера файла. Например, для мегабайтового файла таких групп будет шесть.

Группирование кусков выполняется итеративно. Изначально куски приписываются группам в порядке следования в блоке так, чтобы каждой группе соответствовало примерно равное количество кусков. Для каждой группы строится отдельное дерево Хаффмана. В архив записываются деревья Хаффмана, номер группы для каждого из 50-символьного кусков, а затем все куски сжимаются по алгоритму Хаффмана в соответствии с номером той группы, к которой они относятся.

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

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

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

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

СТРУКТУРНАЯ и ИЕРАРХИЧЕСКАЯ МОДЕЛИ

Отметим основное свойство таких преобразований, как MTF, DC и IF: на большинстве данных, полученных в результате преобразования Барроуза Уилера, малые значения встречаются гораздо чаще больших и легче поддаКнига написана коллективом http://www.compression.ru/ Методы сжатия данных ются предсказанию. Это свойство очень важно учитывать при построении адаптивных моделей, использующих арифметическое кодирование.

Анализируя перечисленные выше 3 вида фрагментов, можно отметить некоторые особенности, которыми можно воспользоваться при моделировании:

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

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

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

Рассмотрим две модели, обладающие описанными качествами, - структурную и иерархическую [18].

Структурная модель. Кодирование символа осуществляется в два этапа. Сначала кодируется номер группы, к которой этот символ относится.

А затем - номер символа внутри группы.

Размеры групп различны. Наиболее частые символь! помещаются в группы, состоящие из небольшого числа символов. Предложенная Петером Фенвиком структурная модель предполагает самостоятельное существование 0-го и 1-го ранга, т. е. каждый из них представляет собой отдельную группу. В следующую (третью по счету) группу помещаются 2-й и 3-й ранг, затем - с четвертого по седьмой и т. д. (рис. 5.22).

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

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) JHOMep _группы MTF обычный, % _ _ MTF_ модифицированный, _ Рис. 5.23. Статистика распределения рангов в группах структурной модели Иерархическая модель. Эта модель также делит символы на группы.

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

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

РАЗМЕР БЛОКА

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

BWT - алгоритм, дающий наилучшую результативность при сжатии однородных данных. А однородные данные предполагают наличие устойчиКнига написана коллективом http://www.compression.ru/ Методы сжатия данных вых сочетаний символов. А раз сочетания не меняются, то увеличение размера блока приведет только к увеличению числа одинаковых символов, находящихся рядом в результате преобразования. А увеличение количества находящихся рядом символов вдвое в идеале требует всего одного дополнительного бита при кодировании. Таким образом, для однородных данных можно сделать однозначный вывод: чем блок больше, тем сжатие будет сильнее. Ниже приведены экспериментальные данные сжатия файла bookl из набора CalgCC. Тестирование производилось на компьютере следующей конфигурации:

Процессор Частота шины Оперативная память Жесткий диск Операционная система Размер блока, Что касается данных неоднородных, то здесь картина иная. Размер блока надо выбирать таким, чтобы его край приходился на то место, где данные резко меняются. Причем для BWT страшна не сама неоднородность как таковая, а изменение статистики символов, предсказываемых устойчивыми контекстами. Например, нас не должен пугать тот факт, что в начале файла часто встречаются строки "abed", а в конце их место занимают "efgh". Гораздо неприятнее, когда вместо строк "abed" начинают появляться строки "abgh". Это не означает, что файл, в котором наблюдается вторая ситуация, сожмется при помощи BWT-компрессора очень плохо. Но разница в сжатии по сравнению с архиваторами, использующими, например, словарные методы, на таких данных будет не в пользу BWT.

Для иллюстрации зависимости эффективности сжатия неоднородных данных от размера блока сожмем исполнимый файл из дистрибутива компилятора Watcom 10.0, wcc386.exe (536,624 байта).

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии)

ПЕРЕУПОРЯДОЧЕНИЕ СИМВОЛОВ

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

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

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

bookl bookl, после переупорядочения символов

НАПРАВЛЕНИЕ СОРТИРОВКИ

Можно сортировать строки слева направо и в качестве результата преобразования использовать последний столбец матрицы отсортированных строк. А можно - справа налево и использовать первый столбец. Как делать лучше с точки зрения степени сжатия?

Первая стратегия подразумевает предсказание символа исходя из того, какие символы за ним следуют, а вторая - исходя из того, какие были раньше. В литературе для обозначения этих двух направлений используются словосочетания "following contexts" и "preceding contexts" соответственно (правосторонние и левосторонние контексты).

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

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

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

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

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

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

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

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) • длинные одинаковые строки;

• короткие одинаковые строки в большом количестве.

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

Что касается текстовых файлов, наиболее часто встречаемая длина повторяющихся строк - 3-5 символов. Для файлов с исходными текстами программ, как правило, эта длина несколько больше - 8-12 символов.

Рассмотрим алгоритмы сортировок, получившие наибольшую известность.

СОРТИРОВКА БЕНТЛИ - СЕДЖВИКА

Данный алгоритм получил, пожалуй, наибольшее распространение среди всех известных сортировок. Впервые он был применен еще одним из основоположников - Уилером. Затем эта сортировка была реализована в bzip2 и других архиваторах (BWC, BA, YBS).

Сортировка Бентли - Седжвика (Bentley - Sedgewick) представляет собой модификацию быстрой сортировки (quick-sort), ориентированной на сравнение длинных строк, среди которых может оказаться значительное количество похожих.

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

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

Работу алгоритма можно описать при помощи следующего исходного текста на языке Си:

void sort (char **s, int n, int d) { char **s_less, **s_eq, **s_greater;

int *n_less, *n_eq, *n_greater;

// выбор значения, с которым будут // сравниваться d-e символы строк char v = choose_value(&s,d);

// осталась только одна строка // деление всех строк на группы Книга написана коллективом http://www.compression.ru/ Методы сжатия данных compare(Ss, v, d, // строки, d-й символ которых меньше v Ss_less, Sn_less, // строки, d-й символ которых равен v // строки, d-й символ которых больше v Ss_greater, Sn_greater);

sort(Ss_less, n_less, d) ;

sort(Ss_greater, n_greater, d) ;

Данная рекурсивная функция сортирует последовательность из п строк s, имеющих d одинаковых начальных символов. Самый первый вызов выглядит как sort(s,n,0);

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

Перечислим основные из них.

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

2. Использование результата предыдущих сравнений для последующих.

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

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

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии)

СОРТИРОВКА СУФФИКСОВ

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

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

Рассмотрим алгоритм на примере. Введем обозначения:

X -массив суффиксов X[i], каждый из которых представляет собой строку, начинающуюся с /-и позиции в блоке;

I -массив индексов суффиксов; положение индексов в этом массиве должно соответствовать порядку лексикографически отсортированных суффиксов;

V[/] - номер группы, к которой относится суффикс X[fl; сортировка выполняется до тех пор, пока все значения в V не станут разными;

S[i] - число суффиксов, относящихся к группе /;

к - порядок сортировки.

Как всегда, будем производить преобразование Барроуза - Уилера строки "абракадабра$" (добавим к строке символ "$", означающий конец строки).

Шаг 1. Упорядочим все символы строки (для определенности предположим, что символ конца строки имеет наименьшее значение).

Затем заполним массив I значениями, равными позициям этих символов в исходной строке.

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

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

Методы сжатия данных Позиции:

Упорядоченные символы:

I[i] V[I[i]] S[i] Шаг 2. Таким образом, завершена обработка суффиксов порядка к=0, т. е. одиночных символов. Теперь отсортируем пары (к=1). Для сортировки суффиксов каждой группы нам потребуются только значения номеров групп суффиксов (обозначаемых далее как Хк), находящихся на к символов правее сортируемых суффиксов. Например, для сортировки группы 1, соответствующей символу "а", нам потребовались группы 6, 9, 8, 6 и 0 от символов "б", "к", "д", "б" и "$".

Позиции:

Упорядоченные символы:

Суффикс Хк V[I[i]+l] Пары:

V[I[i]+l] Упорядоченные пары:

V[I[i]] S[i] Шаг 3. Поскольку все пары теперь отсортированы, можно упорядочить четверки. Для этого каждую группу (которые представляют собой суффиксы, начинающиеся с одинаковых пар) отсортируем в соответствии с парой символов, следующих после этих одинаковых пар. Прочерками отмечены уже отсортированные суффиксы, которые дальше обрабатывать нет необходимости.

Упорядоченные пары:

V[I[i]+2] После сортировки номеров групп I[i] Шаг 4. Как можно заметить, нам осталось отсортировать всего одну группу, состоящую из двух элементов.

Исходная строка:

Упорядоченные четверки:

После сортировки номеров групп:

V[I[i]] S[i] Таким образом, мы получили упорядоченные суффиксы, индексы которых записаны в массиве I (рис. S.25) Упражнение. Выполните сортировку строки "tobeomottobe", используя описанный алгоритм.

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

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

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

Для сравнения методов сортировок полезно ввести понятие средней длины совпадений (Average Match Length, AML), вычисляемой по следующей формуле:

где N - размер блока данных, подвергаемого преобразованию; X - массив суффиксов Х[/], каждый из которых представляет собой строку, начинающуюся с /-и позиции в блоке; I - массив индексов лексикографически упорядоченных суффиксов; Щху) - число совпадающих символов в одинаковых позициях строк х иу, начиная от первого символа строки и заканчивая первым несовпадением.

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

Цена такой устойчивости - повышенные накладные расходы на ее обеспечение.

Для сравнения ниже приведены экспериментальные данные, полученные на компьютере с процессором Intel Pentium 233 МГц и оперативной памятью 64 Мб. Были выбраны одни из наиболее оптимизированных представителей BWT-компрессоров для выявления слабых и сильных сторон различных методов. Требования к памяти участвующих в эксперименте программ довольно близки (от 6 до 8 размеров блока).

• DC 0.99.015b (автор - Эдгар Биндер). В данном архиваторе использованы поразрядная сортировка и сортировка слиянием.

В A l.0lbr5 (Микаель Лундквист), YBS О.ОЗе (Вадим Юкин), ARC (Ян Саттон). Во всех трех программах нашла свое применение сортировка Бентли - Седжвика вместе с поразрядной. Еще стоит упомянуть SBC 0.910 (Сами Мякинен), которая не участвовала в эксперименте по причине невозможности выделить сортировку отдельно от всех остальных процедур.

QSuf (Ларссон и Садакане). В этой программе реализована только суффиксная сортировка, немного улучшенная по сравнению с описанной выше.

Для эксперимента использовались следующие файлы:

bookl из тестового набора "Calgary Corpus", как файл, обладающий основными свойствами типичных текстов. Размер файла - 768 771 байт;

Ше2 (1 000 000 байт). Этот файл был составлен из нескольких больших одинаковых частей, позаимствованных из файла bookl. Был сконструирован для проверки умения алгоритмов сортировки упорядочивать длинные одинаковые строки;

wat.c (1 890 501 байт). Файл исходных текстов, полученный путем слияния исходных текстов, поставляемых с дистрибутивом компилятора Watcom С 10.0. Как уже отмечалась выше, средняя длина устойчивого контекста у таких файлов немного выше, чем у типичных текстов;

kennedy.xls (1 029 744 байта). Данный файл использовался для анализа способности сортировщиков обрабатывать большое количество одинаковых строк небольшой длины.

* В программе QSuf реализована только сортировка, без сжатия и записи информации в файл. Это необходимо учитывать при сравнении быстродействия. Например, архиватор YBS потратил на сжатие преобразованного файла bookl примерно 1 с.

** Архиватор bzip2 приведен только для справки, так как в нем реализовано сжатие на основе метода Хаффмана, а в остальных используется арифметическое, которое заметно медленнее, но дает существенно лучшее сжатие (на 5Кроме того, максимальный размер блока, который позволяет использовать bzip2, - 900 Кб, что не позволяет достичь должного сжатия всех файлов, кроме book]. Хотя и дает небольшой прирост в скорости (2-3 % на файле wat.c). Увеличение размера блока до размера файла могло бы замедлить скорость сжатия файла wat.c на 2-3 %.

Методы сжатия данных По результатам эксперимента можно сделать наблюдения:

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

2. DC провалился именно там, где ожидалось, - на длинных совпаден:!-::

Архиваторы, использующие быструю сортировку, потенциально iотстать от конкурентов на данных с большим количеством леке*фически упорядоченных совпадений. В принципе можно yen.— роться и с теми и с другими слабостями. Но можно предпол на типичных файлах скорее всего сортировка слиянием остя" на коротких контекстах, а сортировка Бентли - Седжвика (что видно на примере файла wat.c).

3. Можно было рассмотреть частичное сортирующее преобрчестве альтернативного преобразования, не требующего тяпри сортировке. Но здесь уже появляются другие требов* ковке - большие затраты памяти и времени. И как правшшее сжатие.

Хотя сортировка суффиксов и не зависит от избыточно' типичных данных методы, использующие быструю сортр ровку слиянием, оказываются быстрее.

Архиваторы, использующие BWT и ST Довольно быстро после опубликования статьи Баооо* появляться первые компрессоры. Это объясняется, во-— метод оказался хорошим компромиссом между быс использующими словарное сжатие, и медленными пстическими компрессорами. Во-вторых, авторы соя шают некоммерческое использова.

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

и версия BWC 0.99 01.1999 Willem mailto:willem@stack n Компрессор и версия IMP-2 1. Winlmp 1. bzip2 1. (bzip0.21) DC 0.99.298b 08.2000 Edgar mailto:EdgarBinder@t-online.de YBS О.ОЗе В А 1.01Ы Zzip 0.36c SBC 0.910b ERI 5.0re 12. GCA 0.9k 7-Zip2.30bl2 01. Семейство программ BRed, BRed и BRed3 написано одним из родоначальников BWT - Дэвидом Уилером. Многие идеи, использованные в этих компрессорах, описаны в работах Петера Фенвика [18] и нашли свое применение в ряде других программ, например в XI.

Bzip использует адаптированную к BWT сортировку Бентли - Седжвика, во многом позаимствованную из вышеупомянутого семейства. После BWT выполняется преобразование методом стопки книг, выходные данные которого сжимаются при помощи интервального кодирования (аналог арифметического сжатия) с использованием 1-2-кодирования и структурной модели Петера Фенвика.

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

В BWC используются такие же методы, что и bzip и bzip2. А именно оптимизированная сортировка, MTF, 1-2-кодирование и интервальное кодирование.

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

Алгоритм сжатия, используемый в bzip2, также включен и в архиватор 7-Zip.

В szip, помимо упоминавшегося частичного сортирующего преобразования, реализована и возможность использования BWT. Реализована, прямо скажем, только для примера, без затей. А вот для сжатия используются очень интересные решения, представляющие собой некий гибрид MTFпреобразования и адаптивного кодера, берущий статистику из короткого окна преобразованных с помощью BWT данных. С участием автора szip и с использованием описанных решений был также создан архиватор ICT UC.

В Zzip применяются все те же испытанные временем структурная модель, сортировка Бентли - Седжвика и кодирование диапазонов.

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

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

Отличительная особенность SBC - наличие мощной криптосистемы. Ни в одном из архиваторов, пожалуй, не реализовано столько алгоритмов шифрования, как в SBC. В SBC используется алгоритм BWT, ориентированный на большие блоки избыточных данных и позволяющий очень быстро сортировать данные с большим количеством длинных похожих строк. Вместо http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) MTF в архиваторе используется кодирование расстояний, хотя пока не так эффективно, как в YBS и DC, но это компенсируется большим количеством фильтров (методов препроцессинга), настроенных на определенные типы данных.

ARC (автор - Ian Sutton, которому также принадлежит РРМ-архиватор BOA). Как и многие другие, использует BWT на основе сортировки Бентли - Седжвика и MTF. Как и в SBC, дополнительно отслеживаются очень длинные повторы данных.

Первые версии YBS также использовали перемещение стопки книг, которое затем было заменено на кодирование расстояний. Что дало заметный выигрыш в степени сжатия.

Среди не распространяемых свободно компрессоров, описание которых опубликовано в научных трудах, можно отметить BKS98 и BKS99, которые принадлежат сразу трем авторам [10]. Эти компрессоры используют суффиксную сортировку и многоконтекстовую модель MTF по трем последним кодам.

СРАВНЕНИЕ BWT-АРХИВАТОРОВ

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

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

Операционная система Windows NT 4.0 Service Pack Начнем со сжатия русских текстов, потому что BWT-архиваторы особенно эффективны именно для сжатия текстов. А русские тексты выбраны для того, чтобы показать эффективность сжатия в чистом виде, без использования текстовых фильтров, которые для русских текстов еще не созданы авторами описываемых программ. Файл имеет длину 1,639,139 байт.

YBS О.ОЗе DC 0.99.298b -а ARC (I.Sutton) b20 459, Compressia' Ь2048 462, Методы сжатия данных Архиватор, версия Размер сжатого szipl.l2b21o Как можно заметить, первенство удерживают компрессоры, использующие кодирование расстояний.

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

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

Для иллюстрации поведения BWT-архиваторов на неоднородных данных применен исполнимый модуль из дистрибутива компилятора Watcom 10.0 wcc386.exe (536,624 байта). Для того чтобы можно было судить об эффективности различных методов и режимов, некоторые строки помечены специальными знаками:

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) m5I2k SBC 0.860 m3a 278, DC 0.99.298b Ь ARC mml ARC (I.Sutton) BA1.01b5-24-z 293, DC 0.99.298b -a 293, ulOOO BA 1.01b BWC/PGCC 0. тбООк bzip2/PGCC 1.0b7 - В качестве файла, содержащего смесь текстовых и бинарных данных, использовался Fileware.doc размером 427,520 байт из поставки русского MS Office'95. Данный пример показывает, что иногда модель, использующая MTF, оказывается достаточно эффективной.

Методы сжатия данных SBC 0.860 тЗа DC 0.99.298b Compressia Ь256 131,737 0. BA1.01b5-24-r 132,651 0. DC 0.99.298b -a YBS О.ОЗе тбООк bzip2/ PGCC1.0b7- szipl.l2b21oO IMP1.10-2ul000 135,431 0.

ЗАКЛЮЧЕНИЕ

Несмотря на то что преобразование Барроуза - Уилера было опубликовано сравнительно недавно, оно пользуется большим вниманием со стороны разработчиков архиваторов. И пожалуй, еще впереди новые исследования, которые позволят повысить эффективность сжатия на основе BWT еще в большей степени.

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

Скорость сжатия - на уровне архиваторов, применяющих словарные методы, например LZ77. Разжатие, как правило, в 3-4 раза быстрее сжатия.

Степень сжатия сильно зависит от типа данных.

Наиболее эффективно применение BWT-архиваторов для текстов и любых данных со стабильными контекстами. В этом случае рассматриваемые компрессоры по своим характеристикам близки к программам, использующим РРМ. На неоднородных данных существующие архиваторы на основе BWT немного уступают лучшим современным компрессорам, используюhttp://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) щим словарные методы или РРМ. Впрочем, существуют способы компенсировать этот недостаток.

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

ЛИТЕРАТУРА

1. Кадач А. В. Эффективные алгоритмы неискажающего сжатия текстовой информации: Дис. к. ф-м. н. - Ин-т систем информатики им.

А. П. Ершова. М., 1997.

2. Albers S., v.Stengel В., Werchner R. A combined BIT and TIMESTAMP Algorithm for the List Update Problem. 1995.

3. Ambuhl C, Gartnerm В., v.Stengel B. A New Lower Bound for the List Update Problem in the Partial Cost Model. 1999.

4. Arimura M., Yamamoto H. Asymptotic Optimality of the Block Sorting Data Compression Algorithm. 1998.

5. Arnavaut Z., Magliveras S. S. Block Sorting and Compression // Proceedings of Data Compression Conference. 1999.

6. Arnavaut Z., Magliveras S. S. Lexical Permutation Sorting Algorithm.

7. Baik H-K., Ha D.S., Yook H-G., Shin S-C, Park M-S. A New Method to Improve the Performance of JPEG Entropy Coding Using Burrows-Wheeler Transformation. 1999.

8. Baik H., Ha D. S., Yook H-G., Shin S-C, Park M-S. Selective Application of Burrows-Wheeler Transformation for Enhancement of JPEG Entropy Coding.

9. Balkenhol В., Kurtz S. Universal Data Compression Based on the Burrows and Wheeler-Transformation: Theory and Practice.

10. Balkenhol В., Kurtz S., Shtarkov Y.M. Modifications of the Burrows and Wheeler Data Compression Algorithm // Proceedings of Data Compression Conference.

Snowbird: Utah, IEEE Computer Society Press, 1999. P. 188-197.

11. Balkenhol В., Shtarkov Y.M. One attempt of a compression algorithm using 12. Baron D., Bresler Y. Tree Source Identification with the BWT. 2000.

13. Burrows M., Wheeler D.J. A Block-sorting Lossless Data Compression Algorithm // SRC Research Report 124, Digital Systems Research Center, Palo Alto, May 1994. http://gatekeeper.dec.com/pub/DEC/SRC/researchreports/SRC-124.ps.Z.

Методы сжатия данных 14. Chapin В. Switching Between Two On-line List Update algorithms for Higher Compression of Burrows-Wheeker Transformed Data // Proceedings of Data Compression Conference. 2000.

15. Chapin В., Tate S. Higher Compression from the Burrows-Wheeler Transform by Modified Sorting. 2000.

16. Deorowicz S. An analysis of second step algorithms in the Burrows-Wheeler compression algorithm. 2000.

17. Deorowicz S. Improvements to Burrows-Wheeler Compression Algorithm.

18.Fenwick P. M. Block sorting text compression // Australasian Computer Science Conference, ACSC'96, Melbourne, Australia, Feb 1996. ftp://ftp.es.

auckland.ac.nz/out/peter-f/ACSC96.ps.

19.Ferragina P., Manzini G. An experimental study of an opportunistic index.

2O.Kruse H., Mukherjee A. Improve Text Compression Ratios with BurrowsWheeler Transform. 1999.

21. Kurtz S. Reducing the Space Requirement of Suffix Trees.

22. Kurtz S. Space efficient linear time computation of the Burrows and Wheeler Transformation // Proceedings of Data Compression Conference. 2000.

23. Kurtz S., Giegerich R., Stoye J. Efficient Implementation of Lazy Suffix Trees. 1999.

24. Larsson J. Attack of the Mutant Suffix Tree.

25. Larsson J. The Context Trees of Block Sorting Compression.

26. Larsson J., Sadakane K. Faster Suffix Sorting.

27. Manzini G. The Burrows-Wheeler Transform: Theory and Practice. 1999.

28. Nelson P.M. Data Compression with the Burrows Wheeler Transform // Dr. Dobbs Journal. Sept 1996. P 46-50. htф://web2.aшnail.net'markn/articles^wt/bwtJltm.

29. Sadakane K. A Fast Algorithm for Making Suffix Arrays and for BWT.

30. Sadakane K. Comparison among Suffix Array Constructions Algorithms.

31. Sadakane K. On Optimality of Variants of Block-Sorting Compression.

32. Sadakane K. Text Compression using Recency Rank with Context and Relation to Context Sorting, Block Sorting and PPM.

33. Schindler M. A Fast Block-sorting Algorithm for lossless Data Compression // Vienna University of Technology. 1997.

34. Schulz F. Two New Families of List Update Algorithms. 1998.

35. Ryabko B. Ya. Data Compression by Means of a "Book Stack"// Problems of Information Transmission. Vol. 16(4). 1980. P. 265-269.

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) Глава 6. Обобщенные методы сортирующих преобразований Сортировка параллельных блоков Английское название метода - Parallel Blocks Sorting (PBS).

Два блока А и- В называются параллельными, если каждому элементу A[i] первого блока поставлен в соответствие один элемент B[i] второго блока и наоборот. Длины блоков LA и LB равны: L A - L B = L. Размеры элементов блоков RA и RB могут быть разными.

Основная идея метода PBS состоит в сортировке элементов In[i] входного блока In и их раскладывании в несколько выходных блоков Out, на основании атрибутов А[] этих элементов. Атрибут А[/] есть значение функции А, определяемой значениями предшествующих элементов 1п[/] и/или элементов ?[к] из параллельного блока Р:

A[i]=A(i, In[j], P[k]), i=0...L-l; j=0,...,i-1; k=0,...,L-l При декодировании осуществляется обратное преобразование: элементы из нескольких блоков Out, собираются в один результирующий, соответствующий несжатому блоку In (рис. 6.1).

Чем лучше значения 1п[/] предсказуемы по значениям А[/], тем эффективнее последующее сжатие блоков Out,- с помощью простых универсальных методов.

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

Размер данных в результате применения PBS, как и при ST/BWT, не изменяется. Для сжатия результата работы метода может быть применена любая комбинация методов - RLE, LPC, MTF, DC, HUFF, ARIC, ENUC, SEM...

В общем случае скорость Vc работы компрессора (реализующего прямое, "сжимающее" преобразование) равна скорости VD декомпрессора (реализующего обратное, "разжимающее" преобразование) и зависит только от размера данных, но не от их содержания: Ус = VD = O(L). Памяти требуется 2L+C. Константа С определяется особенностями реализации и может быть довольно большой. Операций умножения и деления нет.

Методы сжатия банных Рис. 6.1. Иллюстрация PBS: атрибут А[\] определяется значением элемента Р[\];

Из краткого описания общей идеи видно, что • для распаковки нужно иметь не только содержимое сортированных блоков Outj, но и их размеры;

• параллельных блоков может быть и два, и больше;

• если функция А не использует те ?[k], которые находятся после текущей позиции I, т. е. Л=/+1,..., L, то можно создавать параллельный блок Р одновременно с текущим сортируемым In;

• если А задана так, что принимает мало значений: от 2 до, допустим, 16, метод вполне может быть применим и к потокам данных;

• если параллельного блока Р нет, получаем ST/BWT как частный случай

ОСНОВНОЙ АЛГОРИТМ ПРЕОБРАЗОВАНИЯ

В простейшем случае сортирующего преобразования ST(1) значение атриR бута вычисляется так: А[/]=1п[/-1]; при ST(2): A[/]=In[/-l]-2 + In[i-2] и т. д.

В простейшем случае PBS А[/]=Р[/], т. е. значение атрибута равно значению элемента из параллельного блока. Выходных блоков столько, сколько значений принимают ?[{]. Делая проход по Р, считаем частоты значений атрибута и в реhttp://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) зультате получаем размеры сортированных блоков (далее - контейнеров), в которые будем раскладывать элементы из входного блока In:

In - входной сортируемый блок длины L;

Р - параллельный блок длины L;

L - количество элементов во входном блоке;

л=2 - число всех возможных значений атрибута;

Attrfn] - частоты значений атрибута.

Например, в Р содержатся старшие 8 бит массива 16-битовых чисел, а в In - младшие 8. Заметим, что этот процесс "дробления" можно продолжать и дальше, создавая вплоть до 16 параллельных блоков: содержащий первые биты, вторые, и т. д. Кроме того, при сжатии мультимедийных данных часто уже имеются параллельные блоки, например левый и правый каналы стереозвука, красная, зеленая и синяя компоненты изображения и т. п.

Если функция А задана иначе, то и при подсчете частот формула будет иной:

// A[i]=255-P[i] :

for( i - 1 ; iL; i++) Attr[ (P[i]+P[i-1])/2 ]++;

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

tmp=Attr[а]; // длина текущего а-го контейнера Attr[a]=pos; // теперь там адрес-указатель на его начало // (указатель на начало свободного места б нем) pos+=tmp; // начало следующего - дальше на длину текущего В том же массиве Attr[n] теперь адреса-указатели на начала контейнеров.

Остается только пройти по входному блоку, раскладывая элементы из него по контейнерам:

Методы сжатия данных Out - выходной отсортированный блок (sorted, transformed), содержащий все контейнеры. Подробнее:

for( i=0; iL; i++) { // На каждом шаге:

s = I n [ i ] ; / / берем следующий элемент s из входного блока In, a = P [ i ] ; / / берем его атрибут а из параллельного блока Р, // и адрес свободного места в контейнере, задаваемом этим а;

pos=Attr[a];

// кладем элемент s в выходной блок Out по этому адресу, Out[pos]=s;

pos++; //теперь в этом контейнере на один элемент больше, A t t r [ a ] = p o s ; / / а свободное место - на один элемент дальше.

Функция А - та же, что и во втором цикле. То есть, для выше рассмотренных примеров:

(2а) a=P[i]&252;

ОБРАТНОЕ ПРЕОБРАЗОВАНИЕ

Совершенно идентичны первые 3 цикла: инициализируем, в результате прохода по параллельному блоку находим длины контейнеров, затем определяем адреса начал контейнеров во входном отсортированном блоке In.

Именно эти адреса - цель выполнения первых трех циклов. И только в четвертом цикле, наоборот, берем из отсортированного блока с контейнерами In, кладем в единый выходной блок Out:

for(i=0;iL; i++) O u t [ i ] = I n [ A t t r [ P [ i ] ]++]; //(4d) In - входной отсортированный блок со всеми контейнерами;

Out - создаваемый выходной блок.

Подробнее:

for( i=0;

a=P[i];

pos=Attr[a];

//так было при прямом (сжимающем) преобразовании:

//Out[pos]=In[i];

//(в текущих обозначениях это записывается так:

//In[pos]=Out[i];) //а так делаем сейчас, при разжимающем преобразовании:

Out[i]=In[pos];

pos++;

Attr[a]=pos;

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии)

ПУТИ УВЕЛИЧЕНИЯ СКОРОСТИ СЖАТИЯ

Итак, в обоих случаях выполняем два цикла от 0 до n=2 и два цикла от О до L. Какой из них займет больше времени? Чаще всего Д=8, и=256, a L - от нескольких килобайт до десятков мегабайт. И четвертый, главный цикл самый долгий, второй выполняется быстрее, а третий и особенно первый совсем быстро.

Но возможна и обратная ситуация: если, например, Д=16, и=2 =65536, а 1=512, т. е. требуется сжать поток блоков из 512 16-битовых элементов (поток "фреймов"). Тогда, наоборот, самым долгим будет третий цикл, затем первый, четвертый и второй.

Два цикла при больших R Если памяти хватает, поступим так: будем наполнять контейнеры не одновременно, проходя по In, P и записывая элементы In[i] в вычисляемые адреса блока Out, а последовательно: проходя по Out и вычисляя адреса в In, Р, из которых нужно брать значения атрибута и элементы, помещаемые затем в Out. Останутся два цикла от 0 до I, а циклы от 0 до л=2* исчезнут.

При первом проходе заполняем вспомогательный массив Anext, содержащий цепочки указателей на позиции с одинаковыми атрибутами (Ацепочки). То есть в Anext[i] записываем указатель на следующую позицию (i+k) с таким же значением атрибута A[i], если таковая (i+k) в оставшейся части блока есть. В противоположном случае, если в оставшейся части блока атрибут не принимает значение А[(], в Anextfi] записываем /.

// при инициализации: вспомогательные массивы int Anext[L];

int Beg[n]; // начала, int End[n]; // концы и int Flg[n]; // флаги наличия А-цепочек в текущем фрейме / / в цикле для каждого фрейма:

FrameNumber++; // следующий L-элементный фрейм for( i=0; iL; i++) { if(Flg[a]==FrameNumber) //если цепочка, определяемая этим а, e=End[a]; // то конец ее - в массиве концов цепочек Anext[e]=i;// теперь прошлый конец указывает на новый else Flg|a]=FrameNumber;// запишем, что такая цепочка есть Методы сжатия данных Anext[i]=i; / / текущий элемент А-цепочки - ее конец End[a]=i; / / укажем конец в массиве концов цепочек Массив Fig нужен только затем, чтобы инициализировать не Beg и End перед каждым фреймом, а только Fig перед всеми фреймами. Если создать еще два массива Fprev и Fnext, соединяющие все элементы Fig с одним значением в одну F-цепочку (причем Fnext указывает на следующий элемент Fцепочки, Fprev - на предыдущий), то не придется при втором проходе линейно искать в Fig появлявшиеся в текущем фрейме А-цепочки. И цикла от О до л удастся избежать. Соответствующие изменения читатель легко внесет в алгоритм сам.

При втором проходе выполняем сортировку:

pos=f=0;

while (Fnext[f]!=f) { / / (линейный поиск следующей } while(i!=Anext[i]) //до конца На этот раз во втором цикле уже нет обращений к Р, поэтому можно совместить А и Р. Памяти же требуется не 2 1 + /rsizeof(*char), a 2-L + 5-/isizeof(*char), так как Beg, End, Fig, Fprv, Fnxt занимают по nsizeof(*char) байт.

Два цикла при малых R Если памяти доступно больше, чем необходимо для хранения 2-L+n-C элементов, и С достаточно велико - 256 или, например, 512, можно сразу "расформатировать" память под начала контейнеров:

#define К 256;

for( i=0; in; i++) Attr[i]=i*K; // (Ism) // под каждый из п контейнеров отведено К элементов // (1 "сектор") http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) И затем при проходе по In, P, если свободное место в каком-то контейнере кончается, будем записывать в конце "сектора" указатель на следующий сектор, выделяемый под продолжение этого контейнера:

FreeSector=n;

a=P[i]; // берем атрибут а из параллельного блока Р, pos=Attr[a];// и адрес свободного места в контейнере, Out[pos]=In[i];

pos++;

if(pos%K+sizeof(*char)==K)//если свободное место кончилось, Out[pos]=FreeSector;//пишем указатель на следующий сектор // если FreeSector типа int32, a Out[i] типа int8, то:

// Out[pos] =FreeSector%256;

// Out[pos+l] = (FreeSector»8)%256;

// 0ut[pos+2] = (FreeSector»16) %256;

// Out[pos+3] = (FreeSector»24)%256;

pos=FreeSector*K;//свободное место= начало нового сектора FreeSector++; // свободный сектор на один сектор дальше Attr[a]=pos;

Упражнение. Сравните этот цикл с (4с) и оцените, насколько он будет медленнее.

Это очень выгодно, если л256, и, кроме того, после PBS выполняется еще один проход по всем элементам блока Out. Как правило, это так. Таким образом, весь алгоритм сводится к одному тривиальному циклу (Ism) и одному проходу по данным (2sm).

УВЕЛИЧЕНИЕ СКОРОСТИ РАЗЖАТИЯ

Ускорение разжатия возможно, если длины контейнеров сжимать и передавать отдельно. Если L существенно больше л, описание длин занимает незначительную часть сжатого блока, так что потери в степени сжатия будут невелики. Тогда в массив Attr[«] при разжатии можно сразу записывать не длины, а начала контейнеров. Заметим, что и в случае ST/BWT это даст заметное увеличение скорости: подсчет частот элементов требует при разжатии дополнительного прохода по данным.

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

ПУТИ УЛУЧШЕНИЯ СЖАТИЯ

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

Если параллельный блок уже существует и не изменяется при прямом и обратном преобразовании, функцию А можно строить без всяких ограничений, используя любую комбинацию арифметических, логических и других операций. Например, A[i]=(int)P[i]/2; // деление целочисленное Если сравнивать со случаем A[i] = P[J], то можно сказать, что каждая пара контейнеров объединяется в один "двойной" контейнер.

A [ i ] = P [ i ] А ( п - 1 ) ; // или, что то же самое, A[i]=n-1-P[i].

То есть контейнеры будут лежать в Out в обратном порядке по сравнению с А[/]=Р[/]. Это полезно для второго отсортированного блока Out2, записываемого за первым Outl, особенно если данные мультимедийные, поскольку в этом случае значения In[i] и 1п[/+1], как правило, близки.

Еще два варианта вычисления атрибута:

Младшие 4 бита изменяются только на +1 или - 1 :

abs(P[i]&15-P[i-l]&15)=l.

Расстояние до нуля, а знак - в младшем бите.

Упражнение. Напишите к последним двум формулам формулы обратного преобразования.

Функция А может быть и адаптивной, т. е. производится периодическая корректировка каких-то ее коэффициентов, чтобы выходной блок больше соответствовал заданному критерию. Например, известно, что последние 20контейнеров из 256 полезно объединять в четверки, а остальные - в пары:

// последние 256-232=24 контейнера объединяем в четверки К=232;

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

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) где Out[/]-Out[M] - первая производная блока.

Тогда можно вычислять SumCurrent+=Out [ i ] -Out [ i. - l ], при текущем значении К, SumMinus+=Outm[i]-Outm[i-l] при К=К-4, SumPlus+=Outp[i]-Outp[i-1] при К=К+4, и через каждые StepK шагов выбирать новое значение К по результату сравнения SumCurrent, SumMinus и SumPlus:

if (SumMinusSumCurrent && SumMinusSumPlus) K=K-4;

else if (SumPlusSumCurrent) K=K+4;

Может оказаться полезным сохранять блок А вместо Р, особенно если параллельный блок строится одновременно с сортируемым, например, Р[/] вычисляется по Р[«-1] и In[i-1]. Тогда Р должен быть восстановим по А и функция А должна быть биективной: по значению A[iJ=A(P[/]) однозначно находится P[i]. Реально такая функция А сводится к перестановке: имеем контейнеры с атрибутами А[г]=Р[/], затем перетасовываем их, меняя местами внутри единого выходного блока Out, но не изменяя их содержимого. Но формально А может выглядеть очень по-разному, содержать прибавление константы:

A[i]=P[i]+123; // результат берется по модулю п логический XOR:

A[i]=P[i]A157;

сравнения и перестановки битов, в том числе циклическим вращением:

Упражнение. Как будет выглядеть А, собирающая вместе элементы ln(i], соответствующие тем Р[/], остаток которых от деления на заданное К одинаков?

Начните со случаев К=4 и К=8.

Если функция А неадаптивна или зависит только от элементов параллельного блока, сами контейнеры, поскольку их длины известны, можно сортировать внутри единого выходного блока по их длинам. Это может улучшить сжатие даже при ST/BWT, особенно в случае качественных данных, а не количественных. Часто оказывается выгодным группировать короткие контейнеры в одном конце выходного блока, а длинные - в другом.

И при сжатии, и при разжатии процедура сортировки контейнеров по длинам добавится между циклами (2) и (3).

Рассмотрим последний вариант: весь блок А сохраняется и передается (компрессором декомпрессору), поэтому и строится он именно с учетом таКнига написана коллективом http://www.compression.ru/ Методы сжатия данных кой особенности. Если есть параллельный блок Р, можно строить А так, чтобы и Р преобразовывать на основе А, и чтобы суммарно блоки А, Р, In сжимались лучше, чем Р и In. Если нет Р, то получается, что In распадается на две компоненты: "идеальную" - моделируемые, предсказываемые А[/], и "реальную" - отклонения In[i] от предсказанных значений А[/].

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

//если известны т е, что выше и л е в е е, то соседних - четыре:

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

Заметим важное полезное свойство метода: увеличение сложности вычислений не влечет увеличения объема необходимой памяти.

Если рассматривать множество строк как единый блок, то в простейшем случае A[»]=P[i]=In[*-№] {W- число элементов в строке), т. е. в качестве атрибута используется значение "верхнего" элемента. Тогда таблицу длин сохранять не нужно, но первые ^элементов в неизменном виде - обязательно.

Упражнение. Опишите подробно алгоритм сортировки в случае A[i]=ln[i-W].

Характеристики методов семейства PBS:

Степень сжатия: увеличивается в 1.0-2.0 раза.

Типы данных: многомерные или многоуровневые данные.

Симметричность по скорости: в общем случае 1:1.

Характерные особенности: необходимо наличие как минимум двух параллельных блоков данных.

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) Фрагментирование Цель: разбиение исходного потока или блока на фрагменты с разными статистическими свойствами. Такое разбиение должно увеличить степень последующего сжатия. В простейшем случае битового потока необходимо находить границы участков с преобладанием нулей, участков с преобладанием единиц и участков с равномерным распределением нулей и единиц.

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

Основная идея состоит в том, чтобы для каждой точки потока X (лежащей между парой соседних элементов) находить значение функции отличия YO{X) предыдущей части потока от последующей. В базовом простейшем варианте используется "скользящее окно" фиксированной длины: Z элементов до точки Хи Z элементов после нее.

Иллюстрация (Z=7):

...8536429349586436542 19865332 \Х\ 6564387 158676780674389...

Цифрами обозначены элементы потока, вертикальными чертами "|" границы левого и правого окон. Хне элемент потока, а точка между парой элементов, в данном случае между "2" и "6".

При фиксированной длине окон Z и одинаковой значимости, или весе, всех элементов внутри окон (независимо от их удаленности от точки X) значение функции отличия может быть легко вычислено на основании разности частот элементов в левом и правом окнах. Это сумма по всем 2 я возможным значениям F, элементов. Суммируются абсолютные значения разностей: число элементов с текущим значением V в левом окне длиной Z минус число элементов с данным значением V в правом окне длиной Z.

Суммируя 2 я модулей разности, получаем значение О(Х) в данной точке X:

где CountLeftf/7] - число элементов со значением V в левом окне; CountRight[F] - число элементов со значением К в правом окне.

Видно, что если в обоих окнах элементы одинаковые, то сумма будет стремиться к нулю, если же элементы совершенно разные - к 2Z.

Для приведенного выше примера:

Методы сжатия данных После того как все значения FO(A) найдены, остается отсортировать их по возрастанию и выбрать границы по заданному критерию (заданное число границ и/или пока FO(X)Fmin).

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

Для сжатия результата работы метода может быть применена любая комбинация методов- RLE, LPC, MTF, DC, PBS, HUFF, ARIC, ENUC, SEM...

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

Обратного преобразования не требуется.

В общем случае скорость работы компрессора зависит только от размера данных, но не от их содержания: Скорость=О(Размер). Памяти требуется порядка 2 Я+1. Для левого окна - О(2Л), и столько же для правого. Операций умножения и деления нет.

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

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

• задаваемыми параметрами могут быть (максимальная) длина окна Z, Fmin- минимальное значение О(Х), минимальное расстояние между границами Rmin (а в случае фрагментирования блока заданной длины еще и число границ NG, минимальное и/или максимальное число границ:

tynin, Nmax);

• вычисление функции отличия при нескольких длинах окон - 2\,2г, •••..., Zn - в общем случае улучшит качество фрагментирования;

• уменьшение веса элементов окна с удалением от точки Л'также в общем случае улучшит качество фрагментирования.

ОСНОВНОЙ АЛГОРИТМ ПРЕОБРАЗОВАНИЯ

Каков бы ни был размер окон Z, при проходе по входным данным In[7V] в каждой точке X при переходе к следующей точке (Х+1) достаточно следить за тремя элементами: вышедшим из левого окна (из-за сдвига точки ^вправо), вошедшим в правое окно и перешедшим из правого окна в левое. Но http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) сначала разберем самый понятный алгоритм: с проходом по всем элементам окон для каждой точки X.

#define Z for( i=0; in; i++) i=In[x]; //возьмем очередной элемент левого окна 1п[х] CountLeft[i]++; //в левом окне элементов на 1 больше CountRight[i]++;

\n[N] - входной фрагментируемый блок;

- количество байтов во входном блоке;

л=2* - каждый байт может иметь 2 R значений;

FO[N-2-Z] - значения функции отличия;

CountLeftfn] - частоты элементов в левом окне;

CountRight[/i] - частоты элементов в правом окне.

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

for(x=Z; xN-Z-l;

for( i=0; in; i++) //вычислим по формуле как сумму f+=abs(CountLeft[i]-CountRight[i]);/*т. е.если без abs() FO[x]=f; IЫ запишем в массив for(i=0;in;i++) CountLeft[i]=Coun-Right[i]=0;//как в (1) for(j=x+l-Z;jx+l;j++){ //цикл по длине окон: как в (2) CountLeft[Intj]]++;//подсчет частот элементов в левом окне CountRight[In[j+Z]]++; 1Ы аналогично в правом )//но теперь левая граница левого окна - в позиции (x+1-Z) Наконец, последний цикл - это либо сортировка FO[7V] с целью нахождения заданного числа максимальных значений (заданного числа самых "четких" границ), либо просто нахождение таких FO[A;], значение которых больше заданного. Последнее можно делать в основном цикле.

Методы сжатия данных "23ч Упражнение. Внесите необходимые изменения в (3), если задано минимальное значение отличия Fmin.

ПУТИ УЛУЧШЕНИЯ СКОРОСТИ

Если последние два цикла внутри (3) перенести и выполнять их до первого, вычисляющего FO, то (1) и (2) не нужны. Но поскольку внутри циклапрохода (3) по In достаточно следить за тремя элементами, в нем вообще не будет внутренних циклов. После выполнения (1) и (2) поступим так:

f=0; //исходное значение функции отличия for( i=0; in; i++) //вычислим по формуле как сумму (2а) f+« abs(CountLeft[i]-CountRight[i]);

FO[0]=f; //и запишем в массив А внутри основного цикла, проходящего по входному блоку In[N]:

for(x=Z; xN-Z-l;x++) { i=In[x-Z]; //элемент, вышедший из левого скользящего окна f-=abs(CountLeft[i]-CountRight[ i ]);

//сумма без 1 слагаемого CountLeft[i]—; //теперь в левом окне таких на 1 меньше f+=abs(CountLeft[i]-CountRight[i]) ;

//обратно к полной сумме i=In[x+Z]; //элемент, вошедший в правое окно //совершенно аналогично обновлению для левого окна f-=abs(CountLeft[i]-CountRight[i]) ;

CountRight[i]++; //теперь в правом окне таких на 1 больше f+=abs(CountLeft[ij-CountRight[i]) ;

i»In[x];//элемент, перешедший из правого окна в левое f-=abs(CountLeft[i]-CountRight[i]);

CountLeft[i]++; //теперь в левом окне таких на 1 больше CountRight[i]—; //а в правом - на 1 меньше f+-abs(CountLeft[i]-CountRight[i]);

FO[x]=f;//запишем значение функции отличия в массив Упражнение. Как изменится значение f, если все 3 элемента одинаковы, причем в левом окне таких было 7, а в правом 8?

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

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) f=0; // исходное значение функции отличия stacksize=O; // и размера стека i=In[x]; // текущий элемент s=0; // просмотрим все уже обработанные:

while(sstacksize) if (Stack[s]==i) goto NEXT // если элемент еще не вошел f+= abs(CountLeft[i]-CountRight[i]) ;

Stack[stacksize++]=i; // то вносим сейчас NEXT:

FO[0]=f; // запишем в массив Точно так же можно модифицировать первый цикл внутри (3), вычисляющий FO: вместо него будет (2z), т. е. цикл не до я, а до 2-Z.

Чтобы избавиться от второго цикла до п внутри (3), заведем два массива с флагами FlagLeft и FlagRight, параллельные CountLeft и CountRight. В них будем записывать, в какой позиции х делалась запись в соответствующую позицию массива Count. При чтении же из Count будем читать и из Flag. Если значение в Flag меньше текущего х, то в соответствующей ячейке массива Count должен быть нуль.

Упражнение. Перепишите (3) так, чтобы не было циклов до л.

ПУТИ УЛУЧШЕНИЯ СЖАТИЯ

Общий случай Самый выгодный путь - использование окна с убыванием веса элементов при удалении от точки X. Линейное убывание, например: вес двух элементов, между которыми лежит точка X, равен Z, вес двух следующих, на расстоянии I от X, равен Z-1, и т. д., (Z-d) у элементов на расстоянии d, нуль у элемента, только что вышедшего из левого окна, и у элемента, который войдет в правое окно на следующем шаге.

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

В первом случае - Z существенно меньше п, выгоднее цикл до Z - вместо инкрементирования будем добавлять веса, т. е. расстояния от А'до дальней границы (самой левой в случае левого окна, самой правой в случае правого):

f o r ( x=0; xZ; x++) { //цикл по длине окон:

Методы сжатия данных II CountLeft[In[x]]++; //так было в цикле (2) // CountRight[In[x+Z]]++;//а теперь: прибавляем CountLeft[In[x]]+=х+1; // расстояние от левой границы до х, CountRight[In[x+Z]]+=Z-x;// от x+Z до правой границы:

И аналогичные модификации в цикле (3).

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

for(x=Z;xN-Z-l;x++) {//точка X - с позиции Z до N-Z-1 3**) f=0;

for (i=0;in; i++) // как изменятся веса элементов со значением WeightLeft[i]-=CountLeft[i]; // всего их CountLeft[i], WeightRight[i]+=CountRight[i]); // а каждый правый - на + // считаем значение отличия f+=abs(WeightLeft[i]-WeightRight[i]) ;

// теперь сдвинем х на 1 вправо, внося и вынося элементы i=In[x-Z];//элемент, вышедший из левого скользящего окна CountLeft[i]—; // теперь в левом окне таких на 1 меньше //вес его уже 0, поэтому WeightLeft[i] не изменен i=In[x+Z]; //элемент, вошедший в правое окно f-=abs(WeightLeft[i]-WeightRight[i]);

// сумма без 1 слагаемого CountRight[i]++;//теперь в правом окне таких на 1 больше WeightRight[i]++;//и вес их на 1 больше // обратно к полной сумме f+=abs(WeightLeft[i]-WeightRight[i]) ;

i=In[x]; // элемент, перешедший из правого окна в левое f-=abs(WeightLeft[i]-WeightRight[i]);

// сумма без 1 слагаемого CountLeft[i]++; // теперь в левом окне таких на 1 больше WeightLeft[i]+=Z; // вес их на Z больше CountRight[i]—; II а в правом - на 1 меньше WeightRight[i]-=Z; // вес их на Z меньше // обратно к полной сумме f+=abs(WeightLeft[i]-WeightRight[i]);

http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) FO[x]=f; // запишем значение функции отличия в массив Упражнение. Как будут выглядеть циклы (1) и (2) ?

Второй путь улучшения качества фрагментирования - находить максимальное значение функции отличия при нескольких длинах окна: Z|, Z 2,...

..., Z q. Тогда эти вычисляемые значения FO; придется делить на длину соответствующего окна Zj, при котором это FOj вычислено. И предварительно умножать на 2К, чтобы получались величины не от 0 до 2, а от 0 до 2* + l.

Третий путь - периодическое (через каждые Y точек) нахождение оптимальной длины окна 20.

Четвертый - анализ массива FO после того, как он полностью заполнен.

Пятый - использование и других критериев при вычислении FO(A), например не 2| CountLeft[V] - CountRight[V] |, a Z(CountLeft[V] - CountRightfV])2.

D-мерный случай В двумерном случае появляется возможность следить за изменением характеристик элементов при перемещении через точку Л!" по К разным прямым. В простейшем варианте - по двум перпендикулярным: горизонтальной и вертикальной.

Алгоритм может выглядеть, например, так: сначала проходим по строкам и заполняем массив FO значениями функции отличия при горизонтальном проходе: FO[A]=FOrop(A). Затем идем по столбцам, вычисляя отличия при вертикальном проходе F O B E P W записывая в массив максимальное из этих двух значений - FO rO p(^0 и F O B E P W - Дальше можно таким же образом добавить FO при двух диагональных проходах (рис. 6.2), причем не для каждой точки, а в окрестностях точек с максимумами FO[A].

Рис. 6.2. Иллюстрация двумерного случая с К= Кроме того, если хватает ресурсов, можно рассматривать отличие не отрезков длиной Z, отмеченных на К прямых, а секторов круга радиуса Z, разбитого на К секторов. Это могут быть, например, две половины круга или же 4 четвертинки круга.

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

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

В трехмерном случае: либо используем Кп прямых, либо Кк секторов круга, либо Кс секторов сферы. Причем оптимальные (с точки зрения вычисления) значения Кп не 2,4, 8..., как в двумерном, а 3,7, 13...

Упражнение. Нарисуйте эти варианты с тремя прямыми, семью и тринадцатью. Как продолжить процесс дальше?

Совершенно аналогично и в D-мерном случае.

Характеристики метода фрагментирования:

Степень сжатия: увеличивается в 1.0-1.2 раза.

Типы данных: неоднородные данные, особенно с точными границами фрагментов.

Симметричность по скорости: более чем 10:1.

Характерные особенности: может применяться не только для сжатия данных, но и для анализа их структуры.

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

Исходные данные - препроцессор - кодер - сжатые данные а схема декодирования:

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

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

В общем случае преобразования, выполняемые препроцессором, могут быть реализованы в кодере и при этом быть такими же эффективными с http://www.compression.ru/ (7000+ файлов, 850Мб о сжатии) ТОЧКИ зрения улучшения сжатия. Но предварительная обработка позволяет существенно упростить алгоритм работы кодера и декодера, дает возможность создания достаточно гибкой специализированной системы сжатия данных определенного типа на основе универсальных алгоритмов. Модули препроцессор-постпроцессор обычно можно применять в сочетании с различными кодерами и архиваторами, повышая их степень сжатия и, возможно, скорость работы.

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

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

В настоящее время специализированный препроцессинг текстов, позволяющий заметно улучшить сжатие, используется в таких архиваторах, как ARHANGEL, JAR, RK, SBC, UHARC, в компрессорах DC, PPMN.

ИСПОЛЬЗОВАНИЕ СЛОВАРЕЙ

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

Можно выделить несколько стратегий построения словаря. По способу построения словари бывают:

• статическими, т. е. заранее построенными и полностью известными как препроцессору, так и постпроцессору;



Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 8 |
 
Похожие работы:

«пользователя BlackBerry Messenger Руководство Версия: 8.1 Опубликовано: 2014-01-06 SWD-20140106161617577 Содержание Сведения о BBM Преимущества использования BBM Новые функции BBM Значки BBM Проверка наличия новой версии BBM Требования Часто задаваемые вопросы Зачем нужен BlackBerry ID при использовании BBM? Какие звуки можно установить для BBM? Как отключить вибрацию при проверке связи? Начало работы с BBM Перемещение между разделами BBM Добавление контакта путем сканирования штрих-кода...»

«Всемирная организация здравоохранения ШЕСТЬДЕСЯТ СЕДЬМАЯ СЕССИЯ ВСЕМИРНОЙ АССАМБЛЕИ ЗДРАВООХРАНЕНИЯ A67/19 Пункт 14.1 предварительной повестки дня 4 апреля 2014 г. Мониторинг достижения связанных со здоровьем Целей тысячелетия в области развития Доклад Секретариата Исполнительный комитет на своей Сто тридцать четвертой сессии принял 1. к сведению предыдущий вариант этого доклада 1. Нижеследующий вариант доклада был обновлен (в частности, пункты 2, 4, 6, 10, 14, 19, 20, 22, 23, 24 и 26) с учетом...»

«ОРГАНИЗАЦИЯ A ОБЪЕДИНЕННЫХ НАЦИЙ Distr. ГЕНЕРАЛЬНАЯ АССАМБЛЕЯ GENERAL A/HRC/WG.6/4/AZE/1 4 November 2008 Original: RUSSIAN СОВЕТ ПО ПРАВАМ ЧЕЛОВЕКА Рабочая группа по универсальному периодическому обзору Четвертое сессия Женева, 2-13 Февраль 2009 года НАЦИОНАЛЬНЫЙ ДОКЛАД, ПРЕДСТАВЛЕННЫЙ В СООТВЕТСТВИИ С ПУНКТОМ 15 A) ПРИЛОЖЕНИЯ К РЕЗОЛЮЦИИ 5/ СОВЕТА ПО ПРАВАМ ЧЕЛОВЕКА * Азербайджан _ Настоящий документ до его передачи в службы письменного перевода Организации Объединенных Наций не...»

«А/61/48 Организация Объединенных Наций Доклад Комитета по защите прав всех трудящихся-мигрантов и членов их семей Третья сессия (12-16 декабря 2005 года) Четвертая сессия (24-28 апреля 2006 года) Генеральная Ассамблея Официальные отчеты Шестьдесят первая сессия Дополнение № 48 (А/61/48) А/61/48 Генеральная Ассамблея Официальные отчеты Шестьдесят первая сессия Дополнение № 48 (А/61/48) Доклад Комитета по защите прав всех трудящихся-мигрантов и членов их семей Третья сессия (12-16 декабря 2005...»

«Министерство образования и науки Российской Федерации ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ УДК 539.23 № госрегистрации 01201169146 Инв. № УТВЕРЖДАЮ Вице-директор Объединенного института ядерных исследований М. Г. Иткис __ 2012 г. ОТЧЕТ О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ ИССЛЕДОВАНИЕ ФУНКЦИОНАЛЬНЫХ И НАНОСТРУКТУРИРОВАННЫХ МАТЕРИАЛОВ С ИСПОЛЬЗОВАНИЕМ УНИКАЛЬНОЙ УСТАНОВКИ МОДЕРНИЗИРОВАННЫЙ ИМПУЛЬСНЫЙ РЕАКТОР ИБР- Государственный контракт от 12 мая 2011 г. № 16.518.11. Шифр 2011-1.8-518-...»

«Слоеный торт: Роман / Дж. Дж. Коннолли //ООО Издательство ACT МОСКВА, М, 2007 ISBN: ISBN 5-17-040865-Х FB2: “Paco ” vadymkh@gmail.com, 19.08.2007, version 1.0 UUID: 0c741596-a08a-102a-94d5-07de47c81719 PDF: fb2pdf-j.20111230, 13.01.2012 Дж. Дж. Коннолли Слоеный торт Будни дилера трудны – а порою чреваты и реальными опасностями! Купленная буквально за гроши партия первосортного товара оказывается (кто бы сомневался) КРАДЕНОЙ. притом не абы у каких бандитов, а у злобных скинхедов! Боевики скинов...»

«ЗАПИСКИ ВСЕСОЮЗНОГО МИНЕРАЛОГИЧЕСКОГО ОБЩЕСТВА Ч. CXIX 1990 Вып. 5 ХРОНИКА УДК 549 : 061.22.055.5 (47+57) ЗВМО, вып. 5, 1990 г. © 1990 г. ОТЧЕТ О ДЕЯТЕЛЬНОСТИ ВСЕСОЮЗНОГО МИНЕРАЛОГИЧЕСКОГО ОБЩЕСТВА В 1989 г. Число отделений в истекшем году не изменилось. I. Личный состав Общества В число действительных членов Всесоюзного минералогического общества в 1989 г. были при­ няты: Вахрушев С. Н., геолог (Свердлов, горн, ин-т), Абдурахманов Р. Ф., канд. геол.-мин. наук Веремеева Л. И., науч. сотр. ( И...»

«Енё Рэйтё Новые приключения Грязнули Фреда OCR Busya http://www.litres.ru/pages/biblio_book/?art=639735 Енэ Рейтэ Новые приключения Грязнули Фреда. Серия Книги хорошего настроения: АСТ-Пресс Книга; Москва; ISBN 978-5-462-00698-2 Аннотация На затерянном в безбрежных просторах Тихого океана острове бесследно исчез известный ученый-путешественник, почетный член Британского географического общества Густав Барр. Мировая научная общественность взволнована: неужели сего почтенного мужа постигла участь...»

«АНАЛИЗ РЫНКА АКЦИЙ: ТЕЛЕКОММУНИКАЦИИ Южная телекоммуникационная компания ПОКУПАТЬ 71% потенциал ПЕРЕСМОТР ОЦЕНКИ роста 21 мая 2008 г. Повышение справедливой стоимости до 0,26 долл. США за акцию Мы повышаем справедливую стоимость акций Южной телекоммуникационной компании (ЮТК) с 0,18 долл. США за акцию до 0,26 долл. США в связи с поправками, Начальник отдела: Филип Таунсенд которые мы внесли в нашу модель относительно перспектив выручки и рентабельности EBITDA компании. Согласно нашей новой...»

«Алексей Валентинович Фалеев Худеем в два счета Худеем в два счета: Феникс; Ростов-на-Дону; 2004 ISBN 5-222-04965-5 Аннотация Автор книги, кандидат наук, мастер спорта по пауэрлифтингу предлагает свою методику коррекции и поддержания оптимального веса, основанную на очищении организма от шлаков и паразитов, ежедневной минимальной физической нагрузке и правильном режиме питания. В книге содержатся многочисленные отзывы читателей, уже пробовавших на себе данную методику. Алексей Валентинович...»

«ВСЕМИРНАЯ ОРГАНИЗАЦИЯ ЗДРАВООХРАНЕНИЯ ЕВРОПЕЙСКОЕ РЕГИОНАЛЬНОЕ БЮРО КОПЕНГАГЕН ЕВРОПЕЙСКИЙ РЕГИОНАЛЬНЫЙ КОМИТЕТ Пятьдесят первая сессия, Мадрид, 10–13 сентября 2001 г. Пункт 7(b) предв арительной повестки дня EUR/RC51/8 + EUR/RC51/Conf.Doc./6 18 июля 2001 г. 10269M ОРИГИНАЛ: АНГЛИЙСКИЙ БЕДНОСТЬ И ЗДОРОВЬЕ – ФАКТИЧЕСКИЕ ДАННЫЕ И ДЕЙСТВИЯ В ЕВРОПЕЙСКОМ РЕГИОНЕ ВОЗ Бедность и нездоровье образуют порочный круг. Имеются свидетельства о том, что хорошее здоровье – это необходимая предпосылка для...»

«ВАЛЕНТИН СИМОВЕНКОВ ~~ШАРАШКИ)) IBBOBIQIOIIIIIЙ правкt Cta1111 ~ эксмо МОСКВА АЛГОРИТМ 2011 УДК 323 ББК 63.3 С37 Симоненков В. И. 1 Вален С Шарашки : инновационный проект Сталина 37 тин Симоненков.- М.: Эксмо : Алгоритм, 2011.- 192 с. ­ (Загадка 1937 года). ISBN 978-5-699-51049-8 В году были сняты грифы секретности на некоторые архивные 2009 фонды ОГПУ-НКВД-МВД, в том числе хранившие материалы о деятельности сталинских шарашек. Это название применялось для секретных НИИ и КБ, подчиненных...»

«ЕЖЕКВАРТАЛЬНЫЙ ОТЧЕТ Открытое акционерное общество Акционерная нефтяная Компания Башнефть Код эмитента: 00013-A за 4 квартал 2011 г. Место нахождения эмитента: 450008 Россия, Республика Башкортостан, г. Уфа, К. Маркса 30 Информация, содержащаяся в настоящем ежеквартальном отчете, подлежит раскрытию в соответствии с законодательством Российской Федерации о ценных бумагах Президент Дата: 10 февраля 2012 г. А.Л. Корсик подпись Главный бухгалтер Дата: 10 февраля 2012 г. А.Ю. Лисовенко подпись...»

«Обзор судебной практики Верховного Суда РФ за четвёртый квартал 2013 г. (утв. Президиумом Верховного Суда РФ 4 июня 2014 г.) Судебная практика по уголовным делам I. Квалификация преступлений 1. Убийство признаётся совершённым группой лиц только в том случае, если в его совершении участвует не менее двух исполнителей. Установлено, что И. и Р. находились в помещении животноводческой фермы, где распивали спиртное. Пришедший М. сделал И. замечание по поводу распития спиртного и предложил Р....»

«ЧТЕНИЯ ПАМЯТИ ВЛАДИМИРА ЯКОВЛЕВИЧА ЛЕВАНИДОВА Vladimir Ya. Levanidov's Biennial Memorial Meetings Вып. 2 2003 РЫБЫ РЕКИ САМАРГА (ПРИМОРСКИЙ КРАЙ) А. Ю. Семенченко Тихоокеанский научно-исследовательский рыбохозяйственный центр (ФГУП ТИНРО-Центр), тупик Шевченко, 4, Владивосток, 690950, Россия. E-mail: ansemench@tinro.ru; ansemench@mail.primorye.ru Приведены новые данные о промысловых рыбах, добываемых на самых северных приморских прибрежных рыбопромысловых участках. Показана значимость р....»

«УДК 519.63 ПАКЕТ ПАРАЛЛЕЛЬНЫХ ПРИКЛАДНЫХ ПРОГРАММ HELMHOLTZ3D1 Д.С. Бутюгин В работе представлен пакет параллельных прикладных программ Helmholtz3D, который позволяет проводить расчеты трехмерных электромагнитных полей с гармонической зависимостью от времени, распространяющиеся в трехмерных областях со сложной геометрией. Для решения возникающих в результате аппроксимаций систем линейных алгебраических уравнений (СЛАУ) с комплексными плохообусловленными неэрмитовыми матрицами используются...»

«FB2: “rusec ” lib_at_rus.ec, 2013-06-10, version 1.0 UUID: Mon Jun 10 22:10:07 2013 PDF: fb2pdf-j.20111230, 13.01.2012 Александр Шуваев Книга Предтеч Шуваев Александр Книга Предтеч лександр Шуваев А*КНИГА ПРЕДТЕЧ* Книга Предтеч Пролегомон Если у меня нет иных намерений, то места, в которые я попадаю, имеют, как правило, нечто общее. Невысокие холмы, великие и малые реки, луга, болота, в которых не утонешь, заросли кустарника, обозримые, аккуратные рощи, ленты леса вдоль текучей воды. Лесная...»

«ЕЖЕКВАРТАЛЬНЫЙ ОТЧЕТ Открытое акционерное общество Акционерная нефтяная Компания Башнефть Код эмитента: 00013-A за 2 квартал 2011 г. Место нахождения эмитента: 450008 Россия, Республика Башкортостан, К. Маркса 30 Информация, содержащаяся в настоящем ежеквартальном отчете, подлежит раскрытию в соответствии с законодательством Российской Федерации о ценных бумагах Президент Дата: 12 августа 2011 г. А.Л. Корсик подпись Главный бухгалтер Дата: 12 августа 2011 г. А.Ю. Лисовенко подпись Контактное...»

«ЕВРОПЕЙСКИЙ РЕГИОНАЛЬНЫЙ КОМИТЕТ ШЕСТЬДЕСЯТ ЧЕТВЕРТАЯ СЕССИЯ Копенгаген, Дания 15–18 сентября 2014 г. © Dreamstime.com © WHO © WHO © Dreamstime.com © Shutterstock Отчеты о ходе работы Европейский региональный комитет EUR/RC64/19 Шестьдесят четвертая сессия Копенгаген, Дания, 15–18 сентября 2014 г. 4 августа 2014 г. 140422 Пункт 5(h) предварительной повестки дня ОРИГИНАЛ: АНГЛИЙСКИЙ Отчеты о ходе работы Данный сводный документ содержит отчеты о ходе работы: А. по реализации Европейского плана...»

«Евгения Саликова ©2005 Астрологическая практика: выигрывает тот, кто больше знает Содержание: стр. ПРЕДИСЛОВИЕ..2 ГЛАВА I: ПОЛЕЗНЫЕ МЕЛОЧИ Аспекты...3 Системы домов...4 Петли планет...4 Четыре универсальных метода..5 Больная точка...8 Нетрадиционный способ определения Асцендента..9 Совместимость...9 Управитель часа...10 Истинный вопрос...13 ГЛАВА II: ВОПРОСЫ, КОТОРЫЕ ЧАСТО ЗАДАЮТ АСТРОЛОГУ Учеба. Оптимальный способ освоения информации.. Общение. Как быть услышанным? Любовь. Как наладить...»





Загрузка...



 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.