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

HTML LATEX PS PDF |== > К списку публикаций Д.В.Хмелева To the list of publications of D.V.Khmelev

Преобразование Барроуза-Уилера, массив суффиксов и сжатие словарей

Д.В.Хмелёв

18 ноября 2003

Настоящая статья победила в конкурсе статей о сжатии 01.08.2003-31.10.2003 на сервере http://www.compression.ru/.

Статья содержит много математических символов и некоторых браузерах может отображаться некорректно. Кроме того, HTML-вариант не включает в себя алгоритмы. Для корректного просмотра и распечатки статьи используйте PS- или PDF-варианты.

Аннотация

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

1  Введение
2  Преобразование BW и его обратимость
3  Суффиксный массив и BWT
4  Алгоритмы восстановления T и s по B и I
5  Преобразование данных словарного типа
    5.1  Теория
    5.2  Применение для сжатия
    5.3  Применение в качестве фильтра

1  Введение

Преобразование Барроуза-Уилера, изобретённое Д.Дж. Уилером в 1983 году и впервые опубликованное в совместной статье с Барроузом [3] применяется как для сжатия текстов без потерь, так и для сжатия дополнительной индексной информации к тексту. Тем не менее, до сих пор отсутствует математически ясное обоснование некоторых фактов о преобразовании, в частности, обратимости и возможности восстановить суффиксный массив. Настоящая статья заполняет этот пробел. Кроме того, здесь предложена новая модификация преобразования, которую можно использовать для улучшения сжатия данных вроде словарных или корпусных.

Преобразование Барроуза-Уилера будет называться BW-преобразованием или просто BWT от Burrows-Wheeler Transformation.

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

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

2  Преобразование BW и его обратимость

Пусть текст T состоит из 1+N букв, занумерованных с нуля: T[0..N]. Буквы T[i] принадлежат некоторому упорядоченному алфавиту A. Лексикографический порядок (строгий) на строках из букв алфавита A будем обозначать Ј ( < ). Обозначим через SkT циклический сдвиг текста T на k символов влево:
(SkT)[j]=T[(j+k) mod n+1].
Существует перестановка s чисел {0,ј,N}, которая удовлетворяет условию
Ss(i)T Ј Ss(i+1)T,    i=0,ј,N-1.
 (1)
Преобразование Барроуза-Уилера текста T есть текст B[0..N]=BW(T), буквы которого заданы соотношением


Bi=(Ss(i)T)[N].
 (2)
(другими словами, Bi=(Ss(i)-1T)[0]=T[s(i)-1 mod N+1]).

Теорема 1 [Барроуз-Уилер] Для восстановления исходного текста T из преобразования B достаточно знать число I, отвечающее условию s(I)=0 (или Ss(I)T=T).

Далее изложено формальное доказательство теоремы 1, основанное на изучении перестановки d чисел {0,ј,N}, удовлетворяющей условию:
Bd(i) Ј Bd(i+1) при i=0,ј,N-1,
 (3)
и в случае равенства Bd(i)=Bd(i+1) выполнено d(i) < d(i+1). Перестановка d однозначно определяется текстом B и её можно подсчитать за время O(N) с помощью сортировки подсчётом (см. далее алгоритм 1 в разделе 4).

Перестановку d можно рассматривать в качестве отображения d:{0,ј,N}®{0,ј,N}. Итерацию k отображения d обозначим через dk=d°dk-1, причём d0(i) є i, d1(i)=d(i).

Теорема 2 При всех m=1,ј,N+1 верны утверждения
Bd(i)јBdm(i) Ј Bd(i+1)јBdm(i+1) при i=0,ј, N-1,
(4)
и
BiBd(i)јBdm-1(i)=(Ss(i)-1T)[0..m-1] при i=0,ј, N.
(5)

Обычно обратимость BW-преобразования поясняют при помощи составления «концептуальной» таблицы M размерности (N+1)×(N+1), последний столбец которой составлен из букв Bi:
M  =  
*
*
*
ј
B0
*
*
*
ј
B1
*
*
*
ј
B2
:
:
:
···
:
*
*
*
ј
BN
Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получается таблица
Bd(0)
*
*
ј
B0
Bd(1)
*
*
ј
B1
Bd(2)
*
*
ј
B2
:
:
:
···
:
Bd(N)
*
*
ј
BN
в которой буквы первого столбца Bd(i) совпадают с T[si] в силу лексикографического порядка. Теперь, вспомнив, что пары BiBd(i) суть префиксы всех циклических перестановок исходного текста, можно отсортировать эти пары и получить второй столбец матрицы, который даст тройки букв и т.д.

Таким образом, конечно, можно восстановить всю матрицу. Зная номер I строки, отвечающей исходному тексту T, легко найти сам текст T, поскольку s(I)=0 и Ss(I)T=T.

Обычно после такого объяснения, используя аналогии различной степени неточности, без строгого доказательства предлагается метод для восстановления T, который заключается в том, T[i]=Bdi(I), i=0, ..., N. Автору не удалось обнаружить ни одного строгого доказательства правильности этого метода. Некое подобие обоснования дано в оригинальной работе Барроуза и Уилера [3], но они в действительности пользуются преобразованием d-1 и обосновывают алгоритм только для этого случая.

Теорема 2 призвана внести ясность в обоснование BW-преобразования и его обращения. Из неё вытекает, что действительно
M= ж
з
з
з
з
з
з
з
и
Ss0T
Ss1T
Ss2T
:
SsNT
 ц
ч
ч
ч
ч
ч
ч
ч
ш 		  =   ж
з
з
з
з
з
з
з
и
Bd(0)
Bd2(0)
Bd3(0)
ј
BdN(0)
B0
Bd(1)
Bd2(1)
Bd3(1)
ј
BdN(1)
B1
Bd(2)
Bd2(2)
Bd3(2)
ј
BdN(2)
B2
:
:
:
···
:
:
Bd(N)
Bd2(N)
Bd3(N)
ј
BdN(N)
BN
 ц
ч
ч
ч
ч
ч
ч
ч
ш 		.

Доказательство. [Доказательство теоремы 2 проводится индукцией по m=1, ..., N+1] База индукции m=1. В силу определения (3) при всех i=0, ..., N-1 верно сравнение Bd(i) Ј Bd(i+1). В силу определения (2) выполнено Bi=(Ss(i)-1T)[0].

Пусть утверждения теоремы верны при m-1. Докажем их для m. В силу предположения индукции
Bd(i)јBdm-1(i) Ј Bd(i+1)ј Bdm-1(i+1) при i=0,ј, N-1
(6)
Кроме того,
BiBd(i)јBdm-2(i)=(Ss(i)-1T)[0..m-2] при i=0,ј, N
(7)
Набор строк
(BiBd(i)јBdm-2(i),   i=0,ј,N)
(8)
совпадает с точностью до перестановки d с набором строк
(Bd(j)Bd2(j)јBdm-1(j),   j=0,ј,N).
(9)
В силу (6), набор (9) лексикографически упорядочен, а в силу (7) набор (8) есть набор префиксов длины m-1 всех циклических сдвигов исходного текста.

Однако, в силу определения (1) перестановки s набор (Ss(i)T)[0..m-2] также является лексикографически упорядоченным набором префиксов длины m-1 всех циклических сдвигов текста T.

Поэтому
Bd(j)Bd2(j)јBdm-1(j)=(Ss(j)T)[0..m-2] при j=0,ј, N
(10)
С другой стороны, Bj=(Ss(j)-1T)[0]. Поэтому
BjBd(j)Bd2(j)јBdm-1(j)=(Ss(j)-1T)[0..m-1] при j=0,ј, N,
как и требуется в (5).

Остаётся доказать (4), то есть, что набор строк
(Bd(j)Bd2(j)јBdm(d(j)),   j=0,ј,N).
лексикографически упорядочен. Если
Bd(j)јBdm-1(j) № Bd(j+1)јBdm-1(j+1),
то, в силу (6)
Bd(j)јBdm-1(j) < Bd(j+1)јBdm-1(j+1),
откуда вытекает
Bd(j)јBdm-1(j)Bdm(j) < Bd(j+1)јBdm-1(j+1)Bdm(j+1).
Поэтому предположим, что
Bd(j)јBdm-1(j)=Bd(j+1)јBdm-1(j+1).
Это, в частности, означает, что Bd(j)=Bd(j+1), откуда в силу определения (3) вытекает неравенство d(j) < d(j+1). Обозначим r=d(j), s=d(j+1). Выражая вышесказанное через r и s, получим Br=Bs и r < s. В силу Br=Bs, порядок между
BrBd(r)јBdm-1(r)
=Bd(j)Bd2(j)јBdm(j) и
BsBd(s)јBdm-1(s)
=Bd(j+1)Bd2(j+1)јBdm(j+1)
совпадает с порядком между
Bd(r)јBdm-1(r) и Bd(s)јBdm-1(s)
Напомним (см. (10)), что
Bd(r)јBdm-1(r)=(Ss(r)T)[0..m-2] и Bd(s)јBdm-1(s)=(Ss(s)T)[0..m-2]
Из определения (1) и неравенства r < s, получается сравнение
(Ss(r)T)[0..m-2] Ј (Ss(s)T)[0..m-2],
что даёт требуемый в (4) порядок. q.e.d. Воспользуемся теоремой 2 при m=N+1. Тогда при всех i=0, ..., N выполнено
Ss(i)T=Bd(i)јBdN+1(i)
Подстановка i=I с учётом s(I)=0 и S0T=T даёт
T=Bd(I)јBdN+1(I).
 (11)

Доказательство. [Доказательство теоремы 1] Поскольку перестановка d однозначно определяется по B (см. (3)), получаем, что текст T действительно однозначно определяется текстом B и числом I по формуле (11). q.e.d.

3  Суффиксный массив и BWT

Перестановку s называют иногда суффиксным массивом или массивом суффиксов. Это не совсем точно: разные определения суффиксного массива пояснены в конце раздела. Суффиксные массивы играют важную роль в индексации информации. Например, с их помощью легко найти все повторяющиеся подстроки текста и много других важных характеристик текста (см., например, [2]).

Теорема 1 позволяет восстановить исходный текст T из преобразованного текста B и индекса I. Поскольку перестановка s несёт важную информацию о тексте, возникает естественный вопрос: можно ли попутно восстановить перестановку s? Оказывается, можно!

Наивный подход заключается в следующем. Известно, что s(I)=0. Естественно положить s(d(I))=1, ..., s(dN(I))=N. Проблема заключается в том, что набор чисел I, d(I), ..., dN(I) может и не оказаться перестановкой чисел 0, ..., N. Пример, когда это не так, был построен ещё Барроузом и Уилером [3].

Действительно, пусть T[0..5]=»канкан». Тогда матрица из лексикографически отсортированных строк выглядит так:
S1T
=анканк,
S4T
=анканк,
S0T
=канкан,
S3T
=канкан,
S2T
=нканка,
S5T
=нканка,
то есть s =(1,4,0,3,2,5), B=»ккннаа» и I=2. Перестановка d есть
d(0)
=4,
d(1)
=5,
d(2)
=0,
d(3)
=1,
d(4)
=2,
d(5)
=3.
Очевидно, имеется цикл 0[( d) || (® )]4[( d) || (® )]2[( d) || (® )]0, и наивный подход проваливается.

Из теоремы 2 вытекает следующая лемма:

Лемма 1 Предположим, что
{I,d(I),ј,dN(I)}={0,ј,N}.
(12)
Тогда
s(di(I))=i при i=0,ј,N.
(13)

Что означает условие (12)? Оно означает неприводимость перестановки d.

Перестановка d называется неприводимой, если при некотором j совпадают множества {j, d(j), ..., dN(j)}={0, ..., N}.

Лемма 2 Пусть при некотором j выполнено равенство {j, d(j), ..., dN(j)}={0, ..., N}. Тогда

1) dN+1(j)=j;

2) При всех i О {0, ..., N} выполнено
{i,d(i),ј, dN(i)}={0,ј,N}.

3) При всех i О {0, ..., N} имеем dN+1(i)=i.

Доказательство. Утверждения 2) и 3) легко вытекают из утверждения 1), которое и будет показано далее. В силу того, что d - перестановка,
d{j,d(j),ј,dN(j)}=d{0,ј,N}={0,ј,N}.
С другой стороны,
d{j,d(j),јdN-1(j)} = {d(j),d2(j),јdN(j)}={0,ј,N}\{j}.
Таким образом, единственным возможным значением для d(dN(j)) является j. q.e.d.

Не следует путать неприводимую перестановку с циклической. Перестановка d называется циклической, если при некотором K выполнено d(i)=i+K mod N+1 для всех i О {0, ..., N}. Циклическая перестановка является неприводимой тогда и только тогда, когда N+1 и K взаимно просты: НОД(N+1,K)=1. Подкрепляющий пример: преобразование BW(T) определяется упорядочиванием циклических перестановок (сдвигов) текста SjT. Для одновременного восстановления текста T и перестановки s желательна (в силу леммы 1) неприводимость d.

Лемма 3 Предположим, что символ T[N] отличен от всех остальных символов текста T: T[N] № T[i], i=0, ј, N-1. Тогда перестановка d - неприводима.

Доказательство. В силу теоремы 2
T=Bd(I)јBdN+1(I).
Поскольку символ T[N] отличен от всех остальных символов, di(I) № I при i=1,ј,N. Если бы среди чисел di(I) оказалось два одинаковых, например, dj(I)=dk(I), 1 Ј j < k Ј N, то dj+s(I)=dj+(s mod k-j)(I), а потому dj+s(I) № I при всех s > 0, что противоречит условию dN+1(I)=I. Поэтому все числа di(I), i=1, ..., N различны, а вместе с I они составляют множество чисел
{I,ј,dN(I)}={0,ј,N}.
Неприводимость перестановки d следует из леммы 2. q.e.d.

Лемма 4 Предположим, что какой-нибудь символ T[j] отличен от всех остальных символов текста T: T[j] № T[i], i № j. Тогда перестановка d - неприводимая.

Доказательство. Рассмотрим циклический сдвиг Sj+1T, у которого
(Sj+1T)[N]=T[j].
Ясно, что BW(T)=BW(Sj+1T). Обозначим B=BW(T)=BW(Sj+1T). Значит, перестановка d, что строится по BW(T) и BW(Sj+1T), одна и та же. Применяя лемму 3 к Sj+1T получаем неприводимость d. q.e.d.

Лирическое отступление. Вышесказанное не означает, конечно же, что не существует алгоритма, восстанавливающего перестановку s для неприводимых d. Составление такого алгоритма - интересная задача, которая «закруглила» бы теорию преобразования Барроуза-Уилера. Автор настоящей статьи не относится к математикам, которые любят доказывать результаты в максимальной общности. Поэтому здесь дана лишь правдоподобная гипотеза о строении d, которая верна для строки «канкан» (см. начало раздела).

Назовём перестановку d допустимой, если она может возникнуть для какого-нибудь текста T: d =d(BW(T)) при некотором T[0..N].

Гипотеза 1 Пусть k > 0, n > 0 - разложение числа N+1 на целые множители: N+1=kn. Тогда допустима перестановка d со свойствами:

1) dk(0)=0,

2) множество {0,d(0),ј,dk-1(0)} содержит k разных чисел,

3) dj(i)=dj(0)+i при j=0, ..., k-1, и i=0,...,n-1.

Других допустимых перестановок d нет.

Если N+1 - простое число, то из гипотезы вытекает, что возможны 2 варианта: либо d - неприводима (случай k×n=(N+1)×1), либо d(i)=i при всех i (случай k×n=1×(N+1)). Например, первый случай возникает если буква T[N] отличается от всех остальных. Второй - если текст T[0..N] есть повторение одной буквы (например, T[0..N]=aN+1). Конец лирического отступления.

Обозначим $=T[N] - последний символ T, отличный от всех остальных. Будем называть символ $ разделителем. Название обуславливается тем, что этот символ отделяет начало текста от конца. В разделе 5 будет использовано несколько разделителей, чтобы представить несколько текстов в одной строке. В принципе, возможны различные порядки $ относительно других букв алфавита A. Обычно выбирают $ либо лексикографически младшим, либо лексикографически старшим в A. В первом случае s0=0, а во втором случае sN=N. Суффиксным массивом называют перестановку s, из которой убран индекс, указывающий на $.

С точки обозначений наиболее простым является соглашение о лексикографически старшем $. Тогда перестановка s =(s0,ј,sN-1,N), а суффиксный массив - это набор (s0,ј,sN-1). Обычно это упрощает алгоритмы обработки строк, см., например, [2]

Таким образом, чтобы найти перестановку s можно воспользоваться любым из многочисленных методов построения суффиксных массивов для текста T [4,5,6], а потом просто добавить суффикс, отвечающий символу T[N]. В приведённых статьях [4,5,6] обычно делается предположение, что $ Ј A.

Для индекса I, отвечающего s(I)=0 выполнено BI=T[N]=$. Поэтому, чтобы избежать необходимости кодировать символ $ достаточно передать текст Bў=B[0..I-1]B[I+1..N] и номер I. Очевидно, по этой информации легко восстановить
B=Bў[0..I-1] $ Bў[I..N-1].
Обладая этой информацией, по формулам (11) и (13) можно восстановить T и s.

4  Алгоритмы восстановления T и s по B и I

После прочтения предыдущих разделов не должно вызывать затруднений построение текста B (или текста Bў). Остался незатронутым только вопрос о нахождении d по тексту B.

Алгоритм 1 [Нахождение d] Пусть A={a1,ј,an}, причём ai < ai+1.

Для просмотра алгоритма обращайтесь к PS- или PDF-версии.

Нетрудно видеть, что алгоритм 1 есть всего навсего модификация сортировки подсчётом.

Пользуясь формулой
T=Bd(I)јBdN+1(I)
не представляет труда создать алгоритм, восстанавливающий текст T по BW-преобразованию B и индексу I.

Алгоритм 2 [Восстановление T]

Для просмотра алгоритма обращайтесь к PS- или PDF-версии.

Если перестановка d неприводима, то в силу леммы 1,
s(di(I))=i при i=0,ј,N.
Поэтому алгоритм попутного восстановления перестановки s выглядит следующим образом.

Алгоритм 3 [Одновременное восстановление T и s] Предполагается, что перестановка d неприводима.

Для просмотра алгоритма обращайтесь к PS- или PDF-версии.

Используя рассуждения, приведённые в конце раздела 3 легко модифицировать алгоритмы 1, 2, 3 для восстановления текста непосредственно из массива Bў с учётом лексикографического положения разделителя $ относительно других букв алфавита.

5  Преобразование данных словарного типа

5.1  Теория

Пусть текст T[0..N] состоит из n частей, которые разделены специальными символами $0, ..., $n-1, нигде более в тексте T не встречающимися, причём T[N]=$n-1.

Будем считать, что позиции i0, ..., in-1 разделителей упорядочены:
0 Ј i0 < ј < in-1=N, причём T[ik]=$k,   k=0,ј,n-1.
Другими словами,
T=T0$0јTn-1$n-1.
Кроме того, пусть разделители лексикографически предшествуют всем остальным буквам алфавита A:
$k < a для всех a О A\{$0, ј,$n-1} и для всех k=0,ј,n-1.
Каковы свойства у BW(T)? В силу того, что разделители предшествуют всем остальным символам алфавита, они будут стоять (некоторой перестановкой) в первом столбце концептуальной матрицы лексикографически отсортированных сдвигов T:
M  =  
$w(0)
*
*
*
ј
B0
:
:
:
:
:
:
$w(n-1)
*
*
*
ј
Bn-1
Bd(n)
*
*
*
ј
Bn
Bd(n+1)
*
*
*
ј
Bn+1
:
:
:
:
···
:
Bd(N)
*
*
*
ј
BN
(14)
где w - перестановка, удовлетворяющая условию
$w(0) < $w(1) < ј < $w(n-1).
 (15)
Обозначим через Ik позицию разделителя $k в тексте B:
B[Ik]=$k.
Раз уж Bd(j)=$w(j),
d(j)=Iw(j), при j=0,ј,n-1.
 (16)

Пусть lk - длина фрагмента Tk:
l0
=i0,
lk
=ik-(ik-1+1), при k=1,ј,n-1.
Определим также
m(k)= min
 {m | dm(Ik) < n}, и положим m(-1) є m(n-1).
 (17)

Лемма 5 При каждом k=0, ..., n-1 верны утверждения

1) lk=m(k-1).

2) Tk=(Sik-1T)[1..lk]=Bd(Ik-1)јBdm(k-1)(Ik-1).

(здесь i-1 є in-1, I-1 є In-1).

Доказательство. В силу того, что разделитель $k-1 непосредственно предшествует строке Tk, из теоремы 2 вытекает, что
Tk=Bd(Ik-1)јBdlk(Ik-1)
Заметим, что d(dlk(Ik-1))=$k, а потому в силу структуры (14) концептуальной матрицы 0 Ј dlk(Ik-1) < n. Поскольку Tk не содержит разделителей, для всех m=1, ..., lk-1 выполнено dm(Ik-1) і n. Таким образом, m(k-1)=lk, и оба заявленных утверждения верны. q.e.d.

Рассмотрим теперь текст ЩB, полученный из текста B с помощью замены всех символов-разделителей $k на один символ-разделитель $, который предшествует всем символам алфавита A исходного текста T:
^
B
 
i 
 = м
п
н
п
о
Bi,
если Bi № $k, k=0,ј,n-1,
$,
если Bi=$k при некотором 0 Ј k Ј n-1.
(18)
По ЩBi можно построить перестановку Щd, удовлетворяющую условию:
^
B
 
Щd(i) 
 Ј
^
B
 
Щd(i+1) 
 при i=0,ј,N-1,
 (19)
и в случае равенства ЩBd(i)=ЩBd(i+1) выполнено Щd(i) < Щd(i+1). Алгоритм построения Щd совпадает с алгоритмом 1 построения d, только надо на вход подать ЩB вместо B.

Легко видеть, что условия (19) и (3) различаются лишь при i=0, ..., n-1, причём для i=0, ..., n-1 имеем Bd(i)=$w(i) (см. также (16)) и ЩBЩd(i)=$.

Поэтому справедлива следующая лемма.

Лемма 6 d(i)=Щd(i) при i=n, ..., N.

Обозначим через ЩI0 < ј < ЩIn-1 позиции разделителя $ в ЩB:
^
B
 
 [
^
I
 
k 
 ]=$ при k=0, ј, n-1.
Из определения ЩB вытекает

Лемма 7 {ЩI0,ј,ЩIn-1}={I0,ј,In-1}. Другими словами, набор чисел (ЩI0,ј,ЩIn-1) есть перестановка набора чисел (I0,ј,In-1).

Из определения (19) перестановки Щd вытекает, что
^
d
 
 (k)=
^
I
 
k 
 при k=0, ј, n-1.
 (20)

Пусть g - это и есть перестановка чисел {0, ..., n-1}, переводящая набор (ЩI0,ј,ЩIn-1) в набор (I0,ј,In-1):
^
I
 
g(k) 
 =Ik.
 (21)
Кстати говоря, в этой перестановке известен последний элемент: g(n-1)=n-1. По аналогии с (17) определим
^
m
 
 (k)= min
 {m |
^
d
 
 m
 
 (
^
I
 
k 
 ) < n}, и положим
^
m
 
 (-1) є
^
m
 
 (n-1).
 (22)
Поскольку Щd(i)=d(i) при i=n, ..., N, то условие Щdm(ЩIk) < n эквивалентно условию dm(ЩIk) < n. Поэтому справедливо тождество
^
m
 
 (g(k))=m(k).
 (23)

Для упрощения формулировок, положим ЩI-1 є ЩIn-1, g(-1) є g(n-1).

Теорема 3 Обозначим
^
T
 
j 
 =
^
B
 
Щd(ЩIj-1) 
 ј
^
B
 
ЩdЩm(j-1)(ЩIj-1) 
 при j=0,ј,n-1.
(24)
Для всех k=0, ..., n-1,
Tk=
^
T
 
g(k-1)+1 
 .
(25)
Другими словами, наборы строк
(
^
T
 
j 
 | j=0,ј,n-1) и (
^
T
 
k 
 | k=0,ј,n-1)
совпадают с точностью до перестановки, явная формула для которой в терминах g дана тождеством (25).

Доказательство. Пользуясь определением текста ЩB и леммой 6, можно упростить выражение (24):
^
T
 
j 
 =Bd(ЩIj-1)јBdЩm(j-1)(ЩIj-1).
Подставим теперь j=g(k-1)+1. Тогда j-1=g(k-1) и формула приобретает вид
^
T
 
g(k-1)+1 
 =Bd(ЩIg(k-1))јBdЩm(g(k-1))(ЩIg(k-1)).
что с учётом тождеств (23) и (21) даёт упростить выражение справа до
Bd(Ik-1)јBdm(k-1)(Ik-1)=Tk
в силу утверждения 2) леммы 5. q.e.d.

Теорема 4 Имеет место тождество
d(i) = м
п
н
п
о
^
d
 
 (i)
i=n,ј,N
^
d
 
 (g(w(i)))
i=0,ј,n-1.
(26)

Доказательство. При i і n тождество (26) доказано в лемме 6. В силу (20) и определения (21) выполнено тождество Щd(g(k))=ЩIg(k)=Ik при k=0,ј,n-1. Если же подставить k=w(i), i=0,ј,n-1, то из (16) получаем
^
d
 
 (g(w(i)))=Iw(i)=d(i).
 q.e.d.

Теорема 5 Текст T (включая разделители с их порядком w) и перестановка s однозначно восстанавливаются по набору (ЩB, I, z), где текст ЩB определён в (18), целое число I определяется из условия s(I)=0, и z =g°w.

Замечание 1 В силу леммы 3 перестановка d неприводима (последний символ $n-1 отличен от всех остальных). Это согласуется с выводом теоремы 5, который справедлив лишь при неприводимой перестановке d.

Доказательство. В силу (26) с помощью z =g°w и Щd однозначно восстанавливается перестановка d. Обозначим ЩT =T0$јTn-1$. В силу (11), используя известное I и найденную d, можно получить
^
T
 
 =
^
B
 
d(I) 
 ј
^
B
 
dN+1(I) 
 .
Зная ЩT легко восстановить номера разделителей $. При известных номерах можно восстановить Ik, и перестановка w восстанавливается из порядка d-1(Ik). Можно восстановить w и с другого конца: зная Ik можно восстановить g, откуда однозначно находится w =g-1°z.

Наконец, поскольку d - неприводима, в силу леммы 1 легко восстанавливается и перестановка s. q.e.d.

5.2  Применение для сжатия

Теперь покажем, как теорему 3 можно применять на практике. Предположим, что у нас имеестся n последовательностей символов T0, ..., Tn-1, порядок которых нам не существеннен. Это может быть словарь, либо набор статей в корпусе текстов (такие статьи обычно содержат все необходимые читателю выходные данные) и т.п. Объединим эти тексты в один текст, разделив их с помощью специальных символов разделителей, которые нигде больше в T0, ..., Tn-1 не встречаются:
T=T0$0ј,Tn-1$n-1.
Теперь необходимо задать какой-то лексикографический порядок на разделителях. Теорема 3 допускает произвольный порядок, лишь бы разделители лексикографически предшествовали всем символам из текстов T0, ..., Tn-1. Практика показывает, что для данных типа словаря является выгодным порядок разделителей, отвечающий лексикографическому порядку текстов Tk: $j < $kЫTj < Tk. Если строки T0, ..., Tn-1 уже были лексикографически отсортированы, то такой порядок задать ещё проще: $j < $kЫj < k.

После определения порядка символов следует воспользоваться сортировкой суффиксов для построения перестановки s, удовлетворяющей условию (1).

Замечание 2 Если Вы пользуетесь языком Си, тексты Ti не содержат символа с кодом 0, и порядок на суффиксах задаётся по правилу $j < $kЫj < k, то можно разделять тексты Ti только одним символом - с кодом 0, и воспользоваться следующей функцией для сравнения суффиксов T[i..N] и T[j..N] при сортировке: 

      int N;             /* длина минус 1 */
      unsigned char *T;  /* текст T[0..N] */
      int suffix_compare(int i, int j){
        int res=strcmp(T+i,T+j);
        if(res==0) res=i-j;
        return res;
      }

Получив перестановку s, необходимо построить текст ЩB по правилу:
^
B
 
i 
 = м
н
о
Ss(i)-1T[0],
если Ss(i)-1T[0] № $k, k=0,ј,n-1,
$,
если Ss(i)-1T[0]=$k, при некотором k=0,ј,n-1.

Текст ЩB можно подвергнуть сжатию с использованием разнообразных методов: RLE, MTF, DC (Distance Coding), 01BFA (Е.Шелвин), MTH, Huffman, ARI, не считая 0-1 кодирования и прочих хитростей. Реализация этих методов подробно описана другими авторами (см. книгу [1]).

Приведём алгоритм восстановления набора текстов ЩTj, j=0, ..., n-1, который является некоторой перестановкой текстов Tk, из текста ЩB. Алгоритм пользуется соотношением (24). Отметим, что никакой дополнительной информации, кроме самого текста ЩB не требуется (в отличие от алгоритмов 2 и 3).

Алгоритм 4 [Восстановление ЩTj]  
На выходе алгоритма определены переменные:

n - количество фрагментов,

Щlj - длина фрагмента j при j=0,ј,n-1,

ЩTj[0..Щlj-1] - фрагмент ЩTj, j=0,ј,n-1.

Для просмотра алгоритма обращайтесь к PS- или PDF-версии.

5.3  Применение в качестве фильтра

В силу теоремы 5 для однозначного восстановления исходного текста T из ЩB необходимо ещё передать перестановку z =g°w и номер I строки T в концептуальной матрице M. Эта информация позволяет полностью восстановить исходный текст. Основной трюк заключается в том, что справедлива формула
d(i) = м
п
н
п
о
^
d
 
 (i)
i=n,ј,N
^
d
 
 (z(i))
i=0,ј,n-1.
см. (26)
Доказательство теоремы 5 описывает метод восстановления T и s.

В связи с этим возникает естественное предложение о применении ЩB в качестве предварительного фильтра неоднородных данных. Именно, можно назначить во входных данных разделитель (например, символ конца предложения - точку), и попытаться сгруппировать данные так, чтобы было больше близких контекстов в ЩB. При этом можно свободно выбрать порядок на разделителях $k.

Имеет ли смысл такая группировка может показать только практика. При условии равновероятности всех перестановок для оптимального кодирования z можно использовать арифметическое сжатие: первое число - одно из n, следующее - одно из n-1 оставшихся и т.д. Таким образом сжатая информация о z будет требовать
log2(n)+log2(n-1)+ј+log2(1)=
       = log2(n!) »  n(log(n)-1)
ln2
 » 1.44 n(log(n)-1) бит.
Если брать объём N < 230, n » N/1000, то количество дополнительной информации не превосходит 0.0023N байт, а хорошая группировка может, наверное, улучшить сжатие больше чем на 1%.

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

6  Благодарности

Автор пользуется случаем выразить признательность Е. Шелвину и В. Юкину за обсуждение алгоритма 4.

СПИСОК ЛИТЕРАТУРЫ

[1]
Д. Ватолин, А. Ратушняк, М. Смирнов и В. Юкин. Методы сжатия данных. - М.:Диалог-МИФИ, 2002. - 384 с. http://www.compression.ru.

[2]
M. I. Abouelhoda, S. Kurtz, and E. Ohlebusch. The enhanced suffix array and its applications to genome analysis. In Proceedings of the 2nd Workshop on Algorithms in Bioinformatics, number 2452 in LNCS, pages 449-463, 2002. http://theorie.informatik.uni-ulm.de/Personen/eo/PAPERS/WABI02.pdf.

[3]
M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report 124, Digital SRC, Palo Alto, 1994. http://www.compression.ru/download/articles/bwt/burrows_wheeler_1994_pdf.rar

[4]
J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. In 30th International Colloquium on Automata, Languages and Programming, number 2719 in LNCS, pages 943-955, 2003. http://citeseer.nj.nec.com/arkk03simple.html.

[5]
N. J. Larsson and K. Sadakane. Faster suffix sorting. Technical Report LU-CS-TR:99-214, LUNDFD6/(NFCS-3140)/1-20/(1999), Department of Computer Science, Lund University, Sweden, May 1999. http://www.compression.ru/download/articles/bwt/sada_larsson_1999_pdf.rar.

[6]
U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. SIAM J. Comput., 22(5):935-948, 1993.

1  Введение
2  Преобразование BW и его обратимость
3  Суффиксный массив и BWT
4  Алгоритмы восстановления T и s по B и I
5  Преобразование данных словарного типа
    5.1  Теория
    5.2  Применение для сжатия
    5.3  Применение в качестве фильтра


©2003 Д.Хмелёв