Изменения

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

! Вход || Все<br />перестановки циклические <br /> сдвиги || Сортировка<br />строк || Выход

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

* '''База'''. Циклически сдвинем все строки исходной таблицы на <tex>1</tex> влево. Тогда в столбце <tex>n</tex> будут находиться символы, добавленные на первом шаге алгоритма, а в столбце <tex>n - 1</tex> символы, изначально стоявшие в таблице до первого шага алгоритма. Таким образом, полученные на первом шаге алгоритма строки являются суффиксами циклических перестановок строки <tex>$s$</tex>.* '''Предположение'''. Пусть на <tex>k</tex> шаге алгоритма все полученные строки являются суффиксами циклических перестановок строки <tex>$s$</tex>.* '''Переход'''. Рассмотрим <tex>k+1</tex>-ый шаг алгоритма. Все строки отсортированы, поэтому самый левый столбец совпадет с <tex>1</tex> столбцом исходной таблицы. Циклически сдвинем все строки исходной таблицы на <tex>n - k</tex> символов вправо. Теперь по предположению первые <tex>k</tex> символов справа в каждой строке совпадают у исходной таблицы и у таблицы, полученной в результате работы алгоритма. <tex>k</tex>-ые справа столбцы также совпадают. Добавленный на <tex>k+1</tex>-ом шаге столбец также совпадает с <tex>k+1</tex>-ым справа столбцом сдвинутой исходной таблицы, так как совпадает с последним столбцом исходной таблицы, которая была сдвинута на <tex>n-k</tex>.

function reverseBWT(N : Int, M : Int, k : Int, s : Stirng): Int[] <font color="green">// Cчитаем частоты символов</font> '''for''' i = 0 .. M count[i] = 0 '''for''' i = 0 .. N count[s[i]]++ <font color="green">// Упорядочиваем символы, чтобы получить первый столбец исходной матрицы</font> <font color="green">// count[i] указывает на первую позицию символа i в первом столбце</font> sum = 0 '''for''' i = 0 .. M sum = sum + count[i] count[i] = sum - count[i] <font color="green">// Cоздаем вектор обратного преобразования</font> '''for''' i = 0 .. N t[count[s[i]]] = i count[s[i]]++ <font color="green">// И восстанавливаем исходный текст</font> j = t[x] '''for''' i = 0 .. N '''print'''( answer[i] = s[j]) j = t[j] return answer

<tex> S_{k}T = T[(j + k) (mod\bmod\ N + 1)] </tex>

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

Будем обозначать <tex>s^i</tex> <tex>i</tex>-ую циклическую перестановку <tex>$s$</tex>. Пусть <tex>s^0 = s_0 s_1 \ldots s_{n-1}</tex>, <tex>$BWT(s)$\;= L</tex> и <tex>L = L_0L_1\ldots L_{n-1}</tex>, <tex>I</tex> -- номер строки <tex>s^0</tex> в таблице. Предподсчитаем следующие величины:* Для каждого <tex>L_i</tex> количество символов на подстроке <tex>L_0 l_0, \ldots L_, l_{i-1}</tex>, равных <tex>L_i</tex>

# Частота, с которой символ <tex>L_{i}</tex> встречается в подстроке <tex>L_0l_0, \ldots L_, l_{i-1}</tex>

* bzip2 <ref>[https://ru.wikipedia.org/wiki/Bzip2 bzip2]</ref> использует преобразование Барроуза {{---}} Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование [[Преобразование_MTF | MTF (англ. move-to-front)]], и в конце кодирование Хаффмана. == См. также ==* [[Алгоритм_Хаффмана | Алгоритм Хаффмана]]* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]]* [[Арифметическое_кодирование | Арифметическое кодирование]]