數據壓縮演算法
RAR文件的擴展名是.rar（不區分大小寫，），MIME類型是application/x-rar-compressed。同樣是無損數據壓縮，RAR文件通常比ZIP文件壓縮比要高，但是壓縮速度較慢。因為RAR文件頭也要佔據一定空間，在數據壓縮餘地不大時，壓縮過的文件可能比原文件要大。RAR的一個主要優點是可以把文件壓縮目標分割到多個文件，並且很容易從這樣的分割的壓縮文件解壓出源文件。另外，RAR也支持緊縮格式，把所有文件壓縮到同一個數據區以加大壓縮比，代價是解壓一個單獨的文件時必須解壓其前面的所有文件。新的RAR的加密演算法使用的是AES，而舊的RAR的加密演算法是私有的。這兩種演算法都很難破解，所以在沒有密碼的情況下只能用字典暴力破解法來破解。RAR中也可以加入冗餘的修復信息，在文件損壞但是修復信息足夠完好時可以對壓縮包進行修復。
⑵ 數據無損壓縮技術到底怎麼實現的
無損數據壓縮（Lossless Compression）是指使用壓縮後的數據進行重構（或者叫做還原，解壓縮），重構後的數據與原來的數據完全相同；無損壓縮用於要求重構的信號與原始信號完全一致的場合。也就是說數據經過壓縮後信息不受損失，還能完全恢復到壓縮前的原樣。它和有損數據壓縮相對。這種壓縮通常壓縮比小於有損數據壓縮的壓縮比。
一個很常見的例子是磁碟文件的壓縮。根據目前的技術水平，無損壓縮演算法一般可以把普通文件的數據壓縮到原來的1/2～1/4。一些常用的無損壓縮演算法有霍夫曼（Huffman）演算法和LZW(Lenpel-Ziv & Welch）壓縮演算法。
⑶ Elasticsearch之數據壓縮演算法
Lucene使用FST演算法以位元組的方式來存儲所有的Term，重復利用Term Index的前綴和後綴，使Term Index小到可以放進內存，減少存儲空間，不過相對的也會佔用更多的cpu資源。FST在Lucene4.0以後的版本中用於快速定位所查單詞在字典中的位置。
Finite StateTranscers，簡稱 FST，通常中文譯作 有窮狀態轉換器 ，在語音識別和自然語言搜索、處理等方向被廣泛應用。
FST的功能類似於字典，可以表示成FST<Key, Value>的形式。其最大的特點是，可以用 O(length(key)) 的復雜度來找到key對應的value，也就是說查找復雜度僅取決於所查找的key長度。
假設我們現在要將以下term index映射到term dictionary的block序號：
最簡單的做法就是定義個Map<string, integer="">，大家找到自己的位置對應入座就好了，但從內存佔用少的角度想想，有沒有更優的辦法呢？答案就是FST。
對於經典FST演算法來說，要求 Key必須按字典序從小到大加入到FST 中。上面的例子中key已經排好序了。
按照以下步驟建立FST：
最後加入 dogs ，得到最後的結果：
從上圖可以看出，每條邊有兩條屬性，一個表示label（key的元素），另一個表示Value(out)。注意Value不一定是數字，還可一是另一個字元串，但要求Value必須滿足疊加性，如這里的正整數2 + 8 = 10。字元串的疊加行為： aa + b = aab。
建完這個圖之後，我們就可以很容易的查找出任意一個key的Value了。例如：查找dog，我們查找的路徑為：0 → 4 → 8 → 9。 其權值和為： 2 + 0 + 0 + 0 = 2。其中最後一個零表示 node[9].finalOut = 0。所以「dog」的Value為2。
Lucene除了上面說到用FST壓縮term index外，對posting list也會進行壓縮。
有人可能會有疑問：「posting list不是已經只存儲文檔id了嗎？還需要壓縮嗎？」。設想這樣一種情況，Lucene需要對一千萬個同學的性別進行索引，而世界上只有男/女這樣兩個性別，每個posting list都會有數百萬個文檔id，這里顯然有很大的壓縮空間與價值，對於減少索引尺寸有非常重要的意義。
Lucene使用 Frame Of Reference 編碼來實現對posting list壓縮，其思路簡單來說就是： 增量編碼壓縮，將大數變小數，按位元組存儲 。
示意圖如下：
除此之外，Lucene在執行filter操作還會使用一種叫做 Roaring bitmaps 的數據結構來存儲文檔ID，同樣可以達到壓縮存儲空間的目的。
說到Roaring bitmaps，就必須先從bitmap說起。bitmap是一種很直觀的數據結構，假設有某個posting list：
對應的bitmap就是：
非常直觀，用0/1表示某個值是否存在，比如10這個值就對應第10位，對應的bit值是1，這樣用一個位元組就可以代表8個文檔id，舊版本(5.0之前)的Lucene就是用這樣的方式來壓縮的，但這樣的壓縮方式仍然不夠高效，如果有1億個文檔，那麼需要12.5MB的存儲空間，這僅僅是對應一個索引欄位(我們往往會有很多個索引欄位)。於是有人想出了Roaring bitmaps這樣更高效的數據結構。Roaring bitmaps壓縮的原理可以理解為，與其保存100個0，佔用100個bit，還不如保存0一次，然後聲明這個0有100個。
Bitmap的缺點是存儲空間隨著文檔個數線性增長，Roaring bitmaps需要打破這個魔咒就一定要用到某些指數特性：
將posting list按照65535為界限分塊，比如第一塊所包含的文檔id范圍在0 65535之間，第二塊的id范圍65536 131071，以此類推。再用<商，余數>的組合表示每一組id，這樣每組里的id范圍都在0~65535內了，剩下的就好辦了，既然每組id不會變得無限大，那麼我們就可以通過最有效的方式對這里的id存儲。
為什麼是以65535為界限呢？
程序員的世界裡除了1024外，65535也是一個經典值，因為它=2^16-1，正好是用2個位元組能表示的最大數，一個short的存儲單位，注意到上圖里的最後一行「If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value」，如果是大塊，用節省點用bitset存，小塊就豪爽點，2個位元組我也不計較了，用一個short[]存著方便。
那為什麼用4096來區分大塊還是小塊呢？
都說程序員的世界是二進制的，4096*2bytes ＝ 8192bytes < 1KB, 磁碟一次尋道可以順序把一個小塊的內容都讀出來，再大一位就超過1KB了，需要兩次讀。
一種常見的壓縮存儲時間序列的方式是把多個數據點合並成一行。Opentsdb支持海量數據的一個絕招就是定期把很多行數據合並成一行，這個過程叫compaction。類似的vivdcortext使用mysql存儲的時候，也把一分鍾的很多數據點合並存儲到mysql的一行里以減少行數。
這個過程可以示例如下：
合並之後就變成了：
可以看到，行變成了列了。每一列可以代表這一分鍾內一秒的數據。
Elasticsearch有一個功能可以實現類似的優化效果，那就是Nested Document。我們可以把一段時間的很多個數據點打包存儲到一個父文檔里，變成其嵌套的子文檔。示例如下：
可以打包成：
這樣可以把數據點公共的維度欄位上移到父文檔里，而不用在每個子文檔里重復存儲，從而減少索引的尺寸。
在存儲的時候，無論父文檔還是子文檔，對於 Lucene 來說都是文檔，都會有文檔 Id。但是對於嵌套文檔來說，可以保存起子文檔和父文檔的文檔 id 是連續的，而且父文檔總是最後一個。有這樣一個排序性作為保障，那麼有一個所有父文檔的 posting list 就可以跟蹤所有的父子關系。也可以很容易地在父子文檔 id 之間做轉換。把父子關系也理解為一個 filter，那麼查詢時檢索的時候不過是又 AND 了另外一個 filter 而已。前面我們已經看到了 Elasticsearch 可以非常高效地處理多 filter 的情況，充分利用底層的索引。
使用了嵌套文檔之後，對於 term 的 posting list 只需要保存父文檔的 doc id 就可以了，可以比保存所有的數據點的 doc id 要少很多。如果我們可以在一個父文檔里塞入 50 個嵌套文檔，那麼 posting list 可以變成之前的 1/50。
⑷ 數據壓縮
數據壓縮技術主要研究數據的表示、傳輸和轉換方法，目的是減少數據所佔據的存儲空間和縮短數據傳輸時所需要的時間。
衡量數據壓縮的3個主要指標：一是壓縮前後所需的信息存儲量之比要大；二是實現壓縮的演算法要簡單，壓縮、解壓縮速度快，要盡可能做到實時壓縮和解壓縮；三是恢復效果要好，要盡可能完全恢復原始數據。
數據壓縮主要應用於兩個方面。一是傳輸：通過壓縮發送端的原始數據，並在接收端進行解壓恢復，可以有效地減少傳輸時間和增加信道帶寬。二是存儲：在存儲時壓縮原始數據，在使用時進行解壓，可大大提高存儲介質的存儲量。
數據壓縮按照壓縮的失真度分成兩種類型：一種叫作無損壓縮，另一種叫作有損壓縮。
無損壓縮是指使用壓縮後的數據進行重構（或者叫作還原、解壓縮），重構後的數據與原來的數據完全相同；無損壓縮用於要求重構的信號與原始信號完全一致的場合。一個很常見的例子是磁碟文件的壓縮。根據目前的技術水平，無損壓縮演算法一般可以把普通文件的數據壓縮到原來的1/4～1/2。一些常用的無損壓縮演算法有霍夫曼（Huffman）演算法、算術演算法、遊程演算法和LZW（Lenpel-Ziv ＆ Welch）壓縮演算法。
1）霍夫曼演算法屬於統計式壓縮方法，其原理是根據原始數據符號發生的概率進行編碼。在原始數據中出現概率越高的符合，相應的碼長越短，出現概率越少的符合，其碼長越長。從而達到用盡可能少的符號來表示原始數據，實現對數據的壓縮。
2）算術演算法是基於統計原理，無損壓縮效率最高的演算法。即將整段要壓縮的數據映射到一段實數半封閉的范圍［0，1）內的某一區段。該區段的范圍或寬度等於該段信息概率。即是所有使用在該信息內的符號出現概率全部相乘後的概率值。當要被編碼的信息越來越長時，用來代表該信息的區段就會越來越窄，用來表示這個區段的位就會增加。
3）遊程演算法是針對一些文本數據特點所設計的壓縮方法。主要是去除文本中的冗餘字元或位元組中的冗餘位，從而達到減少數據文件所佔的存儲空間。壓縮處理流程類似於空白壓縮，區別是在壓縮指示字元之後加上一個字元，用於表明壓縮對象，隨後是該字元的重復次數。本演算法具有局限性，很少單獨使用，多與其他演算法配合使用。
4）LZW演算法的原理是用字典詞條的編碼代替在壓縮數據中的字元串。因此字典中的詞條越多，壓縮率越高，加大字典的容量可以提高壓縮率。字典的容量受計算機的內存限制。
有損壓縮是指使用壓縮後的數據進行重構，重構後的數據與原來的數據有所不同，但不影響人對原始資料表達的信息造成誤解。有損壓縮適用於重構信號不一定非要和原始信號完全相同的場合。例如，圖像和聲音的壓縮就可以採用有損壓縮，因為其中包含的數據往往多於我們的視覺系統和聽覺系統所能接收的信息，丟掉一些數據而不至於對聲音或者圖像所表達的意思產生誤解，但可大大提高壓縮比。
⑸ 壓縮演算法原理
哈夫曼
哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。
哈夫曼演算法在改變任何符號二進制編碼引起少量密集表現方面是最佳的。然而，它並不處理符號的順序和重復或序號的序列。
2.1 原理
我不打算探究哈夫曼編碼的所有實際的細節，但基本的原理是為每個符號找到新的二進製表示，從而通常符號使用很少的位，不常見的符號使用較多的位。
簡短的說，這個問題的解決方案是為了查找每個符號的通用程度，我們建立一個未壓縮數據的柱狀圖；通過遞歸拆分這個柱狀圖為兩部分來創建一個二叉樹，每個遞歸的一半應該和另一半具有同樣的權（權是 ∑ N K =1 符號數 k , N 是分之中符號的數量，符號數 k 是符號 k出現的次數 ）
這棵樹有兩個目的：
1． 編碼器使用這棵樹來找到每個符號最優的表示方法
2． 解碼器使用這棵樹唯一的標識在壓縮流中每個編碼的開始和結束，其通過在讀壓縮數據位的時候自頂向底的遍歷樹，選擇基於數據流中的每個獨立位的分支，一旦一個到達葉子節點，解碼器知道一個完整的編碼已經讀出來了。
壓縮後的數據流是 24 位（三個位元組），原來是 80 位（ 10 個位元組）。當然，我應該存儲哈夫曼樹，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數據流比輸入的流數據量大。這是相對較短的數據上的副作用。對於大數據量來說，上面的哈夫曼樹就不佔太多比例了。
解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左 / 右分支，每次碰到一個葉子節點的時候，就可以將對應的位元組寫到解壓輸出流中，然後再從根開始遍歷。
2.2 實現
哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實現。
這個實現的基本缺陷是：
1． 慢位流實現
2． 相當慢的解碼（比編碼慢）
3． 最大的樹深度是 32 （編碼器在任何超過 32 位大小的時候退出）。如果我不是搞錯的話，這是不可能的，除非輸出的數據大於 2 32位元組。
另一方面，這個實現有幾個優點：
1． 哈夫曼樹以一個緊密的形式每個符號要求 12 位（對於 8 位的符號）的方式存儲，這意味著最大的頭為 384 。
2． 編碼相當容易理解
哈夫曼編碼在數據有噪音的情況（不是有規律的，例如 RLE ）下非常好，這中情況下大多數基於字典方式的編碼器都有問題。
⑹ 數據壓縮演算法可分無損壓縮和（ ）壓縮兩種
有損壓縮。無損壓縮是指對原數據毫無損害完全保留，有損是指犧牲一部分數據真實性且對原數據影響不大的情況下，換取更小的壓縮後存儲空間。
⑺ 數據的壓縮方法有幾種
總的來說，數據壓縮方法可分為三類：靜態、動態及混合方法。所謂靜態方法就是在 信文傳送之前源文集和碼子集之間的映射關系就已確定，以後給定信文無論什麼時刻出現 在信文集中總被表示為相同的碼字。而動態方法是在信文集和碼子集之間建立一種隨著時 間的變化而變化的映射關系，動態方法也稱為自適應編碼，即它們不斷地修改源信文集與 碼字的對就關系以便更好地適應於信文集特徵隨時間的變化。所有的自適應方法都是一次 操作方法，即只需對源文集掃描一次。靜態編碼需要二次操作：第一次計算概率並確定映 射，第二次傳送碼字。當一個演算法既不完全靜態又不完全動態時，就稱為混合方法。一種 簡單的混合方法是讓發送方和接收方保持一致的含Ｋ個靜態碼子的編碼本。每次傳送信息 時，發送方必須選擇預先約定的Ｋ個碼字中的一個，並通知接收方應解碼。
⑻ 數據壓縮技術一般分哪兩種各有什麼特點
數據壓縮可分成兩種類型，一種叫做無損壓縮，另一種叫做有損壓縮。
無損壓縮是指使用壓縮後的數據進行重構(或者叫做還原，解壓縮)，重構後的數據與原來的數據完全相同；無損壓縮用於要求重構的信號與原始信號完全一致的場合。一個很常見的例子是磁碟文件的壓縮。根據目前的技術水平，無損壓縮演算法一般可以把普通文件的數據壓縮到原來的1/2～1/4。一些常用的無損壓縮演算法有霍夫曼(Huffman)演算法和LZW(Lenpel-Ziv & Welch)壓縮演算法。
有損壓縮是指使用壓縮後的數據進行重構，重構後的數據與原來的數據有所不同，但不影響人對原始資料表達的信息造成誤解。有損壓縮適用於重構信號不一定非要和原始信號完全相同的場合。例如，圖像和聲音的壓縮就可以採用有損壓縮，因為其中包含的數據往往多於我們的視覺系統和聽覺系統所能接收的信息，丟掉一些數據而不至於對聲音或者圖像所表達的意思產生誤解，但可大大提高壓縮比。
⑼ 二進制壓縮演算法有哪些
二進制數據壓縮演算法二進制是計算技術中廣泛採用的一種數制。二進制數據是用0和1兩個數碼來表示的數。它的基數為2，進位規則是「逢二進一」，借位規則是「借一當二」，由18世紀德國數理哲學大師萊布尼茲發現。當前的計算機系統使用的基本上是二進制系統，數據在計算機中主要是以補碼的形式存儲的。計算機中的二進制則是一個非常微小的開關，用「開」來表示1，「關」來表示0。
20世紀被稱作第三次科技革命的重要標志之一的計算機的發明與應用，因為數字計算機只能識別和處理由『0』。『1』符號串組成的代碼。其運算模式正是二進制。19世紀愛爾蘭邏輯學家喬治布爾對邏輯命題的思考過程轉化為對符號「0『』。『』1『』的某種代數演算，二進制是逢2進位的進位制。0、1是基本算符。因為它只使用0、1兩個數字元號，非常簡單方便，易於用電子方式實現。
二進制壓縮 - 演算法
二進制壓縮
在編程時遇到每個數據只有兩種狀態，且 dfs 或者 bfs 時遍歷時間復雜度高時，可以採用二進制壓縮數據，尤其是二維數組。LZFSE
1，zlib和gzip都對deflate進行了封裝，比deflate多了數據頭和尾
1，蘋果開源了新的無損壓縮演算法 LZFSE ，該演算法是去年在iOS 9和OS X 10.10中 引入 的。按照蘋果公司的說法，LZFE的壓縮增益和ZLib level 5相同，但速度要快2~3倍，能源效率也更高。
LZFSE基於Lempel-Ziv，並使用了 有限狀態熵編碼，後者基於Jarek Duda在
非對稱數字系統（ANS）方面所做的熵編碼工作。簡單地講，ANS旨在「終結速度和比率的平衡」，既可以用於精確編碼，又可以用於快速編碼，並且具有數據加密功能。使用ANS代替更為傳統的
Huffman和 算術編碼方法的壓縮庫 越來越多，LZFSE就位列其中。
顯然，LZFSE的目標不是成為最好或最快的演算法。事實上，蘋果公司指出，
LZ4的壓縮速度比LZFSE快，而 LZMA提供了更高的壓縮率，但代價是比Apple
SDK提供的其他選項要慢一個數量級。當壓縮率和速度幾乎同等重要，而你又希望降低能源效率時，LZFSE是蘋果推薦的選項。
GitHub上提供了LZFSE的參考實現。在MacOS上構建和運行一樣簡單：
$ xcodebuild install DSTROOT=/tmp/lzfse.dst
如果希望針對當前的iOS設備構建LZFSE，可以執行：
xcodebuild -configuration 「Release」 -arch armv7 install DSTROOT=/tmp/lzfse.dst
除了 API文檔之外，蘋果去年還提供了一個 示例項目，展示如何使用LZFSE 進行塊和流壓縮，這是一個實用的LZFSE入門資源。
LZFSE是在谷歌 brotli之後發布的，後者在去年開源。與LZFSE相比，brotli 似乎是針對一個不同的應用場景進行了優化，比如壓縮靜態Web資產和Android APK，在這些情況下，壓縮率是最重要的。
⑽ 什麼是壓縮演算法
LZW壓縮演算法的基本概念：LZW壓縮有三個重要的對象：數據流(CharStream)、編碼流(CodeStream)和編譯表(String Table)。在編碼時，數據流是輸入對象（文本文件的據序列），編碼流就是輸出對象（經過壓縮運算的編碼數據）；在解碼時，編碼流則是輸入對象，數據流是輸出對象；而編譯表是在編碼和解碼時都須要用藉助的對象。字元(Character)：最基礎的數據元素，在文本文件中就是一個位元組，在光柵數據中就是一個像素的顏色在指定的顏色列表中的索引值；字元串(String)：由幾個連續的字元組成； 前綴(Prefix)：也是一個字元串，不過通常用在另一個字元的前面，而且它的長度可以為0；根(Root)：一個長度的字元串；編碼(Code)：一個數字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值；圖案：一個字元串，按不定長度從數據流中讀出,映射到編譯表條目. LZW壓縮演算法的基本原理：提取原始文本文件數據中的不同字元，基於這些字元創建一個編譯表，然後用編譯表中的字元的索引來替代原始文本文件數據中的相應字元，減少原始數據大小。看起來和調色板圖象的實現原理差不多，但是應該注意到的是，我們這里的編譯表不是事先創建好的，而是根據原始文件數據動態創建的，解碼時還要從已編碼的數據中還原出原來的編譯表.