编辑“︁Burrows-Wheeler变换”︁（章节）

==Burrows–Wheeler变换的还原过程==

* 基于上述的BWT变换过程，以字符串“banana”为例，我们得到了变换结果“annb$aa”。其还原过程见以下过程：

# 1 基于原字符串矩阵的最后一列为“annb$aa”，我们进行该列进行排序，得到“$aaabnn”,并将其作为还原矩阵的第一列

{| class="wikitable"
|- style="width:500px"
!  colspan="6" | Burrows–Wheeler 还原过程 1
|- 
! 输入
! 转移
! 排序
! 组合
|-|
|
 - - - - - - a<br/>
 - - - - - - n<br/>
 - - - - - - n<br/>
 - - - - - - b<br/>
 - - - - - - $<br/>
 - - - - - - a<br/>
 - - - - - - a<br/>
|
 a - - - - - -<br/>
 n - - - - - -<br/>
 n - - - - - -<br/>
 b - - - - - -<br/>
 $ - - - - - -<br/>
 a - - - - - -<br/>
 a - - - - - -<br/>
|
 $ - - - - - -<br/>
 a - - - - - -<br/>
 a - - - - - -<br/>
 a - - - - - -<br/>
 b - - - - - -<br/>
 n - - - - - -<br/>
 n - - - - - -<br/>
|
 $ - - - - - a<br/>
 a - - - - - n<br/>
 a - - - - - n<br/>
 a - - - - - b<br/>
 b - - - - - $<br/>
 n - - - - - a<br/>
 n - - - - - a<br/>
|}

# 2 经过1.1的转移、排序和组合，我们得到了7对邻接字符串：<a$> <na> <na> <ba> <$b> <an> <an>，将这7对邻接字符串进行排序后，得到<$b> <a$> <an> <an> <ba> <na> <na>，由此，我们得到了还原矩阵的第二列“b$nnaaa”

{| class="wikitable"
|- style="width:500px"
!  colspan="6" | Burrows–Wheeler 还原过程 2
|- 
! 输入
! 转移
! 排序
! 组合
|-|
|
 $ - - - - - a<br/>
 a - - - - - n<br/>
 a - - - - - n<br/>
 a - - - - - b<br/>
 b - - - - - $<br/>
 n - - - - - a<br/>
 n - - - - - a<br/>
|
 a $ - - - - -<br/>
 n a - - - - -<br/>
 n a - - - - -<br/>
 b a - - - - -<br/>
 $ b - - - - -<br/>
 a n - - - - -<br/>
 a n - - - - -<br/>
|
 $ b - - - - -<br/>
 a $ - - - - -<br/>
 a n - - - - -<br/>
 a n - - - - -<br/>
 b a - - - - -<br/>
 n a - - - - -<br/>
 n a - - - - -<br/>

|
 $ b - - - - a<br/>
 a $ - - - - n<br/>
 a n - - - - n<br/>
 a n - - - - b<br/>
 b a - - - - $<br/>
 n a - - - - a<br/>
 n a - - - - a<br/>
|}

# 3 经过1.2的转移、排序和组合，我们得到了7对邻接字符串：<a$b> <na$> <nan> <ban> <$ba> <ana> <ana>，将这7对邻接字符串进行排序后，得到<$ba> <a$b> <ana> <ana> <ban> <na$> <nan>，由此，我们得到了还原矩阵的第三列“abaan$n”

{| class="wikitable"
|- style="width:500px"
!  colspan="6" | Burrows–Wheeler 还原过程 3
|- 
! 输入
! 转移
! 排序
! 组合
|-|
|
 $ b - - - - a<br/>
 a $ - - - - n<br/>
 a n - - - - n<br/>
 a n - - - - b<br/>
 b a - - - - $<br/>
 n a - - - - a<br/>
 n a - - - - a<br/>
|
 a $ b - - - -<br/>
 n a $ - - - -<br/>
 n a n - - - -<br/>
 b a n - - - -<br/>
 $ b a - - - -<br/>
 a n a - - - -<br/>
 a n a - - - -<br/>
|
 $ b a - - - -<br/>
 a $ b - - - -<br/>
 a n a - - - -<br/>
 a n a - - - -<br/>
 b a n - - - -<br/>
 n a $ - - - -<br/>
 n a n - - - -<br/>

|
 $ b a - - - a<br/>
 a $ b - - - n<br/>
 a n a - - - n<br/>
 a n a - - - b<br/>
 b a n - - - $<br/>
 n a $ - - - a<br/>
 n a n - - - a<br/>
|}

# 4 经过1.3的转移、排序和组合，我们得到了7对邻接字符串：<a$ba> <na$b> <nana> <bana> <$ban> <ana$> <anan>，将这7对邻接字符串进行排序后，得到<$ban> < a$ba > <ana$> < anan > < bana > < na$b > < nana >，由此，我们得到了还原矩阵的第四列“na$naba”

{| class="wikitable"
|- style="width:500px"
!  colspan="6" | Burrows–Wheeler 还原过程 4
|- 
! 输入
! 转移
! 排序
! 组合
|-|
|
 $ b a - - - a<br/>
 a $ b - - - n<br/>
 a n a - - - n<br/>
 a n a - - - b<br/>
 b a n - - - $<br/>
 n a $ - - - a<br/>
 n a n - - - a<br/>
|
 a $ b a - - -<br/>
 n a $ b - - -<br/>
 n a n a - - -<br/>
 b a n a - - -<br/>
 $ b a n - - -<br/>
 a n a $ - - -<br/>
 a n a n - - -<br/>
|
 $ b a n - - -<br/>
 a $ b a - - -<br/>
 a n a $ - - -<br/>
 a n a n - - -<br/>
 b a n a - - -<br/>
 n a $ b - - -<br/>
 n a n a - - -<br/>

|
 $ b a n - - a<br/>
 a $ b a - - n<br/>
 a n a $ - - n<br/>
 a n a n - - b<br/>
 b a n a - - $<br/>
 n a $ b - - a<br/>
 n a n a - - a<br/>
|}

# 5 经过1.4的转移、排序和组合，我们得到了7对邻接字符串：<a$ban> <na$ba> <nana$> <banan> <$bana> <ana$b> <anana>，将这7对邻接字符串进行排序后，得到<$bana> <a$ban> < ana$b > <anana> <banan> <na$ba> <nana$>，由此，我们得到了还原矩阵的第五列“anbana$”

{| class="wikitable"
|- style="width:500px"
!  colspan="6" | Burrows–Wheeler 还原过程 5
|- 
! 输入
! 转移
! 排序
! 组合
|-|
|
 $ b a n - - a<br/>
 a $ b a - - n<br/>
 a n a $ - - n<br/>
 a n a n - - b<br/>
 b a n a - - $<br/>
 n a $ b - - a<br/>
 n a n a - - a<br/>
|
 a $ b a n - -<br/>
 n a $ b a - -<br/>
 n a n a $ - -<br/>
 b a n a n - -<br/>
 $ b a n a - -<br/>
 a n a $ b - -<br/>
 a n a n a - -<br/>
|
 $ b a n a - -<br/>
 a $ b a n - -<br/>
 a n a $ b - -<br/>
 a n a n a - -<br/>
 b a n a n - -<br/>
 n a $ b a - -<br/>
 n a n a $ - -<br/>
|
 $ b a n a - a<br/>
 a $ b a n - n<br/>
 a n a $ b - n<br/>
 a n a n a - b<br/>
 b a n a n - $<br/>
 n a $ b a - a<br/>
 n a n a $ - a<br/>
|}

# 6 经过1.5的转移、排序和组合，我们得到了7对邻接字符串：<a$bana> <na$ban> <nana$b> <banaan> <$banan> <ana$ba> <anana$>，将这7对邻接字符串进行排序后，得到<$banan> <a$bana> < ana$ba> <anana$> <banana> <na$ban> <nana$b>，由此，我们得到了还原矩阵的第六列“naa$anb”。

{| class="wikitable"
|- style="width:500px"
!  colspan="6" | Burrows–Wheeler 还原过程 5
|- 
! 输入
! 转移
! 排序
! 组合
|-|
|
 $ b a n a - a<br/>
 a $ b a n - n<br/>
 a n a $ b - n<br/>
 a n a n a - b<br/>
 b a n a n - $<br/>
 n a $ b a - a<br/>
 n a n a $ - a<br/>
|
 a $ b a n a -<br/>
 n a $ b a n -<br/>
 n a n a $ b -<br/>
 b a n a n a -<br/>
 $ b a n a n -<br/>
 a n a $ b a -<br/>
 a n a n a $ -<br/>
|
 $ b a n a n -<br/>
 a $ b a n a -<br/>
 a n a $ b a -<br/>
 a n a n a $ -<br/>
 b a n a n a -<br/>
 n a $ b a n -<br/>
 n a n a $ b -<br/>
|
 $ b a n a n a<br/>
 a $ b a n a n<br/>
 a n a $ b a n<br/>
 a n a n a $ b<br/>
 b a n a n a $<br/>
 n a $ b a n a<br/>
 n a n a $ b a<br/>
|}

经过六次排序转移与组合，还原出了原有的字符串即“$banana”。