이 변환은 블록 정렬 압축으로 불리지만, 실제로는 데이터를 압축하지는 않고 변환만 수행한다. Michael Burrows 씨와 David Wheeler 씨가 켈리포니아의 DEC System Research Center에서 일하면서 고안한 것이다. 이 변환을 수행하게 되면 같은 문자들이 묶여서 반복되는 양상의 문자열이 생성된다. 마찬가지로 데이터의 크기를 줄이지 않지만 비슷한 의미를 가진 전향(MTF, Move To Front) 변환 등과 함께 사용되고 최종적으로는 반복 길이 부호화 인코딩(RLE, Run Length Encoding)과 같은 알고리즘을 이용하여 데이터를 압축하는데 사용되기도 한다.
큰 상관은 없는 이야기이지만, 문자열을 전향 변환으로 처리하는 과정에서 데이터의 반복이 지역적 상관도를 가지는 경우엔 적은 숫자들이 출력 결과에 나타나게 된다. 여기에서 지역적 상관도가 의미하는 바는 이 변환의 경우 가장 최근에 처리된 문자를 이 변환이 사용하는 문자 리스트에서 가장 앞으로 보내게 되고 이는 해당 문자의 문자 리스트 안의 순번이 가장 낮은 값이 됨을 의미하고, 문자가 반복된다면 해당 문자의 인코딩된 결과 값은 상대적으로 낮은 숫자 값을 가지게 되는 것이다.
버로우즈-휠러 변환은 주어진 문자열에 대한 모든 가능한 순열을 생성하고 이렇게 생성된 문자열을 사전식 순서의 오름차순으로 정렬하고 이렇게 생성된 순열의 가장 마지막 문자만을 취해서 출력하게 된다. 결과적으로는 접미사 배열의 모든 원소에 대해서 1을 빼면 버로우즈-휠러 변환 배열이다. 예를 들어서, S=mississippi$를 접미사 배열로 만들면 SA=(11, 10, 7, 4, 1, 0, 9, 8, 6,3, 5, 2)이다. 이제 이 배열에서 1을 빼면 BWA=(10, 9, 6, 3, 0, -1, 8, 7, 5, 2, 4, 1)이 된다. 이를 문자열로 표현하려면 다음과 같이 하면 된다.
S[10] = i
S[9] = p
S[6] = s
S[3] = s
S[0] = m
S[-1] = $
S[8] = p
S[7] = i
S[5] = s
S[2] = s
S[4] = i
S[1] = i
문자열 S의 값의 해당 순번의 BWA 값을 찾아서 연결하면 위와 같이 ipssm$pissii를 얻을 수 있다.
댓글