Day 138-Q2 | BWT + MTF + RLE 圧縮パイプライン

問題

小文字英字のみからなる文字列 $S$（長さ $N$）が与えられる。以下の手順で $S$ を可逆圧縮せよ。

BWT: $S' = S + \mathtt{\$}$（`$`は他のどの文字よりも辞書順で小さい番兵）のサフィックス配列 $SA$ を構築し、$L[i] = S'[(SA[i]-1)\bmod(N+1)]$ によりBWT文字列 $L$ を求める。
MTF: 文字集合を辞書順にソートしたリスト（初期状態）を先頭から更新しながら、$L$ の各文字の現在位置（0-indexed）を出力し、その文字をリスト先頭へ移動する。
RLE: MTF符号化で得た整数列を「値, 連続回数」のペアの列にまとめる。

出力: 1行目にBWT文字列 $L$、2行目にRLEのラン数 $K$、3行目に $2K$ 個の整数「値1 回数1 ... 値K 回数K」。

入力形式

N
S

制約

$1 \le N \le 2\times10^5$

$S$ は小文字英字のみ

$S$ に $ は含まれない

入出力例

入力例1

6
banana

出力例1

annb$aa
5
1 1 3 1 0 1 3 3 0 1

入力例2

1
a

出力例2

a$
2
1 1 0 1

概念図

ヒント（段階的開示）

ヒント1（方向性）

BWTは「同じ文字が連続しやすい」文字列を作る変換である。$L[i]$は「$i$番目に辞書順で小さい接尾辞の直前の文字」であり、似た文脈（同じ接頭辞）を持つ接尾辞が近くに並ぶため、その直前文字も似た分布になりやすい。この性質をMTF（直近使った値ほど小さい番号）とRLE（連続を1つにまとめる）で圧縮に変えられないか。

ヒント2（アプローチ）

BWTはサフィックス配列さえ求まれば$L[i]=S'[SA[i]-1]$の1式で求まる。サフィックス配列はランクの倍加法で$O(N\log^2N)$構築できる：各接尾辞に「最初の$2^k$文字によるランク」を持たせ、$k$を倍々に増やしながら$(rank[i],rank[i+k])$のペアで安定ソートする。MTFはアルファベットを辞書順に並べたリストを状態として持ち、文字を処理するたびにその位置を出力してから先頭へ移動する。

ヒント3（誘導）

def build_sa(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        def key(i):
            return (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if key(sa[i - 1]) < key(sa[i]) else 0)
        rank = tmp
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1
    return sa

BWT文字列を得たらalphabet = sorted(set(L))を初期MTFリストとし1文字ずつ処理、最後にRLEは単純な走査で求まる。

模範解答 (Python)

import sys


def build_sa(s):
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]
    k = 1
    while True:
        def key(i):
            return (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        tmp[sa[0]] = 0
        for i in range(1, n):
            tmp[sa[i]] = tmp[sa[i - 1]] + (1 if key(sa[i - 1]) < key(sa[i]) else 0)
        rank = tmp
        if rank[sa[-1]] == n - 1:
            break
        k <<= 1
        if k > n:
            break
    return sa


def bwt(s):
    n = len(s)
    sa = build_sa(s)
    L = [''] * n
    for i in range(n):
        L[i] = s[(sa[i] - 1) % n]
    return ''.join(L)


def mtf_encode(s):
    alphabet = sorted(set(s))
    table = list(alphabet)
    out = []
    for c in s:
        i = table.index(c)
        out.append(i)
        table.pop(i)
        table.insert(0, c)
    return out


def rle_encode(seq):
    runs = []
    i = 0
    n = len(seq)
    while i < n:
        j = i
        while j < n and seq[j] == seq[i]:
            j += 1
        runs.append((seq[i], j - i))
        i = j
    return runs


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    s = data[1]

    sprime = s + '$'
    L = bwt(sprime)
    mtf_seq = mtf_encode(L)
    runs = rle_encode(mtf_seq)

    out = [L, str(len(runs))]
    flat = []
    for v, c in runs:
        flat.append(str(v))
        flat.append(str(c))
    out.append(' '.join(flat))
    print('\n'.join(out))


main()

Step-by-Step 解説

1サフィックス配列の構築
「最初の1文字のランク」から$k=1,2,4,\dots$と倍々に伸ばしながら「最初の$2k$文字のランク」を再計算する。$O(\log N)$回の反復、各反復$O(N\log N)$のソートで全体$O(N\log^2N)$。

2BWTの構築
$L[i]=S'[(SA[i]-1)\bmod(N+1)]$の1行。番兵$を導入することで巡回シフトのソートと接尾辞のソートが等価になる。

3MTF符号化で連続を作る
似た文脈を持つ接尾辞が近くに集まるため$L$の中で同じ文字が連続しやすい。MTFは「直前に出た文字ほど小さい番号」を与え、同じ文字の連続をほぼ0の連続に変換する。

4RLEで最終圧縮
MTF後の列は0が連続しやすいためランレングス符号化で大幅に圧縮できる。本問はパイプラインの各段の正しさを$L$・ラン数・ラン列で検証する。

5可逆性
BWT・MTF・RLEはいずれも可逆な変換であり、逆BWT・逆MTF・ランの展開により元の$S$を完全に復元できる。bzip2系ツールも同様の3段構成を採用する。

よくあるミス

ミス	原因	正しい書き方
番兵$を付け忘れる	通常の文字列比較では巡回シフトの順序が一意に定まらない	必ず「他のどの文字より小さい」番兵を末尾に付けてからSAを構築する
L[i]=S'[SA[i]]としてしまう	BWTの定義を「その文字自身」と誤解する	L[i]=S'[(SA[i]-1)%(N+1)]と必ず1つ前の位置(mod付き)を取る
MTFの初期リストをa-z+$固定にする	出現しない文字までリストに含めるとランク値がずれる	実際にLに出現する文字集合sorted(set(L))を初期状態にする
N=1などの境界ケースを見落とす	ループ境界処理の考慮不足	S'の長さ2でも正しく動くことをテストする(出力例2で確認)
doublingをk>nでも回し続ける	終了条件をrank[sa[-1]]==n-1のみに頼る	kがnを超えたら強制的にループを抜ける安全策を入れる

次のステップ

発展: 逆BWT（$L$から$S$を復元する）を実装せよ。LF-mapping（Last-to-First mapping）を使えば$O(N)$で復元できる。
発展2: 本問の$O(N\log^2N)$のdoubling法を、Day137-Q2のSA-IS法（$O(N)$）に置き換え、大きな$N$（$10^6$程度）でも高速に動くパイプラインへ改良せよ。

自己評価

完全理解おおむね理解要復習

Day 138-Q2 — BWT + MTF + RLE（可逆文字列圧縮パイプライン）

問題