Изменения

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

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

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

{| borderclass="1wikitable"

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

<font color="red">ABACABA</font>|style="text-align:center;"| <font color="red">ABACABA</font> <br/> BACABAA<br/> ACABAAB<br/> CABAABA<br/> ABAABAC<br/> BAABACA<br/> AABACAB<br/>|style="text-align:center;"| AABACAB<br/> ABAABAC<br/> <font color="red">ABACABA</font><br/> ACABAAB<br/> BAABACA<br/> BACABAA<br/> CABAABA <br/>

BCABAAA, 3

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

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

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

{| borderclass="1wikitable"

! Вход || Все<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/>CABA$ABA<br/>ABA$ABAC<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/>A$ABACAB<br/>BACABA$A<br/>BA$ABACA<br/>CABA$ABA <br/>$ABACABA</span>

<font color="red">ABACABA$</font> BACABA$A ACABA$AB CABA$ABA ABA$ABAC BA$ABACA A$ABACAB $ABACABA | <font color="red">ABACABA$</font> ABA$ABAC ACABA$AB A$ABACAB BACABA$A BA$ABACA CABA$ABA $ABACABA| $CBBAAAA

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

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

{| borderclass="1wikitable"

BCABAAA

<font color="red">ABACABA</font>

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

Как несложно посчитать Временная сложность данного алгоритма <tex>O(N^3logN3\log{N}) </tex>, также он требует пространственная <tex>O(N^2)</tex> памяти.

===Оптимизация=Доказательство корректности====

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

{| class="wikitable"!colspan="3" | <tex>k+1</tex> шаг алгоритма при <tex>k=3</tex>|-! Исходная <br /> таблица || Сдвинутая <br /> таблица || Результат <br /> работы <br /> алгоритма|-|style="text-align:center;"|<font color="red">A</font><font color="green">ABA</font>CA<font color="blue">B</font><br/><font color="red">A</font><font color="green">BAA</font>BA<font color="blue">C</font><br/><font color="red">A</font><font color="green">BAC</font>AB<font color="blue">A</font><br/><font color="red">A</font><font color="green">CAB</font>AA<font color="blue">B</font><br/><font color="red">B</font><font color="green">AAB</font>AC<font color="blue">A</font><br/><font color="red">B</font><font color="green">ACA</font>BA<font color="blue">A</font><br/><font color="red">C</font><font color="green">ABA</font>AB<font color="blue">A</font>|style="text-align:center;"|CA<font color="blue">B</font><font color="red">A</font><font color="green">ABA</font><br/>BA<font color="blue">C</font><font color="red">A</font><font color="green">BAA</font><br/>AB<font color="blue">A</font><font color="red">A</font><font color="green">BAC</font><br/>AA<font color="blue">B</font><font color="red">A</font><font color="green">CAB</font><br/>AC<font color="blue">A</font><font color="red">B</font><font color="green">AAB</font><br/>BA<font color="blue">A</font><font color="red">B</font><font color="green">ACA</font><br/>AB<font color="blue">A</font><font color="red">C</font><font color="green">ABA</font>|style="text-align:right;"|<font color="blue">B</font><font color="red">A</font><font color="green">ABA</font> <br/><font color="blue">C</font><font color="red">A</font><font color="green">BAA</font> <br/><font color="blue">A</font><font color="red">A</font><font color="green">BAC</font> <br/><font color="blue">B</font><font color="red">A</font><font color="green">CAB</font> <br/><font color="blue">A</font><font color="red">B</font><font color="green">AAB</font> <br/><font color="blue">A</font><font color="red">B</font><font color="green">ACA</font> <br/><font color="blue">A</font><font color="red">C</font><font color="green">ABA</font> <br/>|-|} Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических сдвигов <tex> s </tex>, после последнего шага получившиеся строки будут совпадать с циклическими сдвигами <tex> s </tex>. ===Оптимизированный наивный алгоритм=== Наивный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. К предыдущему приписывался новый столбец и имеющиеся данные сортировались. На каждом шаге к строке, которая находилась на <tex> i </tex>-ом месте, приписывался в начало <tex> i </tex> -ый элемент столбца входных данных. Пусть изначально известно, каким по порядку является приписанный в начало символ (то есть каким по порядку в столбце). Из предыдущего шага известно, какое место занимала строка без этого первого символа (<tex> i </tex> -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером <tex> i </tex> всегда будет перемещаться на позицию с номером <tex> j </tex>.  {| borderclass="1wikitable"

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

{| borderclass="1wikitable"

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

====Псевдокод оптимизированного алгоритма====Пусть <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 : String): 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, \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" !colspan="3" | Таблица первого предподсчёта|-! Позиция || Символ || Результат|-align="center"! 0 || B || 0|-! 1 || C || 0|-! 2 || A || 0|-! 3 || B || 1|-! 4 || A || 1|-! 5 || A || 2|-! 6 || A || 3|} {| class="wikitable"!colspan="2" | Таблица второго предподсчёта|-! Символ || Количество <br /> меньших|-align="center"! A || 0|-! B || 4|-! C || 6|} Для удобства пронумеруем известные нам данные:# <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>s_{n-2}</tex> в строке <tex>L</tex>. Зная <tex>s_{n-1}</tex> и <tex>s_{n-2}</tex>, аналогично найдём <tex>s_{n-3}\ldots s_0</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>0+0=0</tex>, <tex>s_5=L_0=B</tex>, <tex>s^0=.....</tex>BA* Суммируем: <tex>0+4=4</tex>, <tex>s_4=L_4=A</tex>, <tex>s^0=....</tex>ABA* Суммируем: <tex>1+0=1</tex>, <tex>s_3=L_1=C</tex>, <tex>s^0=...</tex>CABA* Суммируем: <tex>0+6=6</tex>, <tex>s_2=L_6=A</tex>, <tex>s^0=..</tex>ACABA* Суммируем: <tex>3+0=3</tex>, <tex>s_2=L_3=B</tex>, <tex>s^0=.</tex>BACABA* Суммируем: <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]]* [[Арифметическое_кодирование | Арифметическое кодирование]]

== Ссылки Источники информации ==*[http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0 Википедия: Преобразование Барроуза {{---}} Уилера (Википедия)]

*[http://www.cs.karelia.ru/~aborod/inf/2010/schedule.php.ru cs.karelia.ru: Преобразование Барроуза {{---}} Уилера (cs.karelia.ru)]