Lexical Permutation Sorting Algorithm

Presentation on theme: "Lexical Permutation Sorting Algorithm"— Presentation transcript:

1 Lexical Permutation Sorting Algorithm
LPSA is superior to BWT!?

2 Burrows Wheeler Transform
可逆圧縮の前処理 BWT(ブロックソーティング) Move-to-Front エントロピー圧縮 圧縮効率と処理速度のバランスが良い bzip2, Bred 等の基本アルゴリズム フルカラー画像の圧縮にも有効

3 Burrows Wheeler Transform
BWT（ブロックソーティングアルゴリズム） ローテーション 入力系列を左方向にローテートし、その長さと同じ数の系列を生成する。 ソート 生成した系列群を辞書式にソートする。 出力 出力系列：　L プライマリインデックス：　I

4 ローテーション 原系列： S0 = GEGEGENOGE GEGEGENOGE S0 EGEGENOGEG S1 GEGENOGEGE S2

5 ソーティング 原系列： S0 = GEGEGENOGE EGEGEGENOG S9 EGEGENOGEG S1 EGENOGEGEG S3
ENOGEGEGEG S5 GEGEGEGENO S8 GEGEGENOGE S0 GEGENOGEGE S2 GENOGEGEGE S4 NOGEGEGEGE S6 OGEGEGEGEN S7

6 出力 原系列： S0 = GEGEGENOGE 出力： （ GGGGOEEEEN , 6 ） EGEGEGENOG S9
EGENOGEGEG S3 ENOGEGEGEG S5 GEGEGEGENO S8 GEGEGENOGE S0 GEGENOGEGE S2 GENOGEGEGE S4 NOGEGEGEGE S6 OGEGEGEGEN S7

7 BWTの効果 どうして同じ文字が並ぶの？ こんなに文字を入れ替えちゃってだいじょうぶ？ ソートすることにより、似通った文脈は隣り合う。
ex. encode と decode　→ ode...enc, ode...dec こんなに文字を入れ替えちゃってだいじょうぶ？ 出力系列 L とプライマリインデックス I から原系列を復元できます。

8 原系列の求め方 原系列： S0 = G 出力： （ GGGGOEEEEN , 6 ） ?????????G S? ?????????G S?

9 原系列の求め方 原系列： S0 = G 出力： （ GGGGOEEEEN , 6 ） E????????G S? E????????G S?
G????????E S0 G????????E S? G????????E S? N????????E S? O????????N S?

10 原系列の求め方 原系列： S0 = G 出力： （ GGGGOEEEEN , 6 ） S? GE????????G S?
1 2 3 4 GE????????G S? GE????????G S? GE????????G S? GE????????G S? OG????????O 1 2 3 4 S0 EG????????E S? EG????????E S? EG????????E S? EN????????E S? NO????????N

11 原系列の求め方 原系列： E S5 G S4 O S7 G S8 N S6 E S3 E S9 S0 = G E G 出力：
（ GGGGOEEEEN , 6 ） S? 1 2 3 4 GE????????G 1 2 3 4 S? S1 GE????????G S? GE????????G S? GE????????G S? OG????????O 1 2 3 4 S0 1 2 3 4 EG????????E S? S2 EG????????E S? EG????????E S? EN????????E S? NO????????N

12 Lexical Permutation Sorting Algorithm
文字列は multiset の順列と考えられる φ(n) 個の列を出力列の候補にできる。 φ(n)： n と互いに素な n 以下の数の個数。 ex. φ(7)=6, φ(8)=4 候補の中で、最も都合のよい列を出力系列とする。 一般の文字列の場合とのうまい関係がある。

13 置換 X = { a, b, c, d, e } π: X → X π(a) = b, π(b) = c, π(c) = a,
π(d) = e, π(e) = d . abcde bcaed π = π = [ b, c, a, e, d ] (cartesian form)

14 LPSAの例 原系列： p = [3, 1, 5, 4, 2] 31542 15423 54231 42315 23154 15423 23154 31542 42315 54231 N= N’ = BWTだと・・・ 出力系列： or プライマリインデックス： 3

15 LPSAならお得 15423 23154 31542 42315 54231 1 2 3 4 5 5 3 1 2 4 N’ = θ= = [5,3,1,2,4] θ 5 θ θ 2 θ 3 θ 4 θ 2 3 や も出力系列としてつかえる。 ただし、インデックスがさらに一つ増える。

16 任意の列じゃ駄目？ 154263 263154 315426 426315 542631 631542 1 2 3 4 5 6 4 3 5 6 2 1 2 N’ = θ = θ 6 θ 2 θ 4 θ 2 から は一意には決まらない。 （φ(n) 個の列が候補となる）

17 LPSAなら、さらにお得 π = π LPSAの場合、一列目をみるだけでソートできる。 31542 15423 54231 42315
23154 1 2 3 4 5 3 1 5 4 2 π = 1 N= =[3,1,5,4,2] π i も同様 N=[π ,π , ... ,π ] 1 2 n

18 LPSAなら、さらにお得 π = π π LPSAの場合、一列目をみるだけでソートできる。 31542 15423 54231 42315
23154 1 2 3 4 5 3 1 5 4 2 π = 1 N= =[3,1,5,4,2] π i も同様 π －1 1 = [2, 5, 1, 4, 3] N’=[π π ,π π , ... ,π π ] 1 n 2 －1

19 一般的な文字列に対するLPSA 原系列： Y = a b a b b ソート後： Y’ = a a b b b Y’ ababb babba
abbab bbaba babab ababb abbab babab babba bbaba 1 3 5 2 4 N(Y)= N’(Y) = μ=[1, 3, 5, 2, 4], λ=μ =[1, 4, 2, 5, 3] －1 Y’ [i] = Y [μ( i )], Y [i] = Y’ [λ( i )]

20 一般的な文字列に対するLPSA 得られたλを入力列としてLPSAを行う。 14253 42531 25314 53142 31425
N(λ)= N’(λ) = 原系列を復元するには・・・ k 出力列θ , k, プライマリインデックス, Y’

21 BWTとLPSAの関係 (論文中の定理3.2) N’i, j (Y) = Y’ [N’i, j (λ)] Y を文字列、λ=λとすると、
ababb abbab babab babba bbaba 14253 25314 31425 42531 53142 N’(Y) = N’(λ) = Y’ = a a b b b

22 定理3.2の直感的証明 N’i, j (Y) = Y’ [N’i, j (λ)] ababb babba abbab bbaba babab
14253 42531 25314 53142 31425 N(Y)= N(λ)= Y [i] = Y’ [λ( i )], N(Y) = Y’[N(λ)] N’i, j (Y) = Y’ [N’i, j (λ)]