兩個(gè)有意思的編碼算法

最近在看《Column-Stores vs. Row-Stores: How Different Are They Really?》孽拷, 發(fā)現(xiàn)里面提到了列式數(shù)據(jù)庫(kù)使用了編碼(壓縮)算法來(lái)減少查詢時(shí)候的I/O消耗瑞侮,因此找了兩種有意思的編碼算法: Run length encodingDictionary 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è)字典編碼:

字典編碼在《潛伏》中的應(yīng)用

字典編碼分為兩類朽缎,分類的依據(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á)到了編碼的目的虏冻。

參考資料

  1. Column-Stores vs. Row-Stores: How Different Are They Really?
  2. Run Length Encoding
  3. Dictionary encoding
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市弹囚,隨后出現(xiàn)的幾起案子厨相,更是在濱河造成了極大的恐慌,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件蛮穿,死亡現(xiàn)場(chǎng)離奇詭異庶骄,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)践磅,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門单刁,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人府适,你說(shuō)我怎么就攤上這事羔飞。” “怎么了檐春?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵逻淌,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我疟暖,道長(zhǎng)卡儒,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任誓篱,我火速辦了婚禮,結(jié)果婚禮上凯楔,老公的妹妹穿的比我還像新娘窜骄。我一直安慰自己,他們只是感情好摆屯,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布邻遏。 她就那樣靜靜地躺著,像睡著了一般虐骑。 火紅的嫁衣襯著肌膚如雪准验。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天廷没,我揣著相機(jī)與錄音糊饱,去河邊找鬼。 笑死颠黎,一個(gè)胖子當(dāng)著我的面吹牛另锋,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播狭归,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼夭坪,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了过椎?” 一聲冷哼從身側(cè)響起室梅,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后亡鼠,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體赏殃,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年拆宛,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了嗓奢。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡浑厚,死狀恐怖股耽,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情钳幅,我是刑警寧澤物蝙,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站敢艰,受9級(jí)特大地震影響诬乞,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜钠导,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一震嫉、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧牡属,春花似錦票堵、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至措伐,卻和暖如春特纤,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背侥加。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工捧存, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人担败。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓矗蕊,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親氢架。 傳聞我的和親對(duì)象是個(gè)殘疾皇子傻咖,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • Spring Cloud為開發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見(jiàn)模式的工具(例如配置管理,服務(wù)發(fā)現(xiàn)岖研,斷路器卿操,智...
    卡卡羅2017閱讀 134,716評(píng)論 18 139
  • 個(gè)人筆記警检,方便自己查閱使用 Py.LangSpec.Contents Refs Built-in Closure ...
    freenik閱讀 67,715評(píng)論 0 5
  • 編碼問(wèn)題一直困擾著開發(fā)人員,尤其在 Java 中更加明顯害淤,因?yàn)?Java 是跨平臺(tái)語(yǔ)言扇雕,不同平臺(tái)之間編碼之間的切換...
    x360閱讀 2,483評(píng)論 1 20
  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序:基本語(yǔ)法,類相關(guān)的語(yǔ)法窥摄,內(nèi)部類的語(yǔ)法镶奉,繼承相關(guān)的語(yǔ)法,異常的語(yǔ)法崭放,線程的語(yǔ)...
    子非魚_t_閱讀 31,665評(píng)論 18 399
  • 精力充沛的孩子,經(jīng)常不顧父母的感受决摧。他們會(huì)在沙發(fā)上跳來(lái)跳去亿蒸;拿個(gè)足球在客廳里踢;或者當(dāng)家里來(lái)客人的時(shí)候大喊大...
    方策家族閱讀 184評(píng)論 1 3