一種基於RLE和LZW的優化比特文件壓縮與解壓縮方法與流程
2023-05-18 00:53:56 1
本發明涉及一種基於RLE和LZW的優化比特文件壓縮與解壓縮方法，屬於通信中比特文件壓縮與解壓縮技術領域。
背景技術：
隨著星上應用複雜度的增加，對星上數據處理能力的要求也越來越高，採用的FPGA型號也隨著應用複雜度的提升而不得不採用更高等級的器件。這些先進型號的FPGA由於功能的更為強大，所對應的比特文件也變得更大，配置一片V5130T的FPGA的比特文件較V4SX55增長了大約3倍左右，這就意味著應用一片V5FPGA需要過去3倍的存儲資源來存儲配置比特，這對星上有限的資源來說無疑是個問題，必須要採取一定的壓縮方法來降低存儲資源。而且必須滿足以下要求：1)必須無損的還原比特文件，對比特流進行解壓縮要求能夠準確地恢復出原數據；2)壓縮率要高，壓縮解壓縮時間要短。針對這個問題及以上兩點要求，提出了一種基於RLE和LZW的優化比特文件壓縮與解壓縮方法，以實現高速高壓縮率的比特文件壓縮解壓縮。
數據壓縮通常包括有損壓縮和無損壓縮兩種。有損壓縮是有失真的壓縮，不可逆的，信息會受到損失。無損壓縮是無失真的壓縮，壓縮過程中去除數據中的冗餘度，解壓後不丟失任何信息，與壓縮前完全一致。無損壓縮通常用於文本、程序、重要數據的壓縮，它能保證完全地恢復原始數據。對比特流進行壓縮要求能夠準確地恢復出原數據，因此需要選用無損壓縮技術對比特文件進行壓縮和解壓縮來解決配置比特數據的傳輸和存儲問題。
經典的無損壓縮算法主要有：基於統計模式的算法，如香農編碼、霍夫曼編碼、算術編碼等；基於字典模式的算法，如LZ系列算法；還有一些其它的算法，如遊程編碼、JPEG-LS算法、JPEG2000的DEM算法、BWT算法等。綜合考慮設計複雜度和壓縮效率，字典模式的算法較統計模式的算法更適合用於比特文件壓縮。國內外目前針對比特文件壓縮主要採用的壓縮方法是字典式壓縮或者採用遊程編碼技術壓縮。Xilinx自己的壓縮工具採用字典式的LZ77方法進行比特文件壓縮。通過後面的實驗數據可以看出，Xilinx壓縮的比特文件壓縮率並不高。
技術實現要素：
本發明解決的技術問題為：克服現有技術不足，提供一種基於RLE和LZW的優化比特文件壓縮與解壓縮方法，在快速壓縮和高壓縮率的要求下，本發明通過對比特文件數據結構進行分析，適應性的優化改進了RLE算法，並結合LZW方法進一步提升壓縮率，設計了一種基於RLE和LZW的優化比特文件壓縮/解壓縮方法，該方法通過對比特文件數據結構的分析，創造性的根據比特文件特點優化了RLE算法；在應用優化RLE算法的基礎上，為了進一步提升壓縮率，創造性地將優化後的RLE算法並與LZW算法結合，應用於比特文件壓縮解壓縮。該方法節省了存儲資源，提高了計算效率，壓縮及解壓縮的設計實現，驗證了方法的正確性、有效性、高效性和可行性。
本發明解決的技術方案為：一種基於RLE和LZW的優化比特文件壓縮方法，包括步驟如下：
步驟一：FPGA配置比特文件由多部分數據組成，包含頭部控制字、數據和命令字，其中，數據和命令字格式都是以四字節為一個單位，摳除FPGA配置比特文件的頭部控制字；
初始化RLE中的遊長計數器；將RLE的遊程長度根據步驟一所述比特文件數據特點設置為4；
初始化LZW的壓縮字典，使字典包含所有可能的根，所述根為單一詞條；
設置前綴pre_char，令當前前綴pre_char為空；
步驟二：設置字符串pre_string；將步驟一中摳除頭部控制字的FPGA配置比特文件的第一個字符串賦給字符串pre_string；所述摳除頭部控制字的FPGA配置比特文件為被壓縮文件；
步驟三：將被壓縮文件進行壓縮，步驟如下：
(1)判斷被壓縮文件中是否有字符串需要壓縮，如果沒有字符串需要壓縮，則先輸出字符串pre_string，再輸出遊長計數器的值，進入步驟四；
(2)如果有字符串需要壓縮，設置當前字符串current_string，令當前字符串current_string等於字符流中的下一個字符串；
(3)判斷pre_string與current_string是否一致：如果pre_string與current_string一致，遊長計數器加1，判斷遊長計數器值是否計到255；如果遊長計數器值計到255，先輸出pre_string，再輸出遊長計數器值，令遊長計數器值為1，
讀取待壓縮文件的未壓縮的字符串給pre_string，返回步驟三
如果遊長計數器值未計到255，返回步驟三；
如果pre_string與current_string不一致，輸出pre_string，輸出遊長計數器值，將此時current_string賦給pre_string，返回步驟三；
步驟四：設定當前字符current_char，按照步驟三(1)輸出順序，將輸出依次排列成新的字符流，讀取該字符流中的第一個字符賦給current_char；
步驟五：判斷pre_char與current_char依次排列組成的詞條是否在字典中：如果在字典中，將pre_char與current_char依次排列組成的詞條賦給pre_char；如果未在字典中，則輸出當前前綴pre_char的碼字，添加pre_char與current_char依次排列組成的詞條到字典中，將current_char的值賦給pre_char；
步驟六：判斷新的字符流中是否還有字符需要壓縮，如果有字符需要壓縮，將需要壓縮的第一個字符賦給current_char，返回步驟五；如果沒有字符需要壓縮，輸出當前前綴pre_char的碼字，完成壓縮。
LZW的壓縮字典用於存儲壓縮過程中產生的詞條。
遊長計數器，從1開始計數，即讀取第一個字符串時計1，能夠在遇到連續重複出現的字符串時每次加1，直到出現不同的字符串時，能夠輸出遊長計數器的值，還原初值1；遊長計數器的值為1-255，達到255時還原1。
初始化LZW的壓縮字典的索引值為1-4096。
一種基於RLE和LZW的優化比特文件解壓縮方法，包括步驟如下：
步驟一：初始化解壓縮字典，使字典包含所有可能的根，所述根為單一詞條；
步驟二：設置變量pw，讀取待解壓縮數據流中第一個碼流，賦值給pw，以pw為索引查詢解壓縮字典，讀取該索引對應的詞條，設置字符串變量pre_char，將pw表示的索引對應的詞條賦給pre_char，並輸出pre_char；
步驟三：設置變量cw，繼續讀取待解壓縮數據中的下一個碼流，賦值給cw，判斷在字典中是否有cw表示的索引對應的詞條，如果有cw表示的索引對應的詞條，輸出cw表示的索引對應的詞條，即cw表示的索引對應的字符串數據，設置變量current_char，將cw表示的索引對應的字符串數據賦值給current_char，設置字符變量pc，將pre_char賦值給pc，設置字符變量cc，將current_char對應的詞條的第一個字符賦給cc，將pc和cc依次排列組成的字符串添加到解壓縮字典中；如果沒有cw表示的索引對應的詞條，將pre_char的值賦給pc，將current_char的第一個字符賦給cc，輸出pc和cc依次排列組成的字符串數據，並添加pc和cc依次排列組成的字符串數據到字典中；
步驟四：判斷待解壓縮數據流中是否還有數據需要解壓縮，如果還有數據需要解壓縮，返回步驟三；如果沒有數據需要解壓縮，將步驟三的輸出按輸出順序排列成新的字符串數據，識別新的字符串數據中的頭部控制字；設置字符串head，將頭部控制字賦值給head；
步驟五：設置字符串變量current_string，從去掉頭部控制字的新的字符串數據中按照遊長讀取字符串賦值給current_string，然後再讀取該字符串後的一個字符，即遊長計數器的值，根據讀取出的字符串和遊長計數器的值還原出原始壓縮數據；
步驟六：判斷去掉頭部控制字的新的字符串數據中是否還有待解壓縮的數據，若有，則將待解壓縮的數據代替去掉頭部控制字的新的字符串數據，返回步驟五；，若無，則將head與步驟五輸出的數據依次排列得到原始數據，完成解壓縮。
本發明與現有技術相比的優點在於：
(1)在快速壓縮和高壓縮率的要求下，本發明通過對比特文件數據結構進行分析，適應性的優化改進了RLE算法，並結合LZW方法進一步提升壓縮率，設計了一種基於RLE和LZW的優化比特文件壓縮/解壓縮方法。該方法通過對比特文件數據結構的分析，創造性的根據比特文件特點優化了RLE算法；在應用優化RLE算法的基礎上，為了進一步提升壓縮率，創造性地將優化後的RLE算法並與LZW算法結合，應用於比特文件壓縮解壓縮。該方法節省了存儲資源，提高了計算效率，壓縮及解壓縮的設計實現，驗證了方法的正確性、有效性、高效性和可行性。
(2)本發明通過對比特文件結構以及RLE和LZW算法分析，針對比特文件設計了一種基於RLE和LZW的優化比特文件壓縮以及解壓縮技術方法，創造性的根據比特文件特點優化了RLE算法，為了進一步提升壓縮率，創造性地將優化後的RLE算法並與LZW算法結合，應用於比特文件壓縮解壓縮，在保證一定壓縮率的基礎上節省了壓縮時間和大量的存儲資源，通過相應解壓縮程序設計驗證了壓縮方法的正確性、高效性和可行性。
附圖說明
圖1為本發明基本數碼結構；
圖2為本發明一種基於RLE和LZW的優化比特文件壓縮算法流程圖；
圖3為本發明一種基於RLE和LZW的優化比特文件解壓縮算法流程圖；
圖4為不同壓縮算法壓縮率比較示意圖。
具體實施方式
本發明的基本思路為：一種基於RLE和LZW的優化比特文件壓縮與解壓縮方法，通過對FPGA配置比特文件進行數據格式分析，摳出比特文件的頭部控制字，從真實配置數據開始，採用遊長為4的RLE編碼進行初步壓縮，再進行LZW壓縮進一步提升壓縮率。解壓縮時為壓縮的逆過程，先進行LZW解壓縮還原出中間數據，再對不包含頭部控制字的數據部分進行RLE解壓縮，還原出原始的FPGA配置比特文件。該方法綜合考慮了壓縮/解壓縮的時間和壓縮率，與Xilinx自帶的壓縮工具比較，與單純應用RLE算法，單純應用LZW算法比較，實現了壓縮率與壓縮速度的雙贏。解決了Xilinx先進型號FPGA配置比特文件過大的問題，節省了存儲晶片的開銷，為FPGA在軌重構技術提供了關鍵技術支撐。
下面結合附圖和具體實施例對本發明做進一步詳細描述。
遊程編碼(RLE)又稱為行程編碼，是一種相對簡單的數據壓縮技術。遊程指的是由信源符號或信號樣值構成的數據流中各個字符連續重複而形成字符串的長度，又稱遊程長度或遊長。遊程編碼就是將這種字符序列映射成串的字符串的長度和串的位置的標誌序列，當給定了行程串的字符、串的位置和長度，就能夠恢復出原始數據流。數據流的基本數碼結構如圖1所示，其中標識碼根據具體使用而定，也可以省略。
根據遊程編碼的數據流基本結構可知，只有遊程長度大於3時，遊程編碼才具有數據壓縮的功能。遊程編碼的效率取決於信源符號的重複率，重複率越高，遊長越長，其壓縮效果越明顯。遊程壓縮邏輯和硬體實現簡單，且速度很快。在實際工程中有時將遊程編碼和其它編碼方法一起混合使用，能獲得更好的壓縮效果。
由遊程編碼的原理可以知道，只有當被壓縮樣本重複率比較高的時候遊程編碼的壓縮效果才會較好。分析比特文件的架構，首先每個比特文件都有自己的頭部信息，這部分信息樣本的重複率非常低，相對於整個比特文件而言，頭部信息的所佔的比特位非常少，故在對比特文件進行壓縮時，摳出頭部信息位，僅對頭部信息後面的數據進行壓縮，這樣一定程度上提升了壓縮速度和壓縮率。摳出頭部信息後，剩餘的比特文件仍是有一定規律的，那就是不管是命令字還是數據都是以4個字節為一個單位的，這樣應用遊程編碼對比特文件壓縮的遊長選取為4位元組是最合適的，選取小於4位元組的話會增加更多的遊長信息在壓縮後的文件中，會降低壓縮率；選取大於4位元組的話，樣本的重複率會降低，在壓縮後的文件中會增加標識碼信息，降低壓縮率。在實現了優化RLE壓縮算法後，通過實驗也證實了分析結果。
改進遊程編碼由於壓縮過程不需要存儲，沒有計算，所以壓縮速度很快，但是受限於比特文件複雜度和壓縮算法本身，壓縮率並不是特別高。故在此優化RLE算法的基礎上進一步結合LZW算法對壓縮後的數據進行進一步的處理來提升壓縮率。
LZW算法由Terry Welch在1984年提出，它是LZ78的改進算法，與LZ78算法相比，去掉了標識的第二個欄位。LZW算法是基於字典模式的壓縮算法，不依賴於信源的概率分布，是一種面向通用數據、易於實現的無損數據壓縮算法。LZW算法不依賴於任何數據格式，具有很大的應用範圍，並且編碼速度快，邏輯簡單而且具有自適應的功能，特別有利於硬體實現同時具有很高的實時性。
LZW算法首先將字母表中的所有字符初始化到字典中，通常使用8位字符，因此在輸入數據之前就已經佔用了字典的前256項，即0～255。因為字典已經被初始化，所以輸入的下一個字符總能在字典中找到。實際中字典編碼就是對8位字符集的擴充，用來表示數據中出現的字符串，新增的字典編碼可用9位、10位、11位、12位甚至更多位來表示。例如若每個字符串用9位表示，可以有512個不同的9位代碼。這就是說，轉換表有512個字符串，其中256個表項用來存放已定義的字符，剩下256個用來存放(前綴，字符串)。
LZW算法的編碼原理如下：首先需要初始化字典，將前256項分給0～255，然後每讀入一個字符pre_char，均必須先在字典中進行查找。如果字典中已經有該字符，則更新當前字符為pre_char，並且將當前字符pre_char作為前綴，繼續讀入下一字符current_char作為尾字符，組成一個字符串「pre_char，current_char」，並再次在字典中查找「pre_char，current_char」。如果字典中沒有，則輸出字符pre_char位置碼，並將「pre_char，current_char」添加到字典中，然後將current_char作為前綴。重複以上步驟，直到所有編碼完成。
LZW的解碼算法是編碼的逆過程，同樣的表現為一種基於字典的自適應的算法，一邊生成字典，一邊解碼輸出。
綜上所述，本發明提出了一種基於RLE和LZW的優化比特文件壓縮方法，包括步驟如下：
步驟一：FPGA配置比特文件由多部分數據組成，主要包含頭部控制字、數據和命令字，其中，數據和命令字格式都是以四字節為一個單位，摳除FPGA配置比特文件的頭部控制字；
初始化RLE中的遊長計數器為1；將RLE的遊程長度根據步驟一所述比特文件數據特點設置為4；
初始化LZW的壓縮字典為4096行*32列，使字典包含所有可能的根，所述根為單一詞條，即初始化後的字典第0到255行的第一列數據為0-255；
設置前綴pre_char，令當前前綴pre_char為空；
步驟二：設置字符串pre_string；將步驟一中摳除頭部控制字的FPGA配置比特文件的第一個字符串賦給字符串pre_string；所述摳除頭部控制字的FPGA配置比特文件為被壓縮文件；
步驟三：
(1)判斷被壓縮文件中是否有字符串需要壓縮，如果沒有字符串需要壓縮，則先輸出字符串pre_string，再輸出遊長計數器的值，進入步驟四；
(2)如果有字符串需要壓縮，設置當前字符串current_string，令當前字符串current_string等於字符流中的下一個字符串；
(3)判斷pre_string與current_string是否一致：如果pre_string與current_string一致，遊長計數器加1，判斷遊長計數器值是否計到255；如果遊長計數器值計到255，先輸出pre_string，再輸出遊長計數器值，令遊長計數器值為1，
讀取待壓縮文件的未壓縮的字符串給pre_string，返回步驟三
如果遊長計數器值未計到255，返回步驟三；
如果pre_string與current_string不一致，輸出pre_string，輸出遊長計數器值，將此時current_string賦給pre_string，返回步驟三；
步驟四：(1)設定當前字符current_char，
(2)按照步驟三(1)輸出順序，將輸出依次排列成新的字符流，讀取該字符流中的第一個字符賦給current_char；為了提高壓縮速度，該步驟可以在步驟三有數據輸出時同時啟動進行，讀取步驟三輸出的第一個字符給current_char，然後進行後續步驟；
步驟五：判斷pre_char與current_char依次排列組成的詞條是否在字典中：如果是在字典中，將pre_char與current_char依次排列組成的詞條付給pre_char；如果未在字典中，則輸出當前前綴pre_char的碼字，添加pre_char與current_char依次排列組成的詞條到字典中，將current_char的值賦給pre_char；
步驟六：判斷新的字符流中是否還有字符需要壓縮，如果有字符需要壓縮，將需要壓縮的第一個字符付給current_char，返回步驟五；如果沒有字符需要壓縮，輸出當前前綴pre_char的碼字，完成壓縮。
LZW的壓縮字典用於存儲壓縮過程中產生的詞條。
遊長計數器，從1開始計數，即讀取第一個字符串時計1，能夠在遇到連續重複出現的字符串時每次加1，直到出現不同的字符串時，能夠輸出遊長計數器的值，還原為初值1；遊長計數器的值為1-255。
初始化LZW的壓縮字典的索引值為1-4096。
結合上述優化比特文件壓縮算法及程序設計思路，一種基於RLE和LZW的優化比特文件壓縮算法流程如圖2所示。
在完成了壓縮後，相對應於壓縮技術處理後的數據，解壓縮是壓縮的逆過程既可以實現還原出原始數據，可以需要採用LZW算法還原出優化RLE壓縮的數據，再進行優化RLE解壓縮還原出最初的原始數據。解壓縮與壓縮思路相逆。
下面給出一種優選的具體解壓縮方法流程如圖3所示，本發明優選的一種基於RLE和LZW的優化比特文件解壓縮方法包括步驟如下：
步驟一：初始化解壓縮字典為4096行*32列，使字典包含所有可能的根，所述根為單一詞條，即初始化後的字典第0到255行的第一列數據為0-255；
步驟二：設置變量pw，讀取待解壓縮數據流中第一個碼流，賦值給pw，以pw為索引查詢字典，讀取該索引對應的詞條，設置字符串變量pre_char，將pw表示的索引對應的詞條賦給pre_char，並輸出pre_char；如pw為10，查詢索引為10的字典中字符串數據，賦值為pre_char；
步驟三：設置變量cw，繼續讀取待解壓縮數據中的下一個碼流，賦值給cw，判斷在字典中是否有cw表示的索引對應的詞條，如果有cw表示的索引對應的詞條，輸出cw表示的索引對應的字符串數據(輸出cw表示的索引對應的詞條，即cw表示的索引對應的字符串數據)，設置變量current_char，將cw表示的索引對應的字符串數據賦值給current_char，設置字符變量pc，將pre_char賦值給pc，設置字符變量，將current_char對應的詞條的第一個字符賦給cc，將pc和cc依次排列組成的字符串添加到解壓縮字典中；如果沒有cw表示的索引對應的詞條，將pre_char的值賦給pc，將current_char的第一個字符賦給cc，輸出pc和cc依次排列組成的字符串數據，並添加pc和cc依次排列組成的字符串數據到字典中；如待解壓縮數據為「9 18 300…..4095」，則讀取第一個pw值9，輸出字典第9條表示的字符串「9 256 256….256」給pre_char，並輸出「9」；繼續讀取cw值18，該值在初始化的字典中，輸出字典第18條表示的字符串「18 256 256….256」給current_char，並輸出「18」，添加「9 18 256….256」到字典中，該詞條索引為257；繼續讀取cw值300，該值不在初始化的字典中，輸出「18 18」，添加「18 18 256….256」到字典中，依次類推，直到所有數據處理完成。
步驟四：判斷待解壓縮數據流中是否還有數據需要解壓縮，如果還有數據需要解壓縮，返回步驟三；如果沒有數據需要解壓縮，將步驟三的輸出按輸出順序排列成新的字符串數據，識別新的字符串數據中的頭部控制字；設置字符串head，將頭部控制字賦值給head(如新的字符串數據為「頭部控制字AA AA AA AA 02 BB BB BB BB 01 CC CC CC CC 09……DD DD DD DD 03」，將頭部控制字賦給head，對「AA AA AA AA 02 BB BB BB BB 01 CC CC CC CC 09……DD DD DD DD 03」進行後續解壓縮)；
步驟五：設置字符串變量current_string，從去掉頭部控制字的新的字符串數據中按照遊長讀取字符串賦值給current_string，然後再讀取該字符串後的一個字符，即遊長計數器的值，根據讀取出的字符串和遊長計數器的值還原出原始壓縮數據；如字符串「AA BB CC DD 02」，讀取current_string為「AA BB CC DD」，遊長為2，還原後的數據為「AA BB CC DD AA BB CC DD」；
步驟六：判斷去掉頭部控制字的新的字符串數據中是否還有待解壓縮的數據，若有，則將帶壓縮的數據代替去掉頭部控制字的新的字符串數據，返回步驟五；若無，則將head與步驟五輸出的數據依次排列得到原始數據，完成解壓縮。如帶解壓縮數據還有「AA AA AA AA 02 BB BB BB BB 01 CC CC CC CC 09……DD DD DD DD 03」,先讀取「AA AA AA AA」，根據「02」，還原數據為「AA AA AA AA AA AA AA AA」；再讀取「BB BB BB BB」，根據「01」，還原數據為「BB BB BB BB」，依次讀完所有數據，直到讀取「DD DD DD DD」，根據「03」，還原數據為「DD DD DD DD DD DD DD DD DD DD DD DD」(與頭部控制字拼接完成完整原始數據解壓縮為「頭部控制字AA AA AA AA AA AA AA AA BB BB BB BB……DD DD DD DD DD DD DD DD DD DD DD DD」)。
6、變量current_char作為索引號，解壓縮字典中相應的字符串數據。
相對應於壓縮技術處理後的數據，解壓縮技術首先需要採用LZW算法還原出優化RLE壓縮的數據，再進行優化RLE解壓縮還原出最初的原始數據。算法設計思路與壓縮算法類似，具體解壓縮算法流程如圖3所示。
壓縮和解壓縮程序設計完成後，採用五種不同資源利用率的比特文件進行了壓縮率測試和解壓縮還原試驗，還原後的數據與原始數據一致，驗證了算法實現的正確性。壓縮率大小如下表所示：
表1壓縮試驗數據
圖形化顯示實驗結果如圖4所示，從實驗結果可以看出：
隨著資源的增加，所有壓縮方法的壓縮率都在下降；對於資源使用非常少的數據(1％)，我們開發的三種方法壓縮率都在95％以上，Xilinx的壓縮率只有85％；
對於資源使用非常多的數據(99％)，Xilinx的壓縮方法壓縮率只比優化RLE的壓縮率略高，但還是遠低於LZW以及優化RLE_LZW壓縮方法；
對於資源稍多的數據(20％、56％、81％)，LZW壓縮方法的壓縮率與其他三種方法比較是最高的(百分之七八十)，Xilinx的壓縮率是最低的(只能達到百分之二三十)；
RLE_LZW優化壓縮方法，對於資源使用率較高的比特壓縮率略低於LZW，差別不是很大，但在壓縮時間上較LZW方法提升了許多，這是由於待壓縮數據先經過優化RLE算法壓縮，再送到LZW壓縮時數據量較未壓縮數據已經減少了很多。優化RLE算法本身不耗時，而LZW算法本身由於數據需要與字典進行逐一比較，而字典本身又是動態更新的，所以非常耗時。RLE_LZW優化算法較單純的LZW算法損失的壓縮率是由於優化RLE算法處理後的壓縮數據複雜度較原始數據增加，導致壓縮率受到了一點影響。但是，綜合考慮壓縮時間與壓縮率，一種基於RLE和LZW的優化比特文件壓縮與解壓縮技術是最優的。