Editing Burrows–Wheeler transform (section)

==Sample implementation==
This [[Python (programming language)|Python]] implementation sacrifices speed for simplicity: the program is short, but takes more than the linear time that would be desired in a practical implementation. It essentially does what the pseudocode section does.

Using the [[C0 and C1 control codes#STX|STX/ETX control codes]] to mark the start and end of the text, and using <code>s[i:] + s[:i]</code> to construct the <code>i</code>th rotation of <code>s</code>, the forward transform takes the last character of each of the sorted rows:

<syntaxhighlight lang="python">
from curses.ascii import STX, ETX

def bwt(s: str, start=chr(STX), end=chr(ETX)) -> str:
    r"""
    Apply Burrows–Wheeler transform to input string.

    >>> bwt('BANANA')
    '\x03ANNB\x02AA'
    >>> bwt('BANANA', start='^', end='$')
    'ANNB^AA$'
    >>> bwt('BANANA', start='%', end='$')
    'A$NNB%AA'
    """
    assert (
        start not in s and end not in s
    ), "Input string cannot contain STX and ETX characters"
    s = f"{start}{s}{end}"  # Add start and end of text marker

    # Table of rotations of string
    table = sorted(f"{s[i:]}{s[:i]}" for i, c in enumerate(s))
    last_column = [row[-1:] for row in table]  # Last characters of each row
    return "".join(last_column)  # Convert list of characters into string
</syntaxhighlight>

The inverse transform repeatedly inserts <code>r</code> as the left column of the table and sorts the table.  After the whole table is built, it returns the row that ends with ETX, minus the STX and ETX.

<syntaxhighlight lang="python">
def inverse_bwt(r: str, start=chr(STX), end=chr(ETX)) -> str:
    r"""
    Apply inverse Burrows–Wheeler transform.

    >>> inverse_bwt('\x03ANNB\x02AA')
    'BANANA'
    >>> inverse_bwt('ANNB^AA$', start='^', end='$')
    'BANANA'
    >>> inverse_bwt('A$NNB%AA', start='%', end='$')
    'BANANA'
    """
    str_len = len(r)
    table = [""] * str_len  # Make empty table
    for _ in range(str_len):
        table = sorted(rc + tc for rc, tc in zip(r, table))  # Add a column of r

    # Iterate over and check whether last character ends with ETX or not
    s = next((row for row in table if row.endswith(end)), "")

    # Retrieve data from array and get rid of start and end markers
    return s.rstrip(end).strip(start)
</syntaxhighlight>

Following implementation notes from Manzini, it is equivalent to use a simple [[null character]] suffix instead. The sorting should be done in [[colexicographic order]] (string read right-to-left), i.e. {{code|2=python|1=sorted(..., key=lambda s: s[::-1])}} in Python.<ref name=Manzini/> (The above control codes actually fail to satisfy EOF being the last character; the two codes are actually the ''first''. The rotation holds nevertheless.)