Given the string T = abracadabra$: 0123456789AB abracadabra$ C is the array mapping every symbol to the number of symbols in T that preceed it in alphabetical order: C $ 0 a 1 b 6 c 8 d 9 r 10 ============================== Computing LF from BWT only requires a simple computation. The column SA is NOT necessary and it does not need to be stored. BWT SA SA LF[i]= C[c] + Rank_c(BWT,i) where c=BWT[i] 0 a $ B 1 = 1 + 0 1 r a$ A A = A + 0 2 d abra$ 7 9 = 9 + 0 i.e. SA[9]=6=dabra$ 3 $ abracadabra$ 0 0 = 0 + 0 preceeds SA[2]=7= abra$ 4 r acadabra$ 3 B = A + 1 5 c adabra$ 5 8 = 8 + 0 6 a bra$ 8 2 = 1 + 1 7 a bracadabra$ 1 3 = 1 + 2 8 a cadabra$ 4 4 = 1 + 3 9 a dabra$ 6 5 = 1 + 4 A b ra$ 9 6 = 6 + 0 B b racadabra$ 2 7 = 6 + 1 ============================== Let's rebuild T from BWT. We start from i s.t. BWT[i]=$ and follow the LF chain, rebuilding T from last to front. BWT[i] i LF[i] $ 3 0 a 0 1 r 1 A b A 6 a 6 2 d 2 9 a 9 5 c 5 8 a 8 4 r 4 B b B 7 a 7 3 $ 3 ============================== The PSI function is also the result of an easy computation. C $ 0 a 1 b 6 c 8 d 9 r 10 Select_c(S,i) returns the index j such that S[j]=c and it is the i-th occurrence of c (0-based: the first occurrence is the 0-th). BWT SA SA PSI[i]= Select_c(BWT,r-C[c]) where i \in [C[c],C[c+1]) 0 a $ B 3 = Select_$(BWT,0-0) 0 \in [0,1) => c=$ 1 r a$ A = 2 d abra$ 7 = 3 $ abracadabra$ 0 = 4 r acadabra$ 3 8 = Select_a(BWT,4-1) 4 \in [1,6) => c=a 5 c adabra$ 5 = i.e. SA[4]=3=acadabra$ 6 a bra$ 8 = preceeds SA[8]=4=cadabra$ 7 a bracadabra$ 1 = 8 a cadabra$ 4 = 9 a dabra$ 6 = A b ra$ 9 = B b racadabra$ 2 =