Burrows-Wheeler Transform (버로우스-휠러 변환)

BWT는 bzip2에서 사용되는 알고리즘 중 하나이다. 비슷한 단어(패턴)이 많다는 점에 착안하여 그것들을 모음으로써 run length encoding을 사용할 수 있게끔 해준다.

 

예를들어 'very_very_very_very_long'이라는 문장에 BWT를 적용한다면 'gyyyyvvvvn_oleeee___$rrrr'가 되며 run length encoding을 적용하게 되면 'g4y4vn_ol4e3_$4r'이 된다.

 

변환 과정은

https://ko.wikipedia.org/wiki/%EB%B2%84%EB%A1%9C%EC%9A%B0%EC%A6%88-%ED%9C%A0%EB%9F%AC_%EB%B3%80%ED%99%98

버로우즈-휠러 변환 - 위키백과, 우리 모두의 백과사전

를 참고하기 바란다.