버로우즈-휠러 변환

버로우즈-휠러 변환(BWT, Burrows-Wheeler transform) 또는 블록 정렬 알고리즘은 데이터 압축에 관련된 알고리즘으로, 1994년에 마이클 버로우즈와 데이비드 휠러가 개발하였다.

버로우즈-휠러 변환은 직접적으로 압축을 수행하는 알고리즘은 아니며, 변환을 거친 데이터의 크기는 변하지 않는다. 하지만 원본 데이터에 중복되는 글자가 많이 있다면, 변환 과정을 거친 결과물에는 중복되는 글자가 비슷한 위치에 몰리게 된다. 버로우즈-휠러 변환은 가역 변환이기 때문에 주로 실제 압축 알고리즘을 적용하기 전에 적용하는 경우가 많다. 이 알고리즘을 쓰는 대표적인 압축 포맷으로 bzip2가 있다.

예제

압축 과정

입력된 문자열을 가능한 모든 회전 이동(cyclic shift)을 한 뒤, 이것들을 사전순으로 정렬한다. 이 결과를 나열한 행렬에서 가장 마지막 글자가 출력 문자열이 된다.

변환 과정
입력	All Rotations	Sort the Rows	출력
abraca	abraca aabrac caabra acaabr racaab bracaa	aabrac abraca acaabr bracaa caabra racaab	caraab, I = 1

해제 과정

해제 과정은 조금 복잡한데, 변환되었던 열을 추가하고 정렬하는 과정을 반복하는 것이다. 최초에 제안된 변환에서는 원래의 코드워드가 어느 행에 있었는지에 대한 정보를 추가로 전송하도록 되어 있다. 이것을 해결하기 위한 알고리즘으로서 입력 문자열에 메시지 시작과 끝 문자를 추가하여 해결할 수 있다. 메시지 시작 문자로 시작하는 행이 해당 부가 정보가 된다.

역변환 과정
Input
caraab
Add 1	Sort 1	Add 2	Sort 2
c a r a a b	a a a b c r	ca aa ra ab ac br	aa ab ac br ca ra
Add 3	Sort 3	Add 4	Sort 4
caa aab rac abr aca bra	aab abr aca bra caa rac	caab aabr raca abra acaa brac	aabr abra acaa brac caab raca
Add 5	Sort 5	Add 6	Sort 6
caabr aabra racaa abrac acaab braca	aabra abrac acaab braca caabr racaa	caabra aabrac racaab abraca acaabr bracaa	aabrac abraca acaabr bracaa caabra racaab
Output
abraca (using side information, I = 1)