Burrows–Wheeler transform: Difference between revisions

Revision as of 15:17, 8 April 2025

Revision as of 10:28, 23 April 2025

Line 7:

| data = string

}}

The '''Burrows–Wheeler transform''' ('''BWT''', also called '''block-sorting compression''') rearranges a [[character string (computer science)|character string]] into runs of similar characters. This is useful for [[data compression|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 except the position of the first original character. The BWT iscan thus be used as a "free" methodpreparatory ofstep improvingto improve the efficiency of a text compression algorithmsalgorithm, costing only some extraadditional computation., The Burrows–Wheeler transformand is an [[algorithm]] used tothis prepareway datain for use with [[data compression]] techniquessoftware such as [[bzip2]].

It was invented by [[Michael Burrows (computer scientist)|Michael Burrows]] and [[David Wheeler (computer scientist)|David Wheeler]] in 1994 while Burrows was working at [[DEC Systems Research Center]] in [[Palo Alto]], California. It is based on a previously unpublished transformation discovered by Wheeler in 1983. The algorithm can be implemented efficiently using a [[suffix array]] thus reaching linear time complexity.<ref name=Burrows1994>{{citation

| first1 = Michael

| last1 = Burrows