In [1]:
def rotations(t):
# Return list of rotations of input string t
tt = t * 2
return [ tt[i:i+len(t)] for i in range(len(t)) ]
In [2]:
rotations('cat')
Out[2]:
In [3]:
def bwm(t):
# Return lexicographically sorted list of t’s rotations
return sorted(rotations(t))
In [4]:
bwm('abaaba$')
Out[4]:
In [5]:
print('\n'.join(bwm('abaaba$')))
In [6]:
def bwtViaBwm(t):
# Given T, returns BWT(T) by way of the BWM
return ''.join(map(lambda x: x[-1], bwm(t)))
In [7]:
bwtViaBwm('abaaba$') # we can see the result equals the last column of the matrix above
Out[7]:
In [8]:
def suffixArray(s):
satups = sorted([(s[i:], i) for i in range(len(s))])
return map(lambda x: x[1], satups)
def bwtViaSa(t):
# Given T, returns BWT(T) by way of the suffix array
bw = []
for si in suffixArray(t):
if si == 0:
bw.append('$')
else:
bw.append(t[si-1])
return ''.join(bw) # return string-ized version of list bw
In [9]:
bwtViaBwm('abaaba$'), bwtViaSa('abaaba$') # same result
Out[9]: