- 讀寫二進制資料
- 基因組資料的壓縮
- 游程編碼
- 位圖
- 霍夫曼壓縮
- 前綴碼和單詞查找樹
- 構造前綴碼的單詞查找樹
- 寫入和讀取單詞查找樹
- 使用前綴碼壓縮
- 使用前綴碼展開
- LZW壓縮
- LZW的單詞查找樹
- LZW的單詞查找樹
- LZW壓縮的展開
對資料進行壓縮能夠有效節省保存資訊所需的空間和傳輸資訊所需的時間，雖然計算機存盤設備的成本在不斷降低，但由于需要存盤的資料在飛速膨脹，壓縮演算法仍有非常重要的意義，因為與以往相比，資料被壓縮后節省的空間會更大，
讀寫二進制資料
現代計算機系統中處理的所有型別的資料最終都是用二進制表示的，可以將它們都看作一串位元的序列，
資料壓縮分為無損壓縮和有損壓縮，前者在壓縮、展開后不會丟失任何資訊，但后者不然，有損壓縮常被用于影像、視頻、音樂的壓縮，對于無損壓縮演算法，評價的標準為壓縮率，壓縮率=壓縮后體積/原始體積；對于有損壓縮演算法，評價標準除了壓縮率外，還有主觀的質量感受等，
接下來只討論無損壓縮演算法，
之前的演算法設計輸入輸出時，使用的都是基于java基礎方法封裝的StdIn和StdOut，它們處理的是由Unicode編碼的字符流；但由于壓縮演算法會涉及到對位元流的操作，所以接下來使用BinaryStdIn和BinaryStdOut，BinaryStdIn.readBoolean()方法會從輸入中讀取一個位元并回傳為布林值，BinaryStdOut.write(boolean b)方法則會向輸出中寫入一個位元，
基因組資料的壓縮
接下來從初級的基因組壓縮演算法開始，因為表示基因組的字符集只含有A C T G四個字符，這種方法也適用于字符集大小固定且數量有限的場合，
如果將這四個字符直接用ASCII編碼，需要4×8=32位，但其實只需要用兩個位就可以表示4個值（2^2=4），這樣4個字符只需要2×4=8位就可以了，壓縮率=8/32=25%，
由此可得對基因組資料的壓縮方法：
public static void compress(){
Alphabet DNA=new Alphabet("ACTG");
String s=BinaryStdIn.readString();
int N=s.length();
BinaryStdOut.write(N);
for(int i=0;i<N;i++){
int d=DNA.toIndex(s.charAt(i));
BinaryStdOut.write(d,DNA.lgR());
}
BinaryStdOut.close();
}
實體化Alphabet類時，指定字符集只有ACTG這四個，DNA.lgR()就等于2，每次輸出2個位元，比如遇到字符A，就用0表示，二進制編碼為00，字符B用1表示，二進制編碼為01等等，
展開時，每次讀取2個位元，轉換為整型數字，然后根據這個數字去字符集中取得對應的字符，
public static void expand(){
Alphabet DNA=new Alphabet("ACTG");
int w=DNA.lgR();
int N=BinaryStdIn.readInt();
for(int i=0;i<N;i++){
char c=BinaryStdIn.readChar(w);
StdOut.println("c="+c);
char e=DNA.toChar(c);
StdOut.println("e="+e);
BinaryStdOut.write(DNA.toChar(c));
}
BinaryStdOut.close();
}
游程編碼
位元流中最簡單的冗余形式就是一長串重復的位元，游程編碼就是利用這種冗余來壓縮資料的經典方法，在對位圖的壓縮中有很好的效果，
位圖
位圖經常用于保存影像和掃描檔案，下面是一張最簡單的位圖，解析度為32×48，影像為一個“q”字符，用按行排列的位元流來表示位圖資料，所以這張簡單的位圖是沒有顏色資訊的，或者說只有兩種顏色，
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000011111110000000000
00000000000011111111111111100000
00000000001111000011111111100000
00000000111100000000011111100000
00000001110000000000001111100000
00000011110000000000001111100000
00000111100000000000001111100000
00001111000000000000001111100000
00001111000000000000001111100000
00011110000000000000001111100000
00011110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111110000000000000001111100000
00111111000000000000001111100000
00111111000000000000001111100000
00011111100000000000001111100000
00011111100000000000001111100000
00001111110000000000001111100000
00001111111000000000001111100000
00000111111100000000001111100000
00000011111111000000011111100000
00000001111111111111111111100000
00000000011111111111001111100000
00000000000011111000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000001111100000
00000000000000000000011111110000
00000000000000000011111111111100
00000000000000000111111111111110
00000000000000000000000000000000
00000000000000000000000000000000
取這個位圖中的第5行來分析
00000000001111000011111111100000
這條長度32的字串中，含有：10個0 - 4個1 - 4個0 - 9個1 - 5個0，所有的位元字串都是類似這樣，0和1交替出現，所以對于這條字串，就可以編碼為10，4，4，9，5，如果用4位元表示長度，并以連續的0作為開頭，就可以得到一個20位長的字串（不包含逗號）：1010,0100,0100,1001,0101，壓縮率=20/32=62.5%，
4位編碼能表示的值只有0到15，在實際的應用中是不夠的，所以使用8位編碼，可以表示0-255之間的游程長度，如果游程的長度超過256，就插入一個長度為0的游程，這樣可以確保所有的游程長度都不超過256，
使用游程編碼壓縮的代碼如下：
public static void compress() {
char cnt = 0;
boolean b, old = false;
while (!BinaryStdIn.isEmpty()) {
b = BinaryStdIn.readBoolean();
if (b != old) {
BinaryStdOut.write(cnt);
cnt = 0;
old = !old;
} else {
if (cnt == 255) {
BinaryStdOut.write(cnt);
cnt = 0;
BinaryStdOut.write(cnt);
}
}
cnt++;
}
BinaryStdOut.write(cnt);
BinaryStdOut.close();
}
演算法會逐個讀取位元位，如果它和上一個位元相同，就把游程計數器cnt加1；如果計數器已滿，就將其輸出為編碼，然后計數器歸零，并輸出一個長度為0的游程來分割過長的相同編碼；如果它和上一個位元不同，就將計數器的值輸出然后歸零，
展開的代碼為：
public static void expand() {
boolean b = false;
while (!BinaryStdIn.isEmpty()) {
char cnt = BinaryStdIn.readChar();
for (int i = 0; i < cnt; i++)
BinaryStdOut.write(b);
b = !b;
}
BinaryStdOut.close();
}
展開時每次讀取一個游程的長度（8位編碼），先輸出位元0，按照游程指定的長度輸出完畢后，切換狀態，繼續輸出，
游程編碼被廣泛用于位圖的壓縮，這種壓縮方式還有一項特殊的優勢在于，隨著位圖解析度的提高，它的效果也會大大提高，如果位圖解析度增加一倍，它的總位元數將變為原來的4倍，但游程的數量只會變為原來的2倍，因為橫向的位元數增加不會影響游程的數量，只會影響游程的長度，這樣壓縮后的位元數量變為約原來的2倍，所以壓縮率減半，
但游程編碼只在游程較長時效果較好，如果游程很短，這種演算法可能反而會增加位元數，
霍夫曼壓縮
前綴碼和單詞查找樹
雖然游程編碼在許多場景非常有效，但有的時候需要壓縮的資料特征并不具有較長的游程，比如英文檔案等自然語言檔案，霍夫曼壓縮演算法和LZW壓縮演算法對這種特征的資料也能取得很好的效果，
霍夫曼壓縮的主要思想是，放棄文本檔案的普通保存方式，不再使用7位或8位二進制數表示一個字符，而是用較少的位元表示出現頻率高的字符，用較多的位元表示出現頻率低的字符，
比如對于字串 A B R A C A D A B R A，如果使用7位的ASCII字符編碼，那么只出現了1次的D和出現了5次的A，占用的位元數是一樣的，
如果能這樣編碼
A:0
B:1
R:00
C:01
D:10
那么這個字串的編碼就是0 1 00 0 01 0 10 0 1 00 0，只需要15位，而ASCII碼需要77位，但這種方法并不完整，因為它需要空格來區分字符，如果沒有空格，就會造成歧義，比如01，除了可以解碼為AB，還可以解碼為C，
如果能夠讓所有字符編碼都不會成為其他字符編碼的前綴，就不需要專門的分隔符了，含有這種性質的編碼規則叫做前綴碼，
前綴碼的一種簡便表示方法就是單詞查找樹，
如圖所示的單詞查找樹，就是一種字符的編碼方式，它的左鏈接表示0，右鏈接表示1，每個字符的編碼就是從根結點到該結點的路徑表示的位元字串，
不同的單詞查找樹表示的前綴碼的壓縮率不相同，霍夫曼壓縮演算法構造的單詞查找樹是最優的，
霍夫曼壓縮分為5個步驟：
- 壓縮時：
- 構造前綴碼的單詞查找樹
- 將樹以位元組流的形式輸出
- 使用構造的樹將位元組流編碼為位元流
- 展開時：
- 讀取單詞查找樹
- 使用該樹將位元流解碼
構造前綴碼的單詞查找樹
單詞查找樹的結點
public static class Node implements Comparable<Node> {
private char ch;
private int freq;
private final Node left, right;
Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
public boolean isLeaf() {
return left == null && right == null;
}
public int compareTo(Node that) {
return this.freq - that.freq;
}
}
這份樹結點的實作中，除了用于表示左右結點的left、right和表示葉子節點中字符的ch，還增加了一個整型變數freq，用于統計字符出現的頻率，
構造單詞查找樹
霍夫曼演算法是一個兩輪演算法,為了構造單詞查找樹，演算法會先讀取一次整個輸入流，得到每個字符的頻率，
構造的第一步是創建一片由許多只有一個結點的樹所組成的森林，每棵樹都表示輸入流中的一個字符，然后自底向上根據頻率構造單詞查找樹，找到兩個頻率最小的結點，創建一個包含著兩個子結點的新結點，新結點的頻率值為兩個子結點的頻率值之和，不斷重復這個程序，直到所有子樹都合并為一顆樹，
private static Node buildTrie(int[] freq) {
MinPQ<Node> pq = new MinPQ<Node>();
for (char c = 0; c < R; c++)
if (freq[c] > 0)
pq.insert(new Node(c, freq[c], null, null));
while (pq.size() > 1) {
Node x = pq.delMin();
Node y = pq.delMin();
Node parent = new Node('\0', x.freq + y.freq, x, y);
pq.insert(parent);
}
return pq.delMin();
}
用最小優先佇列可以方便快速的找到最小結點，
寫入和讀取單詞查找樹
寫入
霍夫曼壓縮演算法需要在壓縮時將樹寫入位元流并在展開時讀取它，寫入時，對單詞查找樹進行前序遍歷，遇到內部結點時，寫入位元0，遇到葉子結點時，寫入位元1，緊接著是這個結點中字符的8為ASCII碼，
private static void writeTrie(Node x) {
if (x.isLeaf()) {
BinaryStdOut.write(true);
BinaryStdOut.write(x.ch);
return;
}
BinaryStdOut.write(false);
writeTrie(x.left);
writeTrie(x.right);
}
讀取
在讀取位元字串，重新構造單詞查找樹時，首先讀取一個位元以確定當前結點的型別，如果是葉子結點，就讀取字符并創建一個葉子節點，如果是內部結點，就創建一個內部結點并遞回地構造它的左右子樹，
private static Node readTrie() {
if (BinaryStdIn.readBoolean())
return new Node(BinaryStdIn.readChar(), 0, null, null);
return new Node('\0', 0, readTrie(), readTrie());
}
使用前綴碼壓縮
在壓縮時，首先根據單詞查找樹定義的前綴碼來構造編譯表，為了提升效率，使用由字符索引的陣列st，st的大小為字符集的大小，st中保存了單詞查找樹中包含的字符對應的位元字串，
在構造編譯表時，會遞回遍歷整顆樹，并為每個結點維護了一條從跟結點到它的路徑所對應的二進制字串，0表示左鏈接，1表示右鏈接，每當到達一個葉子節點時，就將結點的編碼設為它對應的位元字串，
private static void buildCode(String[] st, Node x, String s) {
if (x.isLeaf()) {
st[x.ch] = s;
return;
}
buildCode(st, x.left, s + '0');
buildCode(st, x.right, s + '1');
}
編譯表建立后，壓縮的程序，就成了查找樹如字符所對應的編碼并寫入的程序，
public static void compress() {
String s = BinaryStdIn.readString();
char[] input = s.toCharArray();
int[] freq = new int[R];
for (int i = 0; i < input.length; i++)
freq[input[i]]++;
Node root = buildTrie(freq);
String[] st = new String[R];
buildCode(st, root, "");
writeTrie(root);
BinaryStdOut.write(input.length);
for (int i = 0; i < input.length; i++) {
String code = st[input[i]];
for (int j = 0; j < code.length(); j++)
if (code.charAt(j) == '1')
BinaryStdOut.write(true);
else
BinaryStdOut.write(false);
}
BinaryStdOut.close();
}
使用前綴碼展開
在展開時，首先使用前述方法從位元流中還原單詞查找樹，然后根據位元流的輸入從跟結點開始向下移動，如果位元為0，就移動到左子結點，反之就移動到右子結點，當遇到葉子結點時，輸出這個結點的字符并重新回到根結點，
public static void expand() {
Node root = readTrie();
int N = BinaryStdIn.readInt();
for (int i = 0; i < N; i++) {
Node x = root;
while (!x.isLeaf())
if (BinaryStdIn.readBoolean())
x = x.right;
else
x = x.left;
BinaryStdOut.write(x.ch);
}
BinaryStdOut.close();
}
LZW壓縮
LZW演算法的基本思想和霍夫曼壓縮的思想正好相反，霍夫曼壓縮是為輸入中的定長模式產生了變長的編碼編譯表；而LZW壓縮是為輸入中的變長模式生成了一張定長的編碼編譯表，而且，LZW演算法不需要在輸出中附上這張編譯表，
LZW壓縮演算法的基礎是維護一張字串鍵和編碼的編譯表，在符號表中，將128個ASCII碼的值初始化為8位編碼，即在每個字符的編碼值前面添加0，然后用16進制數字來表示編碼，那么A的編碼就是41，R的是52等等，將80編碼保留為檔案借宿的標志，并將81-FF的編碼值分配給在輸入中遇到的各種子字串，
壓縮資料時，會反復進行如下操作：
- 找出未處理的輸入在符號表中最長的前綴字串s；
- 輸出s的8位編碼值；
- 繼續掃描s之后的一個字符c；
- 在符號表中將s+c（連接s和c）的值設為下一個編碼值，
比如下圖所示為處理輸入A B R A C ... B R A的程序，以及對應的三向單詞查找樹：
對于前7個字符，匹配的最長前綴只有1個字符，因此輸出這些字符對應的編碼，并將編碼81到87和產生的7個雙字符的字串關聯，然后發現AB匹配了輸入的前最81，并將ABR添加到符號表中，然后是RA（輸出83并添加RAB），BR（輸出82并添加BRA）和ABR（輸出88并添加ABRA），最后只剩下A（輸出41），
LZW的單詞查找樹
LZW演算法會用到三向單詞查找樹，包含兩種操作：
- 找到輸入和符號表的所有鍵的最長前綴匹配；
- 將匹配的鍵和前瞻字符相連得到一個新鍵，將新鍵和下一個編碼管理并添加到符號表中，
LZW壓縮的展開
在展開時，會維護一張關聯字串和編碼值的符號表，這張表的逆表示壓縮時所用的符號表，在這張表總加入00到7F和所有單個ASCII字符的字串的關聯條目，將第一個未關聯的編碼值設為81，在遇到編碼80前，不斷重復以下操作：
- 輸出當前字串val；
- 從輸入中讀取一個編碼x；
- 在符號表中將s設為和x相關聯的值；
- 在符號表中將下一個未分配的編碼值設為val+c，其中c為s的首字母；
- 將當前字串val設為s；
最終LZW演算法的實作如下，這份用于實際使用的代碼，采用的編碼寬度為12位，
public class LZW {
private static final int R = 256;
private static final int L = 4096;
private static final int W = 12;
public static void compress() {
String input = BinaryStdIn.readString();
TST<Integer> st = new TST<Integer>();
for (int i = 0; i < R; i++)
st.put("" + (char) i, i);
int code = R + 1;
while (input.length() > 0) {
String s = st.longestPrefixOf(input);
BinaryStdOut.write(st.get(s), W);
int t = s.length();
if (t < input.length() && code < L)
st.put(input.substring(0, t + 1), code++);
input = input.substring(t);
}
BinaryStdOut.write(R, W);
BinaryStdOut.close();
}
public static void expand() {
String[] st = new String[L];
int i;
for (i = 0; i < R; i++)
st[i] = "" + (char) i;
st[i++] = " ";
int codeword = BinaryStdIn.readInt(W);
String val = st[codeword];
while (true) {
BinaryStdOut.write(val);
codeword = BinaryStdIn.readInt(W);
if (codeword == R)
break;
String s = st[codeword];
if (i == codeword)
s = val + val.charAt(0);
if (i < L)
st[i++] = val + s.charAt(0);
val = s;
}
BinaryStdOut.close();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102323.html
標籤：其他