TW501350B - Data compression apparatus, database system, data communication system, data compression method, and program transmission apparatus - Google Patents

Description

501350 A7 B7 i、發明說明（ [發明領域] ~ 上本發明係關^ —種資料壓縮方法1以將以-樹狀區域 Q所挨寫之文件貝料壓縮，該樹狀區域語言像是 或者ASN.1。 [背景技藝]

XML(可擴充標示語言）係標示語言之一，用以描述（標 不）使用簡單標籤的一文件之邏輯結構eKXML*，文法 規則已正規化，而且提供邏輯定義，供一文件之組成用， 所以使用者可唯一擴充文件資料。因此，預計未來XML •將可-作爲網際網路上資料交換的一資料格式。 XML具有一觀念稱爲DTD(文件型態定義），可用以決定 -特定DTD文件是否有效。如一特定例子，文法規則將予 以正規化，使節點<標題〉，〈作者 >及< 出版商〉於一節點 <書籍〉下依命名次序各出現一次。而且可決定一預先決 定之文件是否有效，亦即該預先決定之文件是否遵循該文 法規則。 ，至=語言風格，一 XML文件之結構屬於一種稱爲樹狀區 域ΐα 〇的種類。根據樹狀區域語言定義，資料係以一具標 籤樹狀結構表示，而個別節點標記之正確資料係以子節點 標記的正規語言正規化。亦即，於一樹狀區域語言中，屬 於一預先決定之文法的一組樹係以指定個別節點其子節點 清單之正規語言決定，其中該預先決定之文法係以xml 中的DTD正規化。另一種這類樹狀區域語言爲ASN.丨（抽 象語法記號1)。 -4 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） (請先閱讀背面之注意事填寫本頁) 11¾ 經濟部智慧財產局員工消費合作社印製 A7 B7 經濟部智慧財產局員工消費合作社印製 五、發明說明（2 ) 趨勢使用XML撰窝複雜資料結構，供商用應用 m他料使用，該等複料料結構以前無法使用 :L及網際網路上可用之其他資源撰寫。預計，使用此 系統，大型XML文件將可藉由應用程式進行交換。 2而，言，當交換資料或將其儲存I—資料庫時，資料 檔案將予以壓縮，以減少並女I 5 其大小，而且增加傳輸效率。因 匕，推料多可用於各種資料格式型態之多用途資祕縮 ㈣’ W許乡料料特定資料格式制的特殊化資料 ^技術1以交換XML文件。關於壓縮，應注意：當 — 〈貝衬、、·口構時’須仔細考慮多餘使用之標 鐵，才能期待高壓縮率。 [本發明解決之問題] 如^上所述，—般而言，資料㈣壓縮之執行用以協助 資料交換’並且將資料儲存於資料庫巾。使用像是狐 的一樹狀區域語言，則可期待像是標籤等表示文件結構之 資料部分的高壓縮率。 _ 假設’當資料進行通訊時，雙方同樣使用一文法〇，並 且保證其僅交換該文法中有效之狐文件。同時假設， 文法規則將予以正規化，使節點<標題〉，<作者>及< 出 版商〉於節點< 書籍〉下各出現一次。此情況下，當一 XML又件之接受器偵測得該xml文件中的一標籤〈書籍〉 時·，則孩接受器可預測：第一子節點將爲 < 標題 >。因 此，根據此假設，標籤 < 標題 > 變成多餘，因而能夠設計 種知XML文件加以編碼而最佳化訊息長度之方法。其 -5 本紙張尺錢財目國家標準（CNS)ATiiTHF7297公釐） (請先閱讀背面之注意事填寫本頁) 丨裝 ·- -線. 五、發明說明（3 不僅可應用於XML-，同時可應用於任意 士 (例如 ASN.1)。 ^ ^ σ 二文：，=未建議任何壓縮方法，用以將-樹狀區 域居g又件的結構邵分編碼。 、五因此，本發明的一目標爲：使用資料壓縮，將樹狀區域 ㈣構部分編碼，其中該等樹狀 XML或者ASN.1。 X p。像疋 本發明的另一目標爲·担/使 铋馬·棱供一種特殊化之資料壓縮方 法，供一樹狀區域語言用，乂血 .連心而可實現-高壓縮率:…另彳用途貝料壓縮技術 [發明概述] 二達=上目標，根據本發明’―種將資料編碼以及將 馬碼'貝料壓縮之資料壓縮裝置包含：一文法儲存單元，用 :儲存-樹狀區域語言.之文法規則，其中資料係以一具標 戴树狀結構表示；-編·碼器，用以讀取以該樹狀區域组士 撰:寫的一文件，將該文件分割成一結構部分與内容， 經濟部智慧財產局員工消費合作社印制衣 :咸又法儲存單：中所儲存之文法規則，將該結構部分編 二’以及_壓縮器，用以將該編碼器所擷取之文件其内容 f縮並知逐壓^内容編碼。該樹狀區域語言係—樹狀言五 1 ’其中資料係以-具標籤樹狀結構表示，且其中，相^ 於個別郎點標記，正確資料係使用子節點 規語言正規化。 叮使試正 碼器包括：-分割器，用以將-目標文件分割成— -構4分與内容；—自動機建構器，用以建構對應於該文 -6- 五、發明說明（4 ) 法規則之下推自動機；以 機建構器所建構之下推—編碼資料產生器，使用自動 得之文件其結構部分的語2 ’執行該藉由該分割器所獲 編碼資料串。 77析，並產生该結構部分的一 該編碼器之編碼資料彦 ⑽ 建構器所建構之下推自動機^符號指派予藉由該自動機 料產生器使用下推自動：吊駐的選擇。：且該编碼資 件其結構部分，並於所選^斤讀狀區域語言所撰窝之文 等選擇的符號，而產生；:：；擇其位置上輸出指派予該 一 構邵分的編碼資料串。以此安 變成fl 象是標籤之標記撰寫的一文件其結構部分改 的編碼順序。爲了分析使用下推自動機之文件 縱，，°^ 樹狀結構練據先㈣尋加以追 知。亦即，取代使用與-父節點等距之秩序，而是以沿著 =(邵分關係）之節點間的關係作爲優先，追跛供分析用 再者，該壓縮器不僅執行以樹狀區域語言所撰寫之文件 其内容的壓縮與編碼，同時執行藉由編碼器所獲得之文件 其結構邵分的恩縮與编碼。由於該壓縮器所使用之壓墙方 法並未特別限制，所以可使用傳統的多用途方法。當一编 碼器透過將-文件其結構部分編碼而獲得—正規^料串 時，該編碼器可使用像是ΡΚΖΙΡέ々—多用途方法執行壓 縮_，執行該编碼資料串之壓縮與編碼，以期待—高壓縮 率。因此，較佳者，當壓縮文件内容時，同時將編:資料 串壓縮。 -7 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） f請先閱讀背面之>i意事填寫本頁) 裝 訂| 經濟部智慧財產局員工消費合作社印制农 501350 Α7 Β7 經濟部智慧財產局員工消費合作社印製 五、發明說明（5 ) 同時，當將該結構邵分之編碼資料串與文件内容結合_ 起，並將結果資料壓縮時，該結構部分與内容形成一單一 檔案；而且就檔案管理而言，如此較佳。 根據本發明，一資料通訊系統包含：一傳輸來源資料處 理裝置，用以將資料傳輸通過一通訊網路；以及一傳輸目 的地貴料處理裝置，用以接收藉由該傳輸來源資料處理裝 置所傳輸通過通訊網路之資料，該傳輸來源資料處理裝置 包括：一第一又法儲存單元，用以儲存一樹狀區域語言之 又法規則，其中貪料係以—具標籤樹狀結構表示；一編碼 .器，—用以讀取以該樹狀區域語言所撰寫的一文件，將該文 件分割成一結構部分與内容，並使用該第一文法儲存單元 中所儲存之文法规則，將結構部分編碼；一壓縮器，用以 將該編碼器所糊取之文件其内容I縮，並將該壓縮内容編 碼；以及一傳輸器，用以傳輸藉由該編碼器所编碼之結構 邵分’和藉由該壓縮器所壓縮與編碼的内容；而該傳輸目 的地資料處理裝置包括：_接受器，用以接收來自該傳輸 來源資料處理裝置之資料，一第二文法儲存單元，用以倚 存又法規則，其中孩又法規則與該傳輸來源資料處理裝置 的第-文法儲存單元中所儲存之文法規則相同，_解壓縮 =，其使用—解壓縮方法，該方法對應於該傳輸來源資料 處理裝置^縮器所使用的壓縮與編碼方法，將接受器所 接收並對應於孩又件其内容的資料解壓縮，以及—解碼 器’，其使用第二文法規則儲存單元中所错存之文法， 將接党器所接收並對應於該文件其結構部分的資料解碼。 8- (請先閱讀背面之注咅？事*ίΡΡ填寫本頁) 11¾ 裝 -丨線- 本紙張尺度翻巾關家鮮（CNS)A4 χ挪& 501350 經濟部智慧財產局員工消費合作社印製 五、發明說明（6 ) 一種用以實行此處斑 其中該文法規則已準備法規則’ =:的::::二如此可達成"狀心 商務通訊而言，‘：增加通訊效率。由於就 之文法規則、斤 共同使用的一樹狀區域語言 又法規J，所以本發明可輕易引進。 此外’根據本發明 _六 ^ I月儲存及管理一儲存單元中之資斜 一資料庫系統包含：一文法搜在^ T (貝料 域語言之文法規則，/中H早疋’用以儲存一樹狀 •于…… #中w枓係以-具標籤樹狀結構 ::广碼：，用以讀取以樹狀區域語言所撰窝的一文 ::又 < 分割成-結構部分與内容’並使用該文 ^早几中所儲存之文法規則，將該結構部分編碼；鍺斋’二以將I編碼器所擴取之文件其内容壓縮，並將詨縮内谷編碼；以乃 件左错- ππ Λ 垃踩>、丛甘 用以儲存藉由該編碼器 · ”、，又牛/、結構部分，並儲存藉由該壓縮器所壓墙盘 碼之文件其内容。 U坠細與 該壓縮器不僅執行以該樹狀區域語言所撰窝之並 谷的壓鈿與編碼，同時執行藉由該編碼器所獲得之 、’·α構斗刀的壓蝻與編碼。當該結構部分之編碼資料盥 件内容結合一起，並將結果資料壓縮時，該結構部分盥 容形成-單-構案；而且就檔案管理而言，如此較佳了 再者，根據本發明，一種將資料編碼並將該編碼 縮之資枓壓縮方法包含下列步驟：讀取以—樹狀區域任 所撰寫的-文件，其中資料係以一具標鐵樹狀結構表; 的 區 表 文 縮 壓 所 内 其 文 内 壓 (請先閱讀背面之注意事*填寫本頁) 裝 二§!· -9- 本纸張尺度適用中國國家標準（CNS)A4規格（210 χ 297公釐） 501350 A7 B7 五、發明說明（ 並將該文件分割成一結構部分與内容；使用該樹狀區域語 言之文法規則’將該結構部分編碼；以及將藉由編碼器所 擷取之文件其内容壓縮，並將該壓縮内容編碼。 將該文件其結構部分編碼的步驟包括下列步驟··建構下 推自動機，其對應於該文法規則；將符號指派予該下推自 動機中常駐之選擇；根據先深搜尋，使用該下推自動機分 析該文件其結構部分，並於該選擇之位置上輸出指派予該 選擇的符號；以及輸出藉由使用該下推自動機而獲得的_ 符號串，其中該下推自動機作爲以該樹狀區域語言所撰窝 •之文—件其結構部分的編碼資料秦。以此安排，使用像是標 籤之標記所撰寫的一文件其結構部分可加以改變（編碼）， 以獲得一簡單之編碼順序。 該資料壓縮方法進一步包本：_半_ 甘丄#、、π /匕。· 步驟，其中將該屬性改 變至具有該屬性的一元件其一子節點，而將該樹狀區域語 1*之又法規則與文件轉換成由該下推自動機所處理的一樹 狀結構，該步驟於將以該樹狀區域語言所撰寫之文件其結 構邵分編碼的步驟前以及當一屬 、 久田 屬性屬於孩樹狀區域語言一 目標文件的一節點時執行。并錄 、* 仃此種女排較佳，因爲該結構部 分甚至當該屬性包含於傻县 νΛ,τ 、 ·、、 。於像疋一 XML·文件之目標文件中 .，乃可使用该下推自動機編碼。 該資料壓縮方法進一步魚本. m ^ 口 · 一步驟，其中使用另一多 用途壓縮與編碼方法，將兮 、、 μ又件其編碼結構部分進一步壓 縮興，.局碼，該步驅於將該文、 仵。士絲、u 土 件〜構邵分編碼的步驟後執 仃。此種安排較佳，因爲 _ η』W侍一較鬲又壓縮率。 -10 I U------------裝--- (請先閱讀背面之注意事填寫本頁) . 丨線· 經濟部智慧財產局員工消費合作社印剩衣 本紙張尺度適用?國家標準（CNS)i^^ x 297公釐） 501350 五、發明說明（8 ) 根據本發明，提供一儲存媒俨一 + 電腦可讀取程式儲存於該儲輸人裝H 行：一讀取處理，贫敗7 ^孩私式允許該電腦参 件，其中資料係以：二=狀區域語言所撰寫的1 割成-結構部分*㈣核結構表示，並將該文件分 内奋，一編碼處理，使用該樹狀區域攻 …法規則將結構部分編碼；以 ……拉件其内各壓縮，並將該壓縮内容編碼。以 此女排，“以該樹狀區域語言所 安裝此程式之所有资訊#球举菩了咸 于麼細時， •可於通訊與儲存時達成高效率。 且 此外，根據本發明，一程式傳輸裝置包含··错存裝置， 用以儲存一程式，該程式允許-電腦執行-處理，讀取以 -樹狀區域語言所撰寫的—文件 經濟部智慧財產局員工消費合作社印製 樹狀結構表示，並將該文件分剖成_結構部分與内容^執 行-編碼處理，使用樹狀區域語言之文法規則將結構部分 編碼，而且執行一處理，將該編碼器所擷取之文件其内容 壓縮，並將該壓縮内容編碼；以及傳輸裝置，用以讀取來 自該儲存裝置之程式，而且將該程式加以傳輸。以此安 排’昌彳文该私式傳輸裝置下載此程式並安裝之所有資訊處 理裝置將以樹狀區域語言所撰寫的一文件壓縮時，可實現 一高壓縮率，而且於通訊與儲存時，可達成高效率。貝 [♦交佳具體實施例] 現將藉由參照附圖，詳細描述本發明之較佳具體實施 例0 -11 - 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） A7 五、發明說明（9 ) •-----I---I------ (請先閱讀背面之注意事填寫本頁) 、圖1係一圖形，用以解釋根據該具體實施例的一文件壓 縮系統之大致安排。圖1中，一編碼器1 1將一目標文件分 割成一結構部分與内容，並使用一預先決定之儲存裝置中 所儲存的一文法規則1 2，將該結構部分編碼。一壓縮器 1 3包含？X編碼器i 1所編碼的一結構部分，以及該文件之 内各。一解壓縮器21，將該壓縮器13所壓縮之文件解壓 、、宿*解壓縮器2 1將該文件解壓縮時，則將該文件分離 成内谷以及藉由編碼器1 1所編碼的結構部分。一解碼器 23藉由使用一預先決定之儲存裝置中所儲存的一文法規 則2 2 ’重新建構編碼之結構部分，並將該結構部分與内 谷加以組合，而再生該内容。 當本具體實施例之方法用於資料壓縮而供資料通訊用 時’則於傳輸侧提供編碼器1 1與壓縮器1 3，於接受側提 供解壓縮器2 1與解碼器2 3。而且當本具體實施例之方法 根據資料傳輸將一資料庫系統中所儲存的一資料檔案壓縮 時，編碼器11作爲解碼器23之功能，而壓縮器^ 3作爲解 壓縮器2 1之功能。 現在將提供一例子之解釋，其中使用xml作爲一目標樹 狀區域語言。 經濟部智慧財產局員工消費合作社印制衣 圖2係一圖形，用以解釋根據本具體實施例之資料壓縮 處理二於圖2之資料壓縮處理中，首先，一目標XM]L文件 201精由編碼器丨〖讀取，並分割成一結構部分2〇2與内容 204 、…構#分2〇2包括樹狀結構，XMl文件2〇1之標籤名

稱興屬〖生名稱，而内容204包含文件2〇1之#pCDATA -12- 本紙張尺度顧巾國國冢標準（CNS)A4規格（21D X 29fi^i7

五、發明說明（1〇 ) 興屬性値。XML文_件201分割成結構部分202與内容204， 因爲通常結構邵分202與内容204具有相當不同之統計偏 差，所以獨立壓縮此二部分將很具效率。 藉由分割XML文件201而獲得之結構部分202以編碼器 1 1編碼，而且於編碼時使用文法規則1 2。由於此具體實 施例中，XML文件201爲目標，所以文法規則1 2係以die 正規化。稍後此編碼處理將加以描述。然後，將所獲得之 編碼資料串203與内容204傳輸至壓縮器i 3。 最後’壓縮器1 3將編碼資料串2〇3與内容2〇4壓縮與編 碼，並且組合獲得之資料，產生一壓縮XML文件2〇5。關 於編碼處理，壓縮器丨3使用像是LZ77的一傳統之著名方 法。此時，壓縮器13主要執行將内容2〇4壓縮與編碼。然 而，像疋PKZIP的一多用途壓縮與編碼方法可有效率將資 料串203編碼。如稍後所述，於本具體實施例中，編碼資 料串203係以一數値順序輸出。因此，如果該一 串較正規之數字’貝,j可期待一高壓縮率。因此，壓縮^ =可將編碼資料串203和内容2〇4壓縮與編碼。然而應注 意，藉由壓縮器13將編碼資料串2〇3壓縮爲任意處理‘。編 碼資料申203與内容204可簡單彼此相關抑或結合—起、， 而非藉由壓縮器13壓縮，而且可加以交 — 儲存裝置中。 仔於 如以上所述，於本具體實施例中，XML文件2〇ι之社 邯分202係使用本發明的方法壓縮，而且再者： 部分加與内容綱係使用—傳統方法壓縮。因此馬^ «,^1 n n m n I I ϋ ϋ n I 0 n t (請先閱讀背面之注意事lit填寫本頁) 訂- -丨線- 經濟部智慧財產局員工消費合作社印制衣 -13 -

501350 A7 B7 五、發明說明（11 ) 體實施例之資料壓縮方法結合各種傳統壓縮方法使用。 至於將壓縮XML文件205解壓縮，則將以上壓縮處理反 向執行。尤其，解壓縮器2〗使用對應於壓縮器丨3所使用 之壓縮與編碼方法的一方法，將編碼資料串2〇3與内容 204解壓縮。然後，如稍後所詳述，解碼器2 3使用文法規 則2 2·，重新建構解壓縮之編碼資料串2〇3，其中文法規則 2 2與文法規則丨2 _樣，而且以DTD正規化。然後，xml 文件201使用結構部分2〇2以及内容2〇4加以再生，其中結 構部分202爲解碼處理期間所獲得，而内容2〇4係藉由解 ‘壓縮—器2 1以解壓縮。 現在將提供根據本發明而執行之處理的一詳細解釋，其 中將XML文件其結構部分編碼。爲了簡化解釋，有關此 處理，一目標XML文件並未包括任何屬性，而且xml文 件（整個f際主均已開發。稍後將討論如何處置屬性。 圖3係一功能方塊圖，用以解釋將xml文件其結構部分 編碼足編碼器Η的安排。圖3中，編碼器〗丨包本：一分判 用以將目標XML文件201分割成結構部分2〇2與二 Ϊ推Μ自動;f:動機建構备112 ’使用文法規則12重新建構 下推自動機，稍後將描述該下推自· 串產生器⑴，藉由使用自動機建::n = ^ =一碼轉換器，而產生結構部 文=係?形—，其中顯示目標魏文件的_例子。胤 又件其内谷由-内答模型邵分之字元串清單組成，其中該 本纸張尺度刺中fej目家標準（CNS)A4祕⑵Q x -14- 、發明說明（12) 内容模型對應於#PCD AT A。亦即，圖4中之XML文件其内 容係一清單，其中由四個字元串"字串1 ” "字串2 ” 字串 3 "和"字串4 ”組成。此清單可簡潔使用像是以下位元組字 串表示，其中安排以一空字元終止之字元串（，，¥ 0 "表示一 空字元）。 π字串1¥0字串2¥0字串3¥0字串4¥0，· 此字元_與以上所述之結構部分分開壓縮及編碼。 圖5中顯示圖4之XML文件的結構部分。此結構部分以 位置保留記號（□)取代對應於圖4中之XML文件其内容的 字itr串而得。 本具體實施例中，於圖5，編碼器1 1之分割器π 1從圖4 所示的XML文件擷取結構部分，自動機建構器丨丨2使用文 法規則1 2建構下推自動機，而編碼資料串產生器丨丨3使用 下推自動機將結構部分編碼。圖6係一圖形，其中顯示用 以正規文法規則1 2的一 DTD例子。 於分割器111執行分割處理後，爲了使用文法規則12執 行編碼，自動機建構器112建構對應於DTD之下推自動 機。根據圖6中之DTD，當一元件八出現時，表示一元件 B及一元件C各將以命名次序出現，而後敘述移位終止。 類似地，當元件8出現時，將出現，而後敘 述移位終止。當元件C出現時，表示G或更多元件e或者元 件F將出S ’而後敘述移位终止。當元❹出現時，表示 -元件G或者-元件η將出現，而後敘述移位終止。 圖7係一圖形，顯示對應於圖6中之dtd的本質 經濟部智慧財產局員工消費合作社印製 五、發明說明（13) 動機。由於非故f 、„ 、、付5虎D與G爲僅具有終止符號#PCDATA疋明顯規則，所以未顯示。 、去之個別非終止符號的自動機可予以建構，而沒有 任何混淆。因此，a _ 自尽具體實施例應用於資料通訊時，可 ;始白用由傳知側與接受側共同使用之DTD，建構相同的 下推自動機。 ★ 下推自動機用以分析-輸入串之語法。以此方 1::丄自動機於表層接收所有符號串，亦即，安排-或 …。於而：TA所而的所有字串(或者位置保留記號"□") 例如像是所獲得之語法分析樹，—節㈣及 點c必須以命名次庠 〜 ^ 、 出見，馬一節點A的子節點。此外， 推自㈣（後’空敎述移位至最後敘述。如以上所述，下 如用以決定所分析之^文件的語法分析樹（例 現在Si又件物件模型)樹)是否滿足該文法。 機檢太文π執仃々處理的-解釋，其中使用下推自動 職檢且又法，而使用圖8中之 示每一。法树爲例。圖8中，未顯 母茉#PCDATA。欲決定此語法 、 DTD正規化的—文法產生，疋否可精由以圖6( 定：由其子節點所组成的樹的每一節點僅需決 非終止符號之自動機接受。例如疋：可由對應於該節點其 成-字申BC。該等子節點可由對應—凡件Α將其子節點組 7中之A)的自動機接受。因此，^ ;非終止付號A(見圖 法。當藉由使用對應之自動機 ^ :此邵分滿足該文 過所有節點（根據先深搜尋予以追；^定序的相同方式通 ^ 時，文法檢查終止。 ‘纸張尺度適巧國國家標準（CNS)A4規格（21〇 x (請先閱讀背面之注意事HI填寫本頁) 裝 . -丨線‘ - 16 dim αυ 五、發明說明（μ) 以下解釋φ 、、上 Λ 琢語法分析樹之下推自動機的此種用途稱 a有政性‘查。應注意，除了將ε移位至最後敘述外，對 應於以上處理所使用的每_非終止符號其自動機的決定性 自動機數目爲最少。 ^自動機建構器112將圖7中之下推自動機轉換成-轉換 态’用以將XML文件其結構部分（見圖5 )編碼，亦即，用 以刀析一 +元串之語法的自動機。

^\圖7中之下推自動機，假設一項目爲由四個#PCDATA

If4 —口、）所組成的一字串，而且當使用A作爲開始符號 •，，—則f動分析處理。然後，依序產生一節點A，一節點 B及-節點D，而且辨識第一㈣術八。當產生一節點c 時，則提供三種選擇，可產生-節點E，可產生一節點 或者可於節點C終止敘述移位，並且轉回較上節點。 以與標記其字母次序一致之次序（標記ε永遠最後決定）， 對二項選擇指派數字1，2及3。類似地，由於節點Ε的第 敛逑提供兩項選擇，所以可產生一節點g或者一節點 Η ’匕對此等選擇指派數字。於本具體實施例中，對選 f扎派數冬，但可供識別該等選擇之符號不限於數字。像 疋字母字7L或記號之任意符號均可用以指定該等選擇。 圖9係圖形，顯示將圖7中之下推自動機加以轉換所 產生的一編碼轉換器。 、、：為碼斋1 1 I編碼資料串產生器！ 13操作一編碼轉換器， 藏f碼轉換器係由自動機建構器112所建構。 當執行有效性檢查（前定序規則之應用程式）時，圖9中 .U----------—裝--- (請先閱讀背面之注意事填寫本頁) . 經濟部智慧財產局員工消費合作社印製 -17- 501350 A7 B7 五、發明說明（15 的編碼轉換器輸出二對應之選擇數字。尤其，於圖9中， 沒有規則A，B，F和Η之選擇，所以該編碼轉換器沒有任 何輸出。然而，當使用規則c和規則Ε時，編碼轉換器輸 出相關數字。例如，當執行圖8中之語法樹的有效性檢 查，而編碼轉換器追蹤該樹時，其輸出圖！ 〇所示之數 字。 透過以上處理，得一數字· "112123"，其嚴格正規化該 下推自動機之移動。因此，數字串可作爲圖4中之文 件其結構邵分的編碼資料串（圖5 )。 -現-在將描述根據本發明將XML文件其結構部讀碼的處 --------------·— (請先閱讀背面之注意事填寫本頁) 經濟部智慧財產局員工消費合作社印製 欲將XML文件解碼，其中該皿文件係透過以上處理 加以编碼，僅需反轉該編碼轉換器之輸入/輸出。因此， :碼器23使用與圖7的相同下推自動機，產生— :止理。如以上所述，由於該執行的每-終止付叙自動機均可加以建構，沒有任何混淆，如果 DTD:规化的文法規則12與文法規則2 二： 23可建構與圖7正好相同的下推自動機。 ％碼 圖11係-圖形，顯示一解碼轉換 圖7相同之下推自動艟而方4 /、你精由轉換與 "1/Β"表于二：機而產生。於圖"中之解碼轉換器， 表w 一輛入芊元串丨丨i丨丨出現時，則呼叫親目IR 而後將該敘述移位至下一 # Η規則B， η輸入-數字•，並因此’該編碼 座玍对應之語法分析樹。 备知入以上所述之數字串"112123"時，根據原始數字 非 以 器 器 的 18-

本紙張尺度適用(cns)m^m^; x 297公爱）

經濟部智慧財產局員工消費合作社印制衣 501350 A7 B7 _ 五、發明說明（16 ) 指派方式，該下推_自動機（解碼轉換器）可接受XML文件 之編碼數字串，而沒有任何混淆。因此，產生之語法分析 樹與圖8的原始語法分析樹相同。結果，XML文件其結構 部分得以再生。 現在描述屬性之處置。 於本具體實施例中，將一屬性轉換成一樹狀結構，因而 可藉由下推自動機予以處理。尤其，具有屬性之所有元件 (ELEMENTS )均已改變，所以屬性視爲子節點。此時，屬 性以其名稱的字母次序出現。屬性^REQUIRED安排爲不 -改變-，而且屬性#IMPLIED安排爲具有一選項"？"。由於原 本未提供屬性#FIXED之任何資訊，所以其不包含於藉由 轉換所獲得的DTD中。 圖1 2係一圖形，顯示轉換前後所獲得的一預先決定之 DTD敘述的比較。於圖1 2中，將左邊的DTD轉換成右邊 的 DTD。 關於包含屬性之XML文件，同樣根據DTD，將屬性轉換 成元件。圖1 3係一圖形，顯示轉換前後的一預先決定之 XML文件敘述的比較。 當DTD及XML文件以上述方式改變成未提供屬性之敘述 後，則執行以上所述的編碼與解碼處理。應注意，轉換 DTD可於建構下推自動機之前執行，或者於已建構下推自 動機後視需要執行。於第一情況下，藉由轉換而獲得的一 新DTD用以建構下推自動機。於第二情況下，使用（具有 屬性之）原始DTD建構下推自動機。 -19- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） ----------------- (請先閱讀背面之注意事填寫本頁) 訂： ------------B7__ 五、發明說明（17 ) ^ 一·-- /二上所述，根據本具體實施例，XML文件之壓縮側及 解壓縮側必然共同使用相同的剛。因此，當本具體實施 例（貝料壓縮方法用於資料通訊時，必須準備相同的 DTD，供傳輸侧資料處理裝置及接受側資料處理裝置用。 圖1 4係一圖形，用以解釋使用本具體實施例的一資料 通訊系統之組態。於_傳輸侧的一資料處理裝置“Μ中， 編碼1 1接收來自一資料處理器的一 XML文件，並使用一 DTD 1411 (對應於圖}之文法規則〗2)，將該結構部分編 碼。壓縮器1 3將編碼結構部分與内容壓縮，而且一傳輸 -器1Φ12透過一通訊網路，將資料處理裝置142〇中之最後 XML文件傳輸至.一接受側，其中該最後χ M L文件係藉由 編碼器1 1所執行之編碼以及壓縮器i 3所執行之壓縮而產 生。於接受側的資料處理裝置1420中，一接受器1422透 過通訊裝置接收資料，並將其傳輸至解壓縮器2 1。此 時，解壓縮器2 1將接收之資料解壓縮，而將xML文件的 内容恢復。然後，解碼器2 3使用一 DTD_ 1421 (對應於圖χ 之文法規則2 2 )，將已解壓縮之資料其結構部分的編碼資 料串解碼。然後，解碼器2 3將所獲得之結構部分與内容 重新裝配，而再生XML文件，並將該XML文件傳輸至一 資料處理器。於此處理期間，傳輸侧其資料處理裝置141〇 中之DTD 1411具有與接受侧其資料處理裝置142〇中之 DTD 1421相同的内容。 當一 XML文件藉由供商務通訊用之應用程式加以交換 時’於一電子商務事務之過程期間，大部分情況下，其根 -20- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） (請先閱讀背面之注意事填寫本頁) -I裝 . 經濟部智慧財產局員工消費合作社印制衣 501350 A7 B7 經濟部智慧財產局員工消費合作社印製 五、發明說明（18 ) 據彼此所同意，事先建置一 DTD。因此，若假設共同使用 一 DTD，則本具體實施例可應用於商務通訊。 當本具體實施例之方法用以壓縮一資料庫系統所儲存的 一資料檔案，而將一XML文件其結構部分解碼時，用以 將該結構部分編碼之DTD可毫無改變供解碼用，所以不务 考慮是否共同使用一 DTD。 圖1 5係一圖形，用以解釋使用本具體實施例的一資料 庫系統之組態。於一資料庫系統1500中，—編碼器i i接 收來自一資料處理器的一XML文件，並使用_DTD ΐ5〇ι (對應於圖1中之文法規則1 2 )將該結構部分編碼。然後， 一壓縮器1 3將编碼結構部分與内容壓縮。於XML文件由 編碼器1 1編碼，並由壓縮器1 3壓縮後，則將其餘存於一 儲存裝置1502中。欲從儲存裝置1502讀取xml文件，則 以壓縮器1 3作爲解壓縮器2 1功能，以編碼器1 1作爲解碼 器23功能，並使用將XML文件其結構部分編碼的dtd 1501將其解碼。 - 上述解釋中，以XML語言作爲樹狀區域語言。然而，本 具體實施例可用於像是ASN. 1的另一樹狀區域語古。然 而，此情況下，資料檔案壓縮側及解壓縮側必須共同使用 像是XML的DTD文法規則。 [發明優點] 如以上所述，可根據本發明執行資料壓縮，而將一樹狀 區域語言的* 文件其結構部分編碼。 再者，特別將一樹狀區域語言的一資料壓縮方法加 -21 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公釐） (請先閱讀背面之注意事^^填寫本頁) *裝 訂： 以 501350 用以解釋使用下推 A7 __B7 五、發明說明（19 ) 適，並與另一多用途資料通訊技術連用，而得以使用一種 提供一高壓縮率之資料壓縮方法。 圖示簡述： 圖1係一圖形，用以解釋根據本發明一具體實施例的一 文件歷縮系統其大致安排。 圖2係一圖形，用以解釋根據本具體實施例之資料壓縮 處理。 圖3係一圖形，用以解釋根據本具體實施例的一編碼器 之安排。 •圖~4係一圖形，頻示根據本具體實施例的一目標XML文 件例子。 圖5係一圖形，顯示圖4中之XML文件的結構部分。 圖6係一圖形，顯不本具體實施例所使用的一文法規則 例子。 圖7係一圖形，顯示根據圖6之文法規則所建構的下推 自動機。 _ 圖8係一圖形，顯示一語法樹例子， 自動機之文法檢查方法。 (請先閱讀背面之注意事填寫本頁) _裝 ». 經濟部智慧財產局員工消費合作社印製 圖9係一圖形，顯示使用圖7之下推自叙她γ — 伸目勳機所產生的 編碼轉換器。 1 0係一圖形，顯示藉由一有效性檢查所獲得之妗 例子，其中該有效性檢查係根據圖8中的注 又于又、…果 — 法树而執杆。 圖1 1係一圖形，頌示藉由使用與圖7相π、 祁Η <下推自動機 圖 所產生的一解碼轉換器 -22- 本紙張尺度適用中國國家標準（CNS)A4規格（210 X 297公爱） 501350 A7 ____ B7______ 五、發明說明（20 ) 圖1 2係一圖形，-用以解釋將具有屬性的一 DTD轉換成 不具有屬性的一 DTD敘述。 圖1 3係一圖形，用以解釋將具有屬性的一 XML文件轉 換成不具有屬性的一 XML文件敘述。 圖1 4係一圖形，用以解釋本具體實施例應用於一資料 通訊系統結構。 圖1 5係一圖形，用以解釋本具體實施例應用於一資料 庫系統結構。 / [符號描述] • 1 1广編碼器 12，22 :文法規則 1 3 :壓縮器 2 1 :解壓縮器 2 3 :解碼器 201 : XML 文件 202 :結構傳送 203 :編碼資料· 204 :内容 205 :壓縮XML文件 --------------裳--- (請先閱讀背面之注意事填寫本頁) 訂， 經濟部智慧財產局員工消費合作社印製 23 本紙張尺度適财國國家標準（CNS)A4規格（210 —

Claims (1)

1. 娜修调卜 補充 第089122825號專利申請案 年 6 月) 申請專利範圍 "料料裝置.’用以將資科編碼，並將該編碼資 規則，，用以儲存-樹狀區域語言之文法 ，、中#科以_具標籤樹狀結構表示； 文：編：器’用以讀取以該樹狀區域語言所撰寫的- 文法搜：：又件分割成一結構部分與内容，並使用該 ;儲存早元中所儲存之文法規則，將該結構部分編 碼；以及 、壓縮H %以將讀編豸器所擴取之文件内容壓 縮’並將該壓縮内容編碼。 2· 如申請專利範圍第1項之資料壓縮裝置，其中該編碼器 包括： 一分割器，用以將一目標文件分割成一結構部分盥 内容； . ^ 、:自動機建構器，甩以建構下推自動機，其對應於 讀文法規則；以及 一編碼資料產生器，用以使用該自動機建構器所建 構之下推自動機，執行該文件中藉由分割器所獲得的 結構部分之語法分析，並產生該結構部分的一編碼資 料串。 3·如申請專利範圍第2項之資料壓縮裝置，其中該編碼器 之編碼資料產生器將符號指派予藉由該自動機建構器 所建構的下推自動機中之常駐選擇；且其中該編碼資 料產生器使用該下推自動機分析以該樹狀區域碼所撰 窝的文件其結構部分，並於所選定之選擇其位置上輸 出扣派予该選擇的符號，而產生該結構部分之編碼資 料串。 / 如申請專利範圍第i項之資料壓縮裝置，其中該壓縮器 不僅執行以讜樹狀區域語言所撰窝之文件其内容的壓 縮與編碼，同時執行藉由該編碼器所獲得之文件其結 構部分的壓縮與編碼。 一種資料通訊系統，包含： 、一傳輸來源資料處理裝置，用以將資料傳輸通過一 通訊網路；以及 y傳輸目的地資料處理裝置，用以接收藉由該傳輸 來源貪料處理裝置而傳輸通過通訊網路之資料， 該傳輸來源資料處理裝置包括： 第文法儲存早元，用以儲存—樹狀區域語言之 又法規則，其中資料以一具標籤樹狀結構表示， 、一編碼器，用以讀取以該樹狀區域語言所撰窝的一 又件，將該文件分割成一結構部分與内容，並使用該 第一文法儲存單元中所儲存之文法規則，將該結構i 分編碼， 一壓縮器，用以將藉由該編碼器所擷取之文件其内 容壓縮，並將該壓縮内容編碼，以及 一傳輸器，用以傳輸藉由該編碼器所編碼之結構部 分和藉由該壓縮器所壓縮與編碼的内容，以及 該傳輸目的地資料處理裝置包括： 501350 A8 B8 C8 D8

   申請專利範圍 一接受器，用以接收來自該傳輸來源資料處理裝置 之資料， 一弟一文法儲存單元，用以儲存與該傳輸來源資料 處理裝置其第一文法儲存單元中所儲存之文法規則相 同的文法規則， 一壓縮器，用以使用一解壓縮方法，該方法對應於 該傳輸來源資料處理裝置之壓縮器所使用的壓縮與編 碼方法，用以將藉由該接受器所接收且對應於該文件 其内容之資料解壓縮，以及 一解碼器，用以使用該第二文法規則儲存單元中所 儲存之文法規則，將藉由該接受器所接收且對應於該 文件其結構部分的資料解碼。 6· —種資料庫系統，用以儲存及管理一儲存單元中之資 料，包含： 一文法儲存單元，甩以儲存一樹狀區域語言之文法 規則，其中資料係以一具標籤樹狀結構表示； 一編碼器，用以讀取以該樹狀區域語言所撰寫的一 文件，將該文件分割成一結構部分與内容，並使用該 又法儲存單元中所儲存之文法規則，將該結構部分編 碼； 、 一壓縮器，用以將該編碼器所擷取文件之内容壓 縮’並且將該壓縮内容編碼；以及 一儲存單兀，用以儲存藉由該編碼器所編碼之文件 其結構部分，並且儲存藉由該壓縮器所壓縮與編碼的 -3 -

   申請專利範圍 A8 B8 C8 D8 文件其内容。 =申請專利範圍第6项之資料庫系統，其中該壓縮 執行以該樹狀區域語言所撰窝之文件其内容的壓縮 /、編碼，同時執行藉由該編碼器所獲 : 部分的壓縮與編碼。 、、告構 :種資料壓縮方法，用以將資料編碼，並將該編 科壓縮，包含下列步驟： 貝 讀取以一樹狀區域語言所撰寫的—文件，其中，、 係以一具標籤樹狀結構表示，並將該文件分割 2 構部分與内容； 、… 使用該樹狀區域語言之文法規則，將該 碼；以及 刀、，扁 將藉由該編碼器所掏取之文侔 其内容壓縮，並將該 壓縮内容編碼。 如申請專利範圍第8項之資料壓縮方法，其中將該文件 其結構部分編碼的步驟包括下列步驟· 建構對應於該文法規則之下推自動機； 將符號指派予該下推自動機中之常駐選擇； 使用該下推自動機，根據先深搜尋，分析嗜文件其 結構部分，並於該選擇的位置上，輸出指^一擇 的符號；以及 輸出藉由使用該下推自動機所獲得的一符號串，作 為以該樹狀區域語言所撰窝之文件其結構部二的编痛 資料串。 -4- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公f 裝 訂 夂、申請專利範園 10.如申請專利範園第9.項之資科壓縮方法，進—步包含： ―步驟，用以將屬性改變至處理該屬性的_元件其 —子節點，而將該樹狀區域語言之文法規則和該文件 轉換成由該下推自動機所處理的—樹狀結構，該步驟 於將以該樹狀區域語言所撰窝之文件其結構 =步驟前，以及當-屬性屬於該樹狀區域語言的一目1 標文件其一節點時執行。 申請專利範圍第8項之資料壓縮方法，進一步包 含.-步驟，其使用另一多用途壓縮與編碼方法，進 一一步將該文件其編碼結構部分壓縮與編碼，該步驟於 將禮文件其結構部分編碼的步騾後執行。 12. —種程式傳輸裝置，包含： 〜儲存裝置，用以儲存—程式，該程式准許_電腦執 T處理用以項取以一樹狀區域語言所撰窝的一文 件，其中資料係以-具標籙樹狀結構表示，並將該文 件分割成一結構部分與内容， 一處理，使用該樹狀區域語言之文法規則，將該結 構部分編碼，以及 、處理，用以將藉由該編碼器所擷取之文件其内容 壓縮，並將該壓縮内容編碼；以及 傳輸裝置，用以從該儲存裝置讀取該程式，並且傳 輸該程式。 501350 _ 補无 第089122825號專利申請案 中文圖式修正頁(91年6月）