66
правок
Изменения
м
== Примечания ==
<references/>
Delete some wrong "$".
== Пример работы алгоритма ==
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA".
{| class="wikitable"
|}
Результат можно записать так: <tex>$BWT(s) = $(</tex>"BCABAAA", <tex>3)</tex>, где <tex>3</tex> {{---}} номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования.
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA$".
{| class="wikitable"
!colspan="4"|Трансформация
|-
! Вход || Все<br />Перестановки циклические <br/> сдвиги || Сортировка<br />Строк строк || Выход
|-
|
<font color="red">ABACABA$</font>
|style="text-align:center;"|
<span class="tex2jax_ignore"><font color="red">ABACABA$</font><br/>
BACABA$A<br/>
ACABA$AB<br/>
BA$ABACA<br/>
A$ABACAB<br/>
$ABACABA</span>
|style="text-align:center;"|
<span class="tex2jax_ignore"><font color="red">ABACABA$</font><br/>
ABA$ABAC<br/>
ACABA$AB<br/>
BA$ABACA<br/>
CABA$ABA <br/>
$ABACABA</span>
|
$CBBAAAA
При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки, и будет исходной: ("ABACABA$"). Тогда результат можно записать так: <tex>$BWT(s) =$</tex> "$CBBAAAA".
== Обратное преобразование ==
===Наивный алгоритм===
Пусть нам дано: <tex>$BWT(s) =$(</tex>"BCABAAA", <tex>3)</tex>. Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза {{---}} Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно [[Сортировки | отсортируем]] матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок сдвигов строки, которую нам надо найти. Выстроив полный отсортированный список перестановоксдвигов, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.
Алгоритм обратного преобразования описан в таблице ниже:
|}
Следует также заметить, что если нам было бы дано <tex>$BWT(s) = $</tex> "$CBBAAAA", то мы также получили бы нашу исходную строку, только с символом конца строки <tex>\$</tex> на конце: ABACABA$.
Временная сложность данного алгоритма <tex>O(N^3\log{N}) </tex>, пространственная <tex>O(N^2)</tex>.
====Доказательство корректности====
Пусть дана строка <tex>$s$</tex>, к которой было применено преобразование BWT. Докажем, что при использовании наивного алгоритма на каждом шаге получающийся набор строк соответствует суффиксам циклических перестановок сдвигов исходной строки, методом математической индукции.* '''База'''. Циклически сдвинем все строки исходной таблицы на <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>.
{| class="wikitable"
!colspan="3" | <tex>$k+1$</tex> шаг алгоритма при <tex>$k=3$</tex>
|-
! Исходная <br /> таблица || Сдвинутая <br /> таблица || Результат <br /> работы <br /> алгоритма
|}
Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических перестановок сдвигов <tex> $s$ </tex>, после последнего шага получившиеся строки будут совпадать с циклическими перестановками сдвигами <tex> $s$ </tex>.
===Оптимизированный наивный алгоритм===
Наивный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. Мы приписывали К предыдущему приписывался новый столбец и сортировали имеющиеся данныесортировались. На каждом шагу мы шаге к строке, которая находилась на <tex> i </tex>-ом месте приписываем , приписывался в начало <tex> i </tex> -ый элемент столбца входных данных. Пусть изначально мы знаем известно, каким по порядку является приписанный нами в начало символ (то есть каким по порядку в столбце). И конечно же мы знаем исходя из Из предыдущего шага известно, какое место занимала наша строка без этого первого символа (<tex> i </tex> -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером <tex> i </tex> всегда будет перемещаться на позицию с номером <tex> j </tex>.
{| class="wikitable"
====Псевдокод оптимизированного алгоритма====
Пусть <tex> N </tex> — количество символов во входной строке, <tex> M </tex> — количество символов в алфавите, <tex> k </tex> — номер исходной строки в матрице перестановоксдвигов, <tex> s </tex> — входящая строка, <tex> count </tex> — массив для сортировки подсчетом, <tex> t </tex> — вектор обратного преобразования, <tex> x </tex> — номер данной нам строки в таблице.
'''function ''' reverseBWT(N : Int, M : Int, k : Int, s : StirngString): Int[]
<font color="green">// Cчитаем частоты символов</font>
'''for''' i = 0 .. M
answer[i] = s[j]
j = t[j]
'''return ''' answer
====Доказательство корректности====
===Алгоритм за линейное время===
Будем обозначать <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, \ldots , l_{i-1}</tex>, равных <tex>L_i</tex>
* Для каждого уникального <tex>L_i</tex> количество символов в <tex>L</tex>, лексикографически меньших, чем <tex>L_i</tex>
Пример для <tex>$BWT(s) =$</tex> "BCABAAA":
{| class="wikitable"
Для удобства пронумеруем известные нам данные:
# <tex>L</tex>, последний столбец таблицы перестановоксдвигов# <tex>I</tex>, номер строки <tex>$s$</tex> в таблице перестановоксдвигов
# Частота, с которой символ <tex>L_{i}</tex> встречается в подстроке <tex>l_0, \ldots , l_{i-1}</tex>
# Для каждого уникального символа количество лексикографически меньших символов в <tex>L</tex>
Символ <tex>s_{n-1}</tex> находится в строке <tex>L</tex> под номером <tex>I</tex>, так как в таблице строка <tex>s^0</tex> имела номер <tex>I</tex>. Найдём символ <tex>s_{n-2}</tex>.
Символ <tex>s_{n-2}</tex> имеет в строке <tex>L</tex> тот же номер, что строка <tex>s^{n-1}</tex> имела в таблице перестановоксдвигов: строка <tex>s^{n-1}</tex> начинается с символа <tex>s_{n-1}</tex>, <tex>s_{n-2}</tex> находится на 1 левее его и из-за циклического сдвига оказывается в последнем столбце. Нам известен символ <tex>s_{n-1}</tex>. Посчитаем, на каком месте в таблице будет стоять строка, начинающаяся с этого символа.
Из 4 известно количество символов, меньших <tex>s_{n-1}</tex>. Все строки, начинающиеся с этих символов, стоят в таблице раньше <tex>s^{n-1}</tex>. Кроме того, в таблице есть строки, начинающиеся с того же символа, что и <tex>s^{n-1}</tex>. Из 3 известно, сколько их: если символ, равный <tex>s_{n-1}</tex>, встречался в <tex>L</tex> раньше, чем <tex>s_{n-1}</tex>, то в таблице строка, начинающаяся с этого символа, тоже стоит раньше строки, начинающейся с <tex>s_{n-1}</tex>, так как префикс строки, оканчивающейся на этот символ, меньше префикса строки, оканчивающейся на <tex>s_{n-1}</tex>.
Предподсчёт занимает <tex>O(n)</tex> времени, восстановление каждого из <tex>n</tex> символов занимает <tex>O(1)</tex> времени. Суммарное время работы алгоритма <tex>O(n)</tex>.
Пример работы для <tex>$BWT(s) = ($</tex>"BCABAAA", 2<tex>)</tex> (нумерация с 0):
* <tex>s^0 = .......</tex>
* <tex>s_6=L_2 = A</tex>. Тогда <tex>s^0=......</tex>A
* Суммируем: <tex>1+4=5</tex>, <tex>s_2=L_5=A</tex>, <tex>s^0=</tex> ABACABA
== Дополнительно Замечания ==
* bzip2<ref>[https://ru.wikipedia.org/wiki/Bzip2 bzip2]</ref> использует преобразование Барроуза {{---}} Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование [[Преобразование_MTF | MTF]], и в конце кодирование Хаффмана.
* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]]
* [[Арифметическое_кодирование | Арифметическое кодирование]]
== Примечания ==
<references/>
== Источники информации ==
*[http://www.cs.karelia.ru/~aborod/inf/2010/schedule.php.ru cs.karelia.ru: Преобразование Барроуза {{---}} Уилера]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
