16
правок
Изменения
м
<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/>
AABACAB ABAABAC <font color="red">ABACABA</font> ACABAAB BAABACA BACABAA CABAABA | BCABAAA, 3
<font color="red">ABACABA$</font>|style="text-align:center;"|<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|style="text-align:center;"|<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
<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
BCABAAA
<font color="red">ABACABA</font>
Таблицы
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA".
{| borderclass="1wikitable"
!colspan="4"|Трансформация
|-
! Вход || Все<br />Перестановки перестановки || Сортировка<br />Строк строк || Выход
|-
|
|
|}
Пусть нам дана исходная строка <tex>$s =$</tex> "ABACABA$".
{| borderclass="1wikitable"
!colspan="4"|Трансформация
|-
|-
|
|
|}
Алгоритм обратного преобразования описан в таблице ниже:
{| borderclass="1wikitable"
!colspan="8"| Обратное преобразование
|-
|-
|align="center" colspan="8"|
|-
! Добавление 1 || Сортировка 1 || Добавление 2 || Сортировка 2 || Добавление 3 || Сортировка 3 || Добавление 4
|-
|align="center" colspan="8"|
|}
* Переход. Рассмотрим <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 class="1wikitable"
!colspan="3" | <tex>$k+1$</tex> шаг алгоритма при <tex>$k=3$</tex>
|-
! Исходная <br /> таблица || Сдвинутая <br /> таблица || Результат <br /> работы <br /> алгоритма
|-align|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> i </tex>-ом месте приписываем в начало <tex> i </tex> -ый элемент столбца входных данных. Пусть изначально мы знаем каким по порядку является приписанный нами в начало символ (то есть каким по порядку в столбце). И конечно же мы знаем исходя из предыдущего шага какое место занимала наша строка без этого первого символа (<tex> i </tex> -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером <tex> i </tex> всегда будет перемещаться на позицию с номером <tex> j </tex>.
{| borderclass="1wikitable"
|0||а|| ||р||9
|-
{|
|
{| borderclass="1wikitable"
|6
|→
Пример для <tex>$BWT(s) =$</tex> "BCABAAA":
{|border class="1wikitable"
!colspan="3" | Таблица первого предподсчёта
|-
|}
{|border class="1wikitable"
!colspan="2" | Таблица второго предподсчёта
|-
