Преобразование Барроуза-Уилера — различия между версиями
(→Доказательство корректности) |
м (rollbackEdits.php mass rollback) |
||
(не показана 21 промежуточная версия 6 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | '''Преобразование Барроуза {{---}} Уилера''' {{---}} алгоритм, используемый для предварительной обработки данных перед сжатием, разработанный для улучшения эффективности последующего кодирования. Преобразование Барроуза {{---}} Уилера меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов. | + | '''Преобразование Барроуза {{---}} Уилера''' (англ. ''Burrows-Wheeler transform'') {{---}} алгоритм, используемый для предварительной обработки данных перед сжатием, разработанный для улучшения эффективности последующего кодирования. Преобразование Барроуза {{---}} Уилера меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов. |
== Описание алгоритма == | == Описание алгоритма == | ||
− | Преобразование выполняется в три этапа | + | Преобразование выполняется в три этапа: |
− | + | # Составляется таблица всех циклических сдвигов входной строки. | |
− | + | # Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. | |
− | + | # В качестве выходной строки выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной. | |
== Пример работы алгоритма == | == Пример работы алгоритма == | ||
− | Пусть нам дана исходная строка <tex>s = </tex> | + | Пусть нам дана исходная строка <tex>s =</tex> "ABACABA". |
− | {| | + | {| class="wikitable" |
!colspan="4"|Трансформация | !colspan="4"|Трансформация | ||
|- | |- | ||
− | ! Вход || Все<br /> | + | ! Вход || Все<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> | + | Результат можно записать так: <tex>BWT(s) = (</tex>"BCABAAA", <tex>3)</tex>, где <tex>3</tex> {{---}} номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования. |
− | Следует заметить, что иногда в исходной строке приводится | + | Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки <tex>\$</tex>, который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется. |
− | Пусть нам дана исходная строка <tex>s = </tex> | + | Пусть нам дана исходная строка <tex>s =</tex> "ABACABA$". |
− | {| | + | {| class="wikitable" |
!colspan="4"|Трансформация | !colspan="4"|Трансформация | ||
|- | |- | ||
− | ! Вход || Все<br /> | + | ! Вход || Все<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> | ||
| | | | ||
− | + | $CBBAAAA | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
|} | |} | ||
− | При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной: ( | + | При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки, и будет исходной: ("ABACABA$"). Тогда результат можно записать так: <tex>BWT(s) =</tex> "$CBBAAAA". |
== Обратное преобразование == | == Обратное преобразование == | ||
Строка 87: | Строка 85: | ||
===Наивный алгоритм=== | ===Наивный алгоритм=== | ||
− | Пусть нам дано: <tex>BWT(s)=</tex> | + | Пусть нам дано: <tex>BWT(s) =(</tex>"BCABAAA", <tex>3)</tex>. Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза {{---}} Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно [[Сортировки | отсортируем]] матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических сдвигов строки, которую нам надо найти. Выстроив полный отсортированный список сдвигов, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. |
Алгоритм обратного преобразования описан в таблице ниже: | Алгоритм обратного преобразования описан в таблице ниже: | ||
− | {| | + | {| class="wikitable" |
!colspan="8"| Обратное преобразование | !colspan="8"| Обратное преобразование | ||
|- | |- | ||
Строка 96: | Строка 94: | ||
|- | |- | ||
|align="center" colspan="8"| | |align="center" colspan="8"| | ||
− | + | BCABAAA | |
|- | |- | ||
! Добавление 1 || Сортировка 1 || Добавление 2 || Сортировка 2 || Добавление 3 || Сортировка 3 || Добавление 4 | ! Добавление 1 || Сортировка 1 || Добавление 2 || Сортировка 2 || Добавление 3 || Сортировка 3 || Добавление 4 | ||
Строка 221: | Строка 219: | ||
|- | |- | ||
|align="center" colspan="8"| | |align="center" colspan="8"| | ||
− | + | <font color="red">ABACABA</font> | |
|} | |} | ||
− | Следует также заметить, что если нам было бы дано <tex>BWT(s)=</tex> | + | Следует также заметить, что если нам было бы дано <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 /> алгоритма | ||
+ | |- | ||
+ | |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>. |
+ | |||
+ | {| class="wikitable" | ||
|0||а|| ||р||9 | |0||а|| ||р||9 | ||
|- | |- | ||
Строка 256: | Строка 295: | ||
|} | |} | ||
− | Здесь слева | + | Здесь слева отсортированный данный столбец, чтобы мы знали, какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку в нашем алгоритме новый столбец приписывается в начало, то мы из состояния <tex> i </tex> (левый столбец) переходим в состояние <tex> j </tex> (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из <tex> j </tex> в <tex> i </tex> восстановить строку. |
{| | {| | ||
| | | | ||
− | {| | + | {| class="wikitable" |
|6 | |6 | ||
|→ | |→ | ||
Строка 304: | Строка 343: | ||
|а | |а | ||
|} | |} | ||
− | ===Сложность оптимизированного алгоритма=== | + | ====Сложность оптимизированного алгоритма==== |
− | Данный алгоритм работает за <tex>O( | + | Данный алгоритм работает за <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> 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 | |
− | + | answer[i] = s[j] | |
+ | j = t[j] | ||
+ | '''return''' answer | ||
− | ===Доказательство корректности=== | + | ====Доказательство корректности==== |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево: | Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево: | ||
:{| | :{| | ||
− | <tex> S_{k}T = T[(j + k) ( | + | <tex> S_{k}T = T[(j + k) (\bmod\ N + 1)] </tex> |
|} | |} | ||
Строка 369: | Строка 386: | ||
Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением: | Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением: | ||
:{| | :{| | ||
− | <tex>B[i] = S_{p(i)}T[N] | + | <tex>B[i] = S_{p(i)}T[N]</tex>, другими словами <tex>B[i] = S_{p(i) - 1}T[0] = T[(p(i) - 1) (\bmod\ N + 1)] \ \ \textbf{(2)}</tex> |
|} | |} | ||
Строка 389: | Строка 406: | ||
Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получится таблица | Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получится таблица | ||
+ | |||
+ | | class="wikitable" style="text-align:center" | ||
+ | |- | ||
+ | !Таблица | ||
+ | |- | ||
+ | |a||b||c | ||
+ | |- | ||
+ | |a||b||c | ||
+ | | | ||
+ | |||
}} | }} | ||
Строка 399: | Строка 426: | ||
}} | }} | ||
− | == | + | ===Алгоритм за линейное время=== |
+ | |||
+ | Будем обозначать <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]] | ||
+ | * [[Арифметическое_кодирование | Арифметическое кодирование]] | ||
− | + | == Примечания == | |
+ | <references/> | ||
− | == | + | == Источники информации == |
− | *[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://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 Преобразование Барроуза {{---}} Уилера | + | *[http://www.cs.karelia.ru/~aborod/inf/2010/schedule.php.ru cs.karelia.ru: Преобразование Барроуза {{---}} Уилера] |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Алгоритмы сжатия ]] | [[Категория: Алгоритмы сжатия ]] |
Текущая версия на 19:14, 4 сентября 2022
Преобразование Барроуза — Уилера (англ. Burrows-Wheeler transform) — алгоритм, используемый для предварительной обработки данных перед сжатием, разработанный для улучшения эффективности последующего кодирования. Преобразование Барроуза — Уилера меняет порядок символов во входной строке таким образом, что повторяющиеся подстроки образуют на выходе идущие подряд последовательности одинаковых символов.
Описание алгоритма
Преобразование выполняется в три этапа:
- Составляется таблица всех циклических сдвигов входной строки.
- Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы.
- В качестве выходной строки выбирается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.
Пример работы алгоритма
Пусть нам дана исходная строка
"ABACABA".Трансформация | |||
---|---|---|---|
Вход | Все циклические сдвиги |
Сортировка строк |
Выход |
ABACABA |
ABACABA |
AABACAB |
BCABAAA, 3 |
Результат можно записать так:
"BCABAAA", , где — номер исходной строки в отсортированной матрице. Он нужен для обратного преобразования.
Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки , который в преобразовании будет считаться последним (максимальным) символом, тогда сохранение номера исходной строки не требуется.
Пусть нам дана исходная строка "ABACABA$".
Трансформация | |||
---|---|---|---|
Вход | Все циклические сдвиги |
Сортировка строк |
Выход |
ABACABA$ |
ABACABA$ |
ABACABA$ |
$CBBAAAA |
При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки, и будет исходной: ("ABACABA$"). Тогда результат можно записать так:
"$CBBAAAA".Обратное преобразование
Наивный алгоритм
Пусть нам дано: отсортируем матрицу, затем в предыдущий столбец запишем "BCABAAA". Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических сдвигов строки, которую нам надо найти. Выстроив полный отсортированный список сдвигов, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. Алгоритм обратного преобразования описан в таблице ниже:
"BCABAAA", . Тогда выпишем в столбик нашу преобразованную последовательность символов "BCABAAA". Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчноОбратное преобразование | |||||||
---|---|---|---|---|---|---|---|
Вход | |||||||
BCABAAA | |||||||
Добавление 1 | Сортировка 1 | Добавление 2 | Сортировка 2 | Добавление 3 | Сортировка 3 | Добавление 4 | |
B C A B A A A |
A A A A B B C |
BA CA AA BA AB AB AC |
AA AB AB AC BA BA CA |
BAA CAB AAB BAC ABA ABA ACA |
AAB ABA ABA ACA BAA BAC CAB |
BAAB CABA AABA BACA ABAA ABAC ACAB | |
Сортировка 4 | Добавление 5 | Сортировка 5 | Добавление 6 | Сортировка 6 | Добавление 7 | Сортировка 7 | |
AABA ABAA ABAC ACAB BAAB BACA CABA |
BAABA CABAA AABAC BACAB ABAAB ABACA ACABA |
AABAC ABAAB ABACA ACABA BAABA BACAB CABAA |
BAABAC CABAAB AABACA BACABA ABAABA ABACAB ACABAA |
AABACA ABAABA ABACAB ACABAA BAABAC BACABA CABAAB |
BAABACA CABAABA AABACAB BACABAA ABAABAC ABACABA ACABAAB |
AABACAB ABAABAC ABACABA ACABAAB BAABACA BACABAA CABAABA | |
Результат | |||||||
ABACABA |
Следует также заметить, что если нам было бы дано
"$CBBAAAA", то мы также получили бы нашу исходную строку, только с символом конца строки на конце: ABACABA$.Временная сложность данного алгоритма
, пространственная .Доказательство корректности
Пусть дана строка
, к которой было применено преобразование BWT. Докажем, что при использовании наивного алгоритма на каждом шаге получающийся набор строк соответствует суффиксам циклических сдвигов исходной строки, методом математической индукции.- База. Циклически сдвинем все строки исходной таблицы на влево. Тогда в столбце будут находиться символы, добавленные на первом шаге алгоритма, а в столбце символы, изначально стоявшие в таблице до первого шага алгоритма. Таким образом, полученные на первом шаге алгоритма строки являются суффиксами циклических сдвигов строки .
- Предположение. Пусть на шаге алгоритма все полученные строки являются суффиксами циклических сдвигов строки .
- Переход. Рассмотрим -ый шаг алгоритма. Все строки отсортированы, поэтому самый левый столбец совпадет с столбцом исходной таблицы. Циклически сдвинем все строки исходной таблицы на символов вправо. Теперь по предположению первые символов справа в каждой строке совпадают у исходной таблицы и у таблицы, полученной в результате работы алгоритма. -ые справа столбцы также совпадают. Добавленный на -ом шаге столбец также совпадает с -ым справа столбцом сдвинутой исходной таблицы, так как совпадает с последним столбцом исходной таблицы, которая была сдвинута на .
шаг алгоритма при | ||
---|---|---|
Исходная таблица |
Сдвинутая таблица |
Результат работы алгоритма |
AABACAB |
CABAABA |
BAABA |
Таким образом, поскольку на каждом шаге алгоритма получившиеся строки являлись суффиксами циклических сдвигов
, после последнего шага получившиеся строки будут совпадать с циклическими сдвигами .Оптимизированный наивный алгоритм
Наивный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. К предыдущему приписывался новый столбец и имеющиеся данные сортировались. На каждом шаге к строке, которая находилась на
-ом месте, приписывался в начало -ый элемент столбца входных данных. Пусть изначально известно, каким по порядку является приписанный в начало символ (то есть каким по порядку в столбце). Из предыдущего шага известно, какое место занимала строка без этого первого символа ( -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером всегда будет перемещаться на позицию с номером .0 | а | р | 9 | |
1 | а | д | 7 | |
2 | а | a | 0 | |
3 | а | к | 8 | |
4 | а | р | 10 | |
5 | б | a | 1 | |
6 | б | a | 2 | |
7 | д | a | 3 | |
8 | к | a | 4 | |
9 | р | б | 5 | |
10 | р | б | 6 |
Здесь слева отсортированный данный столбец, чтобы мы знали, какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку в нашем алгоритме новый столбец приписывается в начало, то мы из состояния
(левый столбец) переходим в состояние (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из в восстановить строку.
Сложность оптимизированного алгоритмаДанный алгоритм работает за времени и требует памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за действий и требует памяти, где — размер алфавита.Псевдокод оптимизированного алгоритмаПусть — количество символов во входной строке, — количество символов в алфавите, — номер исходной строки в матрице сдвигов, — входящая строка, — массив для сортировки подсчетом, — вектор обратного преобразования, — номер данной нам строки в таблице.function reverseBWT(N : Int, M : Int, k : Int, s : String): Int[] // 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 answer[i] = s[j] j = t[j] return answer Доказательство корректностиПусть текст состоит из символов, занумерованных с нуля: . Буквы принадлежат некоторому алфавиту . Лексикографический порядок (строгий) на строках из алфавита будем обозначать . Обозначим через циклический сдвиг текста на символов влево:Существует перестановка чисел , которая удовлетворяет условию:Преобразование Барроуза-Уилера текста есть текст , буквы которого заданы соотношением:Пусть — перестановка чисел , удовлетворяющая условию:и в случае равенства и выполнено — . Перестановка однозначно определяется текстом и ее можно посчитать за , используя сортировку подсчетом. Рассмотрим перестановку как отображение . Пусть копмозиция отображений , где .
Алгоритм за линейное времяБудем обозначать -ую циклический сдвиг . Пусть , и , -- номер строки в таблице. Предподсчитаем следующие величины:
Пример для "BCABAAA":
Для удобства пронумеруем известные нам данные:
Символ находится в строке под номером , так как в таблице строка имела номер . Найдём символ .Символ имеет в строке тот же номер, что строка имела в таблице сдвигов: строка начинается с символа , находится на 1 левее его и из-за циклического сдвига оказывается в последнем столбце. Нам известен символ . Посчитаем, на каком месте в таблице будет стоять строка, начинающаяся с этого символа.Из 4 известно количество символов, меньших . Все строки, начинающиеся с этих символов, стоят в таблице раньше . Кроме того, в таблице есть строки, начинающиеся с того же символа, что и . Из 3 известно, сколько их: если символ, равный , встречался в раньше, чем , то в таблице строка, начинающаяся с этого символа, тоже стоит раньше строки, начинающейся с , так как префикс строки, оканчивающейся на этот символ, меньше префикса строки, оканчивающейся на .Тогда сумма этих двух величин является номером символа в строке . Зная и , аналогично найдём .Предподсчёт занимает времени, восстановление каждого из символов занимает времени. Суммарное время работы алгоритма .Пример работы для "BCABAAA", 2 (нумерация с 0):
Замечания
См. такжеПримечанияИсточники информации |