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
    t = '$' # start with rightmost character
    while bw[rowi] != '$':
        c = bw[rowi]
        t = c + t # prepend to answer
        # jump to row that starts with c of same rank
        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$'