最近在看《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á)到了編碼的目的虏冻。