TW201621696A - 資料傳輸方法及系統 - Google Patents

Abstract

一種資料傳輸方法及系統。在來源裝置中，分割原始資料為多個來源區段，並對各來源區段進行相似度計算，藉此獲得相似值集合，並傳送相似值集合至目標裝置。在目標裝置中，透過相似值集合來判斷在目標裝置中是否存在有與來源區段對應的目標區段，藉以獲得比對結果，並傳送比對結果至來源裝置。在來源裝置中，依據比對結果，對原始資料進行減量獲得減量資料後，傳送減量資料至目標裝置。在目標裝置中，將減量資料還原為原始資料。

Description

資料傳輸方法及系統

本發明是有關於一種遠端資料傳輸機制，且特別是有關於一種能夠降低網路上資料傳輸量的資料傳輸方法及系統。

在資訊發達的現代，各行各業的營運越來越依賴電子產品，尤其是企業用戶更是大力推廣電子化，進而使用電子產品來執行各種功能，記錄各種資料。在而電子裝置間傳輸檔案是一種常見的動作，用戶可透過網路將本地端電子裝置的檔案上傳至遠端電子裝置。然而，隨著資料量越來越龐大，如何加速本地端裝置與遠端裝置之間的資料傳輸則為目前的一大課題。

本發明提供一種資料傳輸方法及系統，可降低資料傳輸的資料量。

本發明的資料傳輸方法，包括下列步驟。在來源裝置中，分割原始資料為多個來源區段，並對各來源區段進行相似度計 算，藉此獲得相似值集合，並傳送相似值集合至目標裝置，其中相似值集合包括各來源區段的相似值。在目標裝置中，透過相似值集合來判斷在目標裝置中是否存在有與其中任一個來源區段對應的目標區段，藉以獲得比對結果，並傳送比對結果至來源裝置。在來源裝置中，依據比對結果，對原始資料進行減量獲得減量資料後，傳送減量資料至目標裝置。在目標裝置中，將減量資料還原為原始資料。

在本發明的一實施例中，上述在目標裝置中，獲得比對結果的步驟包括下列步驟。在判定在目標裝置中不存在與其中任一個來源區段對應的目標區段時，記錄與不存在對應的目標區段的來源區段的相似值以及對應的空值至比對結果。在判定在目標裝置中存在與來源區段對應的目標區段時，記錄存在對應的目標區段的來源區段的相似值以及所對應的目標區段的相似值至比對結果。取出與來源區段對應的目標區段所包括的多個目標區塊各自的哈希值，並記錄這些哈希值至比對結果。

在本發明的一實施例中，根據比對結果，對原始資料進行減量的步驟包括：依據比對結果，對在目標裝置中不具有對應的目標區段的各來源區段執行差量壓縮(delta compression)演算法；對未執行差量壓縮演算法的各來源區段所包括的多個來源區塊執行去重複演算法。對經執行差量壓縮演算法與去重複演算法後的原始資料進行壓縮而獲得減量資料。

在本發明的一實施例中，上述執行差量壓縮演算法的步 驟包括：依序取出其中一個來源區段作為當前區段，並依據比對結果判斷在目標裝置中是否具有對應的目標區段。若否，往前取出當前區段的多個先前區段，並將這些先前區段與當前區段進行比對，進而在上述先前區段中取出與當前區段相近程度最高的第N個來源區段，以對當前區段與第N個來源區段執行差量壓縮演算法。

在本發明的一實施例中，執行去重複演算法的步驟包括：在未執行差量壓縮演算法的來源區段中，依序取出其中一個來源區段所包括的這些來源區塊；判斷來源裝置中的來源區塊表與比對結果中是否具有相同的哈希值，以在具有相同的哈希值時，對上述相同的哈希值標記目標索引。依據來源區塊表，判斷各來源區塊的哈希值是否重複，以對重複的哈希值標記內部索引。

在本發明的一實施例中，在來源裝置中，在分割原始資料為來源區段的步驟之後，更包括：分割各來源區段為該些來源區塊；對各來源區塊進行哈希值計算而分別獲得各來源區塊的哈希值，並記錄至來源區塊表。

在本發明的一實施例中，在目標裝置中，將減量資料還原為原始資料的步驟包括：將減量資料解壓縮；將解壓縮後的減量資料中經由去重複演算所刪除的來源區塊還原；以及將經由差量壓縮演算法所減量的來源區段還原。

在本發明的一實施例中，在來源裝置中，傳送相似值集合與一已接收相似值至目標裝置，其中已接收相似值包括先前自 目標裝置所接收的比對結果所記錄的目標區段的相似值。在目標裝置中，在目標裝置中存在與任一個來源區段對應的目標區段時，倘若已接收相似值中包括有上述目標區段的相似值時，則不將目標裝置的目標區段包括的目標區塊各自的哈希值記錄至當前欲回傳至來源裝置的比對結果。

本發明的資料傳輸系統，包括來源裝置以及目標裝置。來源裝置包括第一通訊單元以及第一處理單元。目標裝置包括第二通訊單元以及第二處理單元。在此，目標裝置與來源裝置藉由第二通訊單元及第一通訊單元進行溝通。第一處理單元分割原始資料為多個來源區段，並對各來源區段進行相似度計算，藉此獲得相似值集合，並傳送相似值集合至目標裝置，其中相似值集合包括各來源區段的相似值。目標裝置在自來源裝置接收到相似值集合後，第二處理單元透過相似值集合來判斷在目標裝置中是否存在有與其中任一個來源區段對應的目標區段，藉以獲得比對結果，並傳送比對結果至來源裝置。來源裝置在自目標裝置接收到比對結果後，第一處理單元依據比對結果，對原始資料進行減量獲得減量資料後，傳送減量資料至目標裝置。目標裝置在自來源裝置接收到減量資料後，第二處理單元將減量資料還原為原始資料。

基於上述，透過來源裝置和目標裝置的協同作業將重複資料刪除後再進行傳輸，以達到降低網路上資料傳輸的資料量以及節省資料儲存量的目的。

為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。

11‧‧‧第一通訊單元

12‧‧‧第一處理單元

13‧‧‧第一記憶單元

14‧‧‧第一儲存單元

15‧‧‧第二通訊單元

16‧‧‧第二處理單元

17‧‧‧第二記憶單元

18‧‧‧第二儲存單元

30‧‧‧相似度集合

40‧‧‧比對結果

100‧‧‧資料傳輸系統

121‧‧‧哈希計算處理器

122‧‧‧資料處理器

123‧‧‧差量壓縮處理器

124‧‧‧去重複處理器

125‧‧‧壓縮處理器

131‧‧‧來源區段表

143‧‧‧來源區塊表

144‧‧‧原始資料

161‧‧‧哈希計算處理器

162‧‧‧資料處理器

163‧‧‧差量解壓縮處理器

164‧‧‧重建處理器

165‧‧‧解壓縮處理器

171‧‧‧目標區段表

184‧‧‧目標區塊表

185‧‧‧複製資料

A‧‧‧來源裝置

B‧‧‧目標裝置

S205~S235‧‧‧資料傳輸方法的各步驟

S405~S435‧‧‧相似度計算程序的各步驟

S601~S640‧‧‧相似度判斷程序的各步驟

S705~S735‧‧‧差量壓縮程序的各步驟

S805~S860‧‧‧去重複程序的各步驟

S905~S965‧‧‧解壓縮程序的各步驟

圖1是依照本發明一實施例的資料傳輸系統的方塊圖。

圖2是依照本發明一實施例的資料傳輸方法的流程圖。

圖3是依照本發明一實施例的來源裝置的資料處理的示意圖。

圖4是依照本發明一實施例的相似度計算程序的流程圖。

圖5是依照本發明一實施例的目標裝置的資料處理的示意圖。

圖6是依照本發明一實施例的相似度判斷程序的流程圖。

圖7是依照本發明一實施例的差量壓縮程序的流程圖。

圖8是依照本發明一實施例的去重複程序的流程圖。

圖9是依照本發明一實施例的解壓縮程序的流程圖。

圖1是依照本發明一實施例的資料傳輸系統的方塊圖。請參照圖1，資料傳輸系統100包括來源裝置A以及目標裝置B。來源裝置A包括第一通訊單元11、第一處理單元12、第一記憶單元13以及第一儲存單元14。第一處理單元12耦接至第一通訊單 元11、第一記憶單元13以及第一儲存單元14。目標裝置B包括第二通訊單元15、第二處理單元16、第二記憶單元17以及第二儲存單元18。第二處理單元16耦接至第二通訊單元15、第二記憶單元17以及第二儲存單元18。來源裝置A與目標裝置B透過第一通訊單元11與第二通訊單元15來進行溝通。

來源裝置A例如是伺服器、後端儲存裝置等具有運算能力的電子裝置。目標裝置B例如為用以備份的電子裝置。而在其他實施例中，來源裝置A與目標裝置B的數量亦可以是多台來源裝置A對一台目標裝置B，或是多台來源裝置A對多台目標裝置B。

第一記憶單元13與第二記憶單元17例如為隨機存取記憶體(Random Access Memory，RAM)等揮發性記憶體。第一儲存單元14與第二儲存單元18例如為磁碟等非揮發性儲存元件。第一記憶單元13用以儲存來源區段表131，第一儲存單元14用以儲存來源區塊表143以及原始資料144。第二記憶單元17用以儲存目標區段表171，第二儲存單元18用以儲存目標區塊表184以及複製資料185。

第一處理單元12與第二處理單元16例如為中央處理單元(Central Processing Unit，CPU)、可程式化之微處理器(Microprocessor)、嵌入式控制晶片等。第一通訊單元11與第二通訊單元15例如是有線網路介面卡或無線網路介面卡，藉以連線至網路，進而透過網路使得來源裝置A與目標裝置B得以進行溝 通。

在來源裝置A中，第一處理單元12包括哈希(hash)計算處理器121、資料處理器122、差量壓縮(delta compression)處理器123、去重複(deduplication)處理器124以及壓縮處理器125。在目標裝置B中，第二處理單元16包括哈希計算處理器161、資料處理器162、差量解壓縮(delta decompression)處理器163、重建(reconstruct)處理器164以及解壓縮處理器165。透過上述各處理器來實現來源裝置A與目標裝置B之間的資料傳輸方法。

底下即搭配上述資料傳輸系統100來說明資料傳輸方法的各步驟。圖2是依照本發明一實施例的資料傳輸方法的流程圖。請同時參照圖1及圖2，在來源裝置A中，第一處理單元12分割原始資料144為多個來源區段，並對各來源區段進行相似度計算，藉此獲得相似值集合(步驟S205)，並傳送相似值集合至目標裝置B(步驟S210)。在此，相似值集合包括各來源區段進行相似度計算所獲得的多個相似值。

目標裝置B在自來源裝置A接收到相似值集合後，第二處理單元16透過相似值集合來判斷在目標裝置B中是否存在有與其中任一個來源區段對應的目標區段，藉以獲得比對結果(步驟S215)，並傳送比對結果至來源裝置A(步驟S220)。

來源裝置A在自目標裝置B接收到比對結果後，第一處理單元12依據比對結果，對原始資料144進行減量獲得減量資料(步驟S225)，之後傳送減量資料至目標裝置B(步驟S230)。目 標裝置B在自來源裝置A接收到減量資料後，第二處理單元16將減量資料還原至原始資料(步驟S235)。

具體而言，在步驟S205中，來源裝置A的第一處理單元12透過資料處理器122將原始資料144分割為多個區段(segment)，並且將各區段分割為多個區塊(block)。在此，將原始資料144所分割的區段稱為來源區段，而將各來源區段所分割的區塊稱為來源區塊。而哈希計算處理器121對各來源區段進行相似度計算，以將各來源區段的相似值記錄至來源區段表131，並且對各來源區塊進行哈希值計算，以將各來源區塊的哈希值記錄至來源區塊表143。

舉例來說，圖3是依照本發明一實施例的來源裝置的資料處理的示意圖。圖4是依照本發明一實施例的相似度計算程序的流程圖。第一處理單元12透過資料處理器122將原始資料144分割為來源區段SS1~來源區段SS#I。在此，以“#I”表示切割的總數量。在此，來源區段SS1分割為來源區塊SB1~SB#M，來源區段SS2分割為來源區塊SB#M+1~SB#N，來源區段SS3分割為來源區塊SB#N+1~SB#O。在此，以“#M”、“#N”、“#O”分別表示來源區段SS1、SS2、SS3所切割的來源區塊的總數量。其他亦以此類推。

底下搭配圖1~圖4對相似度計算程序進行說明。在步驟S405中，哈希計算處理器121判斷在目前階段是否到達原始資料144的末端。若是，則前進下一個處理程序F2(參照下述圖6)。 若否，在步驟S410中，哈希計算處理器121取出下一個來源區塊。即，首次執行步驟S410時，取出第一個來源區塊SB1，後續再執行步驟S410時，則取出下一個來源區塊SB2，以此類推。

之後，在步驟S415中，哈希計算處理器121計算所取出的來源區塊的哈希值。例如，哈希計算處理器121使用、安全哈希演算法(Secure Hash Algorithm，SHA)、訊息摘要演算法第五版(Message-Digest Algorithm 5，MD5)、循環冗餘查核(Cyclic redundancy check，CRC)或等對來源區塊進行哈希值計算，進而獲得來源區塊的哈希值。

然後，在步驟S420中，哈希計算處理器121將獲得的哈希值記錄至來源區塊表143。並且，在步驟S425中，哈希計算處理器121判斷目前階段是否到達其中一個來源區段的末端。若否，則返回步驟S410，取出下一個來源區塊，以計算其哈希值。

若是，則在步驟S430中，哈希計算處理器121基於這一個來源區段所包括的多個來源區塊的哈希值，而計算出一相似值。在此，來源區段的相似值包括數個具有代表性的哈希值。例如，哈希計算處理器121利用K平均(K-means)演算法、MinHash演算法、SimHash演算法、局部敏感哈希(Locality Sensitive Hashing，LSH)演算法等在所有來源區塊的哈希值中選出具有代表性的多個哈希值，以此來作為其相似值。在圖3中，來源區段SS1對應的相似值為SHS1，來源區段SS2對應的相似值為SHS2，以此類推，來源區段SS#I對應的相似值為SHS#I。

之後，在步驟S435中，哈希計算處理器121將獲得的相似值記錄至來源區段表131中。據此，每一個來源區塊具有一個哈希值，每一個來源區段具有一個相似值(其包括多個具有代表性的哈希值)。

另外，在獲得各來源區塊的哈希值之後，還可透過資料處理器122將各來源區塊的塊編號、對應的哈希值實體位址以及相關區塊編號記錄至第一儲存單元14中的來源區塊表143。以來源區塊SB2而言，假設來源區塊SB的哈希值BHS2與來源區塊SB1的哈希值BHS1相同，則將來源區塊SB2與來源區塊SB1進行關聯。例如，將來源區塊SB1的區塊編號記錄至來源區塊SB2對應的相關區塊編號。

在相似度計算程序結束之後，資料處理器122將各來源區段的相似值作為相似值集合30，並且在步驟S210中，透過第一通訊單元11將相似值集合30傳送至目標裝置B。

在步驟S215中，目標裝置B的資料處理器162會查詢目標區段表171來判斷相似值集合30的相似值與目標區段表171所記錄的相似值之間的相近程度。藉此，資料處理器162判斷在目標裝置B中是否存在與來源區段相對應的目標區段。即，目標區段表171的相似值與相似值集合30所包括的相似值之間的相近程度高時，表示目標裝置B中存在與來源區段相似的目標區段。

具體而言，在目標裝置B中，資料處理器162在接收到複製資料185之後，亦會如同步驟S205，資料處理器162對複製 資料185執行分割而獲得多個區段，並且將各區段分割為多個區塊。在此，將複製資料185所分割的區段稱為目標區段，而將各目標區段所分割的區塊稱為目標區塊。而哈希計算處理器161對各目標區段進行相似度計算，以將各目標區段的相似值記錄至目標區段表171，並且對各目標區塊進行哈希值計算，以將各目標區塊的哈希值記錄至目標區塊表184。在此，來源裝置A與目標裝置B是使用相同的演算法來執行相似度計算，並且雙方在將資料分割為區段的尺寸亦相同，但切割後的數量不一定會相同。

舉例來說，圖5是依照本發明一實施例的目標裝置的資料處理的示意圖。請參照圖5，資料處理器162將複製資料185分割為目標區段TS1~來源區段TS#I。在此，以“#I”表示切割的總數量。目標區段TS1分割為目標區塊TB1~TB#M，目標區段TS2分割為目標區塊TB#M+1~TB#N，目標區段TS3分割為目標區塊TB#N+1~TB#O。在此，以“#M”、“#N”、“#O”分別表示目標區段TS1、TS2、TS3所切割的來源區塊的總數量。其他亦以此類推。

而目標裝置B的相似度計算程序與來源裝置A的相似度計算程序相似，相關描述可參照步驟S405~S435，在此省略不提。哈希計算處理器161在經由如步驟S405~S435之後，獲得各目標區塊的哈希值並將其記錄至目標區塊表184，以及獲得各目標區段的相似值並將其記錄至目標區段表171。而每一個目標區塊具有一個哈希值，每一個目標區段具有一個相似值(其包括多個具有代 表性的哈希值)。

另外，在獲得各目標區塊的哈希值之後，還可透過資料處理器162將其區塊編號、對應的相似值、實體位址以及相關區塊編號記錄至第二儲存單元18中的目標區塊表184。

據此，當目標裝置B自來源裝置A接收到相似值集合30之後，透過資料處理器162來比對相似值集合30的相似值與目標區段表171所記錄的相似值之間的相似程度高低。藉此，判斷在目標裝置B中是否存在有與各來源區段對應的目標區段。

圖6是依照本發明一實施例的相似度判斷程序的流程圖。底下搭配圖1、圖5及圖6對相似度計算程序進行說明。本實施例可承接至圖4的流程。即，在圖4中，當來源裝置A全部的來源區段以及來源區塊皆執行完哈希值計算之後，前進至處理程序F2。在步驟S601中，資料處理器122查詢來源區段表131，並且在步驟S603中，取出原始資料144的相似值集合，而傳送相似值集合至目標裝置B。

接著，目標裝置B透過其資料處理器162來判斷雙方是否具有相似的區段。在步驟S610中，資料處理器162在相似值集合中取出下一個相似值。接著，在步驟S615中，判斷是否具有下一個相似值。也就是說，在首次執行步驟S610時，取出第一個相似值，之後再次執行步驟S610時，則依序取出下一個相似值。而直到最後一個相似值被取出後，再次執行步驟S610、S615時，將不具有下一個相似值，則在步驟S615的否，執行步驟S604。

在步驟S615的是，執行步驟S620，資料處理器162查表並進行比對。即，資料處理器162查詢目標區段表171，比對相似值集合30的相似值與目標區段表171所記錄的相似值之間的相似程度為高或低。

在判定相似值集合30的相似值(底下稱為第一相似值)與目標區段表171所記錄的相似值(底下稱為第二相似值)其中任一之間的相近程度皆不高時(即，目標裝置B中不存在與來源區段對應的目標區段)，返回執行步驟S610，自相似值集合30取出下一個相似值。並且，資料處理器162將與第二相似值之間相近程度低的第一相似值以及對應的空值記錄至比對結果40。例如為“SHS2：{NIL}”。

在判定第一相似值具有相似程度高的第二相似值時(即，判定在目標裝置B中存在與來源區段對應的目標區段)，在步驟S630中，判定該組第一相似值與第二相似值是否已記錄至比對結果40。若否，執行步驟S635，資料處理器162取出相似程度高的第二相似值對應的多個目標區塊各自的哈希值。

之後，在步驟S640中，資料處理器162記錄第一相似值以及對應的相似程度高的第二相似值至比對結果40。例如為“SHS1：{SHT5,SHT8}”、“SHS3：{SHT3}”。並且，資料處理器162將相似程度高的第二相似值對應的多個目標區塊各自的哈希值記錄至比對結果40。例如以“SHS3：{SHT3}”而言，第一相似值SHS3與第二相似值SHT3之間的相似程度高，因而取出第二相似值 SHT3對應的所有的目標區塊TB#N+1~TB#O的哈希值，並記錄至比對結果40。如比對結果40中的“{…,BHT23,…BHT55,…,BHT67,…BHT203,…}”所示。

若在步驟S630中判定上述第二相似值已記錄至比對結果40，則執行步驟S640，資料處理器162不會重複記錄的第二相似值對應的目標區塊的哈希值，而僅再次記錄第二相似值。例如，假設第一相似值SHS4亦與第二相似值SHT3之間相似程度高，由於第二相似值SHT3對應的所有的目標區塊TB#N+1~TB#O的哈希值已記錄至比對結果40，則僅在比對結果40中記錄“SHS4：{SHT3}”。

之後，返回執行步驟S610，直到相似值集合中的相似值全部比對完畢為止。然後，在步驟S604中，目標裝置B回傳比對結果至來源裝置A。並且，在步驟S602中，來源裝置A將比對結果記錄至來源區段表131。例如，記錄各來源區段所對應的目標區段的相似值。之後，前進至下一個處理程序F3(如下述圖7所示)。

對照圖2的流程而言，來源裝置A在接收到比對結果後，在步驟S225中，依據比對結果，對在目標裝置B中不具有對應的目標區段的來源區段執行差量壓縮演算法，並對未執行差量壓縮演算法的來源區段所包括的多個來源區塊執行去重複演算法，以及對經執行差量壓縮演算法與去重複演算法後的原始資料144進行壓縮而獲得減量資料。

圖7是依照本發明一實施例的差量壓縮程序的流程圖。 在本實施例中，差量壓縮處理器123依序取出上述來源區段其中一個作為當前區段，並依據比對結果判斷當前區段在目標裝置B中是否具有對應的目標區段。若否，差量壓縮處理器123往前取出與該當前區段相近程度最高的第N個來源區段，以對當前區段與第N個來源區段執行差量壓縮演算法。

詳細地說，在步驟S705中，列出欲傳送的來源區段{SS2,SS4,SS5…,SS#I}。接著，在步驟S710中，差量壓縮處理器123判斷是否有下一個來源區段。若是，在步驟S715中，差量壓縮處理器123取出下一個來源區段。若否，表示所有來源區段已執行完差量壓縮程序，則前進至下一個處理程序F4(參照下述圖8)。

差量壓縮處理器123在取出來源區段後，在步驟S720中，依據比對結果40來判斷所取出的來源區段(當前區段)是否與目標裝置B中的目標區段之間的為相近程度低。即，當在比對結果中來源區段的相似值對應至一空值時，代表此來源區段與目標裝置B中的目標區段為相近程度低。當在比對結果中來源區段的相似值對應至另一相似值時，代表此來源區段與目標裝置B中的目標區段為相近程度高。以圖5的比對結果40所記錄的“{SHS1：{SHT5,SHT8}”及“SHS3：{SHT3}”而言，其代表來源裝置A的相似值SHS1以及SHS3在目標裝置B中具有相似程度高的的相似值。

若步驟S720為否，則返回執行步驟S705，以取出下一個來源區段。若步驟S720為是，執行步驟S725，差量壓縮處理器 123往前取出相似程度最高的第N個來源區段。詳細地說，差量壓縮處理器123往前取出當前區段的多個先前區段，並將這些先前區段與當前區段進行比對，進而在上述先前區段中取出相似程度最高的第N個來源區段。並且，在步驟S735中，差量壓縮處理器123對所取出的來源區段(當前區段)與第N個來源區段執行差量壓縮演算法。例如，假設目前取出第4個來源區段，則差量壓縮處理器123可以往前取出第1個至第3個來源區段，並且將第1個至第3個來源區段逐一與第4個來源區段進行比對，進而取出與第4個來源區段相近程度最高的其中一個來源區段(例如為第1個來源區段)，而對第4個來源區段與第1個來源區段執行差量壓縮演算法。在此，值得注意的是，由於第1個來源區段不具有先前區段，因此第1個來源區段不會執行差量壓縮演算法，而是從第2個來源區段開始來判斷是否要執行差量壓縮演算法。

圖8是依照本發明一實施例的去重複程序的流程圖。在步驟S805中，列出欲傳送的來源區段{SS2,SS4,SS5…,SS#I}。接著，在步驟S810中，去重複處理器124判斷是否有下一個來源區段。若是，在步驟S815中，去重複處理器124取出下一個來源區段。若否，表示所有來源區段已執行完去重複程序，則前進至下一個處理程序F5(參照下述圖9)。

去重複處理器124在取出來源區段後，在步驟S820中，判斷此一來源區段是否有執行差量壓縮演算法。若是，返回執行步驟S805，以取出下一個來源區段。若否，在步驟S825中，列 出此一來源區段包括的來源區塊。在步驟S830中，去重複處理器124判斷是否有下一個來源區塊。若是，在步驟S835中，去重複處理器124取出下一個來源區塊。若否，表示此一來源區段的所有來源區塊已執行完去重複程序，則返回執行步驟S805，以取出下一個來源區段。

在取出來源區塊後，在步驟S840中，去重複處理器124判斷來源區塊表143與比對結果40中是否有相同的哈希值。在具有相同的哈希值時，在步驟S850中，對相同的哈希值標記一目標索引，代表此一來源區塊在目標裝置B中具有相同的一目標區塊。若步驟S840為否，執行步驟S845，去重複處理器124依據來源區塊表143，判斷各來源區塊的哈希值是否重複。若步驟S845為是，在步驟S855中，對重複的哈希值標記一內部索引，表示此一來源區塊在原始資料144中具有其他相同的區塊。若步驟S845為否，則執行步驟S860，由壓縮處理器125對此一來源區塊執行資料壓縮程序。

據此，在藉由上述步驟S705~S735以及步驟S805~S860後，獲得減量資料。根據目標裝置B回傳的比對結果40，來源裝置A可以知道原始資料144中的哪些來源區塊已經存在於目標裝置B。去重複處理器124可將重複的資料刪除後，再由壓縮處理器125壓縮剩餘的資料。

接著，對圖2的步驟S235進行詳細的說明。圖9是依照本發明一實施例的解壓縮程序的流程圖。在步驟S905中，目標裝 置B列出已接收的來源區段{SS2,SS4,SS5…,SS#I}。接著，在步驟S910中，差量解壓縮處理器163判斷是否有下一個來源區段。若是，在步驟S915中，差量解壓縮處理器163取出下一個來源區段。若否，表示所有來源區段已執行完解壓縮程序，則結束解壓縮程序。

接著，在步驟S920中，差量解壓縮處理器163判斷此一來源區段是否有執行差量壓縮演算法。若步驟S920為是，執行步驟S925，差量解壓縮處理器163對此一來源區段執行差量解壓縮演算法。之後，返回執行步驟S905，以取出下一個來源區段。若步驟S920為否，執行步驟S930，重建處理器164列出來源區段包括的來源區塊。並且，在步驟S935中，列出此一來源區段包括的來源區塊。在步驟S935中，重建處理器164判斷是否有下一個來源區塊。若是，在步驟S940中，重建處理器164取出下一個來源區塊。若否，返回執行步驟S905，以取出下一個來源區段。

在取出來源區塊之後，在步驟S945中，重建處理器164判斷是否有標記目標索引。若步驟S945為是，在步驟S955中，重建處理器164複製對應的目標區塊。之後返回執行步驟S930，以取出下一個來源區塊。若步驟S945為否，在步驟S950中，重建處理器164判斷是否有標記內部索引。若步驟S950為是，在步驟S960中，重建處理器164複製對應的來源區塊。若步驟S950為否，在步驟S965中，解壓縮處理器165對此來源區塊進行解壓縮。之後返回執行步驟S930，以取出下一個來源區塊。

另外，值得注意的是，在其他實施例中，來源裝置A還可依據自目標裝置B先前所接收的比對結果，傳送相似值集合與一已接收相似值至目標裝置B。已接收相似值包括先前自目標裝置B所接收的比對結果所記錄的目標區段的相似值。在目標裝置B中，在判定目標裝置B中存在與來源區段對應的目標區段時，倘若已接收相似值中包括有目標區段的相似值時，則不將目標裝置的目標區段包括的目標區塊各自的哈希值記錄至當前欲回傳至來源裝置A的比對結果。

例如，來源裝置A前次接收的比對結果中包括目標裝置B的相似值SHT3、SHT5、SHT8，則在這次執行步驟S205時，會將目標裝置B的相似值SHT3、SHT5、SHT8作為已接收相似值，並且一併將已接收相似值與這次的相似值集合傳送至目標裝置B。目標裝置B在接收到已接收相似值與這次的相似值集合之後便能夠知道在來源裝置A中已經存在這些相似值SHT3、SHT5、SHT8所包括的所有區塊的哈希值。因此，目標裝置B在執行完步驟S215後，倘若這次回傳的比對結果包括“{SHS1：{SHT5,SHT8}”，則在這次的比對結果中只會傳送相似值SHT5、SHT8，而不會傳送相似值SHT5、SHT8所包括的所有區塊的哈希值。據此，可減少區塊的哈希值的傳遞，進而進一步降低資料傳輸量。

綜上所述，來源裝置將原始資料分割為多個區段並計算其相似值集合，進而傳送資料量較小的相似值集合至目標裝置。在目標裝置中進行比對後，亦是傳送包括資料量小的相似值與哈 希值的比對結果至來源裝置。來源裝置便依據比對結果來對原始資料進行減量。透過來源裝置和目標裝置的協同作業，先傳遞資料量較小的相似值集合，使得來源裝置將重複資料刪除後再進行傳輸。據此，可降低網路上資料傳輸的資料量以及節省資料儲存量。

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

S205~S235‧‧‧資料傳輸方法的各步驟

Claims (14)

1. 一種資料傳輸方法，包括：在一來源裝置中，分割一原始資料為多個來源區段，並對每一該些來源區段進行一相似度計算，藉此獲得一相似值集合，並傳送該相似值集合至一目標裝置，其中該相似值集合包括該些來源區段各自的相似值；在該目標裝置中，透過該相似值集合來判斷在該目標裝置中是否存在有與該些來源區段其中任一個對應的目標區段，藉以獲得一比對結果，並傳送該比對結果至該來源裝置；在該來源裝置中，依據該比對結果，對該原始資料進行減量獲得一減量資料後，傳送該減量資料至該目標裝置；以及在該目標裝置中，將該減量資料還原為該原始資料。
2. 如申請專利範圍第1項所述的資料傳輸方法，其中在該目標裝置中，獲得該比對結果的步驟包括：在判定在該目標裝置中不存在與該些來源區段其中任一個對應的該目標區段時，記錄與不存在對應的該目標區段的其中一個上述來源區段的該相似值以及對應的一空值至該比對結果；在判定在該目標裝置中存在與該些來源區段其中任一個對應的該目標區段時，記錄存在對應的該目標區段的其中一個上述來源區段的該相似值以及所對應的該目標區段的相似值至該比對結果；以及取出與該些來源區段其中任一個對應的該目標區段包括的多 個目標區塊各自的哈希值，並記錄該些哈希值至該比對結果。
3. 如申請專利範圍第2項所述的資料傳輸方法，其中在該來源裝置中，依據該比對結果，對該原始資料進行減量的步驟包括：依據該比對結果，對在該目標裝置中不具有對應的該目標區段的每一上述來源區段執行一差量壓縮(delta compression)演算法；對未執行該差量壓縮演算法的每一上述來源區段所包括的多個來源區塊執行一去重複演算法；以及對經執行該差量壓縮演算法與該去重複演算法後的該原始資料進行壓縮而獲得該減量資料。
4. 如申請專利範圍第3項所述的資料傳輸方法，其中執行該差量壓縮演算法的步驟包括：依序取出上述來源區段其中一個作為一當前區段，並依據該比對結果判斷在該目標裝置中是否具有對應的該目標區段；若否，往前取出該當前區段的多個先前區段，並將該些先前區段與該當前區段進行比對，進而在該些先前區段中取出與該當前區段相近程度最高的第N個上述來源區段，以對該當前區段與上述第N個來源區段執行該差量壓縮演算法。
5. 如申請專利範圍第3項所述的資料傳輸方法，其中執行該去重複演算法的步驟包括：在未執行該差量壓縮演算法的上述來源區段中，依序取出上述來源區段其中一個所包括的該些來源區塊； 判斷該來源裝置中的一來源區塊表與該比對結果中是否具有相同的哈希值，以在具有相同的哈希值時，對上述相同的哈希值標記一目標索引；以及依據該來源區塊表，判斷每一上述來源區塊的哈希值是否重複，以對重複的上述哈希值標記一內部索引。
6. 如申請專利範圍第5項所述的資料傳輸方法，其中在該來源裝置中，在分割該原始資料為該些來源區段的步驟之後，更包括：分割每一該些來源區段為該些來源區塊；以及對每一該些來源區塊進行一哈希值計算而分別獲得該些來源區塊各自的哈希值，並記錄至該來源區塊表。
7. 如申請專利範圍第3項所述的資料傳輸方法，其中在該目標裝置中，將該減量資料還原為該原始資料的步驟包括：將該減量資料解壓縮；將解壓縮後的該減量資料中經由該去重複演算所刪除的上述來源區塊還原；以及將經由該差量壓縮演算法所減量的該些來源區段還原。
8. 如申請專利範圍第2項所述的資料傳輸方法，更包括：在該來源裝置中，傳送該相似值集合與一已接收相似值至該目標裝置，其中該已接收相似值包括先前自該目標裝置所接收的該比對結果所記錄的該目標區段的相似值；以及在該目標裝置中，在該目標裝置中存在與該些來源區段其中 任一個對應的該目標區段時，倘若該已接收相似值中包括有上述目標區段的該相似值時，則不將該目標裝置的上述目標區段包括的上述目標區塊各自的哈希值記錄至當前欲回傳至該來源裝置的該比對結果。
9. 一種資料傳輸系統，包括：一來源裝置，包括一第一通訊單元以及一第一處理單元；以及一目標裝置，包括一第二通訊單元以及一第二處理單元，其中，該目標裝置與該來源裝置藉由該第二通訊單元及該第一通訊單元進行溝通；其中，該第一處理單元分割一原始資料為多個來源區段，並對每一該些來源區段進行一相似度計算，藉此獲得一相似值集合，並傳送該相似值集合至該目標裝置，其中該相似值集合包括該些來源區段各自的相似值；該目標裝置在自該來源裝置接收到該相似值集合後，該第二處理單元透過該相似值集合來判斷在該目標裝置中是否存在有與該些來源區段其中任一個對應的目標區段，藉以獲得一比對結果，並傳送該比對結果至該來源裝置；該來源裝置在自該目標裝置接收到該比對結果後，該第一處理單元依據該比對結果，對該原始資料進行減量獲得一減量資料後，傳送該減量資料至該目標裝置；以及該目標裝置在自該來源裝置接收到該減量資料後，該第二處 理單元將該減量資料還原為該原始資料。
10. 如申請專利範圍第9項所述的資料傳輸系統，其中該來源裝置更包括：一第一記憶單元，耦接至該第一處理單元，儲存一來源區段表；以及一第一儲存單元，耦接至該第一處理單元，儲存該原始資料以及一來源區塊表；其中該第一處理單元更包括：一第一資料處理器，分割該原始資料為該些來源區段，以及分割每一該些來源區段為多個來源區塊；以及一第一哈希計算處理器，對每一該些來源區段進行該相似度計算，以將每一上述來源區段的相似值記錄至該來源區段表，以及對每一該些來源區塊進行該相似度計算，以將該些來源區塊各自的哈希值記錄至該來源區塊表；該目標裝置更包括：一第二記憶單元，耦接至該第二處理單元，儲存一目標區段表；以及一第二儲存單元，耦接至該第二處理單元，儲存一目標區塊表；該第二處理單元包括：一第二資料處理器，透過該相似值集合來判斷在該目標裝置中是否存在有與該些來源區段其中任一個對應的目標區段， 並且分割該複製資料為多個上述目標區段，以及分割每一上述目標區段為多個目標區塊；以及一第二哈希計算處理器，對每一上述目標區段進行該相似度計算，以將每一上述目標區段的相似值記錄至該目標區段表，以及對每一上述目標區塊進行一哈希值計算，以將上述目標區塊自的哈希值記錄至該目標區塊表。
11. 如申請專利範圍第9項所述的資料傳輸系統，其中在該目標裝置獲得該比對結果之後，該第二資料處理器執行下列動作，包括：在判定在該目標裝置中不存在與該些來源區段其中任一個對應的該目標區段時，記錄與不存在對應的該目標區段的其中一個上述來源區段的該相似值以及對應的一空值至該比對結果；在判定在該目標裝置中存在與該些來源區段其中任一個對應的該目標區段時，記錄存在對應的該目標區段的其中一個上述來源區段的該相似值存在對應的該目標區段的其中一個上述來源區段的該相似值以及所對應的該目標區段的相似值至該比對結果；以及取出與該些來源區段其中任一個對應的該目標區段包括的多個目標區塊各自的哈希值，並記錄該些哈希值至該比對結果。
12. 如申請專利範圍第10項所述的資料傳輸系統，其中該第一處理單元更包括：一差量壓縮處理器，依據該比對結果，對在該目標裝置中不 具有對應的該目標區段的每一上述來源區段執行一差量壓縮演算法；一去重複處理器，對未執行該差量壓縮演算法的每一上述來源區段所包括的多個來源區塊執行一去重複演算法；以及一壓縮處理器，對經執行該差量壓縮演算法與該去重複演算法後的該原始資料進行壓縮而獲得該減量資料。
13. 如申請專利範圍第12項所述的資料傳輸系統，其中該第二處理單元更包括：一解壓縮處理器，將該減量資料解壓縮；一重建處理器，將解壓縮後的該減量資料中經由該去重複演算所刪除的該或該些來源區塊還原；以及一差量解壓縮處理器，將經由該差量壓縮演算法所減量的該些來源區段還原。
14. 如申請專利範圍第10項所述的資料傳輸系統，其中在該來源裝置中，該第一資料處理器傳送該相似值集合與一已接收相似值至該目標裝置，其中該已接收相似值包括先前自該目標裝置所接收的該比對結果所記錄的該目標區段的相似值；在該目標裝置中，該第二資料處理器在該目標裝置中存在與該些來源區段其中任一個對應的該目標區段時，倘若該已接收相似值中包括有上述目標區段的該相似值時，則不將該目標裝置的上述目標區段包括的上述目標區塊各自的哈希值記錄至當前欲回傳至該來源裝置的該比對結果。