BWT (figure 3.1)

simple_BWT.py

# -*- coding: utf-8 -*-

if __name__ == '__main__':
    T = "abracadabra$"
    lT = len(T)
    print("Input:", T)

    sa = [T[i:] for i in range(lT)]
    isa = list(zip(range(lT), sa))
    sorted_isa = sorted(isa, key=lambda x: x[1])
    iSA = [x[0] for x in sorted_isa]
    wSA = [x[1] for x in sorted_isa]
    print(iSA)
    print(wSA)

    # compute BWT
    # TB[i] = T[SA[i] - 1] SA[i] > 0
    #       = T[n-1]       SA[i] = 0
    TB = ""
    for i in range(lT):
        if iSA[i] == 0:
            TB += T[lT - 1]
        else:
            TB += T[iSA[i] - 1]
    print("TB:", TB)