버로우즈-휠러 변환 (BWT)

문자열을 더 짧게 만들지 않으면서 순서만 뒤섞는데, 그 결과 같은 글자들이 옆으로 주르륵 뭉친다. 뭉친 데이터는 압축이 훨씬 잘 된다. 게다가 이 변환은 완벽하게 되돌릴 수 있다. bzip2 압축과 DNA 검색 엔진(FM-index)의 심장.

1. 눈으로 보기 — 정변환

문자열 끝에 $(다른 어떤 글자보다 작은 종료 기호)를 붙인다. 「회전 생성」으로 n개의 회전을 만들고, 「정렬」로 사전순 정렬한 뒤, 마지막 열(보라색)을 읽으면 그게 BWT 결과다.

2. 왜 글자가 뭉칠까?

영어에서 he라는 글자쌍을 생각해 보자. 문장 곳곳의 "he ..."로 시작하는 회전들은 정렬 후 한곳에 모인다. 그 줄들의 마지막 글자는 원문에서 h 바로 앞에 오던 글자인데, 영어에서는 t(→ the)가 압도적으로 많다. 그래서 마지막 열에 ttttt...가 줄줄이 생긴다.

3. 어떻게 되돌릴까? — LF 매핑

놀라운 점: 우리가 저장한 건 마지막 열 L과 원문 줄 번호뿐인데도 원문을 완벽히 복원한다. 열쇠는 두 가지 사실이다.

• 첫 열 F는 그냥 L을 정렬한 것이다 (같은 글자 집합이니까).
• LF 성질: L에서 k번째로 나온 글자 c와, F에서 k번째로 나온 글자 c는 원문에서 같은 위치를 가리킨다. (정렬이 안정적이기 때문)

이 성질로 $에서 시작해 F↔L을 번갈아 따라가면 원문이 거꾸로 하나씩 튀어나온다.

4. 코드

# 정변환: 모든 회전을 정렬해 마지막 글자를 모은다
def bwt(s: str) -> str:
    s = s + "$"                          # 종료 기호(가장 작은 문자)
    rots = [s[i:] + s[:i] for i in range(len(s))]
    rots.sort()
    return "".join(r[-1] for r in rots)

# 역변환: LF 매핑으로 원문을 거꾸로 복원
def ibwt(L: str) -> str:
    n = len(L)
    # 각 L[i]가 F에서 몇 번째 줄로 가는지 계산 (안정 정렬)
    idx = sorted(range(n), key=lambda i: (L[i], i))
    row = L.index("$")                     # $로 끝나는 줄 = 원문 줄
    out = []
    for _ in range(n):
        row = idx[row]
        out.append(L[row])
    return "".join(out)[::-1].rstrip("$")

assert ibwt(bwt("banana")) == "banana"   # bwt("banana") == "annb$aa"

※ 실제 구현은 회전 문자열을 실제로 만들지 않고 접미사 배열(suffix array)을 O(n) 또는 O(n log n)으로 만들어 L[i] = s[SA[i]-1]로 계산한다. → 기수 정렬이 접미사 배열 구축에 쓰인다.

5. 어디에 쓰일까