Изменения

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

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

3 байта убрано, 02:01, 24 октября 2013
Доказательство корректности
и в случае равенства <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>.
{{Теорема(1)
|statement=
147
правок

Навигация