Burrows Wheeler Transform

June 20, 2022 - Reading time: 3 minutes

In [1]: 


get_ipython().ast_node_interactivity = 'all'

import string

In [2]: 


import this

Out [1]: 


lipsum = """
Lorem ipsum dolor sit amet, consectetur
adipiscing elit. Nulla tempus convallis
accumsan. Suspendisse ac euismod lectus.
Class aptent taciti sociosqu ad litora
torquent per conubia nostra, per inceptos
himenaeos. Aliquam sit amet urna accumsan,
porttitor sem id, aliquam sapien. Morbi
ullamcorper erat eget auctor viverra.
Nam rutrum eget justo id fermentum. Proin
accumsan condimentum dolor, non bibendum
lorem placerat quis. Sed ultrices, nisl
non varius feugiat, purus eros faucibus
quam, vel laoreet quam turpis laoreet nibh.
Etiam tincidunt massa volutpat ligula
pharetra faucibus. Curabitur malesuada erat
orci, ac aliquet nibh vestibulum tincidunt.
Nulla gravida erat neque, tristique aliquet
erat egestas at. Vivamus tristique tristique
nisl, convallis faucibus nisi dignissim sed.
Cras id erat sed sapien rutrum imperdiet.
Maecenas vestibulum mi libero, non iaculis
nunc viverra sed. Donec massa felis, tincidunt
at ligula ut, ultrices pulvinar libero. Aenean
lectus ipsum, porta sit amet sapien quis, fermentum non.""".replace("\n", " ")

In [3]: 


alphabet = []

BEGIN = "(BEGIN)"
END = "(END)"

alphabet.append(BEGIN)
alphabet.append(END)

for letter in string.ascii_lowercase:
    alphabet.append(letter)

In [4]: 


def all_shifts(l):
    copy = list(l)

    while True:
        copy.insert(0, copy.pop())
        yield list(copy)

        if copy == l:
            return

In [5]: 


def bwt(symbols):
    result = []

    for perm in sorted(all_shifts(symbols)):
        result.append(perm[-1])

    return result

In [6]: 


msg = "BANANA|"
msg = list(msg)

bwt(msg)

Out [2]: 


['B', 'N', 'N', '|', 'A', 'A', 'A']

Let’s see if we can revert it.

In [7]: 


def ibwt(symbols, end=None):
    if not end:
        end = END
    results = []

    for _ in symbols:
        results.append([])

    for _ in symbols:
        for res, s in zip(results, symbols):
            res.insert(0, s)
        results.sort()

    for res in results:
        if res[-1] == end:
            return res

In [8]: 


ibwt("BNN|AAA", "|")

Out [3]: 


['B', 'A', 'N', 'A', 'N', 'A', '|']

In [9]: 


message = []

for c in "nana nana nana nana nana nana nana batmaaaan":
    message.append(c)

message.append(END)

"".join(message)

Out [4]: 


'nana nana nana nana nana nana nana batmaaaan(END)'

In [10]: 


message = bwt(message)

"".join(message)

Out [5]: 


'aaaaaaannnnnnnnmaaannnnnnnb taaaaaaaa      (END)a'

In [11]: 


message = ibwt(message)

"".join(message)

Out [6]: 


'nana nana nana nana nana nana nana batmaaaan(END)'

In [12]: 


lipsum[:70]
len(lipsum)

Out [7]: 


' Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla tempus'

Out [8]: 


['B', 'A', 'N', 'A', 'N', 'A', '|']
1026

In [13]: 


message = bwt(list(lipsum) + [END])
"".join(message)

Out [9]: 


'.......(END).........,enasur,ectttststnn,rs,immttmgtraadscssaa,dsasnsommrmstslndirttdmrctmttts,e,,lmastt,am,,s,tsntmntdmtmaramrita,mma,esmi,dtan,shcra.idtlssroamntsetmossdsdhtnattmsntn                 nddrslilrtlrlsrrr     lti u Mnm   vvNuuiuul   vsessllsss nhvtrnlmmrrp rrrri fff riiiiiru aiiiiiaaenaaaenaiiruuunnnsoa     meueeaccciioaeeieeiar nan  niiisuuuunnasllsSssrr   vf srrtiiimcpbAutmmmacnppp    c pffbb vvccgvvlgugueemmmirtf        neeeui iibbp smtbcb tgbllnnttcccrr   vcccpppddllshd ov tttccd  lltttllllplulupnnnudnrrrssslctlbrVvv esslulupl  C  a    aAaalluee uuuaaoo uuuuouuuueueuuueaaiaauauau   aiirraaa sieuuuaioaoaeeoaeaoreieuiiiioeeeo i     g     ouueeueeeo ootrrsmrddvnnnncDcccctltltM aaLlctpprteints r m aaari   iiae  msii  iiierii  ueeeauooootrotruCeeeeeegooeooooatttttaeeueePeouoeeoottu  isauuiouoauiuieuuaieiouuissmmm   isn    is   iii uoaaaiieeeiiiuoeppiiineaaeeaanaeeaneaeaneeaueniar s pciEss   ssstsici puesll   uurnnnei ccqsqqqqnaaaaqqqqqqqeqqeggcNN   bbpstrrdltlstcccndddttC tppritbbmtbSj lrrnni  ii  al   '

In [14]: 


message = ibwt(message)

"".join(message)

Out [10]: 


' Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nulla tempus convallis accumsan. Suspendisse ac euismod lectus. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Aliquam sit amet urna accumsan, porttitor sem id, aliquam sapien. Morbi ullamcorper erat eget auctor viverra. Nam rutrum eget justo id fermentum. Proin accumsan condimentum dolor, non bibendum lorem placerat quis. Sed ultrices, nisl non varius feugiat, purus eros faucibus quam, vel laoreet quam turpis laoreet nibh. Etiam tincidunt massa volutpat ligula pharetra faucibus. Curabitur malesuada erat orci, ac aliquet nibh vestibulum tincidunt. Nulla gravida erat neque, tristique aliquet erat egestas at. Vivamus tristique tristique nisl, convallis faucibus nisi dignissim sed. Cras id erat sed sapien rutrum imperdiet. Maecenas vestibulum mi libero, non iaculis nunc viverra sed. Donec massa felis, tincidunt at ligula ut, ultrices pulvinar libero. Aenean lectus ipsum, porta sit amet sapien quis, fermentum non.(END)'

Reaction :

Currently there are no comments, so be the first!