[發明專利]壓縮匹配枚舉

有效

• 申請號: 201180071391.0
• 申請日: 2011-10-09
• 公開（公告）號: CN103582880B
• 公開（公告）日: 2017-05-03
• 發明（設計）人: B.A.米克爾
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/00
• 代理公司: 中國專利代理(香港)有限公司72001
• 代理人: 李舒,汪揚

背景技術

計算設備執行用于數據壓縮的各種技術來壓縮數據字節，從而使用較少的存儲器和其它計算設備資源來存儲、處理、保持和/或傳送數據。常規的數據壓縮技術從處理資源的立場來說可能是低效的，并且/或者在查找數據匹配（例如，重復的字節序列）以壓縮數據時可能是不可靠的。例如，對于諸如LZX和LZMA的任何LZ77壓縮實現（implementation）來說，一個關鍵的挑戰是有效且可靠地查找產生最小壓縮數據的數據匹配。

各種LZ77壓縮算法嘗試確定重復的字節序列，并且用（距離，長度）對（pair）來編碼匹配。當壓縮算法從頭到尾處理緩沖器時，在每一位置處，可能的匹配是與緩沖器的當前位置處的字節相同的、來自緩沖器中更早處的字節序列。倒回（back into）緩沖器中的較短距離可用較少的比特來編碼，而更長的長度則覆蓋更多的數據。距離指示了在緩沖器中數據匹配之間的以字節計的距離，而長度指示了匹配的數據字節的數量。為了獲得好的壓縮比，對于緩沖器中的每一位置，算法應當能夠為每一可能的長度枚舉最短的距離。為了快速，算法不應當花費時間來枚舉對于其長度來說不是最短距離的匹配。例如，在緩沖器的某位置中，可能的匹配的全部集（full set）可能是（距離=50，長度=3）、（100,4）、（120,3）、（150,4）、（200,5）。算法將僅枚舉（50,3）、（100,4）和（200,5），這是因為另外兩個（120,3）和（150,4）被至少同樣長（例如，長度3和4）但在距離上更近的匹配所取代。在最優化方面，算法應當快速枚舉匹配的帕萊托前沿（Pareto frontier），其中兩個最優化準則是更長的長度和更短的距離。

LZX算法使用分裂樹（splay tree）來確定壓縮匹配并解決問題。分裂樹是二叉樹，其中新元素被插在根處。這提供了以下屬性：當算法搜索樹來確定匹配時，最新近的且因此是最短距離的匹配被首先遇到。如果樹變得不平衡，諸如若以字母順序插入串，則算法的執行欠佳，并且在實踐中，LZX算法對于大匹配歷史的伸縮性欠佳。

LZMA算法可使用哈希（Hash）鏈、二叉樹和帕特麗夏（Patricia）樹的變體來確定壓縮匹配并解決問題。還存在空間高效的樹實現的技術，如果它們被用在樹的每一節點處最新近插入的數據串的某個概念（notion）來修改，則可以解決問題。然而，這些技術被實施成從樹的根部按層次結構向下到更低級別節點來遍歷樹結構，并且它們在最新近的匹配也是長匹配時是次優的。

發明內容

本概要介紹壓縮匹配枚舉的簡化的概念，并且所述概念還將在下面的詳細說明中描述和/或在附圖中示出。本概要不應被視為描述所要求保護的主題的必要特征，也不應被用來確定或限制所要求保護的主題的范圍。

壓縮匹配枚舉被實施成利用由葉到根的特里（trie）結構來枚舉在存儲的數據序列中的所有的數據匹配可能性。在實施例中，可生成代表存儲在存儲緩沖器中的數據序列的后綴數組（suffix array）。后綴數組然后可被轉換成特里結構，由于特里結構在后綴數組的原地（in-place）生成，所以其在存儲緩沖器中蓋寫后綴數組。特里結構包括節點，每一節點代表后綴數組的一個或多個后綴，其中每一連續后綴或者被與特里結構中的現有節點群聚（group），或者被添加為特里結構中的新節點。當后綴數組的后綴具有如特里結構中的現有節點的數據序列的共同匹配長度時，該后綴可被與該現有節點群聚。數據序列匹配然后可如從特里結構確定的那樣被枚舉。

在其它實施例中，后綴數組是在存儲緩沖器中的緩沖位置的數組，其中緩沖位置由在相應緩沖位置處開始數據序列的數據串按字母順序排序。后綴數組可通過從后綴數組的連續后綴步進地更新特里結構而被轉換成特里結構。特里結構的節點每個均包括對父節點的引用、用于后代（descendant）節點的數據序列的共同匹配長度（例如，以包括節點的直接子節點）和最新近遍歷（traverse）的后代節點的緩沖位置。特里結構的生成可基于：特里結構包括一個或多個非葉節點，其每一個具有至少兩個直接子節點；用于后代節點的數據序列的共同匹配長度是最大的；以及在特里結構中的節點的總數被最小化。

附圖說明

參照以下附圖來描述壓縮匹配枚舉的實施例。相同的標號被貫穿全文地使用以引用附圖中示出的同樣的特征和部件：

圖1圖解在其中可實施壓縮匹配枚舉的實施例的示例性系統。

圖2圖解根據一個或多個實施例的特里結構和壓縮匹配枚舉的例子。