Преобразование Барроуза-Уилера: различия между версиями

Заметим, что каждый столбец матрицы <math>\mathcal{M} \;</math> – и, следовательно, преобразованный текст s – представляет собой перестановку строки s$. В нашем примере F, первый столбец bwt-матрицы <math>\mathcal{M} \;</math>, состоит из всех символов s, отсортированных по алфавиту. На рис. 1 F = $iiiimppssss.

Рисунок 1. Пример преобразования Барроуза-Уилера для строки s=mississippi. Матрица в правой части состоит из строк, отсортированных в лексикографическом порядке. Выходным значением алгоритма bwt является последний столбец отсортированной матрицы; в нашем примере это <math>\hat{s} = bwt(s) = ipssm$pissii \;</math>.