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

Ключевые слова и синонимы

Сжатие данных при помощи блочной сортировки

Постановка задачи

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

До публикации преобразования Барроуза-Уилера в области сжатия данных без потерь доминировали два подхода (см. исчерпывающий обзор в работах [1, 15]). Первый подход был предложен в революционных работах Шеннона и Хаффмана и основан на идее использования более коротких кодовых слов для самых часто встречающихся символов. Идея этого подхода была основана на технике Хаффмана и алгоритме арифметического кодирования, а в более поздний период – и на семействе алгоритмов сжатия PPM (Prediction by Partial Matching, прогнозирование по частичному совпадению). Второй подход был предложен в работах Лемпеля и Зива и основан на идее адаптивного построения словаря и представления входной строки в виде конкатенации словарных слов. Лучшие известные алгоритмы сжатия, основанные на этом подходе, составляют так называемое семейство ZIP; они давно уже являются стандартом и доступны практически на всех вычислительных платформах (в их числе gzip, zip, winzip и многие другие).

Преобразование Барроуза-Уилера воплощает совершенно иной подход к сжатию данных без потерь,основанный на идее преобразования входных данных для того, чтобы их сжатие стало проще. По словам авторов, «(эта) техника [..] заключается в применении обратимого преобразования к текстовому блоку, чтобы сделать избыточность входных данных более доступной для обработки простыми схемами кодирования» [3, раздел 7]. Эта техника не только позволила разработать самые современные алгоритмы сжатия, но и ввела понятие сжатых индексов [14] и была успешно расширена для сжатия (и индексирования) структурированных данных – таких как XML-файлы [7] и таблицы [16].

Основные результаты

Нотация

Пусть s – строка длины n, состоящая из символов алфавита [math]\displaystyle{ \Sigma \; }[/math]. Для i = 0, ... , n - 1 обозначим за s[i] i-й символ строки s, а за s[i, n - 1] – суффикс строки s, начинающийся с позиции i (т.е. начинающийся с символа s[i]). Если даны две строки, s и t, выражение [math]\displaystyle{ s \prec t \; }[/math] будет обозначать, что s лексикографически предшествует t.

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

В работе [3] Барроуз и Уилер предложили новый алгоритм сжатия, основанный на обратимом преобразовании, которое ныне называется преобразованием Барроуза-Уилера (bwt). Пусть имеется строка s. Вычисление значения bwt(s) состоит из трех основных этапов (см. рис. 1):

1. добавить к концу строки s специальный символ $, который меньше любого другого символа в [math]\displaystyle{ \Sigma \; }[/math];

2. сформировать концептуальную матрицу [math]\displaystyle{ \mathcal{M} \; }[/math], строки которой содержат циклические сдвиги строки s$, отсортированные в лексикографическом порядке;

3. построить преобразованный текст [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math], взяв последний столбец матрицы [math]\displaystyle{ \mathcal{M} \; }[/math].

Заметим, что каждый столбец матрицы [math]\displaystyle{ \mathcal{M} \; }[/math] – и, следовательно, преобразованный текст [math]\displaystyle{ \hat{s} \; }[/math] – представляет собой перестановку строки s$. В нашем примере F, первый столбец bwt-матрицы [math]\displaystyle{ \mathcal{M} \; }[/math], состоит из всех символов s, отсортированных по алфавиту. На рис. 1 F = $iiiimppssss.

mississippi$		$	mississipp	i
ississippi$m		i	$mississip	p
ssissippi$mi		i	ppi$missis	s
sissippi$mis		i	ssippi$mis	s
issippi$miss		i	ssissippi$	m
ssippi$missi	[math]\displaystyle{ \Longrightarrow }[/math]	m	ississippi	$
sippi$missis		p	i$mississi	p
ippi$mississ		p	pi$mississ	i
ppi$mississi		s	ippi$missi	s
pi$mississip		s	issippi$mi	s
i$mississipp		s	sippi$miss	i
$mississippi		s	sissippi$m	i

Рисунок 1. Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это [math]\displaystyle{ \hat{s} = bwt(s) = ipssm$pissii \; }[/math].

Хотя из определения это не очевидно, преобразование bwt является обратимым, и оба преобразования (bwt и его обращение) могут быть выполнены за оптимальное время O(n). Ради лучшего согласования с более современной литературой следующая нотация и техники доказательства будут несколько отличаться от изложенных в работе [3].

Определение 1. Для [math]\displaystyle{ 1 \le i \le n \; }[/math] обозначим за [math]\displaystyle{ s[k_i, n - 1] \; }[/math] суффикс строки s, являющийся префиксом строки i матрицы [math]\displaystyle{ \mathcal{M} \; }[/math], и определим [math]\displaystyle{ \Psi(i) \; }[/math] как индекс строки, которой предшествует префикс [math]\displaystyle{ s[k_{i + 1}, n - 1] \; }[/math].

Например, на рис. 1 [math]\displaystyle{ \Psi(2) = 7 \; }[/math], так как строка 2 матрицы [math]\displaystyle{ \mathcal{M} \; }[/math] имеет префикс ippi, а строка 7 – ppi. Отметим, что [math]\displaystyle{ \Psi(i) \; }[/math] не определено для i = 0, поскольку у строки 0 не имеется надлежащего суффикса s. [В работе [3] вместо [math]\displaystyle{ \Psi \; }[/math] авторы используют отображение, в сущности, являющееся обращением [math]\displaystyle{ \Psi \; }[/math]. Использование [math]\displaystyle{ \Psi \; }[/math] было предложено в литературе, посвященной сжатым индексам, где [math]\displaystyle{ \Psi \; }[/math] и его обращение играют важную роль (см. [14]).]

Лемма 1. Для i = 1, ... , n имеет место [math]\displaystyle{ F[i] = \hat{s}[ \Psi(i)] \; }[/math].

Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является [math]\displaystyle{ s[k_i + 1, n - 1] \; }[/math], является [math]\displaystyle{ s[k_i] \; }[/math]. Из этого, согласно определению 1, следует [math]\displaystyle{ \hat{s} [\Psi(i)] = s[k_i] = F[i] \; }[/math], что и требовалось доказать. □

Лемма 2. Если [math]\displaystyle{ 1 \le i \lt j \le n \; }[/math] и F[i] = F[j], то [math]\displaystyle{ \Psi(i) \lt \Psi(j) \; }[/math].

Доказательство. Пусть [math]\displaystyle{ s[k_i, n - 1] \; }[/math] (соответственно, [math]\displaystyle{ s[k_j, n - 1]) \; }[/math] обозначает суффикс s, являющийся префиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что [math]\displaystyle{ s[k_i, n - 1] \prec s[k_j, n - 1] \; }[/math]. Из гипотезы F[i] = F[j] следует, что [math]\displaystyle{ s[k_i] = s[k_j] \; }[/math], поскольку должно иметь место [math]\displaystyle{ s[k_i + 1, n - 1] \prec s[k_j + 1, n - 1] \; }[/math]. Из этого следует утверждение леммы, поскольку по построению [math]\displaystyle{ \Psi(i) \; }[/math] ([math]\displaystyle{ \Psi(j) \; }[/math], соответственно) является лексикографической позицией строки, префиксом которой является [math]\displaystyle{ s[k_i + 1, n - 1] \; }[/math] ([math]\displaystyle{ s[k_j + 1, n - 1] \; }[/math], соответственно). □

Лемма 3. Для любого символа [math]\displaystyle{ c \in \Sigma \; }[/math] верно: если F[j] является [math]\displaystyle{ \ell }[/math]-м вхождением c в F, то [math]\displaystyle{ \hat{s}[\Psi (j)] \; }[/math] является [math]\displaystyle{ \ell }[/math]-м вхождением c в [math]\displaystyle{ \hat{s} \; }[/math].

Доказательство. Возьмем индекс h, такой, что h < j и F[h] = F[j] = c (случай с h > j является симметричным). Из леммы 2 следует, что [math]\displaystyle{ \Psi(h) \lt \Psi(j) \; }[/math], а из леммы 1 – что [math]\displaystyle{ \hat{s}[\Psi(h)] = \hat{s}[\Psi(j)] = c \; }[/math]. Следовательно, количество символов c, предшествующих F[j] в F, совпадает с количеством символов c, предшествующих [math]\displaystyle{ \hat{s}[\Psi(j)] \; }[/math] в [math]\displaystyle{ \hat{s} }[/math] (аналогичная ситуация имеет место для последущих символов), из чего следует справедливость формулировки леммы. □

На рис. 1 имеет место [math]\displaystyle{ \Psi(2) = 7 \; }[/math], и [math]\displaystyle{ F[2] \; }[/math] и [math]\displaystyle{ \hat{s}[7] \; }[/math] являются вторыми вхождениями i в соответствующих строках. Это свойство обычно формулируется так: соответствующие символы имеют один и тот же относительный порядок в строках F и [math]\displaystyle{ \hat{s} }[/math].

Лемма 4. Для любого i значение [math]\displaystyle{ \Psi(i) \; }[/math] может быть вычислено из [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math].

Доказательство. Получить F можно в результате простой алфавитной сортировки символов [math]\displaystyle{ \hat{s} \; }[/math]. Затем вычислим [math]\displaystyle{ \Psi(i) \; }[/math] следующим образом: (1) положим с = F[i]; (2) вычислим [math]\displaystyle{ \ell \; }[/math], такое, что F[i] является [math]\displaystyle{ \ell }[/math]-м вхождением c в F; (3) возвратим индекс [math]\displaystyle{ \ell }[/math]-го вхождения c в [math]\displaystyle{ \hat{s} \; }[/math]. □

Вернемся к рис. 1. Для вычисления [math]\displaystyle{ \Psi(10) \; }[/math] достаточно положить c = F[10] = s и заметить, что F[10] является вторым вхождением s в F. Тогда достаточно локализовать индекс j второго символа "s" в [math]\displaystyle{ \hat{s} \; }[/math], в данном случае это j = 4. Следовательно, [math]\displaystyle{ \Psi(10) = 4 \; }[/math]; префиксом строки 10 является sissippi, а строки 4 – issippi.

Теорема 5. Исходную строку s можно восстановить из bwt(s).

Доказательство. Из леммы 4 следует, что столбец F и отображение [math]\displaystyle{ \Psi \; }[/math] могут быть получены из bwt(s). Обозначим за [math]\displaystyle{ j_0 \; }[/math] индекс специального символа $ в строке [math]\displaystyle{ \hat{s} \; }[/math]. По построению строка [math]\displaystyle{ j_0 \; }[/math] матрицы bwt имеет префикс s[0, n - 1], из чего следует [math]\displaystyle{ s[0] = F[j_0] \; }[/math]. Пусть [math]\displaystyle{ j_1 = \Psi(j_0) \; }[/math]. Согласно определению 1, префиксом строки [math]\displaystyle{ j_1 \; }[/math] является s[1, n - 1], следовательно, [math]\displaystyle{ s[1] = F[j_1] \; }[/math]. Продолжая аналогичные рассуждения, по индукции получаем [math]\displaystyle{ s[i] = F[\Psi^i (j_0)] \; }[/math] для i = 1, ..., n - 1. □

Алгоритмические вопросы

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

Процедура sa2bwt	Процедура bwt2psi	Процедура psi2text
1. bwt[0]=s[n-1];	1. for(i=0;i<=n;i++)	1. k = j0; i = 0;
2. for(i=1;i<=n;i++)	2. c = bwt[i];	2. do
3. if(sa[i] == 1)	3. if(c == '$')	3. k = psi[k] ;
4. bwt[i]='$';	4. j0 = i;	4. s[i++] = bwt[k];
5. else	5. else	while(i<n);
6. bwt[i]=s[sa[i]-1];	6. h = count[c]++;
	7. psi[h]=i;

Рисунок 2. Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) из исходной строки s и ее суффиксного массива sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение [math]\displaystyle{ \Psi \; }[/math], сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива [math]\displaystyle{ [1, | \Sigma] | \; }[/math], который изначально содержит в позиции count[i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения [math]\displaystyle{ j_0 \; }[/math].

Теорема 6. Пусть s[1, n] – строка над алфавитом [math]\displaystyle{ \Sigma \; }[/math] константного размера. Строка [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math] может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.

Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) бит рабочего пространства при помощи, например, алгоритма из [11]. Суффиксный массив представляет собой массив целых чисел sa[1, n], такой, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы [math]\displaystyle{ \mathcal{M} \; }[/math] является уникальный суффикс s, за которым следует специальный символ $, суффиксный массив обеспечивает упорядочение строк в [math]\displaystyle{ \mathcal{M} \; }[/math]. Следовательно, bwt(s) можно вычислить из массива sa за линейное время при помощи процедуры sa2bwt на рис. 2. □

Теорема 7. Пусть s[1, n] – строка над алфавитом [math]\displaystyle{ \Sigma \; }[/math] константного размера. При наличии bwt(s) строка s может быть восстановлена за время O(n) с использованием O(n log n) бит рабочего пространства.

Доказательство. Алгоритм восстановления s практически дословно воспроизводит процедуру, вкратце описанную в доказательстве теоремы 5. Единственное отличие заключается в том, что для большей эффективности все значения отображения [math]\displaystyle{ \Psi \; }[/math] вычисляются за один проход. Это выполняется при помощи процедуры bwt2psi на рис. 2. Вместо работы со столбцом F процедура bwt2psi использует массив count (счетчик), являющийся «компактным» представлением F. В момент начала работы процедуры для любого символа [math]\displaystyle{ c \in \Sigma \; }[/math] счетчик count[c] выдает индекс первой строки матрицы [math]\displaystyle{ \mathcal{M} \; }[/math], префиксом которой является c. Например, на рис. 1 count[i] = 1, count[m] = 5 и т.д. В основном цикле for процедуры bwt2psi сканируется массив bwt, и значение count[c] увеличивается каждый раз при обнаружении вхождения символа c (строка 6). Строка 6 также присваивает переменной h индекс [math]\displaystyle{ \ell }[/math]-го вхождения элемента c в F. Согласно лемме 3, строка 7 корректно сохраняет в psi[h] значение [math]\displaystyle{ i = \Psi(h) \; }[/math]. После вычисления массива psi строка s восстанавливается при помощи процедуры psi2text на рис. 2, корректность которой непосредственно следует из теоремы 5.

Очевидно, что выполнение процедур bwt2psi и psi2text занимает время O(n). Объем рабочего пространства зависит главным образом от стоимости хранения массива psi, который занимает O(n log n) бит. □

Алгоритм сжатия Барроуза-Уилера

Использование процедуры bwt для сжатия данных можно обосновать следующим образом. Рассмотрим строку w, которая k раз встречается внутри строки s. В bwt-матрице s будет k последовательных строк, префиксом которых является w – скажем, строки [math]\displaystyle{ r_w + 1, r_w + 2, ... , r_w + k \; }[/math]. Следовательно, позиции [math]\displaystyle{ r_w + 1, ... , r_w + k \; }[/math] в [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math] будут содержать в точности те символы, коорые непосредственно предшествуют w в s. Если в строке s некоторые шаблоны встречаются чаще других, то для многих подстрок w соответствующие позиции [math]\displaystyle{ r_w + 1, ... , r_w + k \; }[/math] строки [math]\displaystyle{ \hat{s} \; }[/math] будут содержать только несколько различающихся символов. Например, если s – текст на английском языке, а w – строка «his», соответствующая часть [math]\displaystyle{ \hat{s} \; }[/math], скорее всего, будет содержать множество букв «t» и пустых символов и совсем немного других символов. Поскольку [math]\displaystyle{ \hat{s} \; }[/math] является перестановкой s, она обычно оказывается локально гомогенной в том смысле, что ее «короткие» подстроки обычно содержат только несколько различающихся символов. [Очевидно, что это верно в случае, если s обладает некоторой регулярностью: если строка s оказывается случайной, то и [math]\displaystyle{ \hat{s} \; }[/math] также будет случайной.]

Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку [math]\displaystyle{ \hat{s} \; }[/math] с использованием кодирования по модели «движение к началу» (move-to-front) [2] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся с момента предыдущего вхождения этого же символа. Для этого mtf ведет список символов, упорядоченный по давности вхождения; когда встречается следующий символ, алгоритм выводит его текущий ранг и перемещает его в начало списка. Заметим, что mtf вычисляет строку, имеющую ту же длину, что и [math]\displaystyle{ \hat{s} \; }[/math] и в случае, если [math]\displaystyle{ \hat{s} \; }[/math] является локально гомогенной, строка [math]\displaystyle{ mtf(\hat{s}) \; }[/math] будет в основном состоять из целых чисел малой величины. [Если s – текст на английском языке, [math]\displaystyle{ mtf(\hat{s}) \; }[/math] обычно содержит более 50% нулей.] Учитывая это смещенное распределение, строку [math]\displaystyle{ mtf(\hat{s}) \; }[/math] можно легко сжать: Барроуз и Уилер предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел.

Барроуз и Уилер были заинтересованы главным образом в разработке алгоритма с высокой практической эффективностью. И в самом деле, их простая версия превосходила (по критерию коэффициента сжатия) инструмент gzip, бывший в то время стандартом сжатия без потерь. Через несколько лет после публикации bwt в работах [9, 12] было показано, что коэффициент сжатия алгоритма Барроуза-Уилера может быть ограничен в терминах эмпирической энтропии k-го порядка входной строки для любого [math]\displaystyle{ k \ge 0 \; }[/math]. К примеру, Каплан и др. [9] показали, что для любой входной строки s и вещественного числа [math]\displaystyle{ \mu \gt 1 \; }[/math] длина сжатой строки ограничена [math]\displaystyle{ \mu \; n \; H_k (s) + n \; log(\zeta (\mu)) + \mu \; g_k + O(log \; n) }[/math] бит, где [math]\displaystyle{ \zeta (\mu) \; }[/math] – стандартная дзета-функция, а [math]\displaystyle{ g_k \; }[/math] – функция, зависящая только от k и от размера [math]\displaystyle{ \Sigma \; }[/math]. Эта граница поточечно верна для любой строки s, одновременно для любых [math]\displaystyle{ k \ge O \; }[/math] и [math]\displaystyle{ \mu \gt 1 \; }[/math]; и это весьма примечательно, поскольку ни для одного другого алгоритма сжатия аналогичные границы не были доказаны. Теоретическое изучение эффективности алгоритмов сжатия на базе преобразования bwt в настоящее время является областью активных исследований. Дополнительную информацию см. в списке рекомендованной литературы.

Применение

После выхода основополагающей работы Барроуза и Уилера многие исследователи предложили собственные алгоритмы сжатия на базе bwt (см. [4, 5] и ссылки в этих статьях). Особенно интересны в теоретическом плане результаты работы [6], демонстрирующие, что преобразование bwt может быть использовано для разработки «усилителей сжатия» (или механизмов повышения степени сжатия), которые служат инструментом повышения эффективности других алгоритмов сжатия вполне определенным и измеримым образом.

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

Открытые вопросы

Помимо исследования эффективности алгоритмов сжатия на базе bwt, открытым остается весьма важный с практической точки зрения вопрос об эффективности использования памяти при выполнении bwt. Пусть дана строка s длины n над алфавитом [math]\displaystyle{ \Sigma \; }[/math]; s и [math]\displaystyle{ \hat{s} = bwt(s) \; }[/math] требуют [math]\displaystyle{ O(n \; log \; | \Sigma |) }[/math] бит. К сожалению, алгоритмы с линейным временем выполнения, представленные на рис. 2, используют дополнительные массивы (sa и psi), для хранения которых требуется [math]\displaystyle{ \Theta (n \; log \; n) }[/math] бит. Это налагает серьезные ограничения на размер самой большой матрицы bwt, которую можно вычислить в оперативной памяти. Алгоритмы обращения bwt, эфективно использующие память, были предложены в литературе, посвященной индексации сжатого текста [14], однако задача эффективного использования времени и памяти преобразованием bwt по-прежнему остается нерешенной, хотя для нее были получены обнадеживающие предварительные результаты [8, 10, 13].

Экспериментальные результаты

Экспериментальное исследование нескольких алгоритмов сжатия, основанных на преобразовании bwt, и сравнение их с другими современными способами сжатия приведено в работе [4].

Наборы данных

Наборы данных, использовавшиеся в [4], доступны по адресу http://www.mfn.unipmn.it/~manzini/boosting. Другие наборы данных для сжатия и индексации сжатого текста можно найти на сайте Pizza&Chili http://pizzachili.di.unipi.it/.

Ссылка на код

Страница «Усиление алгоритмов сжатия» (Compression Boosting, http://www.mfn. unipmn.it/~manzini/boosting) содержит исходный код алгоритмов, протестированных в работе [4]. «Облегченный» код для вычисления преобразования bwt и его обращения (без сжатия) доступен по адресу http://www.mfn.unipmn.it/~manzini/lightweight. Код bzip2 доступен по адресу http://www.bzip.org.

См. также

• Арифметическое кодирование для сжатия данных
• Усиление степени сжатия текста
• Сжатый суффиксный массив
• Индексация сжатого текста
• Построение суффиксного массива
• Сжатие таблиц
• Сжатие и индексирование дерева

Литература

1. Bell, T.C., Cleary, J.G., Witten, I.H.: Text compression. Prentice Hall, NJ (1990)

2. Bentley, J., Sleator, D., Tarjan, R., Wei, V.: A locally adaptive compression scheme. Commun. ACM 29, 320-330 (1986)

3. Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Report 124, Digital Equipment Corporation (1994)

4. Ferragina, P., Giancarlo, R., Manzini, G.: The engineering of a compression boosting library: Theory vs practice in bwt compression. In: Proc. 14th European Symposium on Algorithms (ESA). LNCS, vol. 4168, pp. 756-767. Springer, Berlin (2006)

5. Ferragina, P., Giancarlo, R., Manzini, G.: The myriad virtues of wavelet trees. In: Proc. 33th International Colloquium on Automata and Languages (ICALP), pp. 561-572. LNCS n. 4051. Springer, Berlin, Heidelberg (2006)

6. Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM 52, 688-713(2005)

7. Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), 184-193, Pittsburgh, PA (2005)

8. Hon, W., Sadakane, K., Sung, W.: Breaking a time-and-space barrier in constructing full-text indices. In: Proc. of the 44th IEEE Symposium on Foundations of Computer Science (FOCS),251-260, Cambridge, MA (2003)

9. Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of Burrows-Wheeler-based compression. Theoretical Computer Science 387(3): 220-235 (2007)

10. Karkkainen, J.: Fast BWT in small space by blockwise suffix sorting. Theoretical Computer Science 387(3): 249-257 (2007)

11. Karkkainen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918-936 (2006)

12. Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48, 407-430(2001)

13. Na, J.: Linear-time construction of compressed suffix arrays using o(nlogn)-bit working space for large alphabets. In: Proc. 16th Symposium on Combinatorial Pattern Matching (CPM). LNCS, vol. 3537, pp. 57-67. Springer, Berlin (2005)

14. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv.39(1)(2007)

15. Salomon, D.: Data Compression: the Complete Reference, 3rd edn. Springer, New York (2004)

16. Vo, B.D., Vo, K.P.: Using column dependency to compress tables. In: Proc. of IEEE Data Compression Conference (DCC), pp. 92-101, IEEE Computer Society Press (2004)