Преобразование Барроуза-Уилера: различия между версиями

Доказательство. Поскольку каждая строка содержит циклический сдвиг строки s$, последним символом строки, префиксом которой является <math>s[k_{i + 1}, n - 1] \;</math>, является <math>s[k_i] \;</math>. Из этого, согласно определению 1, следует <math>\hat{s} [\Psi(i)] = s[k_i] = F[i] \;</math>, что и требовалось доказать. □

'''Лемма 2. Если <math>1 \le i < j \le n \;</math> и F[i] = F[j], то <math>\Psi(i) < \Psi(j) \;</math>.'''

Доказательство. Пусть <math>s[k_i, n - 1] \;</math> (соответственно, <math>s[k_j, n - 1]) \;</math> обозначает суффикс s, являющийся префиксом строки i (строки j, соответственно). Из гипотезы i < j следует, что <math>s[k_i, n - 1] \prec s[k_j,  n - 1] \;</math>. Из гипотезы F[i] = F[j] следует, что <math>s[k_i] = s[k_j] \;</math>, поскольку должно иметь место <math>s[k_{i + 1}, n - 1] \prec s[k_{j + 1}, n - 1] \;</math>. Из этого следует утверждение леммы, поскольку по построению <math>\Psi(i) \;</math> (<math>\Psi(j) \;</math>, соответственно) является лексикографической позицией строки, префиксом которой является <math>s[k_{i + 1}, n - 1] \;</math> (<math>s[k_{j + 1}, n - 1] \;</math>, соответственно). □