Editing Burrows–Wheeler transform (section)

{{Short description|Algorithm used in data compression}}
{{Infobox algorithm
| name = Burrows–Wheeler transform
| class = preprocessing for lossless compression
| time = ''O''(''n'')
| space = ''O''(''n'')
| data = string
}}
The '''Burrows–Wheeler transform''' ('''BWT''') rearranges a [[character string (computer science)|character string]] into runs of similar characters, in a manner that can be reversed to recover the original string. Since [[data compression|compression]] techniques such as [[move-to-front transform]] and [[run-length encoding]] are more effective when such runs are present, the BWT can be used as a preparatory step to improve the efficiency of a compression algorithm, and is used this way in software such as [[bzip2]]. The  algorithm can be implemented efficiently using a [[suffix array]] thus reaching linear time complexity.

It was invented by [[David Wheeler (computer scientist)|David Wheeler]] in 1983, and later published by him and [[Michael Burrows (computer scientist)|Michael Burrows]] in 1994. Their paper included a compression algorithm, called the '''Block-sorting Lossless Data Compression Algorithm''' or '''BSLDCA''', that compresses data by using the BWT followed by move-to-front coding and [[Huffman coding]] or [[arithmetic coding]].<ref name=Burrows1994>{{citation
 | first1 = Michael
 | last1 = Burrows
 | author-link1= Michael Burrows (computer scientist)
 | first2 = David J.
 | last2 = Wheeler
 | author-link2= David Wheeler (British computer scientist)
 | title=A block sorting lossless data compression algorithm
 | publisher=Technical Report 124, Digital Equipment Corporation
 | date=May 10, 1994
 | url=https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html
 | url-status=dead
 | archiveurl=http://web.archive.org/web/20030105080431/https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html
 | archivedate=January 5, 2003
}}</ref><ref name="u822">{{cite conference | last=Arnavut | first=Z. | last2=Magliveras | first2=S.S. | title=Block sorting and compression | publisher=IEEE Comput. Soc. Press | date=1997 | isbn=978-0-8186-7761-8 | doi=10.1109/DCC.1997.582009 | url=https://ieeexplore.ieee.org/document/582009/ | access-date=2025-05-07 | page=181–190}}</ref>