Изменения

Перейти к: навигация, поиск

Преобразование Барроуза-Уилера

2 байта добавлено, 00:32, 24 октября 2013
Доказательство корректности
Пусть текст <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> S_{k}T = T[(j + k) (mod\ n + 1)] </tex>
|}
Существует перестановка <tex>p</tex> чисел <tex>[0..N]</tex>, которая удовлетворяет условию:
:{{|
<tex> S_{p(i)}T \preceq S_{p(i + 1)}T, i\ =\ 0..N\ - \ 1</tex>
}|}
== Дополнительно ==
147
правок

Навигация