解決方案
無損壓縮的上限取決於一種方法能看出多少冗餘。LZ 家族與霍夫曼編碼在一般文字上各自達到瓶頸。
Burrows 與 Wheeler 在 1994 年的 DEC 報告中描述了一種區塊排序轉換:列出該區塊的每一個輪換,將其排序,然後輸出最後一欄。由於各輪換共享後綴,相同字元會聚集在一起,而簡短的遊程編碼與移到前端處理便將其轉化為極少數的符號。
此轉換可逆,因此它是一種重排而非損失。其結果餵養了 bzip2,後者比當代工具更有效地壓縮文字,並使這項技術成為慢但緊湊之壓縮的標準。
它達成了什麼
將區塊的輪換排序,使相似者相鄰
為何有效
排序輪換會將相同符號聚集在上下文相同之處。
接著,遊程編碼與移到前端編碼會找出長而廉價的連續段。
此轉換是一種排列,因此解壓縮是精確的。
它對任何重複結構都有效,因此並非針對單一檔案類型調校。
可應用之處
在壓縮之前,重新排序資料,使相同符號彼此相鄰。一種能聚集可預測部分的轉換,可以讓普通的壓縮器大幅增強。
後續發展
Burrows-Wheeler 轉換成為 bzip2 的引擎,後來又成為 FM-index 的基礎,後者用於尋找子字串並對基因組進行映射。同樣的概念如今驅動著高通量生物資訊比對工具。
追溯依據
參考來源
- A block-sorting lossless data compression algorithm DEC Systems Research Center Research Report 124 · web.stanford.edu
- Burrows-Wheeler transform Wikipedia · en.wikipedia.org