TWI505091B - 用於非揮發性記憶體的自適應壓縮資料儲存方法及使用該方法的系統 - Google Patents

Description

用於非揮發性記憶體的自適應壓縮資料儲存方法 及使用該方法的系統

本發明關於一種自適應壓縮資料儲存方法及使用該方法的系統。特別是關於用於非揮發性記憶體，比如快閃記憶體的一種自適應壓縮資料儲存方法及使用該方法的系統。

由於NAND型儲存單元的尺寸持續縮小並結合使用多層式儲存技術，非揮發性記憶體，比如NAND快閃記憶體固態硬碟，近來成為了消費電子設備和桌上電腦系統具吸引力的解決方案。然而，隨著快閃記憶體儲存單元的密度增加，其性能和可靠性可能顯著惡化。例如，以34nm製程製造的單層式儲存快閃記憶體允許每一區塊具有100,000次編程/擦除週期，而同樣以34nm製程製造的多層式儲存快閃記憶體僅支援每區塊5,000次的編程/擦除週期。多層式儲存快閃記憶體的效能也較單層式儲存快閃記憶體的效能慢了好幾倍。然而，當半導體製程進一步縮減，預計這些問題將會越來越嚴重。 其中一個有機會可以減輕這些問題的方法是使用硬體加速壓縮。

因為使用快閃記憶體的固態硬碟壽命強烈地依賴於寫入固態硬碟的資料量，減少寫入到固態硬碟實際的資料量的資料壓縮，可以是一個改善固態硬碟使用壽命的有效解決方案。此外，如果壓縮作業能以一硬體加速單元操作，因為在I/O作業期間小量的資料實體傳輸於未壓縮的讀寫中，這也能改善固態硬碟的效能。使用資料壓縮於資料儲存的想法並不新穎，但已廣泛地被研究。例如，許多現有的檔案系統支援基於軟體的資料壓縮，以擴充儲存設備的有效容量。雖然基於軟體的壓縮方式可以有效改善固態硬碟的使用壽命，他們卻造成相當大的壓縮/解壓縮開銷費用。因此整體固態硬碟的效能明顯地惡化。因此，當儲存量是設計最重要的目的之一時，通常使用基於軟體的資料壓縮。

資料壓縮指的是減少所需的儲存資料的空間或減少發送資料所需的時間，資料的大小由移除超額資訊而減少。資料壓縮的目的是以數位形式表達資訊來源，其位元數越少越好，而能滿足重建原始資訊的最低要求。只有精確地從壓縮版本重建原始資料是可行時，資料壓縮可以是無損失的。當該來源原始資料非常重要，以至於人們無法失去任何細節時，才使用這樣的無損失技術。這種來源資料的實例是醫學圖像、為法律上原因保存的文字和圖像、一些電腦的可 執行文件等。因為這些演算法不可逆地刪除資料的某些部分，壓縮演算法的另一個家族被稱為"損失性"，僅原始資料的近似值可以被重建。近似重建可能是殷切需求的，因為它可以導致更有效的壓縮。然而，這通常需要視覺品質和計算複雜性之間的良好平衡。因為人類視覺和聽覺系統的運作，諸如多媒體圖像，視頻和音頻的資料藉由損失性壓縮技術，可輕易地被壓縮。損失性演算法達成比無損失演算法更加的壓縮效能。但損失性壓縮被限於音頻、圖像和視頻，其中某些損失是可以接受的。論就"無損失"或"損失性"壓縮技術二者孰優孰劣的問題是沒有意義的，因為每一者都有它的使用面，無損失壓縮技術也許長於某些情況，而損失性壓縮技術優於另一些情況。

時下的一些無損失壓縮技術，它們大多是基於字典或機率及熵的方式。易言之，它們都試圖利用出現在資料中相同的字符/字符串的來實現壓縮。基於字典的壓縮技術，Lempel-Ziv方案分為兩個家族：由LZ77(LZ77、LZSS、LZH與LZB)導出的方案及由LZ78(LZ78、LZW與LZFG)導出的方案。

硬體實現上的壓縮技術的一個很好的例子，由Sungjin Lee等人提出於名為"使用硬體加速壓縮改進固態硬碟效能與使用壽命"論文中，該論文出版於2011年11月的電機電子工程師學會消費性電子會報第57卷第4篇。請見第1圖，一 種固態硬碟架構1包含一直接記憶體存取控制器10、數個快閃記憶體匯流排控制器20，及一壓縮/解壓縮模組30。該直接記憶體存取控制器20接收來自一主機(未繪示)的命令並與主機內的一動態隨機存取記憶體彼此傳送資料。每一快閃記憶體匯流排控制器20執行數個快閃記憶體運作，包含讀、寫與擦除運作，並移動資料進出快閃記憶體晶片。

壓縮/解壓縮模組30實現於直接記憶體存取控制器10與快閃記憶體匯流排控制器20間。壓縮/解壓縮模組30的主要作用在個別執行對傳遞來自直接記憶體存取控制器10或快閃記憶體匯流排控制器20的資料之壓縮或解壓縮。壓縮/解壓縮模組30使用LZRW3演算法，屬於LZ77的演變型。它有四個硬體子模組：一移位暫存器21、一字典表22、一壓縮邏輯電路23，及一壓縮緩衝器24。移位暫存器21暫存用於壓縮要被測試的資料，字典表22包含以前看過重複樣式。壓縮邏輯電路23參照字典表22，轉換移位暫存器21中的資料為符號。壓縮的資料，一連串的符號，儲存於壓縮緩衝器24中且最終移至一快閃記憶體晶片中。

壓縮/解壓縮模組30取得來自直接記憶體存取控制器10中一直接記憶體存取緩衝器11的資料直到移位暫存器21完全填滿，而該直接記憶體存取緩衝器11保有從主機發送的全部資料。壓縮邏輯電路23使用移位暫存器21中資料的首3位元組，創造一雜湊值，該首3位元組用作為字典表22的 字典索引。壓縮邏輯電路23接著檢查字典索引所指的資料登錄。如果對應資料登錄的首3位元組相當於移位暫存器21中的，就假定一個匹配的圖案被發現於字典表22中。當該壓縮邏輯電路23找到一匹配資料登錄，它會比較移位暫存器21中剩餘的位元組與資料登錄中的位元組，找出移位暫存器21與資料登錄間，資料的公共部分。這公共部分稱作資料片段。壓縮邏輯電路23由結合該字典索引與資料片段的長度，及數值為"1"的一壓縮旗，創造一符號。該壓縮旗指出是否該符號表示壓縮的資料或未壓縮的資料。該創造的符號接著寫入壓縮緩衝器24中。最後，整個資料片段由移位暫存器21中捨棄，新的資料由直接記憶體存取緩衝器11傳送到移位暫存器21中。

如果未從字典表22中找到匹配的樣式，一符號僅為該資料的第一個位元組而創造。一9位元符號由增加1位元壓縮旗(其值為0)到移位暫存器21的第一位元組而創造。在該創造的符號寫入壓縮緩衝器24後，來自直接記憶體存取緩衝器11資料的一新的位元組接附於移位暫存器21的尾部，捨棄移位暫存器21的第一位元組。需要注意的是，當一個匹配的樣式不存在字典表22中時，雜湊值所指出資料登錄中的舊樣式由移位暫存器21中的新樣式所取代，以支援新發現的樣式。

藉由固態硬碟架構1，寫入固態硬碟的資料描述於第2圖。第2圖顯示固態硬碟中連續的頁。這些填製斜線的 頁表示所有頁中的儲存單元都寫入了儲存的資料。關於那些部分填製斜線的頁，空白部分不含資料且技術上墊充"0"。斜線區與空白區的比例就是該頁儲存單元裡，含資料部分與未含資料部分的比例。不是所有的資料都能因其特性而被壓縮，第2圖是用於來說明的例子。從第2圖中，很明顯地，實體頁位址P11到P14儲存一未壓縮的資料。實體頁位址P15與P16儲存一壓縮的資料。實體頁位址P17與P18儲存另一壓縮的資料。事實上，頁中的空白不僅是儲存空間的浪費，也是減少固態硬碟使用壽命的原因。所有的壓縮演算法與應用該壓縮演算法的模組都具有前案所點出的相似缺點。因此，亟待能利用頁空白區的方法和應用該方法的系統。

本段文字提取和編譯本發明的某些特點。其他特點將被揭露於後續段落中。其目的在涵蓋附加的申請專利範圍之精神和範圍中，各式的修改和類似的排列。

本發明提供以解決壓縮資料儲存空間無法被利用的問題。進一步，非揮發性記憶體的使用壽命能延長。

依照本發明的一個態樣，揭露一種用於非揮發性記憶體的自適應壓縮資料儲存方法。該方法包含步驟：A.接收一第一資料，其中該第一資料的大小不大於在一非揮發性記憶體中的一頁的大小，連續接收的第一資料形成一原始資料，該原始資料需要儲存於該非揮發性記憶體中；B.如果該 第一資料的大小大於一預定大小，分割第一資料為至少二基本單元，其中至少一基本單元等於該預定大小；C.壓縮該基本單元或該第一資料；D.連接且墊充該壓縮的基本單元或該第一資料以形成一第二資料，以便該第二資料具有的大小為該預定大小的整數倍；E.儲存該第二資料於一緩衝器中；F.如果第二資料的數量為1且該原始資料並未完全被接收，重複步驟A到步驟E；G.搜尋至少二第二資料，該些第二資料能結合而具有該緩衝器中一頁的大小；H.於該緩衝器中結合該至少二第二資料為一第三資料，或如果該原始資料已完全被接收，墊充該第二資料或連接且墊充於該緩衝器中的該第二資料為一第三資料，其中該第三資料的大小與一頁相同；I.編程該第三資料到該非揮發性記憶體中的一特定頁；及J.如果原始資料並未完全被接收，執行步驟A。0被用作墊充的元素。

依照本發明的構想，該自適應壓縮資料儲存方法，進一步包含一步驟I1於步驟I之後：I1.更新一映射表，該映射表儲存該特定頁的一實體頁位址與該原始資料的一邏輯位址之映射連結。該自適應壓縮資料儲存方法亦進一步包含一步驟H1於該步驟H與步驟I間：H1.如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，墊充具有該緩衝器中所有第二資料裏最大的第二資料為該第三資料，並編程該第三資料至該非揮發性記憶體中之一特定頁，其中0被用作墊充的元素。或者進一步包含一步驟H2於該步驟H與步驟 I間：H2.如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，墊充該緩衝器中所有第二資料裏暫存時間最久的第二資料為該第三資料，並編程該第三資料至該非揮發性記憶體中之一特定頁，其中0被用作墊充的元素。

依照本發明，一無損失壓縮演算法被用於步驟C以壓縮該第一資料或該基本單元。其中該無損失壓縮演算法為LZ77、LZSS、LZH、LZB、LZ78、LZW或LZFG。該非揮發性記憶體為NAND快閃記憶體或固態硬碟。一基本單元被壓縮以形成一壓縮的基本單元，或至少二基本單元被壓縮以形成一壓縮的基本單元。

依照本發明的另一種態樣，一種用於非揮發性記憶體的自適應壓縮資料儲存系統，包含：一主機介面單元，用以與一主機溝通及接收來自該主機的第一資料，該些第一資料的尺寸不大於一非揮發性記憶體中一頁的尺寸，其中連續接收的第一資料形成一原始資料，該原始資料需要儲存於該非揮發性記憶體中；一資料壓縮器，電連接至該主機介面單元，如果該第一資料的大小大於一預定大小，用以分割每一第一資料為至少二基本單元及壓縮該基本單元，其中至少一基本單元等於該預定大小；一墊充單元，電連接至該資料壓縮器，用以連接且墊充該壓縮的基本單元以形成一第二資料，及如果該原始資料已完全被接收，墊充該第二資料或連接且墊充該第二資料為一第三資料；一緩衝器，電連接至墊 充單元與該非揮發性記憶體，用以暫時儲存該第二資料、當其已滿或實質已滿時取代一儲存的第二資料，及編程該第三資料至該非揮發性記憶體中的一特定頁；及一結合單元，電連接至該緩衝器，用以結合在該緩衝器中的至少二第二資料為一第三資料。如果該原始資料大小不大於該預定大小，該第一資料將不被分割但被壓縮及墊充為一頁的大小且編程至該非揮發性記憶體中。該第二資料具有的大小為該預定大小的整數倍。該第三資料的大小與一頁相同。0被用作墊充的元素。

依照本案構想，該自適應壓縮資料儲存系統，進一步包含一映射表單元，電連接至該緩衝器，用以儲存與更新一映射表，該映射表有特定頁的一實體頁位址與該原始資料的一邏輯位址之映射連結。如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，該墊充單元進一步墊充一第二資料為該第三資料，該被墊充的第二資料為該緩衝器中所有第二資料裏最大的。如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，該墊充單元進一步墊充一第二資料為該第三資料，該被墊充的第二資料為該緩衝器中所有第二資料裏暫存時間最久的。

1‧‧‧固態硬碟架構

10‧‧‧直接記憶體存取控制器

11‧‧‧直接記憶體存取緩衝器

20‧‧‧快閃記憶體匯流排控制器

21‧‧‧移位暫存器

22‧‧‧字典表

23‧‧‧壓縮邏輯電路

24‧‧‧壓縮緩衝器

30‧‧‧壓縮/解壓縮模組

100‧‧‧自適應壓縮資料儲存系統

101‧‧‧主機介面單元

102‧‧‧資料壓縮器

103‧‧‧墊充單元

104‧‧‧緩衝器

105‧‧‧結合單元

106‧‧‧映射表單元

110‧‧‧非揮發性記憶體

200‧‧‧主機

第1圖為一固態硬碟架構前案的方框圖。

第2圖顯示該固態硬碟中連續的頁。

第3圖依照本發明，一自適應壓縮資料儲存系統實施例的方框圖。

第4圖說明資料儲存於實施例的自適應壓縮資料儲存系統中。

第5圖為依照本實施例，一自適應壓縮資料儲存方法實施例的流程圖。

第6圖說明資料儲存於另一實施例的自適應壓縮資料儲存系統中。

本發明將藉由參照下列的實施例而更具體地描述。

請參閱第3圖，該圖說明依照本發明，用於非揮發性記憶體的一種自適應壓縮資料儲存系統100。非揮發性記憶體，諸如NAND快閃記憶體，包含單層式儲存快閃記憶體、多層式儲存快閃記憶體，及三層式儲存快閃記憶體，皆適用於本發明。此外，模組化的非揮發性記憶體，例如固態硬碟、記憶卡與隨身碟，也可應用。然而，非揮發性記憶體(或模組)必須是以"頁"為單位進行編程。可以隨機存取的非揮發性記憶體，例如，電可擦除可編程唯讀記憶體，並不適用。為了說明方便，使用於本實施例的一非揮發性記憶體110是一 NAND快閃記憶體晶片。市場上有許多種類不同規格的的NAND快閃記憶體晶片，它們都可以被使用，無論其記憶容量與頁的大小。此處，本發明聚焦於非揮發性記憶體110中頁間的互動。正如人們所知，一頁常用的大小範圍由512B到4KB(僅計算資料區，不含備用區中的記憶容量)。為了更好地理解本發明，該頁大小為2KB。

自適應壓縮資料儲存系統100包含數個部分：一主機介面單元101、一資料壓縮器102、一墊充單元103、一緩衝器104、一結合單元105與一映射表單元106。主機介面單元101能與一主機200溝通並接收來自該主機200的第一資料。主機200是一台個人電腦的中央處理單元。它寫資料進入非揮發性記憶體110中，並讀取其中儲存的資料。實作上，主機200也可是一台獨立的電子設備，請求資料儲存，例如，一台筆記型電腦。主機介面單元101能被設計成具有適合於主機200的介面。在本實施例中，該介面可符合內部整合電路(I2C)規範。每一來自主機200的第一資料的大小不大於在非揮發性記憶體110中一頁的大小(2KB)。連續接收的第一資料形成一原始資料，該原始資料需要儲存於該非揮發性記憶體。原始資料，比如一影像檔，可能不會是2KB的整數倍。短的原始資料可能具有500B的資料長度，儲存需要佔一頁的容量。大的原始資料可能具有超過10MB的資料長度，且在分割為數頁大小已進行儲存後，最後一段資料短於2KB。前述的兩種原始資 料都適用於自適應壓縮資料儲存系統100。在本實施例中，具有6KB(3倍頁的大小)的一原始資料用來做說明。其它具不同資料長度的原始資料將在其它實施例中說明。在這種情況下，有3個原始資料的第一資料被接收，如第4圖所示。每一第一資料的大小為2KB。該原始資料的第一資料能在原始資料接收且分割後得到，一個第一資料接著另一個直到原始資料接收完畢，如此的方式也可以，這取決於主機介面單元101的設計，並不為本發明所限制。本實施例應用了後者。

資料壓縮器102電連接至主機介面單元101。它分割每一第一資料為4個基本單元。每一基本單元劇有相同的大小。如第4圖所示，首先接收到的第一資料具有基本單元D1-1、D1-2、D1-3與D1-4。其次接收到的第一資料具有基本單元D2-1、D2-2、D2-3與D2-4。最後接收到的第一資料具有基本單元D3-1、D3-2、D3-3與D3-4。很明顯的所有的基本單元都是512B。512B設為預定大小。基於不同頁大小與一頁中基本單元的數量，預定大小是可變動的。依照本發明，第一資料中基本單元的數量不限於4個，它可以比4大或比4小，但如果第一資料的大小大於該預定大小，則需要至少二個。如此一來，至少一基本單元可等於該預定大小。然而，本實施例介紹的是理想狀況。如果原始資料的長度或原始資料的最後一部份(依序算來最後一筆第一資料)少於一頁，第一資料中僅一個基本單元會不大於該預定大小而其它基本單元都相同 於該預定大小。資料壓縮器102能壓縮基本單元。有許多用於資料壓縮的演算法可以使用。依照本案構想，無損失壓縮演算法最好用於壓縮基本單元。在本實施例中使用LZ77演算法。實作上，也可使用LZSS、LZH、LZB、LZ78、LZW或LZFG等無損失壓縮演算法。

壓縮的結果說明如下。D1-1與D1-2是不可壓縮的。壓縮的基本單元C1-1與C1-2個別和D1-1與D1-2相同。基本單元D1-3與D1-4具有高壓縮比，因而，它們壓縮為另一個壓縮的基本單元C1-3。D2-1到D2-4是高度可壓縮，對應於基本單元D2-1與D2-2的壓縮的基本單元是C2-1，對應於基本單元D2-3與D2-4的壓縮的基本單元是C2-2。相同地，D3-1到D3-4也是高度可壓縮，對應於基本單元D3-1與D3-2的壓縮的基本單元是C3-1，對應於基本單元D3-3與D3-4的壓縮的基本單元是C3-2。

墊充單元103電連接至資料壓縮器102。它能連接且墊充該壓縮的基本單元，以形成一第二資料。第二資料具有預定大小整數倍的大小，例如，1KB或1.5KB。在極端的例子中，壓縮率是0。第二資料的大小能相同於一頁的大小。請再見第4圖，壓縮的基本單元C1-1、C1-2與C1-3相連接且以一墊充P1墊充(或接附)之。壓縮的基本單元C2-1與C2-2相連接且以一墊充P2墊充，壓縮的基本單元C3-1與C3-2相連接且以一墊充P3墊充。0被用作墊充的元素。這表示墊充P1、P2 與P3皆由0所組成。在上述的極端的例子中，墊充步驟仍進行，但沒有"0"接附到連接與壓縮的基本單元之後。壓縮的基本單元相同於對應之接收到的第一資料。這稱為第一墊充，如第4圖所示。

墊充單元103能墊充第二資料，如果原始資料已完全被接收，連接且墊充第二資料為一第三資料。第二資料儲存於緩衝器104中。如第4圖所示，第二資料包含C1-1、C1-2、C1-3與P1(此後稱之為第二資料1)進一步以一墊充P1-2(P1-2都是"0")之。這稱作第二墊充，如第4圖所示。第三資料具有同一頁的大小，且能編程進入在非揮發性記憶體110中的一特定頁(B23P03)。這是儲存原始資料的最後階段。因為沒有第二資料可結合(詳述於後)，緩衝器104中剩餘的第二資料將被墊充(或連接且墊充)，並一次編程至一頁中。如果緩衝器104有一個以上的第二資料，只要其全部大小小於一頁的大小，它們就能被連接、墊充及編程。

緩衝器104電連接至墊充單元103與非揮發性記憶體110，它能暫時儲存第二資料。如果緩衝器104已滿或實質已滿時，它能以一個新的第二資料取代一個已儲存的第二資料。然而，這工作需要墊充單元103的協助。當緩衝器104已滿或實質已滿(例如剩餘空間不滿預定大小)且沒有第二資料的結合具有一頁的大小頁時，墊充單元103墊充一第二資料為一第三資料，該被墊充的第二資料是緩衝器104所有第二 資料最大的。被墊充的第二資料(第三資料)將被編程到非揮發性記憶體110中。在此刻，另一第二資料將被儲存到緩衝器104中。例如，如果緩衝器104設定為4KB(2頁大小)，第二資料1與由C2-1、C2-2與P2(此後稱之為第二資料2)所組成的第二資料在結合後仍無一頁的大小，較大的第二資料1將由C3-1、C3-2與P3所組成的第二資料(此後稱之為第二資料3)所取代。從而，第二資料2與第二資料3能結合以達到一頁的大小頁。對此，有至少二個第二資料留存於緩衝器104中。新的第二資料可具有和編成的第二資料有不同的大小，至少二第二資料的結合(將詳述於後)能繼續下去。被取代的第二資料也能是緩衝器104所有第二資料中，暫存時間最久的。上述二個方法皆能解決緩衝器已滿的問題。

緩衝器104的大小可以是預定大小的整數倍，它應該4倍大於該預定大小。緩衝器104的大小並未限定於本發明中，但最好是8倍於預定大小，以免接收二個第一資料但緩衝器104滿了。除了某些用作控制的邏輯電路，緩衝器104能包含一動態隨機存取記憶體或靜態隨機存取記憶體。動態隨機存取記憶體或靜態隨機存取記憶體常用於緩衝器中。進一步，緩衝器104能編程第三資料到非揮發性記憶體110的一特定頁中。當第三資料被編程到非揮發性記憶體110中時，一部分的原始資料被儲存了。

結合單元105電連接至緩衝器104，用來結合緩衝器104中至少二個第二資料為一第三資料。請見第4圖。當處理以墊充P2墊充的第二資料與以墊充P3墊充的第二資料，結合單元105找到緩衝器104裡的這兩個第二資料具有一頁的大小(4倍預定大小)，該二個第二資料結合為第三資料並接著被編程到非揮發性記憶體110中。這結合可以是4個具有預定大小的第二資料，它也能是二個第二資料，一個為預定大小的三倍而另一個僅剛好一個預定大小。當然，如果一頁包含超過4個基本單元，結合的態樣就會多變化。

應當注意的是如果第一資料的大小不大於該預定大小且沒有其他第二資料留存於緩衝器104中，接收的第一資料將不會被分割，但能被壓縮、墊充至一頁的大小及編程到非揮發性記憶體110中。這狀況僅發生於原始資料短於預定大小或接收到原始資料的最後一筆第一資料而緩衝器104中沒有第二資料。

映射表單元106電連接至緩衝器104，它儲存與更新一映射表，該映射表有特定頁的一實體頁位址與該原始資料的一邏輯位址之映射連結。請參照第4圖。如果要被儲存的影像檔(原始資料)的邏輯位址是在URL：e：\data\image.jpg，對應的實體頁位址會是B23P03(區塊23頁3)及B23P02(區塊23頁2)。更確切地說，原始資料的第一頁大小被壓縮及儲存於B23P03中，而其它部分儲存於B23P02中。一頁資料以此方 式儲存。對市場上現有具有其它壓縮演算法的裝置，因為沒有"結合步驟"來利用一頁中未被使用的空間，仍需要耗費三整頁的空間。映射表單元106可以是一電可擦除可編程唯讀記憶體或其它具有小於非揮發性記憶體110大小的快閃記憶體晶片。

使用自適應壓縮資料儲存系統100之用於非揮發性記憶體的自適應壓縮資料儲存方法描述於第5圖的流程圖中。請同時見第5圖與第4圖。資料壓縮器102接收來自主機介面單元101的一第一資料(包含基本單元D1-1到D1-4，此後稱之為第一資料1)(S01)。在第一資料1後，一第一資料2(包含基本單元D2-1至D2-4)與一第一資料3(包含基本單元D3-1至D3-4)將依序被接收要注意第一資料1、第一資料2與第一資料3的大小相同於非揮發性記憶體110中一頁的大小，如上所述。連續接收的第一資料1、第一資料2與第一資料3形成一原始資料，該原始資料需要儲存於該非揮發性記憶體110。接著，如果第一資料的大小大於預定大小，512B，資料壓縮器102分割第一資料1為4個基本單元(S02)。在步驟S02中，至少需要二基本單元。資料壓縮器102也包含基本單元D1-1至D1-4(S03)。墊充單元103接手基本單元D1-1到D1-4，它連接及墊充壓縮的基本單元D1-1至D1-4以形成第二資料1，以便第二資料1具有預定大小的整數倍(S04)。接著，第二資料1儲存於緩衝器104中(S05)。用於說明，緩衝器104大小設為3KB。

如果第二資料的數目為1且原始資料並未完全被接收，重複步驟S01到S05(S06)。這意味著應有至少二第二資料可供結合單元105進行結合。在重複這些步驟後，獲得了第一資料2，也創造了第二資料2。下一步驟，搜尋至少二個第二資料，該些第二資料能由結合單元105，結合於緩衝器104中以具有一頁的大小(S07)。如果因為結合的第二資料1與第二資料2之大小超過頁而導致這不可行，應該要有其它的第二資料(第二資料3)用來執行步驟S07。因此，步驟S07、S08與S09跳過不執行。當原始資料並未完全被接收時，再執行步驟S01，從而獲得第一資料3及創造出第二資料3。在步驟S07之後，第二資料2與第二資料3被發現可以結合。結合單元105於緩衝器104中結合第二資料2與第二資料3為一第三資料(S08)。應注意的是原始資料不長，以至於它在此時就接收完畢。然而，對於要儲存較大的原始資料，當原始資料並未完全被接收時，結合步驟持續進行。同時，被結合的第二資料數量不限於二個，但最少需要二個。包含第二資料2與第二資料3的第三資料首先被編程到非揮發性記憶體110的一特定頁(B23P02)中(S09)。接著，如果原始資料已完全被接收，第二資料1被墊充及編程到非揮發性記憶體110的另一特定頁(B23P03)中。如上所述，0被用作墊充的元素。

事實上，步驟S01到S09應重複進行直到原始資料接收完畢(S10)。在原始資料儲存後，映射表單元106更新其 內的一映射表(S11)。在步驟S11中，儲存了一映射連結，該映射連結用於特定頁的實體頁位址(B23P02與B23P03)與該原始資料的邏輯位址之連結。

如果緩衝器104的大小較小，例如2KB，第二資料3不能與第二資料1及第二資料2同時存在，依照本發明，有兩種方法可以解決這個問題。第一種，增加一步驟S08'於步驟S08之後：如果緩衝器104已滿或實質已滿且沒有第二資料的結合具有一頁的大小，墊充緩衝器104中較大的第二資料(第二資料1)為第三資料頁，並編程該第三資料至非揮發性記憶體110中的一特定頁。第二種，增加一步驟S08"於步驟S08之後：如果緩衝器104已滿或實質已滿且沒有第二資料的結合具有一頁的大小，墊充緩衝器104中暫存時間最久的第二資料(第二資料1)為該第三資料，並編程該第三資料至非揮發性記憶體110中的一特定頁。相同地，0被用作墊充的元素。

在本實施例中，原始資料僅具3頁大小。在其它實施例中，原始資料的大小不是一頁的整數倍。依照本發明某些步驟要改變。

請見第6圖，某些元素沿用自第4圖。兩個實施例之間的差異說明如下。首先，原始資料是5.5KB，少於前一個實施例中所舉例的原始資料512B。因此，第一資料3(包含基本單元D3-1至D3-3)大小不滿一整頁(要求至少一基本單元等於該預定大小)。第二，第一資料2具有高壓縮比。基本單 元D2-1至D2-4僅能被壓縮為C2-1，並以墊充P2墊充為第二資料2。第一資料1與第二資料2沒改變。

因此，在步驟S07中，第二資料1與第二資料2將首先被結合並接著編程至B23P02中。因為沒有其它第一資料跟在第一資料3後被接收，第二資料3將再被墊充P4墊充，並於步驟S09中編程進B23P03。在這種情況下，步驟S10將被跳過而執行步驟S11。

在其它實施例中，如果原始資料較大，當原始資料接收完畢，二個或更多的第二資料留存，在步驟S07中，第二資料將被連接且墊充於緩衝器104中，成為一第三資料。相似地，步驟S10將會被跳過，步驟S11將會被執行。

在極端情況下，原始資料太短，以致於原始資料的大小不大於該預定大小。第一資料(僅一個)將不被分割，但直接壓縮及墊充為一頁的大小，並編程至非揮發性記憶體110中。僅步驟S01、S04、S05、S08、S09與S11執行，其餘的步驟都不進行，因為不符合這種情況的要求。

雖然本創作已以實施例揭露如上，然其並非用以限定本創作，任何所屬技術領域中具有通常知識者，在不脫離本創作之精神和範圍內，當可作些許之更動與潤飾，因此本創作之保護範圍當視後附之申請專利範圍所界定者為準。

100‧‧‧自適應壓縮資料儲存系統

101‧‧‧主機介面單元

102‧‧‧資料壓縮器

103‧‧‧墊充單元

104‧‧‧緩衝器

105‧‧‧結合單元

106‧‧‧映射表單元

110‧‧‧非揮發性記憶體

200‧‧‧主機

Claims (17)

1. 一種用於非揮發性記憶體的自適應壓縮資料儲存方法，包含步驟：A.接收一第一資料，其中該第一資料的大小不大於在一非揮發性記憶體中的一頁的大小，連續接收的第一資料形成一原始資料，該原始資料需要儲存於該非揮發性記憶體中；B.如果該第一資料的大小大於一預定大小，分割第一資料為至少二基本單元，其中至少一基本單元等於該預定大小；C.壓縮該基本單元或該第一資料；D.連接且墊充該壓縮的基本單元或該第一資料以形成一第二資料，以便該第二資料具有的大小為該預定大小的整數倍；E.儲存該第二資料於一緩衝器中；F.如果第二資料的數量為1且該原始資料並未完全被接收，重複步驟A到步驟E；G.搜尋至少二第二資料，該些第二資料能結合而具有該緩衝器中一頁的大小；H.於該緩衝器中結合該至少二第二資料為一第三資料，或如果該原始資料已完全被接收，墊充該第二資料或連接且墊充於該緩衝器中的該第二資料為一第三資料，其中該第三資料的大小與一頁相同；I.編程該第三資料到該非揮發性記憶體中的一特定頁；及 J.如果原始資料並未完全被接收，執行步驟A，其中0被用作墊充的元素。
2. 如申請專利範圍第1項所述之自適應壓縮資料儲存方法，進一步包含一步驟I1於步驟I之後：I1.更新一映射表，該映射表儲存該特定頁的一實體頁位址與該原始資料的一邏輯位址之映射連結。
3. 如申請專利範圍第1項所述之自適應壓縮資料儲存方法，進一步包含一步驟H1於該步驟H與步驟I間：H1.如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，墊充具有該緩衝器中所有第二資料裏最大的第二資料為該第三資料，並編程該第三資料至該非揮發性記憶體中之一特定頁，其中0被用作墊充的元素。
4. 如申請專利範圍第1項所述之自適應壓縮資料儲存方法，進一步包含一步驟H2於該步驟H與步驟I間：H2.如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，墊充該緩衝器中所有第二資料裏暫存時間最久的第二資料為該第三資料，並編程該第三資料至該非揮發性記憶體中之一特定頁，其中0被用作墊充的元素。
5. 如申請專利範圍第1項所述之自適應壓縮資料儲存方法，其中一無損失壓縮演算法被用於步驟C以壓縮該第一資料或該基本單元。
6. 如申請專利範圍第5項所述之自適應壓縮資料儲存方法， 其中該無損失壓縮演算法為LZ77、LZSS、LZH、LZB、LZ78、LZW或LZFG。
7. 如申請專利範圍第1項所述之自適應壓縮資料儲存方法，其中該非揮發性記憶體為NAND快閃記憶體或固態硬碟。
8. 如申請專利範圍第1項所述之自適應壓縮資料儲存方法，其中一基本單元被壓縮以形成一壓縮的基本單元，或至少二基本單元被壓縮以形成一壓縮的基本單元。
9. 一種用於非揮發性記憶體的自適應壓縮資料儲存系統，包含：一主機介面單元，用以與一主機溝通及接收來自該主機的第一資料，該些第一資料的尺寸不大於一非揮發性記憶體中一頁的尺寸，其中連續接收的第一資料形成一原始資料，該原始資料需要儲存於該非揮發性記憶體中；一資料壓縮器，電連接至該主機介面單元，如果該第一資料的大小大於一預定大小，用以分割每一第一資料為至少二基本單元及壓縮該基本單元，其中至少一基本單元等於該預定大小；一墊充單元，電連接至該資料壓縮器，用以連接且墊充該壓縮的基本單元以形成一第二資料，及如果該原始資料已完全被接收，墊充該第二資料或連接且墊充該第二資料為一第三資料；一緩衝器，電連接至墊充單元與該非揮發性記憶體，用以 暫時儲存該第二資料、當其已滿或實質已滿時取代一儲存的第二資料，及編程該第三資料至該非揮發性記憶體中的一特定頁；及一結合單元，電連接至該緩衝器，用以結合在該緩衝器中的至少二第二資料為一第三資料，其中如果該原始資料大小不大於該預定大小，該第一資料將不被分割但被壓縮及墊充為一頁的大小且編程至該非揮發性記憶體中；該第二資料具有的大小為該預定大小的整數倍；該第三資料的大小與一頁相同；0被用作墊充的元素。
10. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，進一步包含一映射表單元，電連接至該緩衝器，用以儲存與更新一映射表，該映射表有特定頁的一實體頁位址與該原始資料的一邏輯位址之映射連結。
11. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，其中如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，該墊充單元進一步墊充一第二資料為該第三資料，該被墊充的第二資料為該緩衝器中所有第二資料裏最大的。
12. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，其中如果該緩衝器已滿或實質已滿，且無第二資料的結合具有同一頁的大小，該墊充單元進一步墊充一第二資料為 該第三資料，該被墊充的第二資料為該緩衝器中所有第二資料裏暫存時間最久的。
13. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，其中一無損失壓縮演算法被用以壓縮該第一資料或該基本單元。
14. 如申請專利範圍第13項所述之自適應壓縮資料儲存系統，其中該無損失壓縮演算法為LZ77、LZSS、LZH、LZB、LZ78、LZW或LZFG。
15. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，其中該非揮發性記憶體為NAND快閃記憶體或固態硬碟。
16. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，其中該緩衝器包含一動態隨機存取記憶體或一靜態隨機存取記憶體。
17. 如申請專利範圍第9項所述之自適應壓縮資料儲存系統，其中一基本單元被壓縮以成一壓縮的基本單元，或至少二基本單元被壓縮以形成一壓縮的基本單元。