Burrows-Wheeler 변환 (BWT) | 압축을 위한 텍스트 변환

>> 기능

[REVERSIBLE]

완전한 역변환 가능

원본 텍스트를 정확히 복원할 수 있는 무손실 변환입니다.

[CLUSTERING]

문자 클러스터링

유사한 문자를 묶어서 이후 인코더가 더 효율적으로 압축할 수 있게 합니다.

[BZIP2]

bzip2의 핵심

bzip2 계열 압축 알고리즘에서 사용되는 핵심 전처리 단계입니다.

>> 기술 정보

BWT 동작 방식

Burrows-Wheeler 변환은 입력 문자열의 모든 순환 회전을 생성하고 이를 사전식으로 정렬한 뒤, 정렬된 행렬의 마지막 열과 원래 문자열이 위치한 행의 인덱스를 반환합니다. 이렇게 하면 비슷한 문자가 연속해서 모이게 되어 RLE, Move-to-Front, 허프만 코딩과 같은 압축 알고리즘과 잘 어울리는 데이터가 됩니다.

BWT 예시

Input: "banana$"

Rotations:
0: banana$
1: anana$b
2: nana$ba
3: ana$ban
4: na$bana
5: a$banan
6: $banana

Sorted:
0: $banana
1: a$banan
2: ana$ban
3: anana$b
4: banana$
5: na$bana
6: nana$ba

Last column: annb$aa
Original index: 4

Output: annb$aa|4

BWT를 사용할 이유

텍스트 데이터의 압축 효율을 향상
완전한 역변환이 가능한 무손실 변환
비슷한 컨텍스트의 문자를 묶어 준다
bzip2 압축 알고리즘의 기반이 되는 기술
다른 인코딩 단계 앞에서 효과적인 전처리

>> 자주 묻는 질문

Burrows-Wheeler 변환이란 무엇인가요?

Burrows-Wheeler 변환(BWT)은 문자열을 재배열하여 같은 기호가 길게 반복되는 구간을 만들어 주는 역변환 가능한 알고리즘입니다. 1994년에 Michael Burrows와 David Wheeler가 제안했으며, bzip2와 같은 압축기에서 더 좋은 압축률을 얻기 위한 전처리 단계로 사용됩니다.

왜 BWT가 압축에 유리한가요?

BWT는 비슷한 문맥에서 등장하는 문자를 모아서 출력 상에서 같은 기호가 연속으로 나타나도록 합니다. 이런 구간은 런렝스 인코딩, Move-to-Front, 허프만 코딩 같은 알고리즘과 결합했을 때 매우 효율적으로 압축됩니다.

EOF 마커는 무엇인가요?

EOF(End Of File) 마커는 보통 '$'와 같은 고유한 문자로, 모든 회전 문자열이 서로 구별되도록 하고 원래 문자열의 위치를 찾을 수 있게 해 줍니다. 이 마커가 없으면 일부 문자열은 유일한 표현을 가지지 못할 수 있습니다. 역변환 과정에서는 EOF 마커를 제거합니다.

BWT 자체가 완전한 압축 알고리즘인가요?

아니요. BWT는 직접 데이터를 압축하는 것이 아니라, 데이터를 압축하기 쉬운 형태로 바꾸는 변환입니다. 실제 압축에서는 대개 Move-to-Front, RLE, 허프만 코딩 등과 함께 bzip2와 같은 스킴으로 사용됩니다.

[Base64.sh]

> bwt | transform | compress <