16
правок
Изменения
м
Косметические исправления
|}
Результат можно записать так: <tex>$BWT(s) = $(</tex>"BCABAAA", 3<tex>3)</tex>, где <tex>3 </tex> {{---}} номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования.
Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки ''<tex>\$''</tex>, который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется.
===Наивный алгоритм===
Пусть нам дано: <tex>$BWT(s) =$(</tex>"BCABAAA", 3<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>.
{|border ="1"
Данный алгоритм работает за <tex>O(N\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> — номер данной нам строки в таблице.
// 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]
* Суммируем: <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 использует преобразование Барроуза {{---}} Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF (англ. move-to-front), и в конце кодирование Хаффмана.
== Ссылки Источники информации ==*[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)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
