Burrows–Wheeler transform

안녕하세요 Geeks_Company 입니다.

오늘 소개 시켜 드릴 알고리즘은 Burrows–Wheeler transform란 알고 리즘 입니다.

이글에서 사용되는 모든 내용은 http://en.wikipedia.org/wiki/Burrows-Wheeler_transform (이하 위의 링크로 축약해서 표현 하겠습니다) 에서 참조를 하여 사용 하였습니다.

저작권에 침해 되는 내용이 있으면 쪽지 또는 댓글로 알려 주셨음 합니다.

BWT 알고리즘은 압축을 할때 사용되는 알고리즘중 하나 이며,  압축을 시킬 파일의 구성원소(byte or char)을 빈도수 별로 분석 한후 , 분석된 값을 효율적으로 표현 시키는데 사용됩니다.

BWT의 핵심 내용은 input String(char or byte) 속에 있는 캐릭터들을 가능한한 연속된 순서대로 정렬 시키는데 목적이 있습니다.

위의 BWT링크 예제 에서 사용되는 자료를 사용하자면 이러 합니다.

Input	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Output	TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

The output is easier to compress because it has many repeated characters. In fact, in the transformed string, there are a total of six runs of identical characters: XX, SS, PP, .., II, and III, which together make 13 out of the 44 characters in it.

해석을 하자면, ouput이 Input에 비해서 압축 하기가 쉬운 이유는 많은 캐릭터들이 반복해서 나타나기 때문입니다.
변환이 된 output 스트링을 보자면, 총 6개의 구분하기 쉬운 캐릭터들이 있습니다 :XX, SS, PP, .., II, and III 이 케릭터들은 총 44개의 캐릭터중 13개를 차지 합니다.

즉 , 연속된 문자의 String으로 BWT가 변형을 시켜 준다고 이해 하시면 됩니다.

다시 위의 링크 사용된 예제를 사용 하겠습니다.
아래의 예제중 @는 문장의 끝 (구분자)입니다.

Transformation
Input	All Rotations	Sort the Rows	Output
^BANANA@	^BANANA@ @^BANANA A@^BANAN NA@^BANA ANA@^BAN NANA@^BA ANANA@^B BANANA@^	ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA	BNN^AA@A

의사 코드는 이러 합니다.


 function BWT (string s)
   create a table, rows are all possible rotations of s
   sort rows alphabetically
   return (last column of the table)

함수 BWT는 String s를 인자로 받으며, 
Table을 만들고 s의 구성원소의 자리 변환으로 생성되는 String 들을 Table에 저장을 합니다.
각 열을 알파벳 순서로 정렬을 합니다.
(각 열 * 열 로 비교해서 순서대로 정렬 합니다)
Table의 마지막 열의 구성원소를 반환 합니다. 

혹시 헛갈릴 부분을 위해서 다른 자료를 참조 합니다.

http://marknelson.us/1996/09/01/bwt/ 에서 참조한 자료 입니다. 

즉, DRDOBBS 란 String을 입력 받은후 Rotation 을 시킨후 Table형식(2차원 배열)로 저장을 합니다.

이후 저장된 배열의 구성원소를 sorting 하면, 이러한 방식으로 정렬이 됩니다. 

위의 사진 자료처럼 ^BANANA@을 bwt 함수에 적용을 시키면 반환값은 BNN^AA@A 가 됩니다.

이제 결과값을 토대로 다시 원 문으로 복구 시키는 함수를 설명 드리겠습니다.

이름하여 인버스BWT 입니다.


function inverseBWT (string s)
   create empty table
      
   repeat length(s) times
       insert s as a column of table before first column of the table   // first insert creates first column
       sort rows of the table alphabetically
   return (row that ends with the 'EOF' character)


우선 함수 inverseBWT는 String s를 인자 값으로 받습니다.
빈 Table을 만듭니다.

S의 길이 만큼 아래의 구문을 반복합니다
{
동일한 스트링 S를 테이블의 첫번째 컬럼으로 삽입을 합니다 // 컬럼이 없을경우 처음 String을 처음 컬럼 데이터로 사용 합니다. (컬럼 = 세로 = 열)

Table의 데이터를 알파벳 순서로 정렬을 시킵니다.
}

Table의 열 중 끝 문자가 (@ = EOF)인 열을 반환 합니다.



자세한 설명은 http://en.wikipedia.org/wiki/Burrows-Wheeler_transform#Example 를 참조 하면 됩니다.
(화면에 붙여 넣으니 텍스트라  링크로 처리 하였습니다).


^BANANA@ --> Fuction bwf ---> BNN^AA@A 

총 8개 반복없는 문자가, 총 6개의 구분 가능한 문자(반복 문자 NN, AA는 1개씩 처리)로 변환이 되었습니다.



이것으로 BWT 알고리즘의 설명을 마칩니다.

P.S : BWT는 직접 압축을 하는 알고리즘이 아닌, 압축 알고리즘을 위해 사용되는 여러단계중 사용되는 하나의 알고리즘 입니다. Bzip2의 경우 실제 압축 알고리즘은 Move-To-Front and Huffman Coding을 사용 합니다.