Lexical Permutation Sorting Algorithm

Lexical Permutation
Sorting Algorithm
LPSA is superior to BWT!?
Burrows Wheeler
Transform
 可逆圧縮の前処理
1. BWT(ブロックソーティング)
2. Move-to-Front
3. エントロピー圧縮
 圧縮効率と処理速度のバランスが良い
 bzip2, Bred 等の基本アルゴリズム
 フルカラー画像の圧縮にも有効
Burrows Wheeler
Transform
 BWT（ブロックソーティングアルゴリズム）
1. ローテーション
入力系列を左方向にローテートし、その長さと同じ
数の系列を生成する。
2. ソート
生成した系列群を辞書式にソートする。
3. 出力
 出力系列： L
 プライマリインデックス： I
ローテーション
原系列： S0 = GEGEGENOGE
S0
S1
S2
S3
S4
S5
S6
S7
S8
S9
GEGEGENOGE
EGEGENOGEG
GEGENOGEGE
EGENOGEGEG
GENOGEGEGE
ENOGEGEGEG
NOGEGEGEGE
OGEGEGEGEN
GEGEGEGENO
EGEGEGENOG
ソーティング
原系列： S0 = GEGEGENOGE
S9
S1
S3
S5
S8
S0
S2
S4
S6
S7
EGEGEGENOG
EGEGENOGEG
EGENOGEGEG
ENOGEGEGEG
GEGEGEGENO
GEGEGENOGE
GEGENOGEGE
GENOGEGEGE
NOGEGEGEGE
OGEGEGEGEN
出力
原系列：
出
力：
S9
S1
S3
S5
S8
S0
S2
S4
S6
S7
S0 = GEGEGENOGE
（ GGGGOEEEEN , 6 ）
EGEGEGENOG
EGEGENOGEG
EGENOGEGEG
ENOGEGEGEG
GEGEGEGENO
GEGEGENOGE
GEGENOGEGE
GENOGEGEGE
NOGEGEGEGE
OGEGEGEGEN
BWTの効果
 どうして同じ文字が並ぶの？
ソートすることにより、似通った文脈は隣り合う。
ex. encode と decode → ode...enc, ode...dec
 こんなに文字を入れ替えちゃってだいじょうぶ？
出力系列 L とプライマリインデックス I から原系列を
復元できます。
原系列の求め方
原系列：
出
力：
S?
S?
S?
S?
S?
S0
S?
S?
S?
S?
S0 = G
（ GGGGOEEEEN , 6 ）
? ? ? ? ? ? ? ? ? G
? ? ? ? ? ? ? ? ? G
? ? ? ? ? ? ? ? ? G
? ? ? ? ? ? ? ? ? G
? ? ? ? ? ? ? ? ? O
? ? ? ? ? ? ? ? ? E
? ? ? ? ? ? ? ? ? E
? ? ? ? ? ? ? ? ? E
? ? ? ? ? ? ? ? ? E
? ? ? ? ? ? ? ? ? N
原系列の求め方
原系列：
出
力：
S?
S?
S?
S?
S?
S0
S?
S?
S?
S?
S0 = G
（ GGGGOEEEEN , 6 ）
E ? ? ? ? ? ? ? ? G
E ? ? ? ? ? ? ? ? G
E ? ? ? ? ? ? ? ? G
E ? ? ? ? ? ? ? ? G
G ? ? ? ? ? ? ? ? O
G ? ? ? ? ? ? ? ? E
G ? ? ? ? ? ? ? ? E
G ? ? ? ? ? ? ? ? E
N ? ? ? ? ? ? ? ? E
O ? ? ? ? ? ? ? ? N
原系列の求め方
原系列： S0 = G
出
（ GGGGOEEEEN , 6 ）
力：
S? 1 G E ? ? ? ? ? ? ? ?
S? 2 G E ? ? ? ? ? ? ? ?
S? 3 G E ? ? ? ? ? ? ? ?
S? 4 G E ? ? ? ? ? ? ? ?
S? O 1 G ? ? ? ? ? ? ? ?
S0 E 2G ? ? ? ? ? ? ? ?
S? E 3G ? ? ? ? ? ? ? ?
S? E 4G ? ? ? ? ? ? ? ?
S? E N ? ? ? ? ? ? ? ?
S? N O ? ? ? ? ? ? ? ?
G
G
G
G
O
E
E
E
E
N
原系列の求め方
原系列： S0 = GEGE G E N O G E
出
（ GGGGOEEEEN , 6 ）
力：
S? 1 G 1 E ? ? ? ? ? ? ? ?
S9
S? 2 G 2 E ? ? ? ? ? ? ? ?
S1
S? 3 G 3 E ? ? ? ? ? ? ? ?
S3
S? 4 G 4 E ? ? ? ? ? ? ? ?
S5
S? O 1 G ? ? ? ? ? ? ? ?
S8
S0 1 E 2G ? ? ? ? ? ? ? ?
S? 2 E 3G ? ? ? ? ? ? ? ?
S2
S? 3 E 4G ? ? ? ? ? ? ? ?
S4
S? 4 E N ? ? ? ? ? ? ? ?
S6
S? N O ? ? ? ? ? ? ? ?
S7
G
G
G
G
O
E
E
E
E
N
Lexical Permutation
Sorting Algorithm
 入力列を {1, 2, ... ,n} の順列に限定する。
文字列は multiset の順列と考えられる
 φ(n) 個の列を出力列の候補にできる。
φ(n)： n と互いに素な n 以下の数の個数。
ex. φ(7)=6, φ(8)=4
 候補の中で、最も都合のよい列を出力系列
とする。
 一般の文字列の場合とのうまい関係がある。
置換
X = { a, b, c, d, e }
π: X → X
π(a) = b, π(b) = c, π(c) = a,
π(d) = e, π(e) = d .
a b c d e
π= b c a e d
π = [ b, c, a, e, d ]
(cartesian form)
LPSAの例
原系列： p = [3, 1, 5, 4, 2]
3
1
N= 5
4
2
1
5
4
2
3
5
4
2
3
1
4
2
3
1
5
2
3
1
5
4
1
2
N’ = 3
4
5
5
3
1
2
4
4
1
5
3
2
BWTだと・・・
出力系列： 53124 or 34251
プライマリインデックス： 3
2
5
4
1
3
3
4
2
5
1
LPSAならお得
1
2
N’ = 3
4
5
5
3
1
2
4
4
1
5
3
2
2
5
4
1
3
3
4
2
5
1
θ=
1
2
3
4
5
5
3
1 = [5,3,1,2,4]
2
4
θ 5θ θ 2θ 3θ 4
θ や θ も出力系列としてつかえる。
ただし、インデックスがさらに一つ増える。
2
3
任意の列じゃ駄目？
1
2
3
N’ = 4
5
6
5
6
1
2
4
3
4
3
5
6
2
1
2
1
4
3
6
5
6
5
2
1
3
4
3
4
6
5
1
2
2
θ=
1
2
3
4
5
6
4
3
5
6
2
1
θ6 θ2 θ4
2
θ から θ は一意には決まらない。
（φ(n) 個の列が候補となる）
LPSAなら、さらにお得
LPSAの場合、一列目をみるだけでソートできる。
3
1
N= 5
4
2
1
5
4
2
3
5
4
2
3
1
4
2
3
1
5
2
3
1
5
4
N=[π ,π
2 ,π ]
1 , ...
π =1
n
1
2
3
4
5
3
1
5 =[3,1,5,4,2]
4
2 π i も同様
LPSAなら、さらにお得
LPSAの場合、一列目をみるだけでソートできる。
3
1
N= 5
4
2
π
1
5
4
2
3
5
4
2
3
1
4
2
3
1
5
2
3
1
5
4
1
2
3
4
5
π =1
3
1
5 =[3,1,5,4,2]
4
2 π i も同様
－1
= [2, 5, 1, 4, 3]
－1
－1
N’=[π π
,π
π
,
1
1
1... 2,π π ]
1
－1
1
n
一般的な文字列に対するLPSA
原系列： Y = a b a b b
ソート後： Y’ = a a b b b
a
b
N(Y)= a
b
b
b
a
b
b
a
a
b
b
a
b
b
b
a
b
a
b
a
b
a
b
Y’
a b
a b
N’(Y) = b a
b a
b b
a
b
b
b
a
b
a
a
b
b
μ=[1, 3, 5, 2, 4],
－1
λ=μ =[1,
4, 2, 5, 3]
Y’ [i] = Y [μ( i )],
Y [i] = Y’ [λ( i )]
b
b
b
a
a
1
3
5
2
4
一般的な文字列に対するLPSA
得られたλを入力列としてLPSAを行う。
1 4 2 5 3
1 4 2 5
4 2 5 3 1
2 5 3 1
N(λ)= 2 5 3 1 4 N’(λ) = 3 1 4 2
5 3 1 4 2
4 2 5 3
3 1 4 2 5
5 3 1 4
原系列を復元するには・・・
k
出力列θ , k, プライマリインデックス, Y’
3
4
5
1
2
BWTとLPSAの関係
(論文中の定理3.2)
Y を文字列、λ=λとすると、
N’i, j (Y) = Y’ [N’i, j (λ)]
a
a
N’(Y) = b
b
b
b
b
a
a
b
a
b
b
b
a
b
a
a
b
b
b
b
b
a
a
Y’
N’(λ) =
Y’ = a a b b b
1
2
3
4
5
4
5
1
2
3
2
3
4
5
1
5
1
2
3
4
3
4
5
1
2
定理3.2の直感的証明
a
b
N(Y)= a
b
b
b
a
b
b
a
a
b
b
a
b
b
b
a
b
a
b
a
b
a
b
Y’
N(λ)=
1
4
2
5
3
4
2
5
3
1
2
5
3
1
4
Y [i] = Y’ [λ( i )], N(Y) = Y’[N(λ)]
N’i, j (Y) = Y’ [N’i, j (λ)]
5
3
1
4
2
3
1
4
2
5

Download Report