Test Burrows Wheeler Transform (BWT)¶

This is a simple notebook to test the implementation of the BWT.

In [1]:

from Burrows_Wheeler_Transform import transform
from Burrows_Wheeler_Transform import inverse
import time

first we test the correctness of the implementation using some known BWT

In [2]:

finalString = transform('Banana')
if finalString == 'a$nnBaa':
    print('The BWT of the string Banana is: %s' %(finalString))
    

finalString = transform('mississippi')

if finalString == 'ipssm$pissii':
    print('The BWT of the string mississippi is: %s' %(finalString))
    

The BWT of the string Banana is: a$nnBaa
The BWT of the string mississippi is: ipssm$pissii

Now that we have thast the correctness of the implementation we will test the speed of this implementation, in particular we are interesting in smoothly handle string with 1000 characters.

In [3]:

with open('TestSample/oneThousandChar.txt') as file:
    oneChar = file.read().replace('\n', '')

with open('TestSample/twoThousandChar.txt') as file:
    twoChar = file.read().replace('\n', '')

with open('TestSample/twelveThousandChar.txt') as file:
    twelveChar = file.read().replace('\n', '')
    
with open('TestSample/twentyFourChar.txt') as file:
    twentyFourChar = file.read().replace('\n', '')

In [4]:

start_time = time.time()
finalString = transform(oneChar)
end_time = time.time()
print("Execution time BWT of the one thousand characters string: %s seconds" % (end_time - start_time))


start_time = time.time()
inverseTransf = inverse(finalString)
end_time = time.time()

print("Execution time IBWT of the one thousand characters string: %s seconds" % (end_time - start_time))

Execution time for the transform of the one thousand characters string is: 0.014513969421386719 seconds
Execution time for the inverse of the one thousand characters string is: 0.020147085189819336 seconds

In [5]:

start_time = time.time()
finalString = transform(twoChar)
end_time = time.time()
print("Execution time BWT of the two thousand characters: %s seconds" % (end_time - start_time))


start_time = time.time()
inverseTransf = inverse(finalString)
end_time = time.time()

print("Execution time IBWT of the two thousand characters: %s seconds" % (end_time - start_time))

Execution time for the transform of the two thousand characters string is: 0.05203890800476074 seconds
Execution time for the inverse of the two thousand characters string is: 0.05255603790283203 seconds

In [6]:

start_time = time.time()
finalString = transform(twelveChar)
end_time = time.time()
print("Execution time BWT of the twelve thousand characters: %s seconds" % (end_time - start_time))


start_time = time.time()
inverseTransf = inverse(finalString)
end_time = time.time()

print("Execution time IBWT of the twelve thousand characters: %s seconds" % (end_time - start_time))

Execution time for the transform of the twelve thousand characters string is: 1.6825170516967773 seconds
Execution time for the inverse of the twelve thousand characters string is: 1.6775963306427002 seconds

In [7]:

start_time = time.time()
finalString = transform(twentyFourChar)
end_time = time.time()
print("Execution time BWT of the twenty-four thousand characters: %s seconds" % (end_time - start_time))


start_time = time.time()
inverseTransf = inverse(finalString)
end_time = time.time()

print("Execution time IBWT of the twenty-four thousand characters: %s seconds" % (end_time - start_time))

Execution time for the transform of the twenty-four thousand characters string is: 1.7439227104187012 seconds
Execution time for the inverse of the twenty-four thousand characters string is: 1.5500197410583496 seconds

In [ ]: