147
правок
Изменения
→Доказательство корректности
|}
Существует перестановка <tex>p</tex> чисел <tex>[{0, ..., N]}</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>
|}
Пусть <tex>\sigma<tex> {{---}} перестановка чисел <tex>{0, ..., N}</tex>, удовлетворяющая условию:
:{|
<tex>B_{\sigma(i)} \preceq B_{\sigma(i + 1)</tex>, при <tex>i = 0 .. N - 1</tex>,
|}
и в случае равенства <tex>B_{\sigma(i)}</tex> и <tex>B_{\sigma(i + 1)</tex> выполнено {{---}} <tex>\sigma(i) < \sigma(i + 1)</tex>. Перестановка однозначно определяется текстом <tex>B</tex> и ее можно посчитать за <tex>O(N)</tex>, используя сортировку подсчетом. Рассмотрим перестановку <tex>\sigma</tex> как отображение <tex>\sigma : {0, ..., N} \to {0, ..., N}</tex>. Пусть <tex>\sigma^{k}</tex> копмозиция <tex>k</tex> отображений <tex>\sigma^{k} = \sigma \circ \sigma \circ ... \circ \sigma</tex>.
{{Теорема
