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

'''Лемма 3. Для любого символа <math>c \in \Sigma \;</math> верно: если F[j] является <math>\ell</math>-м вхождением c в F, то <math>\hat{s}[\Psi (j)] \;</math> является <math>\ell</math>-м вхождением c в <math>\hat{s} \;</math>.'''

Доказательство. Возьмем индекс h, такой, что h < j и F[h] = F[j] = c (случай с h > j является симметричным). Из леммы 2 следует, что <math>\Psi(h) < \Psi(j) \;</math>, а из леммы 1 – что <math>\hat{s}[\Psi(h)] = \hat{s}[\Psi(j)] = c \;</math>. Следовательно, количество символов c, предшествующих F[j] в F, совпадает с количеством символов c, предшествующих <math>\hat{s}[\Psi(j)] \;</math> в <math>\hat{s}</math> (аналогичная ситуация имеет место для последущих символов), из чего следует справедливость формулировки леммы. □

На рис. 1 имеет место <math>\Psi(2) = 7 \;</math>, и <math>F[2] \;</math> и <math>\hat{s}[7] \;</math> занимают вторую позицию в соответствующих строках. Это свойство обычно формулируется так: соответствующие символы имеют один и тот же относительный порядок в строках F и <math>\hat{s}</math>.

'''Лемма 4. Для любого i значение <math>\POsi(i) \;</math> может быть вычислено из <math>\hat{s} = bwt(s) \;</math>.'''

Доказательство. Получить F можно в результате простой алфавитной сортировки символов <math>\hat{s} \;</math>. Затем вычислим <math>\Psi(i) \;</math> следующим образом: (1) положим с = F[i]; (2) вычислим <math>\ell \;</math>, такое, что F[i] является <math>\ell</math>-м вхождением c в F; (3) возвратим индекс <math>\ell</math>-го вхождения c в <math>\hat{s} \;</math>. □