BWT.JS
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
function RLE(text) {
var n = text.length;
var tmp,out="";
var i,count=0;
temp = text[0];
for (i=0;i<n;i++){
if(temp == text[i]){
count++;
}
else{
out += temp + count;
temp = text[i];
count = 1;
}
}
out += temp + count;
return out;
};
function suffixArray(text) {
n = text.length;
dict = new Object();
substr = new Array();
for(i = 0;i<n;i++){
dict[text.substring(i)]=i
substr.push(text.substring(i))
}
SA = new Array();
substr.sort();
for(i = 0; i < n ; i++){
SA.push(dict[substr[i]])
}
return SA;
};
function BWT(text){
bwt = ""
SA = suffixArray(text)
n = SA.length;
for (i = 0;i<n;i++){
j = SA[i]-1
if(j == -1) j = n -1
bwt += text.charAt(j)
}
return bwt;
}
function update(){
var text = str;
console.log("before:"+text);
console.log("after:"+RLE(text));
console.log("ratio:"+RLE(text).length / text.length);
bwt = BWT(text)
console.log("BWTstring:"+bwt);
console.log("BWTafter:"+RLE(bwt));
console.log("BWTratio:"+RLE(bwt).length / bwt.length);
return true;
}
var str='^BABABABANANABABABABABANANABABABABABANANABANANANAAHH|';
update();
JavaScript
INFO