Изменения

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

* Cоставляется Составляется таблица всех циклических сдвигов входной строки.

* В качестве выходной строки выбрается выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.

Пусть нам дана исходная строка <tex>$s = $</tex>''"ABACABA"''.

BCABAAA, 3

Результат можно записать так: <tex>$BWT(s)=$(</tex>(''"BCABAAA"'', 3<tex>)</tex>, где 3 {{---}} это номер исходной строки в отсортированной матрице, так как он . Он нужен для обратного преобразования.

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

Пусть нам дана исходная строка <tex>$s = $</tex>''"ABACABA$"''.

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

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

Следует также заметить, что если нам было бы дано <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) $s$ </tex>, также он требует после последнего шага получившиеся строки будут совпадать с циклическими перестановками <tex>O(N^2)$s$ </tex> памяти.

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

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