バロウズ・ウィーラー変換(BWT)

巡回シフトがソートされて行列になり、その最終列に同じ文字が集まる様子を観察し、それを可逆的に元に戻す

計算例 — バロウズ・ウィーラー変換(BWT)

生成	7個の巡回シフト — 文字列を左に0、1、2…6文字分シフト

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

シフトをソートするとランができる理由 🖖

テキストのすべての巡回シフトをソートすると、同じ接尾辞を持つシフト同士が隣り合わせになります。最終列 — 各ソート済み接頭辞の直前の文字 — は、元のテキストで同じ文脈の前にあった文字を集めます。繰り返しパターンがあると多くのシフトが共通の接尾辞を持つため、同じ先行文字が最終列で何度も連続して現れます。このランこそが、RLEやmove-to-front符号化が活用するものです。この変換が可逆である理由は、先頭列F(ソート済みBWT)と最終列L(BWTそのもの)が合わせて完全な対応関係 — LF写像 — を符号化しており、この2つの列とキーだけから元のテキストを1文字ずつ復元できるからです。

BWTは並べ替えるだけで縮めない 🖖

BWTだけでは、テキストは少しも小さくならない。出力の長さも文字の種類と個数も元とまったく同じで、並び順だけが変わる。真価は、同じ文字を集め、後段の圧縮処理をしやすくする可逆な前処理にある。後段では、Move-to-Front変換、ランレングス符号化を経て、ハフマン符号化や算術符号化を行う。"abracadabra$"の出力も同じ十二文字だが、入力では二つさえ隣り合わなかったaが四つ連続する。

あなたのDNAを地図化するのと同じ技 🖖

ある圧縮のアイデアが、静かにゲノミクスの土台になりました。FM索引と呼ばれる構造に組み込むと、BWTは30億文字のヒトゲノムの中から短いDNA断片を検索でき、しかもそのゲノムをわずか数ギガバイトで保持できます。BowtieやBWA（Burrows-Wheeler Aligner）といったアライナーはこれを土台にしており、1994年の圧縮の技が、今や日々何百万ものシーケンシングリードの照合を支えています。

全プロセスの詳細解説

全七つの巡回シフトをソートした "banana$" のバロウズ＝ウィーラー変換 5 ステップ
「banana$」のバーローズ–ホイラー変換を求め、何か圧縮されたかどうかを判定せよ。これはBWT出力ステップであり、番兵が付加され、7つの回転がすべてソートされ、最後の列が読み出された状態である。
1. 他の処理が行われる前に、まず番兵が付加される。$ はすべてのアルファベットより前にソートされ、かつ正確に1回しか現れないため、2つの回転が等しく比較されることはなく、ソート結果は一義的に定まる。
  
  $s = banana$ (n = 7), r_{k} = s [k :] + s [: k], k = 0, \dots, 6$
2. 回転を辞書順にソートすることが、この変換の行う唯一の処理である。7つの行を順に下に読み進めると、ソートによって各位置の直後に来る文字ごとに文字列がグループ化されていることがわかる。
  
  $$banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba$
3. ある回転の最後の文字は、元の文字列においてその先頭文字の直前に位置していた文字である。ソートによってランが生じるのはそのためである。1行目と2行目はともに 'a' で始まり、ともに 'n' で終わる。これは banana において、どちらの a の前にも n が存在するからである。キーは元の文字列の行番号であり、これがなければ変換を元に戻す（逆変換する）ことはできない。
  
  $L_{j} = s_{(k_{j} - 1) mod n} ⟹ L = annb$aa, key = 4$
4. まだ何も圧縮されておらず、圧縮され得るはずもない。出力は入力の順列であり、同じ7文字が異なる順序で並んでいるだけである。変化したのはラン構造であり、変化したのはそれだけである。
  
  $b ∣ a ∣ n ∣ a ∣ n ∣ a ∣ $ : R = 7, \overset{r}{ˉ} = 1.00 ⟶ a ∣ nn ∣ b ∣ $ ∣ aa : R = 5, \overset{r}{ˉ} = \frac{7}{5} = 1.4$
5. RLEは1ランあたり2バイトを要するため、7バイトの入力に対して5つのランは10バイトのコストがかかる。その損益分岐点は決して変わらない。ランの数は全体の長さの半分未満である必要があり、ここでは3以下を意味する。
  
  $2 R = 10 > N = 7 ⟹ \frac{7}{10} = 0.70 \times, 2 R < N ⟺ R < 3.5$
解答

パネルには annb$aa、key = 4、平均ラン長 1.4 文字、RLEの 10 bytes、スコア 0.70× と表示される。変換は約束通りのことを正確に行い、1文字も変更することなく平均ラン長を40%引き上げた。しかし、7文字では1ランあたり2バイトのコストをその伸びで相殺するにはテキストが短すぎるため、パイプラインとしては依然として損となる。単語を2倍にすると計算は逆転する。「bananabanana$」は13文字であり、その変換結果は annnnbba$aaaa となる。長さがほぼ2倍になったのに対し、ランは5つではなく6つになり、13バイトに対して12バイト、スコアは 1.08× となる。これこそがBWTの利点のすべてである。ランの数はテキストの長さではなく、テキストに含まれる異なるコンテキストの数によって決まるため、ブロックが長いほど効果を発揮する。bzip2 が単語ではなく最大 900 kB のブロックを変換するのはそのためである。

$bananabanana$ : N = 13, R = 6 ⟹ 2 R = 12 < 13, \frac{13}{12} = 1.08 \times$

学習の道すじ

手作業によるデータ圧縮

参考文献 (3)

Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.

42Math チーム · 更新 2026-08-17

公表された資料と照合しています。訂正のご指摘を歓迎します。編集方針 · 訂正

コンピューティングのレッスン一覧 →

例題

banana - "banana$"は"annb$aa"になる。隣り合うことのなかった三つのaが二群にまとまり、ラン数は7から5に減る。
mississippi - "mississippi$"は"ipssm$pissii"になる。教科書でおなじみの例だが、この長さではラン数は9のままで変わらない。文字をまとめる効果が現れるには、もっと長いテキストが必要になる。
abracadabra - "abracadabra$"は"ard$rcaaaabb"になる。元の文字列では二つも隣り合わなかったaが四つ連続し、ラン数は12から8に減る。ここにある四つの例では、文字が最もよくまとまっている。
DNA配列 - "AGATCAGA$"は"AGC$GTAAA"になる。隣接するAがなかった文字列から、三つのAが連続する。ゲノムでは、FM-indexがこのような変換結果を索引化する。