버로우즈-휠러 변환

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

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

 예제 
 압축 과정 
입력된 문자열을 가능한 모든 회전 이동(cyclic shift)을 한 뒤, 이것들을 사전순으로 정렬한다. 이 결과를 나열한 행렬에서 가장 마지막 글자가 출력 문자열이 된다.
 변환 과정 입력 AllRotations Sort theRows 출력 
 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)

분류:무손실 압축 알고리즘
분류:변환 (수학)