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

В работе [3] Барроуз и Уилер предложили новый алгоритм сжатия, основанный на обратимом преобразовании, которое ныне называется преобразованием Барроуза-Уилера (bwt). Пусть имеется строка s. Вычисление значения bwt(s) состоит из трех основных этапов см. рис. 1):

1. добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>;

3. построить преобразованные текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math>.

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