BWT: перестановка, которую можно развернуть

Если ты построишь BWT для abab, восстановишь текст по последнему столбцу и объяснишь, почему после преобразования одинаковые символы стоят рядом, - листай до «Теперь сам».

Как думаешь, можно ли вернуть текст из перестановки

Тебе дали строку annb$aa и сказали: это буквы слова, переставленные по некоторому правилу; знак $ стоял в конце. Больше ничего - ни номеров, ни таблиц.

Перестановка обычно необратима: из букв aaabnn слово не восстановить, вариантов десятки. Прежде чем читать дальше, подумай: что должно быть особенного в ПРАВИЛЕ перестановки, чтобы по результату можно было однозначно вернуть исходный порядок? И зачем вообще переставлять символы, если длина не меняется?

На что это похоже

Представь указатель к тексту, в котором выписано каждое место: текст, начиная с этого места, а на полях слева - буква, стоявшая прямо перед ним. Строки указателя отсортированы по алфавиту.

Теперь посмотри на строки, которые начинаются с he. Они стоят подряд - сортировка собрала их вместе. А на полях почти у всех одна и та же буква: t, потому что перед he в английском тексте обычно стоит t. Если прочитать сверху вниз одни поля, получатся длинные полосы одинаковых букв: буквы сгруппированы не по тому, где они стояли, а по тому, что шло ПОСЛЕ них. BWT - это и есть столбец полей.

Механизм: сдвиги, сортировка и последний столбец

К тексту дописывается символ конца $ - он не встречается в тексте и считается меньше любого символа. Циклический сдвиг - текст, прочитанный с некоторой позиции по кругу: дошли до конца - продолжаем с начала.

текст: banana$

место    сдвиг (отсортированы)     первый символ    последний символ
  0      $banana                         $                 a
  1      a$banan                         a                 n
  2      ana$ban                         a                 n
  3      anana$b                         a                 b
  4      banana$                         b                 $
  5      na$bana                         n                 a
  6      nana$ba                         n                 a

BWT - последний столбец, прочитанный сверху вниз: annb$aa.

В каждой строке последний символ - это тот, что стоит в тексте прямо ПЕРЕД первым: сдвиг читается по кругу. Строки 1, 2, 3 начинаются с a, и перед этими тремя a в тексте стоят n, n, b.

Сдвиги до символа $ - это суффиксы. Символ $ в тексте один, поэтому два сдвига обязательно различаются не позже, чем один из них дойдёт до $, и всё, что стоит после него, в сравнении уже не участвует. Значит, порядок строк таблицы - это суффиксный массив текста banana$: [6, 5, 3, 1, 0, 4, 2]. Таблицу строить не надо: символ BWT на месте i - это символ текста перед суффиксом sa[i].

Теперь обратимость. Первый столбец известен без таблицы: это те же символы, отсортированные, - $aaabnn. И работает одно наблюдение: первая a в последнем столбце и первая a в первом столбце - это одна и та же буква текста; вторая - вторая, третья - третья. Причина: строки, начинающиеся с a, упорядочены по тому, что идёт после этой a. Строки, КОНЧАЮЩИЕСЯ на a, упорядочены по своему началу - а оно и есть то, что идёт после этой a в тексте. Порядок один и тот же.

Правило

BWT текста - это символы, стоящие перед суффиксами в порядке суффиксного массива: bwt[i] = t[sa[i] − 1] (для sa[i] = 0 берётся символ конца). Длина равна длине текста с символом конца. Обращение: k-е по счёту вхождение символа c в последнем столбце соответствует k-му вхождению c в первом столбце; это соответствие строк называют LF-отображением: последний столбец принято обозначать L, первый - F. Начав со строки 0 и переходя по нему, получаем символы текста от последнего к первому. Символ конца обязан быть единственным и наименьшим - иначе восстановление неоднозначно.

Разбор: прямое преобразование и обратное

def bwt(s, konec):
    t = s + konec
    sa = suf_massiv(t)                # из главы про суффиксный массив
    out = []
    for i in sa:
        out.append(t[i - 1])          # при i = 0 это t[-1], то есть символ конца
    return "".join(out)

def obratno_bwt(L):
    n = len(L)
    kol = {}
    for c in L:
        kol[c] = kol.get(c, 0) + 1
    nach = {}                         # с какого места первого столбца идут символы c
    mesto = 0
    for c in sorted(kol.keys()):
        nach[c] = mesto
        mesto = mesto + kol[c]
    lf = [0] * n
    vstrecheno = {}
    i = 0
    while i < n:
        c = L[i]
        k = vstrecheno.get(c, 0)      # какое это по счёту c в последнем столбце
        lf[i] = nach[c] + k           # строка, которая с этого же c начинается
        vstrecheno[c] = k + 1
        i = i + 1
    out = []
    stroka = 0                        # строка 0 начинается с символа конца
    i = 0
    while i < n - 1:
        out.append(L[stroka])         # символ текста перед началом этой строки
        stroka = lf[stroka]
        i = i + 1
    out.reverse()
    return "".join(out)

print(bwt("banana", "$"))             # annb$aa
print(obratno_bwt("annb$aa"))         # banana

Проход для annb$aa. Первый столбец - $aaabnn: символ $ на месте 0, a на местах 1-3, b на месте 4, n на местах 5-6. Таблица lf: [1, 5, 6, 4, 0, 2, 3].

строка    её последний символ    почему следующая строка такая
  0              a               первая a последнего столбца → первая a первого: строка 1
  1              n               первая n → строка 5
  5              a               вторая a → строка 2
  2              n               вторая n → строка 6
  6              a               третья a → строка 3
  3              b               единственная b → строка 4

Выписано a n a n a b - текст от конца к началу. В обратном порядке: banana. Ответ на вопрос из начала урока: перестановка обратима, потому что правило - сортировка - оставляет след. Отсортированный столбец можно получить из результата, а связь между двумя столбцами восстанавливает порядок.

Разбор: что перестановка делает с сериями

Серия - один или несколько одинаковых символов подряд. Считаем серии до и после преобразования.

текст                             символов    серий до    серий после
banana$                               7           7             5
abracadabra$                         12          12             8
"abracadabra" * 10 + "$"            111         102             9
zhurnal + символ конца              827         775            85
tekst(1000, 4, 1) + "$"            1001         757           731

Третья строка - преобразование в чистом виде. BWT этого текста: a, десять r, десять d, девять a, $, десять r, десять c, сорок a, двадцать b. Десять букв r, стоящих перед десятью одинаковыми продолжениями acadabra…, собрались в одну серию, и так с каждым символом. Было 102 серии, стало девять.

Журнал: 775 серий превратились в 85. В преобразованном тексте почти в самом начале стоят сорок нулей подряд (последняя цифра кода 200 перед каждым переводом строки), сразу за ними сорок букв T (перед каждым пробелом после GET). «Меньше» для символов значит «с меньшим кодом»: у пробела код 32, у перевода строки 10, у знака $ - 36. Поэтому для журнала $ не годится, и символом конца там служит символ с кодом 0, в Python - chr(0).

Последняя строка - граница. В случайном тексте символ не зависит от того, что идёт после него, и группировать нечего: 757 серий и 731.

Сам текст при этом не стал короче ни на символ. Преобразование - подготовка: оно превращает закономерность «символ зависит от соседей», которую простые методы не видят, в закономерность «одинаковые символы стоят рядом», которую видят все. Что делать с ней дальше - в следующем уроке.

Что ломается без этого

Первое: символ конца не наименьший или встречается в тексте. Строка, начинающаяся с него, перестаёт быть нулевой, и обход стартует не оттуда. Для текста с пробелами знак $ уже не годится: пробел меньше. Форматы, которым негде взять лишний символ, вместо него хранят номер строки таблицы, в которой стоит исходный текст, - одно число на блок.

Второе: таблица сдвигов целиком. Построить n строк по n символов и отсортировать - квадратичная память: для блока в сто тысяч символов это десять гигабайт. BWT строят через суффиксный массив.

Третье: обращение сортировкой. Наивный способ развернуть BWT - n раз приписать столбец слева к таблице и отсортировать её. Это n сортировок по n строк. LF-отображение делает то же за один проход.

Четвёртое: ожидание сжатия от самого BWT. Длина выхода равна длине входа плюс символ конца. Если после преобразования ничего не делать, получится перемешанный текст того же размера.

Зачем это в работе

Первый сюжет - архиватор bzip2. Он режет файл на блоки до 900 килобайт, применяет к каждому BWT и затем простые методы. На текстах он сжимает плотнее gzip - на уроках этого курса разница почти в полтора раза. Платит временем распаковки: обратное преобразование прыгает по всему блоку, и разворачивается архив в разы медленнее, чем у gzip.

Второй - поиск в сжатом тексте. LF-отображение умеет больше, чем разворачивать текст. Если уметь быстро отвечать на вопрос «сколько символов c в первых i позициях BWT», можно искать образец, проходя его справа налево, за время порядка его длины - не распаковывая текст. Такая структура называется FM-индексом, и это тот самый сжатый индекс, обещанный в главе про суффиксный массив: геном человека с ним занимает несколько гигабайт вместо двенадцати. На нём работают программы, раскладывающие прочитанные фрагменты ДНК по геному.

Третий - общий приём. Обратимое преобразование, которое не сжимает, а делает данные удобными для простого сжатия, встречается постоянно: разности соседних значений в рядах измерений, перестановка байтов чисел по разрядам в таблицах. BWT - самый сильный пример этой идеи для текста.

Теперь сам

Построй BWT для текста abab с символом конца $. Затем восстанови текст по результату.

место    суффикс     начало    символ перед ним
  0      $              4           b
  1      ab$            2           b
  2      abab$          0           $
  3      b$             3           a
  4      bab$           1           a

строка 0: последний символ b, это первая b  → строка 3
строка 3: последний символ a, первая a      → строка 1
строка 1: последний символ b, вторая b      → строка 4
строка 4: последний символ a, вторая a      → строка 2