HTML L^AT_EX PS PDF |== > К списку публикаций To the list of publications

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

Д.В.Хмелёв

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. Тогда 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))=ЩI_g(k)=I_k при 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 =T₀$јT_n-1$. В силу (11), используя известное I и найденную d, можно получить

^ T   = ^ B   d(I)  ј ^ B   dN+1(I)  .

Зная ЩT легко восстановить номера разделителей $. При известных номерах можно восстановить I_k, и перестановка w восстанавливается из порядка d^-1(I_k). Можно восстановить w и с другого конца: зная I_k можно восстановить g, откуда однозначно находится w =g^-1°z.

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

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

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

Замечание 2 Если Вы пользуетесь языком Си, тексты T_i не содержат символа с кодом 0, и порядок на суффиксах задаётся по правилу $_j < $_kЫj < k, то можно разделять тексты T_i только одним символом - с кодом 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]).

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

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

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

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

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

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

В связи с этим возникает естественное предложение о применении Щ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 < 2³⁰, n » N/1000, то количество дополнительной информации не превосходит 0.0023N байт, а хорошая группировка может, наверное, улучшить сжатие больше чем на 1%.

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

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

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

[1]

Д. Ватолин, А. Ратушняк, М. Смирнов, и В. Юкин. Методы сжатия данных. Диалог-МИФИ, Москва, 2002. 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.

[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.