BWT란 Burrows-Wheeler Transform의 약자로 데이터를 연속되는 문자열로 간주하여, 예를 들면 10바이트 데이터는 10바이트 문자열이 10개가 있는 메트릭스로 여기고, 그 문자열들을 좌로 1~n번 쉬프트 시키는 변환으로 생긴 10개의 문자열을 정렬한 후에 변환 전의 맨 처음 문자열의 첫 글자의 위치가 어느 문자열의 마지막 문자로 이동했는지 만을 알면 정렬된 문자열들로 원래의 문자열 배열로 복원할 수 있는 reversable transfrom 알고리즘이 BWT 알고리즘이다.
여담으로 Wheeler는 1983년에 행렬을 연구하다 이 변환 알고리즘을 발견했지만, 그 쓰임새를 확실히 모르고 있다가 1994년 DEC 연구소에서 Burrows와 만나 데이터 치환에 대한 연구를 하다가 데이터 압축 과정의 데이터 전처리 과정에 사용되면 매우 효율적일 수 있다는 것을 깨닳고, 1995년에 Universal Data Compression 이라는 논문을 발표하게 된다. 어떤 알고리즘이나 프로토콜에 Universal 이라는 단어를 사용한다는 것은 BWT가 얼마나 범용성이 높은 압축 전처리 방식인가를 뜻한다. (USB가 Universal Serial Bus 라든가?)
BWT 방식을 사용한 데이터 압축은 각 문자열들을 정렬한 후에 MTF(Move to front)시킨 후에 일반적인 statistical coding(Huffman or Arithmetic coding 등)으로 압축하는 것을 BWT 방식 데이터 압축이라 말한다.
이 방식은 Block sorting compression 알고리즘이라고 불리기도 하며, 다른 압축 방식들 즉, LZ-77, LZ-78, DMC, PPM 등과 가장 큰 차이점은 block sorting에 많은 시간이 소모 된다는 것이며 압축률을 높이기 위해서는 더 큰 문자열을 정렬해야만 하는 단점을 가진다. 예를 들어 1Mbyte의 데이터를 block sorting 하기 위해서는 1M bytes 문자열 1백만 개를 정렬해야 한다. 정렬에도 여러 획기적인 기법들이 소개되었으나 대량 문자열 정렬에 따른 압축 속도 저하는 불가피하다.
하지만 압축률은 Lempel-Ziv 77 방식을 사용하는 WinZip, WinRar 등에 비해 월등히 높고, PC 상에서는 구현이 힘들어 실용적이지 못한 PPM 방식에 약간 떨어지는 정도이다.
- BWT 압축 알고리즘은 보통 4단계로 나뉘어진다.
- Burrows-Wheeler Transform.
- Sorting
- MTF(Move to front)
- Statistical coding(Huffman 또는 arithmetic coding 류)
