[머신러닝] BWT(Burrows- Wheeler Transform)알고리즘- 컴도리돌이

---

Burrows-Wheeler transform (BWT)

Transform

LF mapping

Reversing with BWT

Searching with table occurrence and count

---

BWT (Burrows-Wheeler transform)

• 블록 정렬 알고리즘으로 변환 결과에 Index 정보가 포함되어 있어, 다른 정보가 없더라도 변환된 문자열의 경우 유사한 문자열들끼리 뭉쳐진 형태로 나타나는 경우가 많아 압축을 위한 전처리 알고리즘

• 동일한 문자를 조합(block-sorting compression)

• 데이터 압축에 사용(예: bzip2)

• 압축성을 항상 향상하는 것은 아니다.

• 변환은 되돌릴 수 있다.

• 패턴의 위치를 효율적으로 찾다(O|pattern|)

---

변환(Transform) - ex) Text = banana

 

• 매우 긴 서열을 변환한다면, BWT는 유사한 문자들을 모이게 하고, 압축을 할 수 있도록 해준다. 

BWT example

 

1. 변환하고자 하는 텍스트의 맨 마지막에 단어의 끝을 알리는 토큰(token : $)을 넣는다.

2. 토큰을 넣은 문자열을 왼쪽으로 한 칸씩 이동(Shift)을 수행하며 행렬을 생성한다.

3. 생성된 행렬을 첫 번째 열을 기준으로 사전 순 정렬을 한다.

4. 정렬된 행렬의 맨 마지막 열의 문자들로 생성된 문자열이 변환된 결과이다.

---

후-전 사상(LF mapping)

T-ranking

• 첫 번째 열은 두 번째 열 별로 정렬한다. -> BWT(abaaba)

• 정렬된 행렬에서 첫 번째(First) 열과 마지막(Last) 열을 제외하고 가운데 있는 모든 문자열을 삭제를 한다.

• 특징 : 첫 번째 열의 원소의 순서와 마지막 열의 원소의 순서는 동일한 순서로 정렬된다. ->BWT는 결과적으로 정렬(sort)이 되었기 때문에 첫 번째와 마지막 열의 순서는 같을 수밖에 없다.

• LF mapping 특징 덕분에 연속된 데이터에서 원하는 데이터를 효율적으로 탐색이 가능해진다.

 

LF mapping - When each character in T has a rank, ith occurrence of a character in last column is same as the ith occurence in first column

---

BWT의 역변환(reversing with BWT)

Reversing BWT(abaaba)

• $을 기준으로 a0이 문자열의 맨 끝을 시작의 의미하면 a0으로 이동하면 b0과 대칭되어 있는데 이것은 a0 앞에 b0의 문자가 있다는 것을 의미한다. 이런 식으로 해당 문자를 타고 역순으로 이동하면 원래 문자열이 복구가 된다.

---

테이블을 이용한 탐색 방법(Searching with table occurrence and count)

"ana" 패턴 찾기

1. table occ와 table c를 만든다.

• table occ를 만드는 방법은 마지막 열(last column)의 값으로 테이블을 완성한다. 첫 번째 열에 A가 나타났기 때문에 a 값을 1 증가시킨다. 두 번째 열에서 N이 나타났기 때문에 n의 값을 증가시킨다. a의 값은 증가된 값으로 계속 가져간다.

• table c는 각 변수가 발생한 열의 위치이다 a의 값은 첫 번째 열에서 발생하였기 때문에 값이 1이고 b의 값은 4번째에서 발생했기 때문에 4이다.

 

2. 마지막 문자열이 'a'이기 때문에 다음 문자열인 'n'을 찾아야하는데 A0과 A1이 각각 N을 갖고있다. N의 시작 인덱스는 5이기 때문에 C(5) + 0(N의 번호) , C(5) + 1(N의 번호)으로 이동 시킨다.

3. C(n)에서 다시 a로 가야하는데 a값이 증가되었는지 확인하고 증가되었기 때문에 해당 C(a) 위치로 간다.

---