Burrows-Wheeler Transform
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.
