This 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.
Using the null character as the end of file marker, and using
s + s to construct the ith rotation of
s, the forward transform takes the last character of each of the sorted rows:
The inverse transform repeatedly inserts
r as the left column of the table and sorts the table. After the whole table is built, it returns the row that ends with null, minus the null.
Here is another, more efficient method for the inverse transform. Although more complex, it increases the speed greatly when decoding lengthy strings.def ibwt(r, *args): "Inverse Burrows-Wheeler transform. args is the original index if it was not indicated by a null byte" firstCol = "".join(sorted(r)) count = *256 byteStart = *256 output = * len(r) shortcut = *len(r) #Generates shortcut lists for i in range(len(r)): shortcutIndex = ord(r) shortcut = count count += 1 shortcutIndex = ord(firstCol) if byteStart == -1: byteStart = i localIndex = (r.index("x00") if not args else args) for i in range(len(r)): #takes the next index indicated by the transformation vector nextByte = r output = nextByte shortcutIndex = ord(nextByte) #assigns localIndex to the next index in the transformation vector localIndex = byteStart + shortcut return "".join(output).rstrip("x00")
Read more about this topic: Burrows–Wheeler Transform
Other articles related to "sample implementation, implementation":
... C implementation #include #include #define NODES 6 #define MIN(X,Y) X < Y ? X Y #define INFINITE 10000000 void push(const int **C, int **F, int *excess, int u. 0 # start from front of list else p += 1 return sum(F) Note that the above implementation is not very efficient ...
Famous quotes containing the word sample:
“All that a city will ever allow you is an angle on itan oblique, indirect sample of what it contains, or what passes through it; a point of view.”
—Peter Conrad (b. 1948)