How to improve Burrows-Wheeler Transform performance?

Question

I have implemented the Burrows-Wheeler Transform as below:

eofChar = FromCharacterCode[255];

BurrowsWheelerTransform[string_] :=
 With[{s = string <> eofChar},
  StringJoin @@ (StringPart[#, -1] & /@ Sort[NestList[
       StringRotateLeft[#, 1] &, s, StringLength[s] - 1]
      , LexicographicOrder])]

InverseBurrowsWheelerTransform[string_] :=
 With[{len = StringLength[string], c = Characters[string]},
  StringJoin @@ Most[SelectFirst[Nest[
      SortBy[Transpose[Prepend[Transpose[#], c]], 
        s |-> StringJoin @@ s, LexicographicOrder] &, {}, 
      len], #[[-1]] == eofChar &]]
  ]

bwt = BurrowsWheelerTransform["swiss miss is on a mission to mississippi"]
(*"nssaosn ss mwmsmp   oot ipississsiiiiiÿ si"*)

InverseBurrowsWheelerTransform[bwt]
(*"swiss miss is on a mission to mississippi"*)

However, this implementation is very slow for larger strings especially in the inverse transform. I suspect this is due to all this Transpose business with column insertion. Is there a better way to implement this?