버로우즈–휠러 변환(BWT) 계산기

문자열을 한 칸씩 돌린 것을 모두 만들어 사전순으로 늘어놓고 마지막 열만 뽑아내는 재배열입니다. 길이도 글자 개수도 그대로이지만 같은 글자가 뭉쳐 나오게 되어, 뒤에 붙는 압축이 훨씬 잘 먹습니다. bzip2가 BWT → MTF → 런길이 부호화 → 허프만 순서로 이 변환을 앞단에 씁니다.

되지 않습니다. BWT 자체는 한 바이트도 줄이지 않으며 글자별 엔트로피도 정확히 그대로입니다. 「BWT로 압축했다」는 말은 틀렸고 「BWT로 압축이 잘 되게 만들었다」가 맞습니다. 바뀌는 것은 같은 글자가 이어지는 덩어리의 수뿐이고, 그 덕에 뒤에 붙는 단계가 잘 먹는 것입니다.

정렬 기준이 각 행의 「뒤에 오는 글자들」인데, 그 행의 마지막 글자는 그 글자들의 바로 앞 글자이기 때문입니다. 영어에서 "he" 앞에는 t가 자주 오므로 "he…"로 시작하는 행이 한 덩어리로 모이면 그 행들의 마지막 열에 t가 줄줄이 늘어섭니다. 문맥이 비슷한 자리의 앞 글자가 비슷하다는 성질을 정렬로 끌어모으는 셈입니다.

첫 열이 마지막 열을 정렬한 것이고, 같은 글자끼리는 두 열에서 순서가 같기 때문입니다. 마지막 열의 k번째 A와 첫 열의 k번째 A가 원문의 같은 자리를 가리킵니다. 두 열의 A들이 모두 「그 뒤에 오는 문자열의 사전순」으로 줄 서 있어서 그렇습니다. 이 대응(LF 매핑)을 따라가면 원문을 뒤에서부터 한 글자씩 되짚을 수 있습니다.

어느 행이 원문이었는지 알아야 역변환을 시작할 수 있기 때문입니다. 끝을 알리는 특수문자를 문자열 끝에 붙이는 방식을 쓰면 행 번호 없이도 되지만, 그러면 원문에 그 문자가 없어야 한다는 조건이 붙습니다. 실제 구현은 아무 데이터에나 쓸 수 있는 행 번호 쪽을 대개 씁니다.

방금 쓴 글자를 목록 맨 앞으로 옮기고, 각 글자를 「그때 목록에서의 자리」로 적는 변환입니다. 같은 글자가 이어지면 0이 줄줄이 나오므로 뒤에 런길이 부호화를 붙이면 크게 줄어듭니다. BWT를 거친 뒤에 붙이면 0의 비율이 눈에 띄게 오르는데, bzip2가 두 변환을 이 순서로 붙이는 이유가 그것입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.