Аноним

Преобразование Барроуза-Уилера: различия между версиями

Материал из WEGA

Преобразование Барроуза-Уилера (посмотреть исходный код)

Версия от 19:38, 2 февраля 2017

2715 байт добавлено ,  2 февраля 2017
м
→‎Ссылка на код
 
(не показаны 24 промежуточные версии этого же участника)
Строка 6: Строка 6:




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




Строка 19: Строка 19:
'''Преобразование Барроуза-Уилера'''
'''Преобразование Барроуза-Уилера'''


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


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


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


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




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


 
{| class="wikitable"
mississippi$ $ mississipp i
|mississippi$
ississippi$m i $mississip P
|
ssissippi$mi i ppi$missis s
|$
sissippi$mis i ssippi$mis s
|mississipp
issippi$miss i ssissippi$ m
|i
ssippi$missi m —^ ississippi $
|-
sippi$missis P i$mississi P
|ississippi$m
ippi$mississ P pi$mississ i
|
ppi$mississi s ippi$missi s
|i
pi$mississip s issippi$mi s
|$mississip
i$mississipp s sippi$miss i
|p
$mississippi s sissippi$m i
|-
|ssissippi$mi
Рисунок 1
|
 
|i
Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>.
|ppi$missis
|s
|-
|sissippi$mis
|
|i
|ssippi$mis
|s
|-
|issippi$miss
|
|i
|ssissippi$
|m
|-
|ssippi$missi
| <math>\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>\hat{s} = bwt(s) = ipssm$pissii \;</math>.




Строка 52: Строка 111:




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


Например, на рис. 1 это будет "^(2) = 7, поскольку строка 2 матрицы <math>\mathcal{M} \;</math> имеет префикс ippi, а строка 7 – ppi. Отметим, что ^(i) не определено для  i = 0, поскольку у строки 0 не имеется надлежащего суффикса s.1


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


'''Лемма 1. Для i = 1, ... , n имеет место F[i] = s[W(i)].'''


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


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


'''Лемма 2. Если 1 < i < j < n и F[i] = F[j], то'''


Доказательство. Пусть s[ki, n - 1]  (соответственно, s[kj, n - 1]) обозначает суффикс s, являющийся перфиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что s[ki, n - 1] -< s[kj,  n - 1]. Из гипотезы F[i] = F[j] следует, что s[ki] = s[kj], поскольку должно иметь место s[ki + 1, n - 1] -< s[kj + 1, n - 1]. Из этого следует утверждение леммы, поскольку по построению ^(i) (&(j), соответственно) является лексикографической позицией строки, префиксом которой является s[ki + 1, n - 1] (s[kj + 1, n - 1], соответственно). □
'''Лемма 2. Если <math>1 \le i < j \le n \;</math> и F[i] = F[j], то <math>\Psi(i) < \Psi(j) \;</math>.'''


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


'''Лемма 3. Для любого символа c 2 X1 верно: если F[j] _0 £-f/i-е вхождением c в F, то s[4^(j)] является l-м вхождением c в s.'''


Доказательство. Возьмем индекс h, такой, что h < j и F[h] = F[j] = c (случай с h > j является симметричным). Из леммы 2 следует, что <^(fc) < Ф()), а из леммы 1 – что s[W(h)] = s[W(j)] = c. Следовательно, количество символов c, предшествующих F[j] в F, совпадает с количеством символов c, предшествующих s[^(j)] в s (аналогичная ситуация имеет место для последущих символов), из чего следует справедливость формулировки леммы. □
'''Лемма 3. Для любого символа <math>c \in \Sigma \;</math> верно: если F[j] является <math>\ell</math>-м вхождением c в F, то <math>\hat{s}[\Psi (j)] \;</math> является <math>\ell</math>-м вхождением c в <math>\hat{s} \;</math>.'''


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


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


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


'''Лемма 4. Для любого i значение может быть вычислено из s = bwt(s).'''


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


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


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


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


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


Доказательство. Из леммы 4 следует, что столбец F и отображение 4> могут быть получены из bwt(s). Обозначим за j0 индекс специального символа $ в строке s. По построению строка j0 матрицы bwt имеет префикс s[0, n - 1], из чего следует s[0] = F[j0]. Пусть j1 = ^(/o). Согласно определению 1, префиксом строки j1 является s[1, n - 1], следовательно, s[1] = F[j1]. Продолжая аналогичные рассуждения, по индукции получаем j0)] для i = 1, ..., n - 1. □
'''Теорема 5. Исходную строку s можно восстановить из bwt(s).'''


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


Строка 97: Строка 153:




Рисунок 2
{| class="wikitable"
! Процедура 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;
|
|}


Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение (?, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива  [1, |27|], который изначально содержит в позиции count [i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения j0


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


'''Теорема 6. Пусть s[1, n] – строка над алфавитом S константного размера. Строка s = bwt(s) может быть вычислена за время O(n) с использованием O(n log n) бит рабочего пространства.'''


Доказательство. Суффиксный массив строки s можно вычислить за время O(n) с использованием O(nlog n) ) бит рабочего пространства при помощи, например, алгоритма из [ ]. Суффиксный массив представляет собой строку целых чисел sa[1, n], такую, что для i = 1, ... , n значением s[sa[i], n - 1] является i-й суффикс s в лексикографическом порядке. Поскольку префиксом каждой строки матрицы <math>\mathcal{M} \;</math> является уникальный суффикс s, за которым идет специальным символ $, суффиксный массив обеспечивает упорядочение строк в <math>\mathcal{M} \;</math>. Следовательно, bwt(s) можно вычислить из sa за линейное время при помощи процедуры sa2bwt на рис. 2. □
'''Теорема 6. Пусть s[1, n] – строка над алфавитом <math>\Sigma \;</math> константного размера. Строка <math>\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>\mathcal{M} \;</math> является уникальный суффикс s, за которым следует специальный символ $, суффиксный массив обеспечивает упорядочение строк в <math>\mathcal{M} \;</math>. Следовательно, bwt(s) можно вычислить из массива sa за линейное время при помощи процедуры sa2bwt на рис. 2. □


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


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




Строка 117: Строка 204:
'''Алгоритм сжатия Барроуза-Уилера'''
'''Алгоритм сжатия Барроуза-Уилера'''


Использование процедуры bwt для сжатия данных можно обосновать следующим образом. Рассмотрим строку w, которая k раз встречается внутри строки s. В bwt-матрице s будет k последовательных строк, префиксом которых является w – скажем, строки say rw + 1, rw + 2, ... , rw + k. Следовательно, позиции rw + 1, ... , rw + k в J = bwt(s) будут содержать в точности те символы, коорые непосредственно предшествуют w в s. Если в строке s некоторые шаблоны встречаются чаще других, то для многих подстрок w соответствующие позиции rw + 1, ... : : , rw + k строки s будут содержать только несколько различающихся символов. Например, если s – текст на английском языке, а w – строка «his», соответствующая часть J, скорее всего,  будет содержать множество букв «t» и пустых символов и совсем немного других символов. Поскольку J является перестановкой s, она обычно оказывается локально гомогенной в том смысле, что ее «короткие» подстроки обычно содержат только несколько различающихся символов.2
Использование процедуры bwt для сжатия данных можно обосновать следующим образом. Рассмотрим строку w, которая k раз встречается внутри строки s. В bwt-матрице s будет k последовательных строк, префиксом которых является w – скажем, строки <math>r_w + 1, r_w + 2, ... , r_w + k \;</math>. Следовательно, позиции <math>r_w + 1, ... , r_w + k \;</math> в <math>\hat{s} = bwt(s) \;</math> будут содержать в точности те символы, коорые непосредственно предшествуют w в s. Если в строке s некоторые шаблоны встречаются чаще других, то для многих подстрок w соответствующие позиции <math>r_w + 1, ... , r_w + k \;</math> строки <math>\hat{s} \;</math> будут содержать только несколько различающихся символов. Например, если s – текст на английском языке, а w – строка «his», соответствующая часть <math>\hat{s} \;</math>, скорее всего,  будет содержать множество букв «t» и пустых символов и совсем немного других символов. Поскольку <math>\hat{s} \;</math> является перестановкой s, она обычно оказывается ''локально гомогенной'' в том смысле, что ее «короткие» подстроки обычно содержат только несколько различающихся символов. ''[Очевидно, что это верно в случае, если s обладает некоторой регулярностью: если строка s оказывается случайной, то и <math>\hat{s} \;</math> также будет случайной.]''
 
 
Для того чтобы использовать это свойство, Барроуз и Уилер предложили обрабатывать строку s с использованием кодирования по модели «движение к началу» (move-to-front) [ ] (процедура mtf). mtf кодирует каждый символ количеством различных символов, встретившихся после предыдущего вхождения этого же символа. Для этого mtf ведет список символов, упорядоченный по давности вхождения; когда встречается следующий символ, алгоритм выводит его текущий ранг и перемещает его в начало списка. Заметим, что mtf вычисляет строку, имеющую ту же длину, что и J и в случае, если J является локально гомогенной, строка mtffs) будет в основном состоять из целых числе малой величины.3 Учитывая это смещенное распределение, можно легко сжать строку mtffs): Барроуз и Уилер  предложили проделать это при помощи алгоритма Хаффмана или арифметического кодирования – возможно, после однократного прогона на наборах одинаковых целых чисел.


2 Очевидно, что это верно в случае, если s обладает некоторой регулярностью: если строка s оказывается случайной, то и s также будет случайной.


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




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


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




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


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


== Экспериментальные результаты ==
== Экспериментальные результаты ==
Строка 142: Строка 226:


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


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


== См. также ==
== См. также ==
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/12192...12235