버로우즈-휠러 變換
(
BWT, Burrows-Wheeler transform
) 또는
블록 整列 알고리즘
은
데이터 壓縮
에 關聯된 알고리즘으로,
1994年
에
마이클 버로우즈
와
데이비드 휠러
가 開發하였다.
버로우즈-휠러 變換은 直接的으로 壓縮을 遂行하는 알고리즘은 아니며, 變換을 거친 데이터의 크기는 變하지 않는다. 하지만 元本 데이터에 重複되는 글字가 많이 있다면, 變換 過程을 거친 結果物에는 重複되는 글字가 비슷한 位置에 몰리게 된다. 버로우즈-휠러 變換은
可逆 變換
利器 때문에 主로 實際 壓縮 알고리즘을 適用하기 前에 適用하는 境遇가 많다. 이 알고리즘을 쓰는 代表的인 壓縮 포맷으로 bzip2街 있다.
예제
[
編輯
]
壓縮 過程
[
編輯
]
入力된 文字列을 可能한 모든 回轉 移動(cyclic shift)을 한 뒤, 이것들을 事前順으로 整列한다. 이 結果를 羅列한 行列에서 가장 마지막 글字가 出力 文字列이 된다.
| 變換 過程
|
| 入力
|
All
Rotations
|
Sort the
Rows
|
出力
|
abraca
|
abraca
aabrac
caabra
acaabr
racaab
bracaa
|
aabra
c
abrac
a
acaab
r
braca
a
caabr
a
racaa
b
|
caraab, I = 1
|
解除 過程
[
編輯
]
解除 過程은 조금 複雜한데, 變換되었던 熱을 追加하고 整列하는 過程을 反復하는 것이다. 最初에 提案된 變換에서는 元來의 코드워드가 어느 行에 있었는지에 對한 情報를 追加로 電送하도록 되어 있다. 이것을 解決하기 위한 알고리즘으로서 入力 文字列에 메시지 始作과 끝 文字를 追加하여 解決할 수 있다. 메시지 始作 文字로 始作하는 行이 該當 附加 情報가 된다.
| 逆變換 過程
|
| Input
|
caraab
|
| Add 1
|
Sort 1
|
Add 2
|
Sort 2
|
c
a
r
a
a
b
|
a
a
a
b
c
r
|
ca
aa
ra
ab
ac
br
|
aa
ab
ac
br
ca
ra
|
| Add 3
|
Sort 3
|
Add 4
|
Sort 4
|
caa
aab
rac
abr
aca
bra
|
aab
abr
aca
bra
caa
rac
|
caab
aabr
raca
abra
acaa
brac
|
aabr
abra
acaa
brac
caab
raca
|
| Add 5
|
Sort 5
|
Add 6
|
Sort 6
|
caabr
aabra
racaa
abrac
acaab
braca
|
aabra
abrac
acaab
braca
caabr
racaa
|
caabra
aabrac
racaab
abraca
acaabr
bracaa
|
aabrac
abraca
acaabr
bracaa
caabra
racaab
|
| Output
|
abraca (using side information, I = 1)
|
