BWT

Взять слово $w$ над упорядоченным алфавитом и выписать все $|w|$ его циклических сдвигов в столбик, получив квадратную матрицу. Отсортировать строки матрицы лексикографически, получая матрицу $T(w)$. Вернуть последний столбец матрицы $(\text{bwt}(w))$.

Каждая буква из $w$ является последней ровно для одного циклического сдвига. Следствия: $\text{bwt}(w)$ является анаграммой $w$. $\text{bwt}$ как функция является действием некоторой перестановки (зависящей от $w$).