最近在看《Column-Stores vs. Row-Stores: How Different Are They Really?》孽拷， 發(fā)現(xiàn)里面提到了列式數(shù)據(jù)庫(kù)使用了編碼(壓縮)算法來(lái)減少查詢時(shí)候的I/O消耗瑞侮，因此找了兩種有意思的編碼算法: Run length encoding和Dictionary encoding找出來(lái)學(xué)習(xí)了一下楼肪。
Run Length Encoding
Run Length Encoding(RLE)是無(wú)損壓縮的一種始鱼，這種壓縮方法在數(shù)據(jù)連續(xù)重復(fù)的情況較多的時(shí)候比較有用千埃，比如下面的數(shù)據(jù):
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
利用RLE會(huì)被壓縮成:
12W1B12W3B24W1B14W
意思是說(shuō): 12個(gè)W，一個(gè)B赠堵，12個(gè)W, 3個(gè)B小渊，24個(gè)W，1個(gè)B茫叭，14個(gè)W酬屉。原來(lái)需要67個(gè)字符表示的字符串，利用RLE之后只需要18個(gè)字符揍愁。
Dictionary Encoding
字典編碼也稱為替換編碼呐萨，也是無(wú)損數(shù)據(jù)壓縮的一種。它維護(hù)一個(gè)字典莽囤，在編碼的時(shí)候把要編碼的字符串轉(zhuǎn)換成字典里面這個(gè)字母對(duì)應(yīng)的下標(biāo)谬擦，而解碼的時(shí)候這從這個(gè)下標(biāo)還原成原來(lái)的字符。我們余則成同志跟組織聯(lián)系使用的就是這個(gè)字典編碼：
字典編碼分為兩類朽缎，分類的依據(jù)是所依賴的字典是靜態(tài)的還是動(dòng)態(tài)的惨远。上面的例子里面則成通知使用的書(好像是《康熙字典》之類的)就是靜態(tài)的字典。靜態(tài)字典應(yīng)用的場(chǎng)景一般是要編碼的字符比較固定话肖，并且內(nèi)容很長(zhǎng)锨络；跟靜態(tài)字典相對(duì)應(yīng)的是動(dòng)態(tài)字典, 所謂的動(dòng)態(tài)字典是在編碼的過(guò)程中動(dòng)態(tài)構(gòu)建出來(lái)的，一開始字典是空的狼牺，輸入的字符越來(lái)越多羡儿，這個(gè)字典也就越來(lái)越豐富。(具體的構(gòu)建過(guò)程就不詳細(xì)介紹了)
字典編碼的關(guān)鍵是編碼之后輸出的不再是原來(lái)的字符了是钥，而是代表這個(gè)字符的引用(通常是下標(biāo))掠归，而且可以把多個(gè)字符編碼成一個(gè)數(shù)字，因?yàn)閿?shù)字比字符串占用的空間小悄泥，因此也就達(dá)到了編碼的目的虏冻。
