버로우즈-휠러 변환
보이기
이 문서의 내용은 출처가 분명하지 않습니다. (2013년 5월) |
버로우즈-휠러 변환(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) |
![]() |
이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |