Сайт о сжатии >> Раздел "Cтатьи и исходники"

WIN | KOI | LAT

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

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

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

Д.В.Хмелёв

18 ноября 2003

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

Аннотация

1  Введение

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

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

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

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

Bi=(Ss(i)T)[N].

(2)

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

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

Далее изложено формальное доказательство теоремы 1, основанное на изучении перестановки d чисел {0,ј,N}, удовлетворяющей условию:

Bd(i) Ј Bd(i+1) при i=0,ј,N-1,

(3)

и в случае равенства B_d(i)=B_d(i+1) выполнено d(i) < d(i+1). Перестановка d однозначно определяется текстом B и её можно подсчитать за время O(N) с помощью сортировки подсчётом (см. далее алгоритм 1 в разделе 4).

Перестановку d можно рассматривать в качестве отображения d:{0,ј,N}®{0,ј,N}. Итерацию k отображения d обозначим через d^k=d°d^k-1, причём d⁰(i) є i, d¹(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), последний столбец которой составлен из букв B_i:

M  =   * * * ј B0 * * * ј B1 * * * ј B2 : : : ··· : * * * ј BN

Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получается таблица

Bd(0) * * ј B0 Bd(1) * * ј B1 Bd(2) * * ј B2 : : : ··· : Bd(N) * * ј BN

в которой буквы первого столбца B_d(i) совпадают с T[s_i] в силу лексикографического порядка. Теперь, вспомнив, что пары B_iB_d(i) суть префиксы всех циклических перестановок исходного текста, можно отсортировать эти пары и получить второй столбец матрицы, который даст тройки букв и т.д.

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

Обычно после такого объяснения, используя аналогии различной степени неточности, без строгого доказательства предлагается метод для восстановления T, который заключается в том, T[i]=B_dⁱ(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 верно сравнение B_d(i) Ј B_d(i+1). В силу определения (2) выполнено B_i=(S_s(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 набор (S_s(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)

С другой стороны, B_j=(S_s(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).

Это, в частности, означает, что B_d(j)=B_d(j+1), откуда в силу определения (3) вытекает неравенство d(j) < d(j+1). Обозначим r=d(j), s=d(j+1). Выражая вышесказанное через r и s, получим B_r=B_s и r < s. В силу B_r=B_s, порядок между

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 и S₀T=T даёт

T=Bd(I)јBdN+1(I).

(11)

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

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

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

Наивный подход заключается в следующем. Известно, что s(I)=0. Естественно положить s(d(I))=1, ..., s(d^N(I))=N. Проблема заключается в том, что набор чисел I, d(I), ..., d^N(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), ..., d^N(j)}={0, ..., N}.

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

1) d^N+1(j)=j;

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

{i,d(i),ј, dN(i)}={0,ј,N}.

3) При всех i О {0, ..., N} имеем d^N+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(d^N(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) определяется упорядочиванием циклических перестановок (сдвигов) текста S_jT. Для одновременного восстановления текста 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] отличен от всех остальных символов, dⁱ(I) № I при i=1,ј,N. Если бы среди чисел dⁱ(I) оказалось два одинаковых, например, d^j(I)=d^k(I), 1 Ј j < k Ј N, то d^j+s(I)=d^{j+(s mod k-j)}(I), а потому d^j+s(I) № I при всех s > 0, что противоречит условию d^N+1(I)=I. Поэтому все числа dⁱ(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 - неприводимая.

Доказательство. Рассмотрим циклический сдвиг S_j+1T, у которого

(Sj+1T)[N]=T[j].

Ясно, что BW(T)=BW(S_j+1T). Обозначим B=BW(T)=BW(S_j+1T). Значит, перестановка d, что строится по BW(T) и BW(S_j+1T), одна и та же. Применяя лемму 3 к S_j+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) d^k(0)=0,

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

3) d^j(i)=d^j(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]=a^N+1). Конец лирического отступления.

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

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

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

Для индекса I, отвечающего s(I)=0 выполнено B_I=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

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

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

Пользуясь формулой

T=Bd(I)јBdN+1(I)

не представляет труда создать алгоритм, восстанавливающий текст T по BW-преобразованию B и индексу I.

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

Если перестановка d неприводима, то в силу леммы 1,

s(di(I))=i при i=0,ј,N.

Поэтому алгоритм попутного восстановления перестановки s выглядит следующим образом.

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

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

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

5.1  Теория

Будем считать, что позиции i₀, ..., i_n-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)

Обозначим через I_k позицию разделителя $_k в тексте B:

B[Ik]=$k.

Раз уж B_d(j)=$_w(j),

d(j)=Iw(j), при j=0,ј,n-1.

(16)

Пусть l_k - длина фрагмента T_k:

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) l_k=m(k-1).

2) T_k=(S_ik-1T)[1..l_k]=B_d(Ik-1)јB_{d^m(k-1)(Ik-1)}.

(здесь i_-1 є i_n-1, I_-1 є I_n-1).

Доказательство. В силу того, что разделитель $_k-1 непосредственно предшествует строке T_k, из теоремы 2 вытекает, что

Tk=Bd(Ik-1)јBdlk(Ik-1)

Заметим, что d(d^l_k(I_k-1))=$_k, а потому в силу структуры (14) концептуальной матрицы 0 Ј d^l_k(I_k-1) < n. Поскольку T_k не содержит разделителей, для всех m=1, ..., l_k-1 выполнено d^m(I_k-1) і n. Таким образом, m(k-1)=l_k, и оба заявленных утверждения верны. q.e.d.

Рассмотрим теперь текст ЩB, полученный из текста B с помощью замены всех символов-разделителей $_k на один символ-разделитель $, который предшествует всем символам алфавита A исходного текста T:

^ B   i  = м п н п о Bi, если Bi № $k, k=0,ј,n-1, $, если Bi=$k при некотором 0 Ј k Ј n-1.

(18)

По ЩB_i можно построить перестановку Щd, удовлетворяющую условию:

^ B   Щd(i)  Ј ^ B   Щd(i+1)  при i=0,ј,N-1,

(19)

и в случае равенства ЩB_d(i)=ЩB_d(i+1) выполнено Щd(i) < Щd(i+1). Алгоритм построения Щd совпадает с алгоритмом 1 построения d, только надо на вход подать ЩB вместо B.

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

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

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

Обозначим через ЩI₀ < ј < ЩI_n-1 позиции разделителя $ в ЩB:

^ B   [ ^ I   k  ]=$ при k=0, ј, n-1.

Из определения ЩB вытекает

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

Из определения (19) перестановки Щd вытекает, что

^ d   (k)= ^ I   k  при k=0, ј, n-1.

(20)

Пусть g - это и есть перестановка чисел {0, ..., n-1}, переводящая набор (ЩI₀,ј,ЩI_n-1) в набор (I₀,ј,I_n-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, то условие Щd^m(ЩI_k) < n эквивалентно условию d^m(ЩI_k) < n. Поэтому справедливо тождество

^ m   (g(k))=m(k).

(23)

Для упрощения формулировок, положим ЩI_-1 є ЩI_n-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. Тогд