|
1.什么是BWT 壓縮技術(shù)主要的工作方式就是找到重復(fù)的模式，進(jìn)行緊密的編碼。 BWT(Burrows–Wheeler_transform)將原來的文本轉(zhuǎn)換為一個(gè)相似的文本，轉(zhuǎn)換后使得相同的字符位置連續(xù)或者相鄰，之后可以使用其他技術(shù)如：Move-to-front transform 和 游程編碼 進(jìn)行文本壓縮。 2.BWT原理 2.1 BWT編碼 (1)首先，BWT先對需要轉(zhuǎn)換的文本塊，進(jìn)行循環(huán)右移，每次循環(huán)一位。可以知道長度為n的文本塊，循環(huán)n次后重復(fù)，這樣就得到看n個(gè)長度為n的字符串。如下圖中的“Rotate Right”列。（其中‘#’作為標(biāo)識符，不在文本塊的字符集中，這樣保證n個(gè)循環(huán)移位后的字符串均布相同。并且定義'#'小于字符集中的任意字符）。 (2)對循環(huán)移位后的n個(gè)字符串按照字典序排序。如下圖中的“Sorted (M)”列。 (3)記錄下“Sorted (M)”列中每個(gè)字符串的最后一個(gè)字符，組成了“L”列。(其中'F'列是“Sorted (M)”列中每個(gè)字符串的前綴) 
這樣，原來的字符串“banana#”就轉(zhuǎn)換為了“annb#aa”。在某些情況下，使用L列進(jìn)行壓縮會有更好的效果?！癓”列就是編碼的結(jié)果。 2.2 BWT解碼 因?yàn)檫M(jìn)行的是循環(huán)移位，且是循環(huán)左移注意下面的性質(zhì)： 1、L的第一個(gè)元素是Text中的最后一個(gè)元素 2、對于M中的每一行（第一行除外）第一個(gè)元素都是最后一個(gè)元素的下一個(gè)元素。 也就是說，對于文本塊而言，同一行中F是L的下一個(gè)元素，L是F的前一個(gè)元素。 這樣，就需要 (1)通過'F'列中的元素，找到他前面的字符，就是對應(yīng)的同一行“L”列； (2)通過“L”列中的元素，找到他在“F”列中的對應(yīng)字符位置。但是“L”中有3個(gè)字符a，如何對應(yīng)F中的3個(gè)a呢？因?yàn)長是F的前一個(gè)元素，多個(gè)具有相同前綴的字符串排序，去掉共同前綴后相對次序沒有變化。所有遇到多個(gè)相同的字符，相對位置不變； (3)轉(zhuǎn)到(1)，直到結(jié)束。 因?yàn)镕列是已經(jīng)排序的，可以從L列獲得，所有只需要保存L列就可以。從L列中的字符獲取在F列中的位置時(shí)，需要： (1)前綴和數(shù)組，記錄小于當(dāng)前字符的字符數(shù)個(gè)數(shù)。 (2)count計(jì)數(shù)，計(jì)算L中從開始位置到當(dāng)前字符位置等于該字符的字符數(shù)。(保證多個(gè)相同字符下'L'到“F”的相對位置不變)。 3.BWT文本塊編碼、解碼實(shí)例  1 #include 2 #include string> 3 #include 4 #include string.h> 5 using namespace std; 6 7 ///編碼，生成last數(shù)組 8 int getLastArray(char *lastArray,const string &str){ ///子串排序 9 int len=str.size();10 string array[len];11 12 for(int i=0;i<>){13 array[i] = str.substr(i);14 }15 sort(array,array+len);16 for(int i=0;i<>){17 lastArray[i] = str.at((2*len-array[i].size()-1)%len);18 }19 return 0;20 }21 22 int getCountPreSum(int *preSum,const string &str){23 memset(preSum,0,27*sizeof(int));24 for(int i=0;i<>){25 if(str.at(i) == '#')26 preSum[0]++;27 else28 preSum[str.at(i)-'a'+1]++;29 }30 31 for(int i=1;i27;i++)32 preSum[i] += preSum[i-1];33 return 0;34 }35 36 ///解碼，使用last數(shù)組，恢復(fù)原來的文本塊37 int regainTextFromLastArray(char *lastArray,char *reGainStr,int *preSum){38 int len=strlen(lastArray);39 int pos=0;40 char c;41 for(int i=len-1;i>=0;){42 reGainStr[i] = lastArray[pos];43 c = lastArray[pos];44 pos = preSum[c-'a']+count(lastArray,lastArray+pos,c);45 i--;46 }47 return 0;48 }49 50 int main (){51 string str('sdfsfdfdsdfgdfgfgfggfgdgfgd#');52 int preSum[27];53 int len=str.size();54 55 char *lastArray = new char[len+1];56 char *reGainStr = new char[len+1];57 lastArray[len]='\0';58 reGainStr[len]='\0';59 60 getCountPreSum(preSum,str);61 getLastArray(lastArray,str);62 regainTextFromLastArray(lastArray,reGainStr,preSum);63 64 cout' str: '<>endl;65 cout'lastArray : '<>endl;66 cout'reGainStr : '<>endl;67 68 delete lastArray;69 delete reGainStr;70 return 0;71 } 代碼執(zhí)行輸出： 
參考： http://en./wiki/Burrows%E2%80%93Wheeler_transform http://emily2ly./blog/742869 額外閱讀： MTF(Move-to-front transform)數(shù)據(jù)轉(zhuǎn)換 基于統(tǒng)計(jì)的壓縮算法：游程編碼
|
