> bwt | transform | compress <
// Burrows-Wheeler 變換 —— 透過可逆轉換優化文字壓縮效果
0 字元
0 字元
>> 主要功能
[REVERSIBLE]
完全可逆
無損轉換，可從結果精準還原原始文字。
[CLUSTERING]
字元聚類
將相似字元聚集排列，讓後續編碼器能更有效率地壓縮。
[BZIP2]
bzip2 的核心技術
廣泛用於以 BWT 為基礎的壓縮演算法，例如 bzip2。
>> 技術細節
BWT 的運作方式
Burrows-Wheeler 變換會建立輸入字串的所有循環輪轉，將這些字串依字典序排序，並輸出排序矩陣的最後一欄以及原始字串所在的列索引。這種重新排列會讓相似字元集中在一起，使輸出資料非常適合搭配 RLE、Move-to-Front 與熵編碼進一步壓縮。
BWT 範例
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
為什麼要使用 BWT
- 大幅提升文字資料的可壓縮性
- 演算法本身完全可逆且無損
- 將相似上下文整理成連續區段
- 是 bzip2 壓縮演算法的基礎組件
- 可作為其他編碼步驟前的高效預處理
>> 常見問題
什麼是 Burrows-Wheeler 變換？
Burrows-Wheeler 變換（BWT）是一種可逆演算法，透過重新排列字串，使相同符號在輸出中形成較長的連續區段。此技術由 Michael Burrows 與 David Wheeler 在 1994 年提出，常用作 bzip2 等壓縮器的前處理步驟，以获得更佳壓縮率。
BWT 為什麼有助於壓縮？
BWT 會把出現在相似上下文中的字元聚集在一起，讓同一符號在結果中連續出現。這些長度較長的區段非常適合搭配游程編碼、Move-to-Front 以及 Huffman 等熵編碼進行壓縮。
EOF 標記的用途是什麼？
EOF（End Of File）標記通常使用 '$' 或其他唯一字元，用來確保所有循環輪轉皆可區分，並協助定位原始字串所在的列。如果沒有 EOF，有些輸入字串可能無法得到唯一表示。在反向變換時會移除該標記。
BWT 本身算是一個完整的壓縮演算法嗎？
不是。BWT 並不直接壓縮資料，而是將資料轉換成更易於壓縮的形式。實務上會與 Move-to-Front、RLE 以及 Huffman 編碼等技術一起使用，組成類似 bzip2 的壓縮流程。