基於數據字典的數據壓縮方法、裝置的製作方法
2023-07-25 09:35:51 1
專利名稱：基於數據字典的數據壓縮方法、裝置的製作方法
技術領域：
本發明涉及一種數據壓縮方法、裝置。
背景技術：
在數據的傳輸過程中，通常需要對待傳輸的數據進行壓縮，以減少實際傳輸的數據量，減少網絡傳輸資源的佔用以及減少傳輸失敗的機會，提高數據傳輸的效率。例如，TCP/IP協議對於每一個已經建立的傳輸進程中的數據包的生命周期有嚴格的限制，也就是當傳輸的進程建立之後，按照TCP/IP協議的基本原理，發送端在發送一個數據包之後必須在規定的時間內收到從接收端返回的接收成功信息才會發送第二個數據包，否則認為上一個包發送失敗，重新發送第一個包；從接收方來看，超過一定的時間沒有收到發送方的數據包會認為連接超時，自動斷開連接。因此，所以數據的壓縮必須滿足在規定的時間內將發送端的數據包處理完成，轉發給接收端，並向數據發送端反饋正確的信息，這樣才能實現即壓縮了數據，又保證了數據傳輸進程的連接。
在對數據的壓縮過程中，通常需要使用數據字典幫助完成數據的壓縮。所述數據字典中存儲有數據壓縮使用的具有高重複概率的字符串及其代碼，這些字符串及其代碼構成了數據壓縮的樣本數據，一般，只有一定的重複數據量樣本數據才能達到良好的壓縮比，數據的壓縮率就會越高，因此，快速獲得一個內容較多且其中的樣本數據重複概率較大的數據字典成為一個數據傳輸系統的重要組成部分。
傳統的以所述數據字典為基礎實現的數據壓縮，需要獲得被壓縮的全部數據後才能容易地從中查找於所述數據字典中匹配的最長字符串，從而進行數據的靜態壓縮。所述基於數據字典的數據壓縮方法通常的步驟是1)使用數據緩衝區暫存需要壓縮的字符；2)按照某種規則對緩衝區中的數據進行分割，3)用分割出的數據段與數據字典中的樣本字符串進行匹配，如果匹配成功則用所述數據字典中的該樣本字符串的引用標籤代替所述數據段完成數據的輸出，從而實現數據的壓縮。該方法的特點是，需要至少一個數據緩衝區暫存待壓縮的全部數據，然後在緩衝區中的數據中查找可以和所述數據字典中樣本數據相同的字符串。由於需要預先獲得儘可能多的待編碼數據後才能啟動字符串的查找操作，必然導致壓縮完成時間的延遲，難以滿足實時數據的傳輸要求，而且這種方法需要開闢相對較大的內存空間作為數據緩衝區，也過多地佔用了系統資源。
發明內容
本發明要解決的技術問題在於，提供一種壓縮效率較高，壓縮延時較低的數據壓縮方法和數據壓縮裝置。
本發明提供的基於數據字典的數據壓縮方法，包括A、預置數據字典資料庫；
B、將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出；C、在待壓縮數據字符串處理完畢時，將輸出的引用標籤和字符串組裝成壓縮數據。
其中，按照下述步驟將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出B1、從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；B2、判斷在所述數據字典資料庫中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫的引用標籤，並將掃描指針向後移動大於或等於最長字符串的長度，轉步驟D繼續，否則，判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；B3、判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串，回到步驟B1繼續。
而且，如果沒有在數據字典資料庫中找到最長字符串，判斷所述最長字符串的長度值是否等於或超過設定的第一閾值，如果等於或超過，將所述最長字符串存儲入所述數據字典資料庫，否則，繼續操作。
所述方法還包括，如果所述待壓縮數據字符串掃描完畢，將所述數據字典資料庫中所有記錄的匹配次數計數值復位。
其中，如果在所述數據字典中找到所述最長字符串，將與所述最長字符串內容相同記錄的匹配次數計數值加1。
所述方法還包括，如果所述待壓縮數據字符串掃描完畢，判斷所述數據字典資料庫的記錄個數是否超過設定的第一閾值，如果超過，刪除所述成功次數計數值小於第二閾值的記錄。
或者，按照下述步驟將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出B1、用待壓縮數據字符串的第一個字符預置最長字符串變量，並使所述當前位置指針和掃描指針指向待壓縮數據字符串的第二個字符；B2、從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；B3、判斷在所述數據字典資料庫中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫的引用標籤，並將掃描指針向後移動大於或等於最長字符串的長度，轉步驟D繼續，否則，判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；B4、判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串，回到步驟B2繼續。
本發明提供的基於數據字典的數據壓縮裝置，包括用於存儲樣本字符串的數據字典資料庫、用於存儲待壓縮的字符串的數據緩衝區，以及用於暫存中間壓縮數據的壓縮資料庫；還包括字符串壓縮單元、用於將數據緩衝區中的待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出到壓縮資料庫；壓縮數據生成單元，用於在待壓縮數據字符串處理完畢時，將所述壓縮資料庫中的引用標籤和字符串組裝成壓縮數據。
其中，所述字符串壓縮單元進一步包括掃描子單元，從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；第一判斷子單元，用於判斷在所述數據字典資料庫中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫的引用標籤，並將數據緩衝區的掃描指針向後移動大於或等於最長字符串的長度；第二判斷子單元，用於判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；第三判斷子單元，用於判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串。
與現有技術相比，本發明通過預置數據字典資料庫的形式，將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出，這樣，隨著待壓縮字符串中的字符不斷流入所述數據緩衝區，從字符串開始形成的掃描能夠保證及時將流入數據緩衝區的一串字符用引用標籤替換後或者直接輸出，能夠保證數據的輸入引導壓縮的實現，即對待壓縮字符串(數據)的動態壓縮。
更進一步，本發明提供的動態壓縮方案能夠對所述數據字典資料庫的內容進行優化，因此能夠進一步改善數據動態壓縮的效果。
圖1是本發明所述數據壓縮方法的第一個實施例流程圖；圖2描述了圖1所示實施例在動態壓縮過程中的指針變化示例圖；圖3是本發明所述數據壓縮方法的第二個實施例流程圖；圖4是本發明所述數據壓縮裝置的一個實施例框圖；圖5是圖4所述實施例的字符串壓縮單元實施例框圖。
具體實施例方式
本發明實現的一個關鍵的環節，就是首先選擇經常使用的某一領域和行業的樣本數據，例如，通過網絡傳輸概率較高的文本數據，經由壓縮字典訓練軟體訓練出壓縮用的數據字典，並將其存儲到方便使用的資料庫中。在待壓縮的字符串(通常為經過處理的無含義數據流)不斷流入數據緩衝區使，利用所述數據字典資料庫對數據緩衝區內的字符進行壓縮，從而保證了系統的實時性。
下面結合附圖對本發明進行進一步的說明。
圖1是本發明所述數據壓縮方法的第一個實施例流程圖。圖1所示的實施例涉及一個數據字典資料庫，其中存儲有已經設置完畢的樣本字符串，所述數據字典資料庫的結構通常包括下述欄位樣本字符串欄位，用於存儲高重複概率字符串；散列值欄位，用於幫助檢索或查詢所述高重複概率字符串；計數器欄位，用於記錄相應記錄的高重複概率字符串被充公匹配的次數；引用標籤欄位，用於在數據壓縮時代替所述高重複概率字符串。此外，本實施例還涉及一個數據緩衝區，用於串行接收待壓縮的字符串，以便隨著字符串的輸入，不斷掃描輸入的字符串，實現對不斷輸入的字符串進行動態壓縮。
按照圖1的指示，首先在步驟11預置數據字典資料庫，使該資料庫存儲有足夠的高重複概率的樣本字符串，從而實現對待壓縮字符串的壓縮。此外，還要預置一個字符串變量——最長字符串length，用於累積掃描到的最長的字符串，以便在數據字典資料庫中完成匹配樣本字符串的操作。步驟11預置數據字典資料庫的詳細細節可以參考本申請人同日申請的另外一篇名稱為「數據字典的生成方法、裝置和數據字典的優化方法」的文件。
在步驟12，從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成在所述數據字典中可能出現的最長字符串。本例中所述預定個數為1。由於待壓縮數據字符串串行流入所述數據緩衝區，因此所述掃描字符實際上是連續讀取流入到所述數據緩衝區中的字符，每次掃描1個字符，即以1個字符作為生成可能在所述數據字典中出現的最長字符串的單位，將所述掃描得到的一個字符累加到最長字符串變量中，例如，如果本次掃描的字符為「a」，length的內容為「」(空)，則將所述掃描得到的一個字符「a」累加到最長字符串變量length中後，length的內容為「a」；而如果length的內容為「afds」，則將所述掃描得到的一個字符「a」累加到最長字符串變量length中後，length的內容為「afdsa」。
每次掃描一個字符後，都要在步驟12生成新的在所述數據字典資料庫中可能出現的最長字符串length。而length中的字符串是否最長的能夠進行壓縮的字符串，所述能夠壓縮即能夠用引用標籤替換，要看length中的字符串是否能夠與所述數據字典資料庫中的某個記錄的樣本字符串相等或匹配，因此在步驟13，判斷在所述數據字典資料庫中是否找到所述最長字符串length，所述判斷實際上是一個字符串的查找或匹配操作，該操作需要通過計算所述最長字符串length的散列值，通過所述散列值的查找實現對所述樣本字符串的查找。如果經過所述步驟13在所述數據字典資料庫中找到所述最長字符串length中的內容，說明已經掃描得到的字符串，即length中的字符串可以被所述數據字典資料庫中的引用標籤替換，實現對length中內容的壓縮。此時，通過步驟14，在另一個資料庫或表中按照順序記錄或輸出該字符串在所述數據字典資料庫中的引用標籤(也可以記錄序號，只是在最後組成壓縮數據時，再將所述序號還原為引用標籤)，接著在步驟15將所述當前位置指針的值，和掃描指針的值向後移動等於最長字符串length中的長度，該長度值即是length中的字符個數，這樣就可以從繼續輸入的字符流中查找下一個最長字符串length的內容，即可能被壓縮的新的字符串。本例中，步驟15實際涉及兩個指針的操作，表面上，一個指針是動態的，即掃描指針，一個指針是靜態的，指向被掃描字符串首的當前位置指針，但是由於字符是串行流入所述數據緩衝區的，因此該兩個指針實際上相對與動態字符流的輸入，所述數據緩衝區中的字符數在變化，因此這兩個指針的物理指向也在動態變化。
如果經過所述步驟13在所述數據字典資料庫中沒有找到所述最長字符串length中的內容，說明已經掃描得到的字符串，即length中的字符串不能被所述數據字典資料庫中的引用標籤替換，此時應該決定是繼續掃描還是判斷已經掃描的字符串不可能被一個引用標籤替換，從而開始進行新起點待壓縮字符串的掃描。因此，在步驟16判斷所述最長字符串length的內容(即字符串的長度)是否超過預定的長度，例如已經超過所述數據字典資料庫中最長的樣本字符串的長度，如果超過(有時也視「相等」滿足條件)，說明已經沒有可能在所述數據字典資料庫中找到相匹配的樣本字符串，以及可以替換的引用標籤，因此在步驟18輸出當前位置的字符，即當前位置指針指向的字符，在另一個資料庫或表中按照順序記錄或輸出該字符，準備將該字符作為不可壓縮的普通字符，然後在步驟19將所述當前位置指針後移1個字符的位置，同時將掃描指針設置與所述當前位置指針指向相同的位置或單元，開始進行下一輪的字符串掃描。如果在步驟16判斷所述最長字符串length的內容沒有超過預定的長度，說明可能還沒有達到能夠被引用標籤替換的樣本字符串的長度，應當繼續掃描及累積最長字符串length的內容，因此在步驟17，將新掃描的字符或字符組累加到當前最長字符串length中，形成新的最長字符串length，然後將所述掃描指針後移1個字符的位置，繼續下一步的字符串掃描。(步驟17中，當前位置指針指向不變。且所述掃描指針只能後移1個字符的位置)圖2(1)示出了在數據動態壓縮過程中的一個瞬間的指針狀態，當前位置指針指向字符A，掃描指針指向字符w，出現這個狀態說明從當前位置指針指向的字符A，掃描到字符w，最長字符串length中累積的字符串為「Adsq」，如果此時在步驟13，判斷在所述數據字典中已經找到所述最長字符串length的內容「Adsq」，則在步驟14，用所述數據字典資料庫中相應記錄(樣本字符串為「Adsq」的記錄)的引用標籤替換「Adsq」存入另外的資料庫，然後在步驟15將當前位置指針指向字符w，掃描指針也指向字符w，繼續掃描後續不斷輸入的字符串。參考圖2(2)。(此時可以將當前位置指針和掃描指針繼續後移，例如指向字符「r」，能夠提高掃描速度，或者避免數據緩衝區溢出，但此時付出的代價是損失了一些在所述數據字典資料庫中匹配到最長字符串length的可能性。)如果在圖2(1)狀態經步驟13，判斷在所述數據字典中沒有找到所述最長字符串length的內容「Adsq」，則在步驟16判斷所述最長字符串length的內容(即字符串的長度)是否超過預定的長度，如果最長字符串length的長度沒有超過指定的長度，然後在步驟17將新掃描的字符w累加到當前最長字符串length中，形成新的最長字符串length，此時為「Adsqw」，然後使當前位置指針指向字符A不動，使掃描指針指向字符e，繼續掃描後續的字符串。參考圖2(3)。
如果在圖2(1)狀態經步驟13，判斷在所述數據字典中沒有找到所述最長字符串length的內容「Adsq」，則在步驟16判斷所述最長字符串length的內容(即字符串的長度)是否超過預定的長度，如果最長字符串length的長度超過指定的長度，然後在步驟18將當前位置指針指向字符A輸出到另外資料庫中，準備形成壓縮字符串，然後使當前位置指針和掃描指針均指向字符d，開始進行新起點的下一輪的字符串掃描。參考圖2(4)。
圖2說明了先掃描一個字符，後生成最長字符串length的情況，掃描一個字符後即生成最長字符串length的情況與此類似，區別僅在於增加一個初始化步驟，即用待壓縮數據字符串的第一個字符預置最長字符串變量，並使所述當前位置指針和掃描指針指向待壓縮數據字符串的第二個字符，這樣就會在掃描一個字符後即生成最長字符串length。
下面繼續圖1所示實施例的說明。在當前位置指針和/或掃描指針移動後，可能待壓縮的字符串已經掃描完畢，尤其在步驟17的指針移動後，累積在最長字符串length中的字符可能為提高壓縮速度全部作為原始字符輸出，因此要在步驟20判斷待壓縮的字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串，回到步驟12繼續。這裡所說的復位有三種情況，第一種是經過步驟15的情況，此情況下的所述復位是將最長字符串length預置為最近掃描得到的字符，例如圖2(1)中的「w」，或者置空。第二種是經過步驟17的情況，此種情況下的所述復位是將最近掃描得到的字符，例如w，累加到最長字符串length中。第三種是經過步驟19的情況，此種情況下的所述復位是將最長字符串length預置為空。
如果在步驟20判斷待壓縮的字符串已經掃描完畢，將記錄或存儲在另外資料庫中的所述引用標籤和原始字符組成壓縮後的數據串，該數據串可以進行傳輸或進行後續的處理。
在本發明的其它以圖1所示實施例為基礎的實施例中，為了提高待壓縮字符串的掃描速度，即提高待壓縮字符串的動態壓縮速度，從所述數據緩衝區的第一個接收輸入字符的單元起，連續掃描多個字符，即以多個字符為一組作為生成可能在所述數據字典中出現的最長字符串的單位。這裡所述掃描字符的數量選擇，可以參考所述數據緩衝區的字符流入速度，一般應當保證掃描處理字符的速度略大於所述數據緩衝區的字符流入速度，以避免所述數據緩衝區流入字符的溢出。
同理，如果經過所述步驟13在所述數據字典資料庫中找到所述最長字符串length中的內容，在步驟15將所述當前位置的值向後移動大於最長字符串length中的長度，該長度值即是length中的字符個數，這樣就可以從繼續輸入的字符流中查找下一個最長字符串length的內容。
另外，在步驟16的判斷條件還可以有多種，例如，判斷所述最長字符串length的生存時間是否超時，如果超時，也可以啟動新起點的最長字符串length的累積。
圖3是本發明所述數據壓縮方法的第二個實施例流程圖。該實施例與圖1所示實施例的區別在於在步驟16和步驟18之間增加了一個步驟24。該步驟是對壓縮進程進行改進的一個步驟，如果經步驟13在數據字典資料庫中沒有找到最長字符串length，並且在步驟16判斷所述最長字符串的長度值等於或超過設定的第一閾值，在步驟24將所述最長字符串length存儲入所述數據字典資料庫。當然，在步驟24還要同時生成散列值欄位、計數器欄位、引用標籤欄位的值。
圖3所述的實施例可以優化所述資料庫，但其功能並不完整，在本發明的另外的實施例中，以圖3所示實施例為基礎，在步驟20和步驟23之間還包括一個步驟，用於將所述數據字典資料庫中所有記錄的匹配次數計數值復位，以利於在每次對待壓縮字符串進行壓縮時，輔助優化所述數據字典資料庫。因此，在該實施例中，在經過步驟13，在所述數據字典資料庫中沒有找到所述最長字符串length中的內容後的分支，即步驟14、15這個分支，還包括一個步驟(例如設置在步驟14、15之間)，將與所述最長字符串內容相同記錄的匹配次數計數值加1，從而實現樣本字符串重複概率的統計。
繼續的優化在本發明的其它實施例中有描述，增加了一個補充上述實施例不足的步驟，該步驟判斷所述數據字典資料庫的記錄個數是否超過設定的第一閾值，如果超過，刪除所述成功次數計數值小於第二閾值的記錄。所述第二閾值可以根據統計經驗設置。
圖4是本發明所述數據壓縮裝置的實施例框圖。圖4所示裝置包括用於存儲待壓縮的字符串的數據緩衝區41，用於存儲樣本字符串的數據字典資料庫42，用於暫存中間壓縮數據的壓縮資料庫43，還包括字符串壓縮單元44和壓縮數據生成單元45；所述字符串壓縮單元44、用於將數據緩衝區41中的待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫42中相應記錄的引用標籤替換輸出或者直接輸出到壓縮資料庫43；所述壓縮數據生成單元45，用於在待壓縮數據字符串處理完畢時，將所述壓縮資料庫43中的引用標籤和字符串組裝成壓縮數據。
所述字符串壓縮單元44進一步包括掃描子單元51，從數據緩衝區41中的待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；第一判斷子單元52，判斷在所述數據字典資料庫42中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫42中的引用標籤，並將數據緩衝區的掃描指針向後移動大於或等於最長字符串的長度；第二判斷子單元53，用於判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；第三判斷子單元54，用於判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串。
圖4所示的實施例涉及的數據字典資料庫42，其中存儲有已經設置完畢的樣本字符串，所述數據字典資料庫的結構通常包括下述欄位樣本字符串欄位，用於存儲高重複概率字符串；散列值欄位，用於幫助檢索或查詢所述高重複概率字符串；計數器欄位，用於記錄相應記錄的高重複概率字符串被充公匹配的次數；引用標籤欄位，用於在數據壓縮時代替所述高重複概率字符串。預置數據字典資料庫的詳細細節可以參考本申請人同日申請的另外一篇名稱為「數據字典的生成方法、裝置和數據字典的優化方法」的文件。本實施例涉及的數據緩衝區41，用於串行接收待壓縮的字符串，以便隨著字符串的輸入，不斷掃描輸入的字符串，實現對不斷輸入的字符串進行動態壓縮。當然，預先將待壓縮字符串(數據)的一部分輸入數據緩衝區41更是實際中常用的緩衝區使用方式，而且能夠提高對字符串的壓縮速度。
圖4中，字符串壓縮單元44的掃描子單元51還要預置一個字符串變量——最長字符串length，用於累積掃描到的最長的字符串，以便在數據字典資料庫42中完成匹配樣本字符串的操作。
掃描子單元51從數據緩衝區41待壓縮數據字符串的當前位置起連續掃描預定個數的字符(或者隨著待壓縮字符的流入數據緩衝區就從當前位置指針指向的字符起連續掃描預定個數的字符)，用預定個數的字符生成在所述數據字典資料庫42中可能出現的最長字符串。本例中所述預定個數為1。由於待壓縮數據字符串串行流入所述數據緩衝區41，因此所述掃描字符實際上是連續讀取流入到所述數據緩衝區41中的字符，每次掃描1個字符，即以1個字符作為生成可能在所述數據字典資料庫42中出現的最長字符串的單位，將所述掃描得到的一個字符累加到最長字符串變量length中，例如，如果本次掃描的字符為「a」，length的內容為「」(空)，則將所述掃描得到的一個字符「a」累加到最長字符串變量length中後，length的內容為「a」；而如果length的內容為「afds」，則將所述掃描得到的一個字符「a」累加到最長字符串變量length中後，length的內容為「afdsa」。
每次掃描一個字符後，都要生成新的在所述數據字典資料庫42中可能出現的最長字符串length。而length中的字符串是否為最長的能夠進行壓縮的字符串，所述能夠壓縮即能夠用引用標籤替換，要看length中的字符串是否能夠與所述數據字典資料庫42中的某個記錄的樣本字符串相等或匹配，因此掃描子單元51在生成新的最長字符串length後，要通知第一判斷子單元52，判斷在所述數據字典資料庫42中是否找到所述最長字符串length，所述判斷實際上是一個字符串的查找或匹配操作，該操作例如需要通過計算所述最長字符串length的散列值，通過所述散列值的查找實現對所述樣本字符串的查找。如果經過在所述數據字典資料庫42中找到所述最長字符串length中的內容，說明已經掃描得到的字符串，即length中的字符串可以被所述數據字典資料庫42中的引用標籤替換，實現對length中內容的壓縮。此時，在另一個資料庫，即壓縮資料庫43中按照順序記錄或輸出該字符串在所述數據字典資料庫42中的引用標籤(也可以記錄序號，只是在最後組成壓縮數據時，再將所述序號還原為引用標籤)，接著通知所述掃描子單元51將所述當前位置指針的值，和掃描指針的值向後移動等於最長字符串length中的長度，該長度值即是length中的字符個數，這樣就可以從繼續輸入的字符流中查找下一個最長字符串length的內容，即可能被壓縮的新的字符串。本例中，指針的移動實際涉及兩個指針的操作，表面上，一個指針是動態的，即掃描指針，一個指針是靜態的，指向被掃描字符串首的當前位置指針，但是由於字符是串行流入所述數據緩衝區的，因此該兩個指針實際上相對與動態字符流的輸入，所述數據緩衝區中的字符數在變化，因此這兩個指針的物理指向也在動態變化。
如果經過第一判斷子單元52在所述數據字典資料庫42中沒有找到所述最長字符串length中的內容，說明已經掃描得到的字符串，即length中的字符串不能被所述數據字典資料庫42中的引用標籤替換，此時應該決定是繼續掃描還是判斷已經掃描的字符串不可能被一個引用標籤替換，從而開始進行新起點待壓縮字符串的掃描。因此，由第二判斷子單元53判斷所述最長字符串length的內容(即字符串的長度)是否超過預定的長度，例如已經超過所述數據字典資料庫42中最長的樣本字符串的長度，如果超過(有時也視「相等」滿足條件)，說明已經沒有可能在所述數據字典資料庫42中找到相匹配的樣本字符串，以及可以替換的引用標籤，因此輸出當前位置的字符，即當前位置指針指向的字符，在另一個資料庫，即壓縮資料庫43中按照順序記錄或輸出該字符，準備將該字符作為不可壓縮的普通字符，然後通知所述掃描子單元51，將所述當前位置指針後移1個字符的位置，同時將掃描指針設置與所述當前位置指針指向相同的位置或單元，開始進行下一輪的字符串掃描。如果第三判斷子單元54判斷所述最長字符串length的內容沒有超過預定的長度，說明可能還沒有達到能夠被引用標籤替換的樣本字符串的長度，應當繼續掃描及累積最長字符串length的內容，因此通知所述掃描子單元51，將新掃描的字符或字符組累加到當前最長字符串length中，形成新的最長字符串length，然後將所述掃描指針後移1個字符的位置，繼續下一步的字符串掃描。
在當前位置指針和/或掃描指針移動後，可能待壓縮的字符串已經掃描完畢，尤其是累積在最長字符串length中的字符可能為提高壓縮速度全部作為原始字符輸出，因此要在壓縮數據生成單元45的一個判斷子單元(圖中未繪出)判斷待壓縮的字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串，通知所述掃描子單元51繼續掃描。這裡所說的復位有三種情況，第一種復位是將最長字符串length預置為最近掃描得到的字符，或者置空。第二種復位是將最近掃描得到的字符累加到最長字符串length中。第三種是將最長字符串length預置為空。
如果壓縮數據生成單元45的那個判斷子單元判斷待壓縮的字符串已經掃描完畢，則由壓縮數據生成單元45另外的子單元的將記錄或存儲在壓縮資料庫43中的所述引用標籤和原始字符組成壓縮後的數據串，該數據串可以進行傳輸或進行後續的處理。
鑑於圖4、5所述實施例的實現細節在本發明的方法部分的實施例中有詳細的說明，在此不再贅述。
採用上述方法或裝置的實施例，例如，經過所述壓縮數據生成單元45將所述壓縮資料庫43中的引用標籤和字符串組裝成壓縮數據如下表1所示。
表1
表中的數據包含了引用標籤和原始的數據(字符)，這樣數據在傳輸以前還需要進一步的處理，增加一個數據頭或頭文件，以便於數據接收端對對壓縮數據的識別和還原。例如在原始數據壓縮過程中就要形成一個頭文件，用於標識壓縮數據的性質，例如是標籤還是原始數據的標誌，這樣，在動態壓縮之後也同樣形成一個頭文件，例如，如果壓縮數據是標籤，就用八位二進位的最高位置「1」標識，如果壓縮數據是原始字符就用八位二進位的最高位置「0」標識。所以在頭文件中就會有一段數據是專門標識壓縮文件中數據的組成。
例如如果在壓縮之後的數據為表1所示的標籤字符串，則在頭文件的標識數據位上就會這樣如表2所示表2
這裡假設標籤的長度最長為128位，則每一個標籤的標識數據為8位，即最高位(第一位)標識性質，後7位標識長度，在原始數據段超過128位時則用下一個標識單元繼續標識。
權利要求
1.一種基於數據字典的數據壓縮方法，其特徵在於包括A、預置數據字典資料庫；B、將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出；C、在待壓縮數據字符串處理完畢時，將輸出的引用標籤和字符串組裝成壓縮數據。
2.如權利要求1所述的基於數據字典的數據壓縮方法，其特徵在於，按照下述步驟將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出B1、從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；B2、判斷在所述數據字典資料庫中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫的引用標籤，並將掃描指針向後移動大於或等於最長字符串的長度，轉步驟D繼續，否則，判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；B3、判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串，回到步驟B1繼續。
3.如權利要求2所述的數據字典的生成方法，其特徵在於，如果沒有在數據字典資料庫中找到最長字符串，判斷所述最長字符串的長度值是否等於或超過設定的第一閾值，如果等於或超過，將所述最長字符串存儲入所述數據字典資料庫，否則，繼續操作。
4.如權利要求2或3所述的數據字典的生成方法，其特徵在於還包括，如果所述待壓縮數據字符串掃描完畢，將所述數據字典資料庫中所有記錄的匹配次數計數值復位。
5.如權利要求4所述的數據字典的生成方法，其特徵在於，如果在所述數據字典中找到所述最長字符串，將與所述最長字符串內容相同記錄的匹配次數計數值加1。
6.如權利要求5所述的數據字典的生成方法，其特徵在於還包括，如果所述待壓縮數據字符串掃描完畢，判斷所述數據字典資料庫的記錄個數是否超過設定的第一閾值，如果超過，刪除所述成功次數計數值小於第二閾值的記錄。
7.如權利要求1所述的基於數據字典的數據壓縮方法，其特徵在於，按照下述步驟將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出B1、用待壓縮數據字符串的第一個字符預置最長字符串變量，並使所述當前位置指針和掃描指針指向待壓縮數據字符串的第二個字符；B2、從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；B3、判斷在所述數據字典資料庫中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫的引用標籤，並將掃描指針向後移動大於或等於最長字符串的長度，轉步驟D繼續，否則，判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；B4、判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串，回到步驟B2繼續。
8.一種基於數據字典的數據壓縮裝置，包括用於存儲樣本字符串的數據字典資料庫、用於存儲待壓縮的字符串的數據緩衝區，以及用於暫存中間壓縮數據的壓縮資料庫；其特徵在於還包括字符串壓縮單元、用於將數據緩衝區中的待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出到壓縮資料庫；壓縮數據生成單元，用於在待壓縮數據字符串處理完畢時，將所述壓縮資料庫中的引用標籤和字符串組裝成壓縮數據。
9.如權利要求1所述的基於數據字典的數據壓縮裝置，其特徵在於，所述字符串壓縮單元進一步包括掃描子單元，從待壓縮數據字符串的當前位置起連續掃描預定個數的字符，用預定個數的字符生成最長字符串；第一判斷子單元，判斷在所述數據字典資料庫中是否找到所述最長字符串，如果找到，記錄該字符串在所述數據字典資料庫的引用標籤，並將數據緩衝區的掃描指針向後移動大於或等於最長字符串的長度；第二判斷子單元，用於判斷所述最長字符串是否滿足處理條件，如果不滿足，形成新的最長字符串，並將所述掃描指針向後移動一個字符，否則，記錄當前位置指針的字符，並使所述當前位置指針向後移動至少一個字符，並使掃描指針指向當前位置指針指向的字符；第三判斷子單元，用於判斷所述待壓縮數據字符串是否掃描完畢，如果沒有掃描完畢，復位所述最長字符串。
全文摘要
本發明公開了一種基於數據字典的數據壓縮方法，包括預置數據字典資料庫；將待壓縮數據字符串當前位置起的連續的預定個數的字符構成的字符串，用所述數據字典資料庫中相應記錄的引用標籤替換輸出或者直接輸出；在待壓縮數據字符串處理完畢時，將輸出的引用標籤和字符串組裝成壓縮數據。本發明能夠實現對待壓縮字符串的動態壓縮，並能夠進一步改善數據動態壓縮效果的方案。本發明還公開了一種基於數據字典的數據壓縮裝置。
文檔編號H03M7/30GK1928850SQ20061010962
公開日2007年3月14日 申請日期2006年8月11日 優先權日2006年8月11日
發明者白傑, 李薇, 魯徵宇 申請人:白傑, 李薇, 魯徵宇