Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Сортировка, используемая в BWT

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

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

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

■ длинные одинаковые строки;

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

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

Что касается текстовых файлов, наиболее часто встречаемая длина по­вторяющихся строк - 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);

// осталась только одна строка if( n <= 1 ) return;

// деление всех строк на группы

compare(Ss, v, d,

// строки, d-й символ которых меньше v

&s_less, Sn_less,

// строки, d-й символ которых равен v

&s_eq, &n_eq,

// строки, d-й символ которых больше v

&s_greater, &n_greater);

sort(Ss_less, n_less, d) ;

sort(&s_eq, n_eq, d+1);

sort(Ss_greater, n_greater, d) ;
)

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

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

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

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

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

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

Сортировка суффиксов

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

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

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

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

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

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

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

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

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

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

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

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

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

Позиции:

0

1

2

3

4 5

б

7

8

9 10 11

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

а

б

Р

а

к а

д

а

б

р а $

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

$

а

а

а

а а

б

б

Д

к р р

I[i]

11

0

3

5

7 10

1

8

6

4 2 9

V[I[i]]

0

1

1

1

1 1

6

б

8

9 10 10

S[i]

-1

5

2

-2

2

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

Позиции:

0

1 2

3

4

5 6 7 8

9

10 11

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

а

б р

а

к

а д а б

Р

а $

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

$

а а

а

а

а б б д

к

Р Р

Суффикс Хк

а

б К

д

б

$ р р а

а

а а

V[I[i]+l]

1

6 9

8

6

0 10 10 1

1

1 1

Пары:

аб ак

ад

аб

а$ бр бр да

ка

pa pa

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

V[I[i]+l]

106689 10 10 1111

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

$а а$ аб аб ад ак бр бр да ка pa pa

I[i]

11 10 0.753186429

V[I[i]]

0122456689 10 10

S[i]

-2 2-2 2-2 2

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

Позиции:

0123456789 10 11

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

абракадабра$

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

$а а$ аб аб ад ак бр бр да ка pa pa

Суффикс Хк

- pa pa - - ак а$ - - ка $а

V[I[i]+2]

10 10 5 1 9 0

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

Суффикс Хк

- pa pa - - a$ ак

-

$a ка

V[I[i]+2]

10 10 15

9 0

I[i]

11 10 0 7 5 3 8 1

6

4 9 2

V[I[i]]

01224567

8

9 10 11

S[i]

-2 2 -8

Шаг 4. Как можно заметить, нам осталось отсортировать всего одну группу, состоящую из двух элементов.

Позиции:

0 12 3 456789 10 11

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

а б р а кадабр а$

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

$абр - абра абра ----- када -

Суффикс Хк

када $абр ------ --

V[I[i]+4]

9 0

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

V[I[i]+4]

0 9 15 9 0

Hi]

11 10 7053816492

V[I[i]]

0123456789 10 11

S[i]

-12

Таким образом, мы получили упорядоченные суффиксы, индексы кото­рых записаны в массиве I (рис. S.25)

i

I[i]

Суффикс

0

11

$

1

10

а$

2

7

абра$

3

0

абракадабра$

4

5

адабра$

5

3

акадабра$

6

8

бра$

7

1

бракадабра$

8

6

дабра$

9

4

кадабра$

10

9

ра$

11

2

ракадабра$

Рис. 5.25. Результат сортировки суффиксов

Упражнение. Выполните сортировку строки "tobeomottobe", используя описан­ный алгоритм.

Сравнение алгоритмов сортировки

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

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

^MZ,=_L.gD(x[i[i]],x[i[i+i]]),

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

Исследования показали, что время, затрачиваемое суффиксной сорти­ровкой, пропорционально логарифму средней длины совпадений, в то время как алгоритмы, основанные на быстрой сортировке или сортировке слияни­ем, демонстрируют, как правило, линейно-пропорциональную 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 байт;

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

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

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

bookl

file2

wat с

kennedy

QSuf ♦

3.30

9.23

10.00

4.23

YBS

3.13

4.77

6.76

4.15

DC

2.36

4:23.59

6.92

2.97

ARC

4.17

4.34

6.43

5.00

BA

4.45

5.82

7.36

4.73

bzip2 **

3.03

4.23

6.81

4.07

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

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

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

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

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

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

Подать онлайн заявку на кредит - oneclickmoney

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