逆走MTF for BWT

逆走MTFとは配列の値を小さい値に偏らせるMove to frontの逆走版です。つまり最後尾から先頭に向かって走査します。そんな事して良い事あるのかって? 勿論あります。MTFより小さい値が増える傾向にあるのです。すると圧縮しやすくなる。

実装編

例によってJavaScriptで書き散らかしておきます。

/*
変換関数
MTFBe(In,Out,Rank)
@In		:要素が0～255の数値配列
@Out	:変換先配列
@Rank	:復元用に使う配列.使用する数値を格納
返値	:要素が0～255の数値配列

逆変換関数
MTFBd(In,Out,Rank)
@In		:要素が0～255の数値配列
@Out	:逆変換先配列
@Rank	:復元用に使う配列
返値	:要素が0～255の数値配列
*/
function MTFBe(In,Out,Rank){
	for(var a=In.length,b,c=Rank.length=0;a;Rank[c]=b){
		for(b=In[--a];Rank[c]^b&&Rank[c]>-1;)c++;
		for(Out[a]=c;c;)Rank[c]=Rank[--c]
	}
	return Out
}
function MTFBd(In,Out,Rank){
	for(var a=0,b,c,d,l=In.length;a<l;Rank[c]=Out[a++]=d)
		for(b=In[a],d=Rank[c=0];c<b;)Rank[c]=Rank[++c];
	return Out
}

BWT + MTFB test

function BWT(T,U,n){n=n||T.length;
	for(var a=n,i,S=U||new Uint8Array(n),I=new Uint32Array(n);a;)I[--a]=a;
	I.sort(function(a,b,c,d){for(c=n;c--;)if(d=T[a++%n]-T[b++%n])return d});
	for(;a<n;S[a++]=T[--i])(i=I[a])||(S.i=a,i=n);
	return S
}
let T=Array.from("That that is is that that is not is not is that it it is",a=>a.charCodeAt()),
	U=BWT(T),
	enc=[],dec=[],rank=[];

MTFBe(U,enc,rank);
MTFBd(enc,dec,rank);
document.write("MTFB<br>",enc,"<hr>BWT<br>",dec,"<hr>rank<br>",rank)

rank表は別途保存しておかないと逆変換できないという欠点があります。

benchmark

それではBWT+MTF/MTFBによる圧縮限界値はどうなるのか? Canterbury Corpusのfileで試してみます

file	MTF	MTFB
alice29.txt	48679	48634
asyoulik.txt	44647	44600
fields.c	3091	3065

微々たる差ですがMTFBの方が圧縮しやすくなっています。binary fileや巨大fileだと顕著になるかも