Burrows-Wheeler Transform

字串 london 經過 BWT 會得到2 個資訊(nnoold 與 index=1),而由這2個資訊可以再還原回原始資訊 london
---
<rots>
london
ondonl
ndonlo
donlon
onlond
nlondo

<sort>
F     L
donlon
london <
ndonlo
nlondo
ondonl
onlond

得到2個資訊 nnoold 與 index=1
============================
還原 (nnoold 與 index=1)
<sort>
dlnnoo


d     n < n的下一個字元為d
l      n < n的下一個字元為l <--index=1
n     o < o的下一個字元為n
n     o < o的下一個字元為n
o     l < l的下一個字元為o
o     d < d的下一個字元為o

step1:l的下一個字元為o
lo    n
step2:o的下一個字元為n
lon   n
step3:n的下一個字元為d
lond  n
step4:d的下一個字元為o
london <--得到還原後的資訊

相關連結:
(Research Blog of 穆信成 Shin-Cheng Mu)Inverting the Burrows-Wheeler transform
(Mark Nelson Programming, mostly.)Data Compression with the Burrows-Wheeler Transform
(wiki)Burrows-Wheeler transform