# CG_BWT_Reverse

``````

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(0, len(t)) ]

def bwm(t):
''' Return lexicographically sorted list of t’s rotations '''
return sorted(rotations(t))

def bwtViaBwm(t):
''' Given T, returns BWT(T) by way of the BWM '''
return ''.join(map(lambda x: x[-1], bwm(t)))

``````
``````

In [2]:

t = 'abaaba\$'
b = bwtViaBwm(t)
b

``````
``````

Out[2]:

'abba\$aa'

``````
``````

In [3]:

def rankBwt(bw):
''' Given BWT string bw, return parallel list of B-ranks.  Also
returns tots: map from character to # times it appears. '''
tots = dict()
ranks = []
for c in bw:
if c not in tots:
tots[c] = 0
ranks.append(tots[c])
tots[c] += 1
return ranks, tots

``````
``````

In [4]:

ranks, tots = rankBwt(b)
print zip(b, ranks) # print characters of BWT(T) in order, along with rank

``````
``````

[('a', 0), ('b', 0), ('b', 1), ('a', 1), ('\$', 0), ('a', 2), ('a', 3)]

``````
``````

In [5]:

def firstCol(tots):
''' Return map from character to the range of rows prefixed by
the character. '''
first = {}
totc = 0
for c, count in sorted(tots.iteritems()):
first[c] = (totc, totc + count)
totc += count
return first

``````
``````

In [6]:

firstCol(tots)

``````
``````

Out[6]:

{'\$': (0, 1), 'a': (1, 5), 'b': (5, 7)}

``````
``````

In [7]:

# confirm that the representation of the first column above is sensible
print('\n'.join(bwm(t)))

``````
``````

\$abaaba
a\$abaab
aaba\$ab
aba\$aba
abaaba\$
ba\$abaa
baaba\$a

``````
``````

In [8]:

def reverseBwt(bw):
''' Make T from BWT(T) '''
ranks, tots = rankBwt(bw)
first = firstCol(tots)
rowi = 0 # start in first row
while bw[rowi] != '\$':
c = bw[rowi]
t = c + t # prepend to answer
rowi = first[c][0] + ranks[rowi]
return t

``````
``````

In [9]:

reverseBwt(b)

``````
``````

Out[9]:

'abaaba\$'

``````
``````

In [10]:

reverseBwt(bwtViaBwm('In_the_jingle_jangle_morning\$'))

``````
``````

Out[10]:

'In_the_jingle_jangle_morning\$'

``````