버로우즈-휠러 변환

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

버로우즈-휠러 변환(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)