Burrows-Wheeler transform in Python

def bwt(s):
  s = s + '\0'
  return ''.join([x[-1] for x in
         sorted([s[i:] + s[:i] for i in range(len(s))])])

def ibwt(s):
  L = [''] * len(s)
  for i in range(len(s)):
    L = sorted([s[i] + L[i] for i in range(len(s))])
  return [x for x in L if x.endswith('\0')][0][:-1]

The Burrows-Wheeler transform [1] is an invertible mathematical transformation which tends to clump related sequences of data together; hence it is useful as a pre-pass for some compression algorithms. The BWT domain in the above code excludes the null character; to include the null character, modify the transformation to also output the row of sorted([s[i:] + s[:i]...]) on which s occurs, then in IBWT simply return this row after the for loop. The Python code above is not particularly fast.