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

基于上述的BWT变换过程，以字符串“banana”为例，我们得到了变换结果“annb$aa”。其还原过程见以下过程：
1 基于原字符串矩阵的最后一列为“annb$aa”，我们进行该列进行排序，得到“$aaabnn”,并将其作为还原矩阵的第一列
| Burrows–Wheeler 还原过程 1> 输入 | Burrows–Wheeler 还原过程 1> 转移 | Burrows–Wheeler 还原过程 1> 排序 | Burrows–Wheeler 还原过程 1> 组合 | Burrows–Wheeler 还原过程 1>  | Burrows–Wheeler 还原过程 1>  |
| --- | --- | --- | --- | --- | --- |
|  - - - - - - a  - - - - - - n  - - - - - - n  - - - - - - b  - - - - - - $  - - - - - - a  - - - - - - a  |  a - - - - - -  n - - - - - -  n - - - - - -  b - - - - - -  $ - - - - - -  a - - - - - -  a - - - - - -  |  $ - - - - - -  a - - - - - -  a - - - - - -  a - - - - - -  b - - - - - -  n - - - - - -  n - - - - - -  |  $ - - - - - a  a - - - - - n  a - - - - - n  a - - - - - b  b - - - - - $  n - - - - - a  n - - - - - a  |  |  |
2 经过1.1的转移、排序和组合，我们得到了7对邻接字符串：<a$> <na> <na> <ba> <$b> <an> <an>，将这7对邻接字符串进行排序后，得到<$b> <a$> <an> <an> <ba> <na> <na>，由此，我们得到了还原矩阵的第二列“b$nnaaa”
| Burrows–Wheeler 还原过程 2> 输入 | Burrows–Wheeler 还原过程 2> 转移 | Burrows–Wheeler 还原过程 2> 排序 | Burrows–Wheeler 还原过程 2> 组合 | Burrows–Wheeler 还原过程 2>  | Burrows–Wheeler 还原过程 2>  |
| --- | --- | --- | --- | --- | --- |
|  $ - - - - - a  a - - - - - n  a - - - - - n  a - - - - - b  b - - - - - $  n - - - - - a  n - - - - - a  |  a $ - - - - -  n a - - - - -  n a - - - - -  b a - - - - -  $ b - - - - -  a n - - - - -  a n - - - - -  |  $ b - - - - -  a $ - - - - -  a n - - - - -  a n - - - - -  b a - - - - -  n a - - - - -  n a - - - - -  |  $ b - - - - a  a $ - - - - n  a n - - - - n  a n - - - - b  b a - - - - $  n a - - - - a  n a - - - - a  |  |  |
3 经过1.2的转移、排序和组合，我们得到了7对邻接字符串：<a$b> <na$> <nan> <ban> <$ba> <ana> <ana>，将这7对邻接字符串进行排序后，得到<$ba> <a$b> <ana> <ana> <ban> <na$> <nan>，由此，我们得到了还原矩阵的第三列“abaan$n”
| Burrows–Wheeler 还原过程 3> 输入 | Burrows–Wheeler 还原过程 3> 转移 | Burrows–Wheeler 还原过程 3> 排序 | Burrows–Wheeler 还原过程 3> 组合 | Burrows–Wheeler 还原过程 3>  | Burrows–Wheeler 还原过程 3>  |
| --- | --- | --- | --- | --- | --- |
|  $ b - - - - a  a $ - - - - n  a n - - - - n  a n - - - - b  b a - - - - $  n a - - - - a  n a - - - - a  |  a $ b - - - -  n a $ - - - -  n a n - - - -  b a n - - - -  $ b a - - - -  a n a - - - -  a n a - - - -  |  $ b a - - - -  a $ b - - - -  a n a - - - -  a n a - - - -  b a n - - - -  n a $ - - - -  n a n - - - -  |  $ b a - - - a  a $ b - - - n  a n a - - - n  a n a - - - b  b a n - - - $  n a $ - - - a  n a n - - - a  |  |  |
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”
| Burrows–Wheeler 还原过程 4> 输入 | Burrows–Wheeler 还原过程 4> 转移 | Burrows–Wheeler 还原过程 4> 排序 | Burrows–Wheeler 还原过程 4> 组合 | Burrows–Wheeler 还原过程 4>  | Burrows–Wheeler 还原过程 4>  |
| --- | --- | --- | --- | --- | --- |
|  $ b a - - - a  a $ b - - - n  a n a - - - n  a n a - - - b  b a n - - - $  n a $ - - - a  n a n - - - a  |  a $ b a - - -  n a $ b - - -  n a n a - - -  b a n a - - -  $ b a n - - -  a n a $ - - -  a n a n - - -  |  $ b a n - - -  a $ b a - - -  a n a $ - - -  a n a n - - -  b a n a - - -  n a $ b - - -  n a n a - - -  |  $ b a n - - a  a $ b a - - n  a n a $ - - n  a n a n - - b  b a n a - - $  n a $ b - - a  n a n a - - a  |  |  |
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$”
| Burrows–Wheeler 还原过程 5> 输入 | Burrows–Wheeler 还原过程 5> 转移 | Burrows–Wheeler 还原过程 5> 排序 | Burrows–Wheeler 还原过程 5> 组合 | Burrows–Wheeler 还原过程 5>  | Burrows–Wheeler 还原过程 5>  |
| --- | --- | --- | --- | --- | --- |
|  $ b a n - - a  a $ b a - - n  a n a $ - - n  a n a n - - b  b a n a - - $  n a $ b - - a  n a n a - - a  |  a $ b a n - -  n a $ b a - -  n a n a $ - -  b a n a n - -  $ b a n a - -  a n a $ b - -  a n a n a - -  |  $ b a n a - -  a $ b a n - -  a n a $ b - -  a n a n a - -  b a n a n - -  n a $ b a - -  n a n a $ - -  |  $ b a n a - a  a $ b a n - n  a n a $ b - n  a n a n a - b  b a n a n - $  n a $ b a - a  n a n a $ - a  |  |  |
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”。
| Burrows–Wheeler 还原过程 5> 输入 | Burrows–Wheeler 还原过程 5> 转移 | Burrows–Wheeler 还原过程 5> 排序 | Burrows–Wheeler 还原过程 5> 组合 | Burrows–Wheeler 还原过程 5>  | Burrows–Wheeler 还原过程 5>  |
| --- | --- | --- | --- | --- | --- |
|  $ b a n a - a  a $ b a n - n  a n a $ b - n  a n a n a - b  b a n a n - $  n a $ b a - a  n a n a $ - a  |  a $ b a n a -  n a $ b a n -  n a n a $ b -  b a n a n a -  $ b a n a n -  a n a $ b a -  a n a n a $ -  |  $ b a n a n -  a $ b a n a -  a n a $ b a -  a n a n a $ -  b a n a n a -  n a $ b a n -  n a n a $ b -  |  $ b a n a n a  a $ b a n a n  a n a $ b a n  a n a n a $ b  b a n a n a $  n a $ b a n a  n a n a $ b a  |  |  |
经过六次排序转移与组合，还原出了原有的字符串即“$banana”。