147
правок
Изменения
→Доказательство корректности
===Доказательство корректности===
Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево:
Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением:
:{|
<tex>B[i] = S_{p(i)}T[N], </tex>, другими словами <tex>B[i] = S_{p(i) - 1}T[0] = T[(p(i) - 1) (mod\ N + 1)] \ \ \textbf{(2)}</tex>
|}
|proof=
|9||р|| ||б||5
|-
|10||р|| ||б||6
Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получится таблица
