147
правок
Изменения
→Доказательство корректности
:{|
<tex> S_{p(i)}T \preceq S_{p(i + 1)}T,\ i = 0 , .. ., N - 1\ \ \textbf{(1)}</tex>
|}
Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением:
:{|
:{|
<tex>B_{\sigma(i)} \preceq B_{\sigma(i + 1)}</tex>, при <tex>i = 0 , .. ., N - 1\ \ \textbf{(3)}</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^{k - 1} \circ \sigma</tex>, где <tex>\sigma^{1} = \sigma, \sigma^{0} \equiv i</tex>.
{{Теорема
|statement=
''При всех <tex>m = 1, ..., N + 1</tex> верны утверждения,
<tex>B_{\sigma_{i}...B_{\sigma^{m}_{i} \preceq B_{\sigma_{i + 1}}...B_{\sigma^{m}_{i + 1}}</tex>, при <tex>i = 0, ..., N - 1\ \ \textbf{(4)}</tex>''
|proof=
}}
{{Теорема
