4551
правка
Преобразование Барроуза-Уилера: различия между версиями
Материал из WEGA
Преобразование Барроуза-Уилера (посмотреть исходный код)
Версия от 13:48, 24 января 2017
, 24 января 2017→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 153: | Строка 153: | ||
{| class="wikitable" | |||
! Процедура sa2bwt !! Процедура bwt2psi !! Процедура psi2text | |||
|- | |||
| 1. bwt[0]=s[n-1]; | |||
| 1. for(i=0;i<=n;i++) | |||
| 1. k = j0; i = 0; | |||
|- | |||
| 2. for(i=1;i<=n;i++) | |||
| 2. c = bwt[i]; | |||
| 2. do | |||
|- | |||
| 3. if(sa[i] == 1) | |||
| 3. if(c == '$') | |||
| 3. k = psi[k] ; | |||
|- | |||
| 4. bwt[i]='$'; | |||
| 4. j0 = i; | |||
| 4. s[i++] = bwt[k]; | |||
|- | |||
| 5. else | |||
| 5. else | |||
| while(i<n); | |||
|- | |||
| 6. bwt[i]=s[sa[i]-1]; | |||
| 6. h = count[c]++; | |||
| | |||
|- | |||
| | |||
| 7. psi[h]=i; | |||
| | |||
|} | |||
Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение (?, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива [1, |27|], который изначально содержит в позиции count [i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения j0 | |||
Рисунок 2. Алгоритмы для вычисления и обращения преобразования Барроуза-Уилера. Процедура sa2bwt вычисляет bwt(s) для исходной строки s и ее суффиксный массив sa. Процедура bwt2psi принимает на вход bwt(s) и вычисляет отображение (?, сохраняя его в массиве psi. bwt2psi ткже сохраняет в j0 индекс строки, префиксом которой является s[0, n - 1]. bwt2psi использует дополнительный счетчик массива [1, |27|], который изначально содержит в позиции count [i] количество вхождений в bwt(s) символов 1, ..., i - 1. Наконец, процедура psi2text восстанавливает строки при наличии bwt(s), массива psi и значения j0 | |||
