Burrows–Wheeler transform: Difference between revisions
Add source attribution, move Python specific verbiage to Python entry
Thundergnat (talk | contribs) m (Thundergnat moved page BWT to Burrows–Wheeler transform: Name is ambiguous, gwnerally we try to avoid TLAs in titles) |
Thundergnat (talk | contribs) (Add source attribution, move Python specific verbiage to Python entry) |
||
Line 1:
{{draft task}}
{{draft task}}The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding. More importantly, the transformation is reversible, without needing to store any additional data. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation.▼
▲
Source: [[wp:Burrows–Wheeler_transform|Burrows–Wheeler transform]]
▲https://en.wikipedia.org/wiki/Burrows–Wheeler_transform
=={{header|Python}}==▼
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 STX/ETX control codes to mark the start and end of the text, and using s[i:] + s[:i] 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 ETX, minus the STX and ETX.
▲=={{header|Python}}==
<lang Python>
| |||