맨위로가기

버로우즈-휠러 변환

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

버로우즈-휠러 변환(Burrows-Wheeler Transform, BWT)은 데이터를 압축하기 위한 알고리즘으로, 텍스트 문자열을 변환하여 압축 효율을 높이는 데 사용된다. BWT는 입력 문자열의 모든 원형 이동을 사전식 순서로 정렬하여 마지막 열을 추출하는 방식으로 작동하며, 이 변환은 가역적이어서 원래 데이터를 복원할 수 있다. BWT는 데이터 압축, 염기 서열 정렬, 이미지 압축, 유전체 데이터베이스 압축, 시퀀스 예측 등 다양한 분야에 활용된다. BWT는 자체적으로는 압축을 수행하지 않지만, 데이터를 "압축하기 쉽게" 만들어 MTF, RLE, 엔트로피 부호화 등의 후처리 과정을 통해 압축 효율을 높인다.

더 읽어볼만한 페이지

  • 변환 (수학) - 르장드르 변환
    르장드르 변환은 볼록 함수에 적용되어 도함수의 상에 작용하며 쌍대성을 통해 함수 관계를 재표현하는 변환으로, 해석역학, 열역학, 미시경제학 등에서 활용되고 볼록 켤레 함수라고도 불린다.
  • 변환 (수학) - 이산시간 푸리에 변환
    이산시간 푸리에 변환(DTFT)은 이산 시간 신호를 주파수 영역에서 분석하는 변환으로, 주기적인 스펙트럼을 가지며 샘플링된 신호 분석 및 시스템 주파수 응답 특성 파악에 유용하고 Z 변환과 밀접한 관계를 가진다.
  • 무손실 압축 알고리즘 - VP9
    VP9는 구글이 개발한 오픈 소스 비디오 코덱으로, VP8보다 압축 효율을 높이고 HEVC보다 나은 성능을 목표로 개발되었으며, WebM 형식으로 사용되고 주요 웹 브라우저와 넷플릭스, 유튜브 등에서 지원했으나 AV1의 등장으로 개발이 중단되었다.
  • 무손실 압축 알고리즘 - FLAC
    FLAC은 조시 콜슨이 개발한 무손실 오디오 코덱으로, 원본 음질을 유지하면서 파일 크기를 줄이기 위해 오디오 데이터를 압축하며, 4~32비트 샘플 크기, 최대 8 채널을 지원하고, 미국 국립 문서 기록 관리청에서 디지털 오디오에 선호되는 형식으로 지정되었다.
버로우즈-휠러 변환
알고리즘 개요
종류무손실 압축을 위한 전처리
특징
시간 복잡도O(n)
공간 복잡도O(n)
데이터문자열
개발 및 발표
개발자마이클 버로스
데이비드 J. 휠러
발표일1994년 5월 10일

2. 원리

BWT(버로우즈-휠러 변환)는 입력 데이터의 모든 원형 이동을 사전식 순서로 정렬하여 얻어지는 행렬의 마지막 열을 추출하는 방식으로 작동한다.[2]

BWT는 문자열의 순서를 순열하는데, 원본 문자열에 자주 나타나는 부분 문자열이 있으면 변환된 문자열에는 같은 문자가 여러 번 반복되는 경우가 많아진다. 예를 들어 "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"를 변환하면 "TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT"가 되는데, 여기에는 XX, SS, PP, .., II, III와 같이 동일한 문자가 반복되는 구간이 6개나 나타난다.

변환 과정은 입력 문자열 `S`의 모든 원형 이동을 사전식 순서로 정렬하고, 정렬된 문자열 집합에서 마지막 열과 원래 문자열의 인덱스를 추출한다. 예를 들어 입력 문자열이 `S = ^BANANA$` 라면 (여기서 `^`는 문자열의 시작, `$`는 'EOF'를 나타냄), 문자열을 N번 회전하여 모든 원형 이동을 만든다. 이를 사전식으로 정렬한 후, 마지막 열 `L = BNN^AA$A` 와 원래 문자열 `S` 가 위치한 행의 인덱스 `I = 6` 을 얻는다.

BWT의 핵심은 변환된 문자열이 원본 문자열보다 압축하기 쉽다는 점뿐만 아니라, 마지막 열의 데이터만으로도 원본 문자열을 복원할 수 있다는 점이다. 역변환은 마지막 열의 문자들을 알파벳 순으로 정렬하여 첫 번째 열을 만들고, 마지막 열과 첫 번째 열을 조합하여 모든 연속된 문자 쌍을 찾고, 이를 다시 정렬하여 첫 번째와 두 번째 열을 얻는 과정을 반복하여 전체 문자열을 복원한다.

길이 ''n''의 데이터를 순환 이동시켜 얻을 수 있는 모든 문자열을 사전식 정렬하여 만들어진 ''n''×''n'' 행렬의 n번째 열이 BWT 시퀀스이다. 이 BWT 시퀀스와, 원래 문자열이 정렬되었을 때 행렬의 몇 번째에 위치했는지를 기억해두면, 이를 통해 원래 문자열을 복호화할 수 있다.

2. 1. 부호화 (Encoding)

회전3. 사전식으로
정렬4.
마지막 열 가져오기5. 출력align=center |



`$`와 `^` 중 적어도 하나는 사용해야 변환을 반전할 수 있다.

다음은 버로우즈-휠러 변환(BWT)과 역변환을 수행하는 의사 코드이다.

'''function''' BWT (''string'' s)

테이블 생성, 행은 s의 모든 가능한 회전

알파벳 순으로 행 정렬

'''return''' (테이블의 마지막 열)

'''function''' inverseBWT (''string'' s)

빈 테이블 생성

'''repeat''' length(s) '''times'''

// 먼저 삽입하여 첫 번째 열 생성

s를 테이블의 첫 번째 열 앞에 열로 삽입

테이블의 행을 알파벳 순으로 정렬

'''return''' ( 'EOF' 문자로 끝나는 행)

다음은 파이썬 구현이다.



from curses.ascii import STX, ETX

def bwt(s: str, start=chr(STX), end=chr(ETX)) -> str:

r"""

입력 문자열에 버로우즈-휠러 변환 적용

>>> bwt('BANANA')

'\x03ANNB\x02AA'

>>> bwt('BANANA', start='^', end='$')

'ANNB^AA$'

>>> bwt('BANANA', start='%', end='$')

'A$NNB%AA'

"""

assert (

start not in s and end not in s

), "입력 문자열에는 STX 및 ETX 문자를 포함할 수 없습니다"

s = f"{start}{s}{end}" # 텍스트 마커의 시작과 끝 추가

# 문자열 회전 테이블

table = sorted(f"{s[i:]}{s[:i]}" for i, c in enumerate(s))

last_column = [row[-1:] for row in table] # 각 행의 마지막 문자

return "".join(last_column) # 문자 목록을 문자열로 변환





def inverse_bwt(r: str, start=chr(STX), end=chr(ETX)) -> str:

r"""

역 버로우즈-휠러 변환 적용

>>> inverse_bwt('\x03ANNB\x02AA')

'BANANA'

>>> inverse_bwt('ANNB^AA$', start='^', end='$')

'BANANA'

>>> inverse_bwt('A$NNB%AA', start='%', end='$')

'BANANA'

"""

str_len = len(r)

table = [""] * str_len # 빈 테이블 만들기

for _ in range(str_len):

table = sorted(rc + tc for rc, tc in zip(r, table)) # r의 열 추가

# 반복하고 마지막 문자가 ETX로 끝나는지 확인

s = next((row for row in table if row.endswith(end)), "")

# 배열에서 데이터를 검색하고 시작 및 종료 마커 제거

return s.rstrip(end).strip(start)



예시로 "cacao" 문자열의 변환과정을 살펴보면 다음과 같다.

먼저, 순환 행렬을 생성한다.

ABCDE
1cacao
2ocaca
3aocac
4caoca
5acaoc



그 다음, 행렬을 정렬한다.

ABCDE
5acaoc
3aocac
1cacao
4caoca
2ocaca



정렬된 행렬의 마지막 열(E열)을 세로로 취하고, 원래 문자열이 몇 번째 행에 있었는지(3번째)를 기록하여 "ccoaa, 3"을 결과로 얻는다.

2. 2. 복호화 (Decoding)

BWT 출력 문자열과 인덱스를 이용하여 원본 문자열을 복원한다. BWT 출력 문자열을 정렬하여 첫 번째 열을 생성하고, 마지막 열과 첫 번째 열을 조합하여 순차적으로 원본 문자열을 찾는다. 인덱스를 활용하여 올바른 순서의 문자열을 선택한다.[4]

복호화는 BWT 시퀀스 문자열을 정렬하여 행렬의 첫 번째 열을 얻는 것에서 시작한다. BWT 시퀀스 문자열과 첫 번째 열의 문자들은 원본 문자열에서 서로 앞뒤 관계를 가진다. 이 성질을 이용하여 오른쪽으로 열을 추가하고 정렬하는 과정을 반복하면 원본 문자열을 복원할 수 있다.

예시를 통해 복호화 과정을 살펴보자. 입력 BWT 문자열은 'caraab'이다.

역변환 과정
Input
align=center colspan=4 |
Add 1Sort 1Add 2Sort 2
align=right |align=right |align=right |align=right |
Add 3Sort 3Add 4Sort 4
align=right |align=right |align=right |align=right |
Add 5Sort 5Add 6Sort 6
align=right |align=right |align=right |align=right |
Output
align=center colspan=4 |



위 표와 같이, 마지막 열을 앞에 추가하고 정렬하는 과정을 반복하면 원본 문자열 'abraca'를 얻을 수 있다.

복호화 과정에서 매번 정렬을 수행하는 것은 비효율적이다. 따라서, 각 행의 이동이 일대일 대응된다는 점을 이용하여 복원하는 것이 일반적이다.

다음은 복호화를 간략하게 설명하는 의사 코드이다:

'''function''' inverseBWT (''string'' s)

빈 테이블 생성

'''repeat''' length(s) '''times'''

// 먼저 삽입하여 첫 번째 열 생성

s를 테이블의 첫 번째 열 앞에 열로 삽입

테이블의 행을 알파벳 순으로 정렬

'''return''' ( 'EOF' 문자로 끝나는 행)

다음은 파이썬 코드이다.



def inverse_bwt(r: str, start=chr(STX), end=chr(ETX)) -> str:

r"""

역 버로우즈-휠러 변환 적용

>>> inverse_bwt('\x03ANNB\x02AA')

'BANANA'

>>> inverse_bwt('ANNB^AA$', start='^', end='$')

'BANANA'

>>> inverse_bwt('A$NNB%AA', start='%', end='$')

'BANANA'

"""

str_len = len(r)

table = [""] * str_len # 빈 테이블 만들기

for _ in range(str_len):

table = sorted(rc + tc for rc, tc in zip(r, table)) # r의 열 추가

# 반복하고 마지막 문자가 ETX로 끝나는지 확인

s = next((row for row in table if row.endswith(end)), "")

# 어레이에서 데이터를 검색하고 시작 및 종료 마커 제거

return s.rstrip(end).strip(start)


3. 특징

BWT는 문자열의 순서를 순열하여 원본 문자열에 자주 나타나는 부분 문자열이 있을 경우, 변환된 문자열에서 동일한 문자가 연속적으로 반복되는 경향을 증가시킨다. 이러한 특징은 압축 효율을 높이는 데 기여한다.[2]

예를 들어, "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"라는 문자열을 BWT로 변환하면 "TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT"가 된다. 이 변환된 문자열에는 "XX", "SS", "PP", "..", "II", "III"와 같이 동일한 문자가 반복되는 구간(런)이 6개 나타나며, 이는 전체 44개 문자 중 13개를 차지한다.[2]

입력SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
출력TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT[2]



BWT는 텍스트의 모든 원형 이동을 사전식 순서로 정렬한 후, 정렬된 순열 집합의 마지막 열과 원본 문자열의 인덱스를 추출하는 방식으로 수행된다.

입력 문자열이 `S = ^BANANA$`일 때 (여기서 빨간색 `^`는 문자열의 시작을, 빨간색 `$`는 'EOF'를 나타낸다), 문자열 S의 길이만큼 회전하여 모든 원형 이동을 생성한다. 이후 이 원형 이동들을 사전식으로 정렬하고, 마지막 열 `L = BNN^AA$A`와 원본 문자열 S를 포함하는 행의 인덱스 `I = 6` (0부터 시작)을 얻는다.

변환
1. 입력2. 모든
회전		3. 사전식으로
정렬		4.
마지막 열 가져오기		5. 출력
align=center |



BWT는 가역 변환으로, 변환된 데이터로부터 원본 데이터를 완벽하게 복원할 수 있다. 역변환은 마지막 열만으로 첫 번째 열을 재구성하고, 이를 반복하여 전체 문자열을 복원하는 방식으로 이루어진다.

BWT의 특징은 단순히 출력을 쉽게 압축할 수 있도록 만드는 것이 아니라, 이 변환이 가역적이라는 점이다. 즉, 마지막 열의 데이터만으로도 원본 문서를 다시 생성할 수 있다는 것이다.

4. 최적화

BWT 알고리즘은 출력 변경 없이 더 효율적으로 실행될 수 있도록 여러 최적화 방법이 적용될 수 있다. 인코더나 디코더에서 표를 나타낼 필요가 없으며, 인코더에서는 표의 각 행을 문자열에 대한 단일 포인터로 나타내고, 정렬은 인덱스를 사용하여 수행할 수 있다. 디코더에서도 표를 저장할 필요가 없고, 정렬도 전혀 필요하지 않다. 알파벳 크기와 문자열 길이에 비례하는 시간 안에, 디코딩된 문자열은 오른쪽에서 왼쪽으로 한 번에 한 글자씩 생성될 수 있다.[3] 알고리즘에서 "문자"는 바이트, 비트 또는 기타 편리한 크기가 될 수 있다.

인코딩된 문자열은 접미사 배열의 간단한 수정으로 계산될 수 있으며, 접미사 배열은 선형 시간과 메모리로 계산될 수 있다. BWT는 텍스트 T의 접미사 배열 SA에 대해 다음과 같이 정의될 수 있다(1부터 시작하는 인덱싱).[3]

:BWT[i] = \begin{cases} T[SA[i]-1], & \text{if }SA[i] > 0\\ \$, & \text{otherwise}\end{cases}

실제 'EOF' 문자를 가질 필요는 없다. 대신, 'EOF'가 존재한다면 문자열의 어느 부분에 있을지를 기억하는 포인터를 사용할 수 있다. 이 접근 방식에서 BWT의 출력은 변환된 문자열과 포인터의 최종 값을 모두 포함해야 한다. 그런 다음 역 변환은 원래 크기로 다시 축소한다. 즉, 문자열과 포인터가 주어지면 문자열만 반환한다.[1]

알고리즘에 대한 전체 설명은 Burrows와 Wheeler의 논문 또는 여러 온라인 소스에서 찾을 수 있다.[1] 알고리즘은 EOF 사용 여부와 정렬 방향에 따라 다소 다르다. 실제로, 원래 공식은 EOF 마커를 사용하지 않았다.[4]

블록 정렬을 수행하려면 순환 문자열을 정렬해야 하지만, 일반적인 정렬 방법(예: 퀵 정렬)을 단순하게 적용하면 문자열 길이 n에 대해 \mathrm{O}(n^2\log n)의 시간이 필요하게 된다. 따라서 일반적으로 순환 문자열이라는 점을 이용하여 더욱 효율적인 정렬을 수행한다.

이를 위한 알고리즘은 여러 개 제안되었으며, \mathrm{O}(n), \mathrm{O}(n\log\log n), \mathrm{O}(n\log n)의 알고리즘이 알려져 있지만, 실용상 자연어와 같은 일반적인 입력 데이터에 대해서는 \mathrm{O}(n\log n)인 것이 속도와 메모리 효율 면에서 최적이다.

bzip2에서는 \mathrm{O}(n\log\log n)과 \mathrm{O}(n\log n)의 알고리즘을 입력에 따라 최적의 것으로 전환하여 사용하고 있다. 또한 블록 크기는 100k바이트에서 900k바이트까지, `-1` ~ `-9` 옵션으로 선택할 수 있으며, 기본값은 900k바이트이다.

5. 전단사 변환 (Bijective Variant)

전단사 변환은 버로우즈-휠러 변환(BWT)의 변형으로, 입력 문자열을 고유하게 식별할 수 있도록 하는 방법이다. 이 변환은 Lyndon 단어 분해를 기반으로 하며, 변환된 문자열은 원본 문자열을 유일하게 결정한다.[5][6]

전단사 변환은 입력을 감소하지 않는 Lyndon 단어 시퀀스로 분해하여 계산한다. 이러한 분해는 Chen–Fox–Lyndon 정리에 의해 유일하게 존재하며,[7] 선형 시간과 상수 공간으로 찾을 수 있다.[8] 알고리즘은 모든 단어의 회전을 정렬한다. Burrows–Wheeler 변환과 마찬가지로 정렬된 ''n''개의 문자열 시퀀스를 생성한다. 변환된 문자열은 이 정렬된 목록에서 각 문자열의 마지막 문자를 선택하여 얻어진다. 이때 길이가 다른 문자열은 일반적인 방식으로 정렬되지 않고, 두 문자열을 무한히 반복하여 비교한다. 예를 들어, "ORO"는 "OR"보다 앞선다. "OROORO..."가 "OROROR..."보다 앞서기 때문이다.

예를 들어, 텍스트 "^BANANA$"는 다음 단계를 거쳐 "ANNBAA^$"로 변환된다. (빨간색 $ 문자는 원본 문자열의 EOF 포인터를 나타낸다.) EOF 문자는 전단사 변환에는 필요하지 않으므로 변환 중에 삭제되고 파일의 적절한 위치에 다시 추가된다.

전단사 변환
입력모든
회전		알파벳순으로 정렬됨회전된 Lyndon 단어의
마지막 열		출력
align=center |



역 전단사 변환 과정은 마지막 단계를 제외하면 역 Burrows–Wheeler 프로세스와 동일하다. 단, 여기서는 단일 시퀀스의 회전이 아닌 Lyndon 단어의 회전을 제공한다. (프로세스가 계속되면 반복되기 시작한다.)

역 전단사 변환
입력
align=center colspan=4 |
Add 1Sort 1Add 2Sort 2
align=right |align=right |align=right |align=right |
Add 3Sort 3Add 4Sort 4
align=right |align=right |align=right |align=right |
출력
align=center colspan=4 |



이 과정에서 네 개의 개별 Lyndon 단어 (A), (AN) (두 번), (B) 및 (^)의 반복을 볼 수 있다. (NANA...는 ANAN....의 사이클이므로 개별 단어를 나타내지 않는다.) 이 단어들은 역순으로 정렬되어 (^), (B), (AN), (AN), (A)가 되고, 연결하면 ^BANANA를 얻는다.

Burrows–Wheeler 변환은 전단사 변환의 특수한 경우로 볼 수 있다. 문자열의 끝에 새로운 문자를 추가하는 대신, 문자열의 시작 부분에 배치된 모든 기존 문자를 선행하는 것으로 비교되는 새로운 문자를 도입한다. 전체 문자열은 Lyndon 단어가 되며, 전단사 변환을 거치면 역변환 시 최종 조립이 필요 없는 변환된 결과를 얻는다.

변환된 텍스트는 Lyndon 단어당 하나의 문자만 BWT의 결과와 다르다. 예를 들어, 입력이 여섯 개의 Lyndon 단어로 분해되면 출력은 여섯 개의 문자만 달라진다.

예를 들어, 전단사 변환을 적용하면 다음과 같다.

입력SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Lyndon 단어SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
출력STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT


6. 응용 분야

버로우즈-휠러 변환(BWT)은 다양한 분야에서 활용되는 무손실 압축 알고리즘이다. BWT는 가역적(reversible) 변환을 통해 원본 데이터를 복구할 수 있다는 특징을 가지며, 이러한 특성 덕분에 여러 알고리즘에 응용되고 있다.

분야설명
시퀀스 정렬차세대 염기 서열 분석(NGS) 기술에서 DNA 리드를 참조 게놈에 정렬하는 데 사용된다. Bowtie, BWA, SOAP2 등의 프로그램이 BWT를 활용한다.[12] [13] [14]
이미지 압축BWIC와 같이 BWT를 기반으로 한 압축 방식은 무손실 JPEG, JPEG 2000 등의 기존 알고리즘보다 뛰어난 성능을 보이기도 한다.[15]
데이터 압축텍스트, 이미지, 유전체 데이터 등 다양한 데이터 압축에 활용된다.[17]
시퀀스 예측기계 학습 및 자연어 처리 분야에서 시퀀스 예측에 활용된다. BWT의 무손실 데이터 압축을 활용하는 SuBSeq 방식은 학습 시간과 정확성 측면에서 뛰어난 성능을 보인다.[18]


6. 1. 데이터 압축

BWT는 텍스트, 이미지, 유전체 데이터 등 다양한 데이터의 압축에 활용된다. BWT는 전방 이동 변환(Move-To-Front, MTF), 런-렝스 인코딩(Run-Length Encoding, RLE), 엔트로피 부호화 등의 압축 기법과 함께 사용되어 압축률을 높인다.[17]

BWT 시퀀스는 동일한 기호가 연속되기 쉬운 성질을 가지므로 MTF를 사용하면 작은 정수 값에 크게 편중된다. 따라서 RLE와 엔트로피 부호화를 적용하여 압축을 수행할 수 있다.

원래 문자열에 자주 나타나는 부분 문자열이 있는 경우, 변환된 문자열은 단일 문자가 여러 번 연속으로 반복되는 여러 위치를 갖게 된다. 예를 들어 "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"를 BWT로 변환하면 "TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT"가 되는데, 여기에는 XX, SS, PP, .., II, III와 같이 동일한 문자의 반복이 나타난다. 이러한 반복되는 문자열은 압축하기가 더 쉽다.

BWT는 "the"와 같이 자주 나타나는 단어가 포함된 긴 영어 텍스트를 변환할 때 효과적이다. 텍스트를 회전하여 정렬하면 "he "로 시작하는 회전이 그룹화되고, "he " 앞의 문자는 일반적으로 "t"가 되므로, 변환 결과에는 여러 개의 "t" 문자가 나타난다.

BWT의 장점은 단순히 압축하기 쉬운 출력을 생성하는 것이 아니라, 가역적(reversible) 변환을 통해 원본 데이터를 복구할 수 있다는 점이다.

6. 2. 염기서열 정렬 (Sequence Alignment)

2000년대 후반 차세대 염기 서열 분석(NGS) 기술이 나오면서 버로우즈-휠러 변환의 또 다른 응용 분야가 나타났다. NGS에서 DNA는 작은 조각으로 분해되고, 그 중 처음 몇 개의 염기가 DNA 염기 서열 분석되어 수백만 개의 "리드"가 생성되며, 각 리드는 30~500 염기쌍("DNA 문자") 길이이다. ChIP-Seq와 같은 많은 실험에서 이러한 리드를 참조 게놈에, 즉 해당 유기체의 알려진 거의 완전한 서열(수십억 염기쌍까지 가능)에 정렬하는 것이 과제이다. 이 작업을 위해 특화된 여러 정렬 프로그램이 발표되었으며, 처음에는 해시 함수를 사용했다(예: Eland, SOAP,[10] 또는 Maq[11]). 서열 정렬의 메모리 요구 사항을 줄이기 위해, 버로우즈-휠러 변환을 사용하는 여러 정렬 프로그램(Bowtie,[12] BWA,[13] 및 SOAP2[14])이 개발되었다.

6. 3. 이미지 압축

BWT는 영상 압축에 사용되는 기본적인 기술이다.[15] 예를 들어, BWT 적용 후 역변환, 런-렝스 인코더, 산술 인코더를 사용하는 압축 파이프라인을 통해 만들어진 역변환 인코더를 사용한 버로우즈-휠러 변환(BWIC)은 무손실 JPEG 및 JPEG 2000과 같이 널리 사용되는 알고리즘보다 뛰어난 압축 성능을 보인다. BWIC는 방사선 촬영 의료 영상의 최종 압축 크기에서 각각 5.1%와 4.1% 더 나은 성능을 보였다. 이는 BWIC와 이미지의 사전 BWIC 스캔을 수직 스네이크 순서로 결합하여 달성한 결과이다.

최근에는 move-to-front transform, MTF, 전방 이동 변환과 함께 BWT를 구현하여 이미지의 거의 무손실 압축을 달성하는 연구도 발표되었다.[16] BWT는 무손실 압축 알고리즘으로서 인코딩이 가역적이며, 압축 결과로부터 원래 데이터를 복구할 수 있다는 중요한 특징이 있다.

6. 4. 유전체 데이터베이스 압축

무손실 압축 알고리즘으로서 버로우즈-휠러 변환은 그 인코딩이 가역적이며, 결과 압축으로부터 원래 데이터를 복구할 수 있다는 중요한 특징을 제공한다. 버로우즈 알고리즘의 무손실 특성은 시퀀스 정렬, 이미지 압축, 데이터 압축 등의 다양한 알고리즘에 활용된다.[17] Cox 등[17]은 인간 유전체 정보를 포함한 여러 유전체 데이터 세트 압축의 첫 번째 단계에서 BWT를 알고리즘으로 사용하는 유전체 압축 방식을 제시했다. 그들의 연구는 두 개 이상의 접두사 문자의 접미사가 같을 수 있다는 사실을 이용하여, 동일-이전 인코딩("SAP")이라고 하는 두 번째 단계 압축 메커니즘을 포함시켜 BWT 압축을 향상시킬 수 있다고 제안했다. Cox 등은 BWT-SAP 압축 메커니즘을 통해 크기가 135.5GB인 유전체 데이터베이스 ERA015743에서 BWT-SAP 압축 방식이 ERA015743 데이터 세트를 약 94% 압축하여 8.2GB로 줄일 수 있음을 보였다.

6. 5. 시퀀스 예측 (Sequence Prediction)

BWT는 기계 학습 및 자연어 처리에서 일반적인 연구 분야인 시퀀스 예측에도 유용한 것으로 입증되었다.[18] 특히, Ktistakis 등은 BWT의 무손실 데이터 압축을 활용하는 SuBSeq라는 시퀀스 예측 방식을 제안했다. SuBSeq는 FM-인덱스를 추출한 다음, 주어진 접미사에 대한 예측을 검색하기 위해 backwardSearch, forwardSearch, neighbourExpansion 및 getConsequents라는 일련의 연산을 수행하여 BWT를 활용한다. 예측은 가중치를 기반으로 분류되어 배열에 배치되며, SuBSeq 알고리즘의 예측으로 가장 높은 가중치를 가진 요소가 제공된다. SuBSeq는 학습 시간과 정확성 측면에서 모두 최첨단 시퀀스 예측 알고리즘보다 뛰어난 성능을 보이는 것으로 나타났다.

참조

[1] 간행물 A block sorting lossless data compression algorithm https://www.hpl.hp.c[...] Technical Report 124, Digital Equipment Corporation 1994-05-10
[2] 웹사이트 adrien-mogenet/scala-bwt https://github.com/a[...] 2018-04-19
[3] 논문 Efficient construction of an assembly string graph using the FM-index 2010-06-15
[4] 서적 Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS'99 Szklarska Poreba, Poland, September 6-10, 1999 Proceedings Springer Science & Business Media 1999-08-18
[5] 간행물 A bijective string sorting transform http://bijective.dog[...] 2009-07-09
[6] 간행물 Prague Stringology Conference http://www.stringolo[...]
[7] 간행물 Combinatorics on words Cambridge University Press
[8] 간행물 Factorizing words over an ordered alphabet
[9] 논문 A Four-Stage Algorithm for Updating a Burrows–Wheeler Transform
[10] 논문 SOAP: short oligonucleotide alignment program
[11] 논문 Mapping short DNA sequencing reads and calling variants using mapping quality scores 2008-08-19
[12] 논문 Ultrafast and memory-efficient alignment of short DNA sequences to the human genome
[13] 논문 Fast and accurate short read alignment with Burrows–Wheeler Transform
[14] 논문 SOAP2: an improved ultrafast tool for short read alignment
[15] 서적 2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) 2015
[16] 논문 Near lossless medical image compression using block BWT–MTF and hybrid fractal compression techniques https://link.springe[...] 2019
[17] 논문 Large-scale compression of genomic sequence databases with the Burrows–Wheeler transform Oxford University Press
[18] 서적 Database and Expert Systems Applications 2019
[19] 서적 Pythonで学ぶアルゴリズムとデータ構造 講談社 2019-11-26


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com