단어의 글자를 섞어 기록했는데, 어느 자리에 있던 글자인지 다시 찾을 수 있을까요? 단어 TOMATO에 끝 표시 $를 한 번 붙이고, 한 칸씩 원형으로 옮긴 모든 문자열을 사전순으로 정렬해 볼까요? $는 모든 글자보다 먼저 온다고 약속해요. 원래 단어에는 $가 없어요. 마지막 글자를 맨 앞으로 옮겨도 한 회전이고, 맨 앞 글자를 뒤로 옮겨도 한 회전이에요.
| 행 번호 | 정렬한 회전 | 마지막 글자 |
|---|---|---|
| 0 | $TOMATO | O |
| 1 | ATO$TOM | M |
| 2 | MATO$TO | O |
| 3 | O$TOMAT | T |
| 4 | OMATO$T | T |
| 5 | TO$TOMA | A |
| 6 | TOMATO$ | $ |
마지막 열 OMOTTA$만 남기면 표의 나머지 글자는 사라져요. 그래도 단어는 유일하게 돌아와요. 다만 ‘글자가 빠지지 않았다’는 사실만으로 충분한 것은 아니에요. 어떤 글자가 다음 어느 행으로 이어지는지를 따져야 해요.
마지막 열을 L, 그 글자들을 정렬한 목록을 F라 해 볼까요? 실제 표에서 첫 열은 이미 정렬되어 있고, 어느 열이나 같은 글자들을 한 번씩 담아요. 따라서 F는 첫 열이에요. L의 첫 번째 O는 F의 첫 번째 O에, 두 번째 O는 F의 두 번째 O에 이어요. 다른 글자도 같은 등장 순위끼리 이어요. 이렇게 얻는 행 번호 대응을 P라 해 볼까요?
이 대응은 모든 행 번호를 하나씩 다른 행 번호에 이어요. 하지만 그것이 곧 전체를 한 바퀴로 잇는다는 뜻은 아니에요. 지금은 $가 적힌 6번 행에서 시작하여 6→0→3→5→1→2→4→6으로 일곱 행을 모두 지나요. 그 순서로 L의 글자를 읽으면 $OTAMOT입니다. 이를 거꾸로 읽으면 TOMATO$입니다. 끝 표시를 떼어 원래 단어를 얻어요.
왜 같은 O끼리 앞에서부터 짝지어도 될까요? 마지막 글자가 같은 두 행을 사전순으로 비교할 때는 그 앞부분이 순서를 결정해요. 그 마지막 글자를 맨 앞으로 옮기면 두 새 행의 첫 글자는 같고, 그 뒤에 이전 앞부분이 와요. 그러므로 두 행의 상대적인 순서는 유지돼요. 이것이 등장 순위 대응을 써도 되는 이유예요. 같은 글자의 개수만 세는 설명에는 이 순서 정보가 빠져 있어요.
이제 아무 마지막 열이나 받을 수 있는지 볼까요? 후보 A$BA에는 $가 한 번 있고, A 두 개와 B 한 개가 있어요. 정렬하면 F=$AAB이며 같은 순위 대응은 다음과 같아요.
두 작은 순환이 따로 남아요. $가 적힌 행에서 따라가도 다른 두 행은 방문하지 못해요. 이 기록은 주어진 규칙의 결과가 아니에요. 글자 개수와 끝 표시의 개수를 모두 확인했어도 그 결론은 달라지지 않아요.
일반 길이 N에서도 정확한 기준이 있어요. $가 한 번 있는 L에 같은 등장 순위 대응 P를 만들었을 때, L이 유효한 마지막 열일 필요충분조건은 P가 모든 N개 행을 잇는 한 순환인 거예요.
먼저 실제 결과라면 P는 한 행의 마지막 글자를 맨 앞으로 옮긴 행으로 이동해요. $가 한 번뿐이므로 N개의 회전은 모두 달라요. 한 칸씩 N번 옮기면 모든 회전을 방문한 뒤 처음으로 돌아와요. 따라서 한 순환이어야 해요.
반대 방향도 확인해야 해요. P가 한 순환이면 그 역대응을 Q라 하고, 행 i를 다음 글자 목록으로 만들어요. Q를 반복하는 것은 같은 함수를 여러 번 합성하는 일이에요.
Q가 전체를 돌므로 이 행들은 같은 문자열의 모든 회전이에요. 각 행에 $가 한 번씩 있어 행들도 서로 달라요. 마지막 글자는 F의 P(i)번째 글자이며, 대응의 정의에 따라 L의 i번째 글자와 같아요.
남은 점은 행들이 실제로 사전순인지다. 번호 i<j의 첫 글자가 다르면 F가 정렬되어 있으므로 앞 행의 글자가 작아요. 첫 글자가 같으면 Q는 그 글자 묶음에서 등장 순위를 그대로 보존하여 Q(i)<Q(j)가 돼요. 다음 글자도 같으면 이 판단을 반복해요. 서로 다른 두 회전은 언젠가 글자가 달라지며, 최초로 달라지는 자리에서 앞 행의 글자가 작아요. 그래서 만든 표는 사전순이고 마지막 열은 정확히 L입니다. $로 끝나는 행은 하나뿐이므로 원문도 유일해요.
Burrows와 Wheeler의 원문은 마지막 열과 원래 행 번호를 저장해요. 이 글은 끝 표시 $를 추가한 자체 조건 아래에서 어떤 기록을 받아들일 수 있는지 검사했어요. 끝 표시 없이 같은 짧은 단어가 반복되는 원문에는 짧은 순환도 생길 수 있다고 원저자는 따로 설명해요. 방금 한 순환 조건에서 $를 지우면 안 돼요. 또한 이 단계는 글자 수를 줄이지 않으므로 순서 변환만으로 압축률이 좋아졌다고 결론 내리지 않아요.
교사는 ‘일대일 대응이다’와 ‘모든 번호를 한 바퀴로 지난다’를 나누어 적게 해요. 제공 교재의 일대일 대응·합성함수 정의는 P와 반복 이동을 설명하는 데 썼어요. 이 문자열 변환과 유효성 정리까지 교재에 실려 있다는 뜻은 아니에요. 원문 재구성과 유효하지 않은 기록의 거절은 서로 다른 확인이며 둘 다 필요해요.
출처·착안: Burrows·Wheeler, A Block-sorting Lossless Data Compression Algorithm, §2. 자체 문자열·표·끝 표시 조건·유효성 문항과 증명이며, 원문 예시·도판·성능 자료를 옮기지 않았다.