Burrows-Wheeler Transform

in STEMGeekslast year

Introduction
Many communication and storage technologies rely on data compression to increase throughput or apparent storage capacity. Data compression is a way to reduce the size of data by taking advantage of patterns in the data, at the cost of additional processing power using compression and decompression algorithms. There are two types of compression, lossless and lossy. The former retains all essential information while the latter removes information the algoritm deems unnecessary.

Some types of data are often not suited to compression because the raw structure of the data contains few patterns that algorithms can take advantage of. This is the case for text and sometimes executable code. To effectively compress these types of data they need to first be transformed into something better suited to compression. One method to accomplish this transformation is known as a Burrows-Wheeler Transform (BWT), presented in the video below, and further covered in another example following the video.


BWT example using "mississippi"
BWT_00.png

BWT_01.png

BWT_02.png

BWT_03.png

BWT_04.png

BWT_05.png

BWT_06.png

BWT_07.png

BWT_08.png

BWT_09.png

Posted with STEMGeeks