Day 155-Q5 — 逆BWT（Inverse Burrows-Wheeler Transform・LFマッピング）

2026-09-16 赤色 Master / Phase 8+ ★★★★★★★★★ Last-to-Firstマッピングによる元列のO(N)復元

問題

Day149-Q1では、BWT文字列からFM-indexを使ってパターンの出現回数を数える問題を扱った。今回はその逆方向——BWT文字列だけから元の文字列を完全に復元する問題を扱う。

文字列 $S$（末尾に、他のどの文字よりも辞書順で小さい番兵文字`$`が1つだけ付いている）のBurrows-Wheeler変換 `BWT(S)` が与えられる。`BWT(S)` から $S$ を復元せよ。逆変換には元の巡回シフト表全体を保持する必要はなく、LF-mapping（Last-to-First対応）という$O(N)$の対応関係だけで復元できる。

入力形式

BWT文字列

制約

文字列長$N$は$1\le N\le 2\times10^5$
アルファベット小文字+番兵`$`(1個)のみ
`$`は他のどの文字よりも辞書順で小さい

入出力例

入力例1

ard$rcaaaabb

出力例1

abracadabra$

概念図：LFマッピングの連鎖（最初の数ステップ）

$位置(i=3)から出発してLFを辿る i=3 $ i=0 a i=1 r i=10 b i=6 a ... 収集文字: $,a,r,b,a,... → 12回たどった後に反転すると abracadabra$ LF[i]=start_index[bwt[i]]+rank(bwt[i],i)-1

ヒント（段階的開示）

ヒント1（方向性）

BWT文字列（最終列, Last column）だけが与えられ最初の列（First column）は直接与えられていない。しかしLast columnをソートするだけでFirst columnが手に入る（各巡回シフトの最後の文字の集合と最初の文字の集合は同じ文字の多重集合であるため）。この事実がすべての出発点になる。

ヒント2（アプローチ）

ある行の最後の文字（Last column）の次に来る文字は、その行を1つ巡回シフトした行の先頭文字（First column）になる。Last columnのi番目の文字とFirst column上の対応位置を結びつける写像 LF(i) を、「bwt[i]という文字が先頭からi番目までに何回目の出現か(rank)」と「その文字がsorted(bwt)の中で最初に現れる位置(start_index)」から計算する。

ヒント3（誘導） 
def inverse_bwt(bwt):
    n = len(bwt)
    count = defaultdict(int); rank = [0]*n
    for i, c in enumerate(bwt):
        count[c] += 1; rank[i] = count[c]
    first_sorted = sorted(bwt)
    start_index = {}
    for i, c in enumerate(first_sorted):
        if c not in start_index: start_index[c] = i
    LF = [start_index[bwt[i]] + rank[i] - 1 for i in range(n)]
    i = bwt.index('$')
    res = []
    for _ in range(n):
        res.append(bwt[i]); i = LF[i]
    return ''.join(reversed(res))

模範解答 (Python)

import sys
from collections import defaultdict

def solve():
    bwt = sys.stdin.readline().strip()
    n = len(bwt)

    # 各位置の文字が、先頭から数えて何回目の出現かを記録
    count = defaultdict(int)
    rank = [0] * n
    for i, c in enumerate(bwt):
        count[c] += 1
        rank[i] = count[c]

    # sorted(bwt)（=First column）上での各文字の最初の出現位置
    first_sorted = sorted(bwt)
    start_index = {}
    for i, c in enumerate(first_sorted):
        if c not in start_index:
            start_index[c] = i

    # LF-mapping
    LF = [start_index[bwt[i]] + rank[i] - 1 for i in range(n)]

    # '$' の位置から出発して LF を n 回たどる
    i = bwt.index('$')
    res = []
    for _ in range(n):
        res.append(bwt[i])
        i = LF[i]

    print(''.join(reversed(res)))

solve()

Step-by-Step 解説

1First columnはLast columnをソートするだけで求まる
BWT行列の各行は同じ文字列$S$の巡回シフトなので、どの列も$S$に含まれる文字の多重集合として見れば同じ内容になる。巡回シフト表を明示的に構築する必要はない。
2LF-mappingが成り立つ理由
ある行を1つ右に巡回シフトすると先頭文字がbwt[i]に一致する。BWT行列は辞書順ソート済みなので、「bwt[i]という文字の中でi番目までに何回登場したか(rank)」からFirst column上の対応位置が一意に決まる。
3実測トレース（S="abracadabra$"）
BWT(S)="ard$rcaaaabb"。start_index={'$':0,'a':1,'b':6,'c':8,'d':9,'r':10}。$の位置i=3から出発しLFを12回たどると res=[$,a,r,b,a,d,a,c,a,r,b,a]となり、反転すると"abracadabra$"——元の文字列と完全一致（本ファイル作成時にPythonで実測・res==sを確認済み）。
4計算量
rank, start_index, LFの構築はいずれもO(N)（ソート部分だけO(N log N)、カウンティングソートでO(N)にできる）。復元ループもO(N)。Day149-Q1のFM-index（検索）とこの逆BWT（復元）は同じLF-mapping/Occという道具を別目的に使い回している関係にある。

よくあるミス

ミス原因正しい書き方
start_indexを構築せずFirst columnを使おうとする各文字の開始位置の辞書を作り忘れるstart_index[c]を「sortedされた列でcが最初に現れる位置」として構築する
rankの数え始めを0からにしてしまう1-origin/0-originの混同count[c]+=1してからrank[i]=count[c]とし、LF[i]の式もrank[i]-1にする
$の位置をFirst column上の位置と勘違いLast column中の$の位置とFirst column上の$の位置の混同復元の出発点はLast column（入力のbwt文字列）中のbwt.index('$')
復元した文字列を反転し忘れるLFマッピングを逆向きに辿っているため文字は末尾から先頭の順になるresをappendし終えたら必ずreversed(res)してから結合する

次のステップ

  • 発展: `$`を使わずBWTを復元する方法や、Occ配列を疎に持つFM-index形式での逆変換の高速化を試す。
  • 次回予告（Day156）: 今回の5テーマ（チャープZ変換・大整数乗算・サイクル検出・資源割当・文字列復元）を踏まえ、数論変換系・グラフ探索系・文字列系のいずれかをさらに深掘りする

自己評価

自分の回答

気づき・メモ