無損壓縮的上限取決於一種方法能看出多少冗餘。LZ 家族與霍夫曼編碼在一般文字上各自達到瓶頸。

Burrows 與 Wheeler 在 1994 年的 DEC 報告中描述了一種區塊排序轉換:列出該區塊的每一個輪換,將其排序,然後輸出最後一欄。由於各輪換共享後綴,相同字元會聚集在一起,而簡短的遊程編碼與移到前端處理便將其轉化為極少數的符號。

此轉換可逆,因此它是一種重排而非損失。其結果餵養了 bzip2,後者比當代工具更有效地壓縮文字,並使這項技術成為慢但緊湊之壓縮的標準。

將區塊的輪換排序,使相似者相鄰

排序輪換會將相同符號聚集在上下文相同之處。

接著,遊程編碼與移到前端編碼會找出長而廉價的連續段。

此轉換是一種排列,因此解壓縮是精確的。

它對任何重複結構都有效,因此並非針對單一檔案類型調校。

在壓縮之前,重新排序資料,使相同符號彼此相鄰。一種能聚集可預測部分的轉換,可以讓普通的壓縮器大幅增強。

Burrows-Wheeler 轉換成為 bzip2 的引擎,後來又成為 FM-index 的基礎,後者用於尋找子字串並對基因組進行映射。同樣的概念如今驅動著高通量生物資訊比對工具。

追溯依據

參考來源

  1. A block-sorting lossless data compression algorithm DEC Systems Research Center Research Report 124 · web.stanford.edu
  2. Burrows-Wheeler transform Wikipedia · en.wikipedia.org