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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Доказательство корректности наивного алгоритма)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
  
'''Преобразование Барроуза {{---}} Уилера''' {{---}} алгоритм, используемый для предварительной обработки данных перед сжатием, разработанный для улучшения эффективности последующего кодирования. Преобразование Барроуза {{---}} Уилера меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов.
+
'''Преобразование Барроуза {{---}} Уилера''' (англ. ''Burrows-Wheeler transform'') {{---}} алгоритм, используемый для предварительной обработки данных перед сжатием, разработанный для улучшения эффективности последующего кодирования. Преобразование Барроуза {{---}} Уилера меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов.
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
  
 
Преобразование выполняется в три этапа.  
 
Преобразование выполняется в три этапа.  
* Cоставляется таблица всех циклических сдвигов входной строки.
+
* Составляется таблица всех циклических сдвигов входной строки.
 
* Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы.
 
* Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы.
* В качестве выходной строки выбрается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.
+
* В качестве выходной строки выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.
  
 
== Пример работы алгоритма ==
 
== Пример работы алгоритма ==
  
Пусть нам дана исходная строка <tex>s = </tex>''"ABACABA"''.  
+
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA".  
  
 
{| border="1"
 
{| border="1"
Строка 38: Строка 38:
 
  CABAABA  
 
  CABAABA  
 
|
 
|
  BCABAAA
+
  BCABAAA, 3
 
|}
 
|}
  
Результат можно записать так: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3), где 3 {{---}} это номер исходной строки в отсортированной матрице, так как он нужен для обратного преобразования.  
+
Результат можно записать так: <tex>$BWT(s) = $(</tex>"BCABAAA", 3<tex>)</tex>, где 3 {{---}} номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования.  
  
  
Следует заметить, что иногда в исходной строке приводится, так называемый, символ конца строки ''$'', который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется.
+
Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки ''$'', который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется.
  
  
Пусть нам дана исходная строка <tex>s = </tex>''"ABACABA$"''.
+
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA$".
  
 
{| border="1"
 
{| border="1"
Строка 81: Строка 81:
  
  
При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной: (''"ABACABA$"''). Тогда результат можно записать так: <tex>BWT(s)=</tex>''"$CBBAAAA"''.
+
При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки, и будет исходной: ("ABACABA$"). Тогда результат можно записать так: <tex>$BWT(s) =$</tex> "$CBBAAAA".
  
 
== Обратное преобразование ==
 
== Обратное преобразование ==
Строка 87: Строка 87:
 
===Наивный алгоритм===
 
===Наивный алгоритм===
  
Пусть нам дано: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3). Тогда выпишем в столбик нашу преобразованную последовательность символов ''"BCABAAA"''. Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза {{---}} Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем ''"BCABAAA"''. Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.
+
Пусть нам дано: <tex>$BWT(s) =$(</tex>"BCABAAA", 3<tex>)</tex>. Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза {{---}} Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.
 
Алгоритм обратного преобразования описан в таблице ниже:
 
Алгоритм обратного преобразования описан в таблице ниже:
  
Строка 224: Строка 224:
 
|}
 
|}
  
Следует также заметить, что если нам было бы дано <tex>BWT(s)=</tex>''"$CBBAAAA"'', то мы также получили бы нашу исходную строку, только с символом конца строки ''$'' на конце: ''ABACABA$''.
+
Следует также заметить, что если нам было бы дано <tex>$BWT(s) = $</tex> "$CBBAAAA", то мы также получили бы нашу исходную строку, только с символом конца строки ''$'' на конце: ''ABACABA$''.
 +
 
 +
Временная сложность данного алгоритма <tex>O(N^3\log{N}) </tex>, пространственная <tex>O(N^2)</tex>.
 +
 
 +
===Доказательство корректности===
 +
 
 +
Пусть дана строка <tex>$s$</tex>, к которой было применено преобразование BWT. Докажем, что при использовании наивного алгоритма на каждом шаге получающийся набор строк соответствует суффиксам циклических перестановок исходной строки, методом математической индукции.
 +
* База. Циклически сдвинем все строки исходной таблицы на 1 влево. Тогда в столбце <tex>n</tex> будут находиться символы, добавленные на первом шаге алгоритма, а в столбце <tex>n - 1</tex> символы, изначально стоявшие в таблице до первого шага алгоритма. Таким образом, полученные на первом шаге алгоритма строки являются суффиксами циклических перестановок строки <tex>$s$</tex>.
 +
* Предположение. Пусть на <tex>k</tex> шаге алгоритма все полученные строки являются суффиксами циклических перестановок строки <tex>$s$</tex>.
 +
* Переход. Рассмотрим <tex>k+1</tex>-ый шаг алгоритма. Все строки отсортированы, поэтому самый левый столбец совпадет с 1 столбцом исходной таблицы. Циклически сдвинем все строки исходной таблицы на <tex>n - k</tex> символов вправо. Теперь по предположению первые <tex>k</tex> символов справа в каждой строке совпадают у исходной таблицы и у таблицы, полученной в результате работы алгоритма. <tex>k</tex>-ые справа столбцы также совпадают. Добавленный на <tex>k+1</tex>-ом шаге столбец также совпадает с <tex>k+1</tex>-ым справа столбцом сдвинутой исходной таблицы, так как совпадает с последним столбцом исходной таблицы, которая была сдвинута на <tex>n-k</tex>.
 +
 
 +
{|border ="1"
 +
!colspan="3" | <tex>$k+1$</tex> шаг алгоритма при <tex>$k=3$</tex>
 +
|-
 +
! Исходная <br /> таблица || Сдвинутая <br /> таблица || Результат <br /> работы <br /> алгоритма
 +
|-align="center"
 +
|
 +
<font color="red">A</font><font color="green">ABA</font>CA<font color="blue">B</font>
 +
<font color="red">A</font><font color="green">BAA</font>BA<font color="blue">C</font>
 +
<font color="red">A</font><font color="green">BAC</font>AB<font color="blue">A</font>
 +
<font color="red">A</font><font color="green">CAB</font>AA<font color="blue">B</font>
 +
<font color="red">B</font><font color="green">AAB</font>AC<font color="blue">A</font>
 +
<font color="red">B</font><font color="green">ACA</font>BA<font color="blue">A</font>
 +
<font color="red">C</font><font color="green">ABA</font>AB<font color="blue">A</font>
 +
|
 +
CA<font color="blue">B</font><font color="red">A</font><font color="green">ABA</font>
 +
BA<font color="blue">C</font><font color="red">A</font><font color="green">BAA</font>
 +
AB<font color="blue">A</font><font color="red">A</font><font color="green">BAC</font>
 +
AA<font color="blue">B</font><font color="red">A</font><font color="green">CAB</font>
 +
AC<font color="blue">A</font><font color="red">B</font><font color="green">AAB</font>
 +
BA<font color="blue">A</font><font color="red">B</font><font color="green">ACA</font>
 +
AB<font color="blue">A</font><font color="red">C</font><font color="green">ABA</font>
 +
|
 +
<font color="blue">B</font><font color="red">A</font><font color="green">ABA</font>
 +
<font color="blue">C</font><font color="red">A</font><font color="green">BAA</font>
 +
<font color="blue">A</font><font color="red">A</font><font color="green">BAC</font>
 +
<font color="blue">B</font><font color="red">A</font><font color="green">CAB</font>
 +
<font color="blue">A</font><font color="red">B</font><font color="green">AAB</font>
 +
<font color="blue">A</font><font color="red">B</font><font color="green">ACA</font>
 +
<font color="blue">A</font><font color="red">C</font><font color="green">ABA</font>
 +
|-
 +
|}
  
Как несложно посчитать сложность данного алгоритма <tex>O(N^3logN) </tex>, также он требует <tex>O(N^2)</tex> памяти.
+
Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических перестановок <tex> $s$ </tex>, после последнего шага получившиеся строки будут совпадать с циклическими перестановками <tex> $s$ </tex>.
  
 
===Оптимизация===
 
===Оптимизация===
Строка 256: Строка 297:
 
   |}
 
   |}
  
Здесь слева это отсортированный данный столбец, чтобы мы знали какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку мы в нашем алгоритме новый столбец приписываем в начало, то мы из состояния <tex> i </tex> (левый столбец) переходим в состояние <tex> j </tex> (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из <tex> j </tex> в <tex> i </tex> восстановить строку.
+
Здесь слева отсортированный данный столбец, чтобы мы знали, какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку в нашем алгоритме новый столбец приписывается в начало, то мы из состояния <tex> i </tex> (левый столбец) переходим в состояние <tex> j </tex> (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из <tex> j </tex> в <tex> i </tex> восстановить строку.
 
{|
 
{|
 
  |
 
  |
Строка 305: Строка 346:
 
|}
 
|}
 
===Сложность оптимизированного алгоритма===
 
===Сложность оптимизированного алгоритма===
Данный алгоритм работает за <tex>O(NlogN)</tex> действий и требует <tex>O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>O(N+M)</tex> действий и требует <tex>O(N+M)</tex> памяти, где <tex>M</tex> — размер алфавита.
+
Данный алгоритм работает за <tex>O(N\log{N})</tex> времени и требует <tex>O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>O(N+M)</tex> действий и требует <tex>O(N+M)</tex> памяти, где <tex>M</tex> — размер алфавита.
  
 
===Псевдокод оптимизированного алгоритма===
 
===Псевдокод оптимизированного алгоритма===

Версия 16:51, 6 декабря 2015

Определение

Преобразование Барроуза — Уилера (англ. Burrows-Wheeler transform) — алгоритм, используемый для предварительной обработки данных перед сжатием, разработанный для улучшения эффективности последующего кодирования. Преобразование Барроуза — Уилера меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов.

Описание алгоритма

Преобразование выполняется в три этапа.

  • Составляется таблица всех циклических сдвигов входной строки.
  • Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы.
  • В качестве выходной строки выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.

Пример работы алгоритма

Пусть нам дана исходная строка [math]$s =$[/math] "ABACABA".

Трансформация
Вход Все
Перестановки
Сортировка
Строк
Выход
ABACABA
ABACABA
BACABAA
ACABAAB
CABAABA
ABAABAC
BAABACA
AABACAB
AABACAB
ABAABAC
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA 
BCABAAA, 3

Результат можно записать так: [math]$BWT(s) = $([/math]"BCABAAA", 3[math])[/math], где 3 — номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования.


Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки $, который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется.


Пусть нам дана исходная строка [math]$s =$[/math] "ABACABA$".

Трансформация
Вход Все
Перестановки
Сортировка
Строк
Выход
ABACABA$
ABACABA$
BACABA$A
ACABA$AB
CABA$ABA
ABA$ABAC
BA$ABACA
A$ABACAB
$ABACABA
ABACABA$
ABA$ABAC
ACABA$AB
A$ABACAB
BACABA$A
BA$ABACA
CABA$ABA 
$ABACABA
$CBBAAAA


При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки, и будет исходной: ("ABACABA$"). Тогда результат можно записать так: [math]$BWT(s) =$[/math] "$CBBAAAA".

Обратное преобразование

Наивный алгоритм

Пусть нам дано: [math]$BWT(s) =$([/math]"BCABAAA", 3[math])[/math]. Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. Алгоритм обратного преобразования описан в таблице ниже:

Обратное преобразование
Вход
BCABAAA
Добавление 1 Сортировка 1 Добавление 2 Сортировка 2 Добавление 3 Сортировка 3 Добавление 4
B
C
A
B
A
A
A
A
A
A
A
B
B
C
BA
CA
AA
BA
AB
AB
AC
AA
AB
AB
AC
BA
BA
CA
BAA
CAB
AAB
BAC
ABA
ABA
ACA
AAB
ABA
ABA
ACA
BAA
BAC
CAB
BAAB
CABA
AABA
BACA
ABAA
ABAC
ACAB
Сортировка 4 Добавление 5 Сортировка 5 Добавление 6 Сортировка 6 Добавление 7 Сортировка 7
AABA
ABAA
ABAC
ACAB
BAAB
BACA
CABA
BAABA
CABAA
AABAC
BACAB
ABAAB
ABACA
ACABA
AABAC
ABAAB
ABACA
ACABA
BAABA
BACAB
CABAA
BAABAC
CABAAB
AABACA
BACABA
ABAABA
ABACAB
ACABAA
AABACA
ABAABA
ABACAB
ACABAA
BAABAC
BACABA
CABAAB
BAABACA
CABAABA
AABACAB
BACABAA
ABAABAC
ABACABA
ACABAAB
AABACAB
ABAABAC
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA
Результат
ABACABA

Следует также заметить, что если нам было бы дано [math]$BWT(s) = $[/math] "$CBBAAAA", то мы также получили бы нашу исходную строку, только с символом конца строки $ на конце: ABACABA$.

Временная сложность данного алгоритма [math]O(N^3\log{N}) [/math], пространственная [math]O(N^2)[/math].

Доказательство корректности

Пусть дана строка [math]$s$[/math], к которой было применено преобразование BWT. Докажем, что при использовании наивного алгоритма на каждом шаге получающийся набор строк соответствует суффиксам циклических перестановок исходной строки, методом математической индукции.

  • База. Циклически сдвинем все строки исходной таблицы на 1 влево. Тогда в столбце [math]n[/math] будут находиться символы, добавленные на первом шаге алгоритма, а в столбце [math]n - 1[/math] символы, изначально стоявшие в таблице до первого шага алгоритма. Таким образом, полученные на первом шаге алгоритма строки являются суффиксами циклических перестановок строки [math]$s$[/math].
  • Предположение. Пусть на [math]k[/math] шаге алгоритма все полученные строки являются суффиксами циклических перестановок строки [math]$s$[/math].
  • Переход. Рассмотрим [math]k+1[/math]-ый шаг алгоритма. Все строки отсортированы, поэтому самый левый столбец совпадет с 1 столбцом исходной таблицы. Циклически сдвинем все строки исходной таблицы на [math]n - k[/math] символов вправо. Теперь по предположению первые [math]k[/math] символов справа в каждой строке совпадают у исходной таблицы и у таблицы, полученной в результате работы алгоритма. [math]k[/math]-ые справа столбцы также совпадают. Добавленный на [math]k+1[/math]-ом шаге столбец также совпадает с [math]k+1[/math]-ым справа столбцом сдвинутой исходной таблицы, так как совпадает с последним столбцом исходной таблицы, которая была сдвинута на [math]n-k[/math].
[math]$k+1$[/math] шаг алгоритма при [math]$k=3$[/math]
Исходная
таблица
Сдвинутая
таблица
Результат
работы
алгоритма
AABACAB
ABAABAC
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA
CABAABA
BACABAA
ABAABAC
AABACAB
ACABAAB
BAABACA
ABACABA
BAABA
CABAA
AABAC
BACAB
ABAAB
ABACA
ACABA

Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических перестановок [math] $s$ [/math], после последнего шага получившиеся строки будут совпадать с циклическими перестановками [math] $s$ [/math].

Оптимизация

Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. Мы приписывали новый столбец и сортировали имеющиеся данные. На каждом шагу мы к строке, которая находилась на [math] i [/math]-ом месте приписываем в начало [math] i [/math] -ый элемент столбца входных данных. Пусть изначально мы знаем каким по порядку является приписанный нами в начало символ (то есть каким по порядку в столбце). И конечно же мы знаем исходя из предыдущего шага какое место занимала наша строка без этого первого символа ([math] i [/math] -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером [math] i [/math] всегда будет перемещаться на позицию с номером [math] j [/math].

0 а       р 9
1 а д 7
2 а a 0
3 а к 8
4 а р 10
5 б a 1
6 б a 2
7 д a 3
8 к a 4
9 р б 5
10 р б 6

Здесь слева отсортированный данный столбец, чтобы мы знали, какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку в нашем алгоритме новый столбец приписывается в начало, то мы из состояния [math] i [/math] (левый столбец) переходим в состояние [math] j [/math] (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из [math] j [/math] в [math] i [/math] восстановить строку.

6 10 4 8 3 7 1 5 9 0 2
а б р а к а д а б р а

Сложность оптимизированного алгоритма

Данный алгоритм работает за [math]O(N\log{N})[/math] времени и требует [math]O(N)[/math] памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за [math]O(N+M)[/math] действий и требует [math]O(N+M)[/math] памяти, где [math]M[/math] — размер алфавита.

Псевдокод оптимизированного алгоритма

Пусть [math] N [/math] — количество символов во входной строке, [math] M [/math] — количество символов в алфавите, [math] k [/math] — номер исходной строки в матрице перестановок, [math] s [/math] — входящая строка, [math] count [/math] — массив для сортировки подсчетом, [math] t [/math] — вектор обратного преобразования, [math] x [/math] — номер данной нам строки в таблице.

// Cчитаем частоты символов
for i = 0 .. M 
  count[i] = 0
for i = 0 .. N 
  count[s[i]]++
// Упорядочиваем символы, чтобы получить первый столбец исходной матрицы
// count[i] указывает на первую позицию символа i в первом столбце
sum = 0
for i = 0 .. M
  sum = sum + count[i]
  count[i] = sum - count[i]
// Cоздаем вектор обратного преобразования
for i = 0 .. N
  t[count[s[i]]] = i
  count[s[i]]++
// И восстанавливаем исходный текст
j = t[x]
for i = 0 .. N
  print(s[j])
  j = t[j]

Доказательство корректности

Пусть текст [math]T[/math] состоит из [math]N + 1[/math] символов, занумерованных с нуля: [math]T[0..N][/math]. Буквы [math]T[i][/math] принадлежат некоторому алфавиту [math]A[/math]. Лексикографический порядок (строгий) на строках из алфавита [math]A[/math] будем обозначать [math]\preceq (\prec)[/math]. Обозначим через [math]S_{k}T[/math] циклический сдвиг текста [math]T[/math] на [math]k[/math] символов влево:

[math] S_{k}T = T[(j + k) (mod\ N + 1)] [/math]

Существует перестановка [math]p[/math] чисел [math]\{0, ..., N\}[/math], которая удовлетворяет условию:

[math] S_{p(i)}T \preceq S_{p(i + 1)}T,\ i = 0, ..., N - 1\ \ \textbf{(1)}[/math]

Преобразование Барроуза-Уилера текста [math]T[/math] есть текст [math]B[0..N] = BW(T)[/math], буквы которого заданы соотношением:

[math]B[i] = S_{p(i)}T[N][/math], другими словами [math]B[i] = S_{p(i) - 1}T[0] = T[(p(i) - 1) (mod\ N + 1)] \ \ \textbf{(2)}[/math]

Пусть [math]\sigma[/math] — перестановка чисел [math]\{0, ..., N\}[/math], удовлетворяющая условию:

[math]B_{\sigma(i)} \preceq B_{\sigma(i + 1)}[/math], при [math]i = 0, ..., N - 1\ \ \textbf{(3)}[/math],

и в случае равенства [math]B_{\sigma(i)}[/math] и [math]B_{\sigma(i + 1)}[/math] выполнено — [math]\sigma(i) \lt \sigma(i + 1)[/math]. Перестановка однозначно определяется текстом [math]B[/math] и ее можно посчитать за [math]O(N)[/math], используя сортировку подсчетом. Рассмотрим перестановку [math]\sigma[/math] как отображение [math]\sigma : \{0, ..., N\} \to \{0, ..., N\}[/math]. Пусть [math]\sigma^{k}[/math] копмозиция [math]k[/math] отображений [math]\sigma^{k} = \sigma^{k - 1} \circ \sigma[/math], где [math]\sigma^{1} = \sigma, \sigma^{0} \equiv i[/math].

Теорема:
При всех [math]m = 1, ..., N + 1[/math] верны утверждения,
[math]B_{\sigma(i)}...B_{\sigma^{m}(i)} \preceq B_{\sigma(i + 1)}...B_{\sigma^{m}(i + 1)}[/math], при [math]i = 0, ..., N - 1\ \ \textbf{(4)}[/math]
[math]B_iB_{\sigma(i)}...B_{\sigma^{m - 1}(i)} = S_{p(i) - 1}T[0..m - 1][/math], при [math]i = 0, ..., N\ \ \textbf{(5)}[/math]
Доказательство:
[math]\triangleright[/math]
Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получится таблица
[math]\triangleleft[/math]
Теорема:
Для восстановления исходного текста [math]T[/math] из преобразования [math]B[/math] достаточно знать число [math]I[/math], отвечающее условию [math]p(I) = 0[/math], другими словами [math]S_{p(I)}T = T[/math].

Дополнительно

  • bzip2 использует преобразование Барроуза — Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF (англ. move-to-front), и в конце кодирование Хаффмана.

Ссылки