中文文件檔壓縮處理方法及裝置的製作方法

2023-05-05 06:18:36

專利名稱：中文文件檔壓縮處理方法及裝置的製作方法
技術領域：
本發明是關於一種中文文件檔壓縮處理方法及裝置，特別是關於一種利用中文詞作為處理單元，以檔案壓縮技術，達到大量壓縮中文文件檔所佔存貯器容量的方法及裝置。
中文電腦化逐漸普及後，產生大量的電腦中文文件，例如每天出刊28版面的日報社在電腦化之後，每天即產生約兩百五十萬個中文字的文字檔，其它如出版社，政府機關，公司等每天所產生的中文字檔更是難以計數。在這種資料爆炸的情況下，或為減少儲存空間的浪費，或為提高資料傳輸的速度，實有將中文文件壓縮的必要。
目前常用來壓縮中文文件的技術中，有一種ARC程式，是以字節為單元，亦即利用代表中文字的位元組，依其在中文文件中出現的頻率，組成霍夫曼碼，利用公知的霍夫曼法，壓縮中文文件。由於此種方式是將中文文件以壓縮英文資料的方式壓縮，並未利用到中文的特性，因此壓縮比例不高，可以達到大約75%上下壓縮比率。
通用的中文碼，不論是BIG-5碼或是TCA碼，對每個中文字編以兩個字節的碼。此種編碼方式，由於實用性及與英文ASCII碼相容性的考慮，並沒有完全用到可以使用的碼空間。因此，另一種可能的文件壓縮法，是將中文字重新編碼，減少每一碼的位數，即可很輕易的得到一些壓縮。
例如，對一萬多個中文字，只需以每字14個位的碼(注2的14次為16384)加以重新編碼，即可得到14/16＝87.5%的壓縮比率。
上述的兩種方式，均是以「字」為編碼單元。但是中文使用的邏輯單元實際上是「詞」而不是字，理論上詞編碼應可以得到較佳的壓縮效果。例如。常用中文詞的數目大約在六萬左右，如果以詞編碼，每個詞可編以16個位的碼(注2的16次為65536)，即可足敷六萬詞的需要，這種方式，參照每個中文詞的平均字數約為1，6，可以大約算出平均每個字的碼長是16/1.6＝10個位。因此壓縮比率則大約為10/16＝62.5%。遠較以字為單元的編碼更有效率。
上述方法對壓縮單元的研究均只涉及編碼的完全性(或不完全性incompleteness)，運用BIC-5碼與TCA碼的不完全性，重新對字或詞編以充分利用碼空間的碼來達到壓縮效果，而且所處理的都是等長度的碼。在傳統的資料壓縮方法裡，強調利用編碼單元的出現機率，對出現機率高的單元以編以較長的碼，藉此來達到壓縮的目的，此類方法的壓縮效率通常由壓縮單元的選取來決定。然而公知的類比機率編碼的方法，均不能利用中文的特色，提供較大的壓縮比例，以合乎使用者的需要。
本發明的目的乃在提供一種利用中文的特性，壓縮中文文件檔的中文文件檔壓縮處理方法及裝置。
本發明的另一目的也在提供一種中文文件檔之壓縮方法及裝置，以將中文文件檔的儲存記憶量做更有效的壓縮。
本發明另一個目的也在提供一種中文壓縮處理單元的決定方法，以提供中文更有效的壓縮效果。
經發明人發現，過去經編碼法達到壓縮效果的技術，其關鍵在文件的混亂度(Entropy)值-即根據所有壓縮單元的出現機率而計算出的一個數目。亂度值的意義與計算方法雖不在本發明的討論範圍之內，但以亂度值之概念協助文件壓縮的技術思想可簡述如下所欲壓縮的檔案中，所有壓縮單元個別的出現機率愈越一致(可預測性低，混亂度高)，壓縮效果愈差;反之，若壓縮單元個別出現機率愈不一致(可預測性高，混亂度低)，則壓縮效果愈佳。
每一個文件都有它的最大可能壓縮比率，而文件壓縮的前置手段即在找出一組使文件的混亂度儘量降低的編碼單元。因此，本發明雖不必受限於其理論，但發明人認為，會使中文文件混亂度降到理論最低值的壓縮單元組，應是最接近自然定義的中文詞彙，換言之，以類似中文詞彙為壓縮單元所編成的霍夫曼碼，可以將中文文件壓縮到接近理論上的極限。
綜合以上的觀察與分析，發明人認為，如果找到一個最接近中文詞句的壓縮單元組，將中文以此壓縮單元組為壓縮單元編碼，首先可以因其編碼的完全性與邏輯性得到第一步的壓縮，再加上因各壓縮單元使用機率的可預測性編成霍夫曼碼，進一步得到更多的壓縮。
以下參照


本發明的方法與裝置。
第1圖表示本發明中文文件檔的壓縮方法及裝置一實施例的系統圖。
第2圖表示本發明中文文件檔的壓縮方法及裝置一實施例的壓縮處理單元切割裝置的動作系統圖。
在語言學的理論上，如何尋找出一個客觀上最佳的壓縮單元組(或稱「編碼詞典」)，而將文件檔壓縮到理論上最小值，是一個很值得研究的問題。但在應用上只要找出一個理想的、易於處理(獲得)的「編碼詞典」即可提供有效的壓縮效果。以下說明本發明的方法與裝置如何利用此一「編碼詞典」將中文文件有效的切割成一低混亂度的碼串，藉以進行壓縮處理。
(1)中文文件檔的壓縮第1圖表示本發明一實施例之系統圖。本發明所提出的壓縮首先包含一個壓縮處理單元切割裝置(100)以及一個「編碼詞典」(101)。編碼詞典(101)中注有每一壓縮處理單元的使用機率。壓縮處理單元切割裝置(100)可依編碼詞典(101)中記載各壓縮單元的使用機率將文件切割成混亂度最低的壓縮單元碼串。
編碼對照表產生裝置(102)可依編碼詞典(101)中所記載各壓縮單元的使用機率，以適用的方法衍生霍夫曼樹而製作出一個編碼對照表(103)，記載各編碼單元與霍夫曼碼之對應關係。通常，在應用上這個編碼對照表(103)是事先製作出來的一個表，以適當方式儲存在存貯器中。(104)是一個存儲器，供儲存經過處理的文件檔。
利用本發明的中文文件檔壓縮處理裝置壓縮處理中文文件檔時，首先由系統將中文原始文件讀入，放在存貯器(104)中等待處理。作壓縮處理時，由壓縮處理單元切割裝置(100)依編碼詞典(101)中記載各壓縮單元的使用機率，將文件依本發明的方法，切割成混亂度最低的壓縮單元碼串，再度儲存於存貯器(104)中。壓縮裝置(105)將編碼處理過的中文文件檔，參考編碼對照表(103)，把文件檔中構成一列碼串的壓縮單元逐一轉換成霍夫曼碼而得到壓縮檔，再度儲存在存貯器(104)中，完成壓縮處理。
在進行反壓縮處理時，反壓縮處理裝置(106)先將存貯器(104)中的壓縮檔，參考編碼對照表(103)把代表壓縮檔的霍夫曼碼逐一反轉成原始壓縮單元，而得到原來的文件檔。
(2)壓縮處理單元的切割如前所述，在作壓縮處理時是先以壓縮處理單元切割裝置(100)依編碼詞典(101)中記載各壓縮單元的使用機率，將文件切割成混亂度最低的壓縮單元碼串。此時，切割效果的優劣，將成為處理效果如何的一大關鍵。
公知的切割方法，是利用最長壓縮單元的手段，將一個中文片段(通常是一個中文句子)，由已知的切割點往句子末端搜尋最長的壓縮單元。尋得後，以此壓縮單元尾端為下一上切割點，然後反覆運用此手段，進行切割。
例如中文片段「研究所的確實行動」以此方法，將被切割成「研究所｜的確｜實行｜動」，可是這並不是一個理想的切割法。混亂度較低的切割法應該是「研究所｜的｜確實｜行動」，所以上述方法並不適合作為中文文件切割處理手段。
本發明在切割處理方面，系提出一個「機率競爭」的切割手段。經由手段，可以將中文文件檔切割成一串低混亂度的編碼單元碼串，將此碼串轉換成霍夫曼碼後，原始中文文件檔可以得到很大的壓縮。此種機率競爭的切割手段，能適用於各種不同的編碼詞典，它可提供所參考的編碼詞典下混亂度最低的切割效果;編碼詞典愈是最佳化，所得到的結果愈佳。雖然理論上的最佳編碼單元詞典並非本發明的重點，但是用一般的中文詞典與本發明搭配使用，已可達到非常好的壓縮效果。
以下依據第2圖說明本發明的中文文件壓縮處理單元切割裝置(100)的動作流程。
本發明啟動後，首先於(200)從存貯器(104)中的中文文件檔中取得一個中文片段，準備處理。這個中文片段通常是句子。
於(201)系統檢查以此中文片段的首字為首，組成的不同長度字串是否列於編碼詞典(101)之中。對每一個尋得的編碼單元，建立一虛擬路徑，並在壓縮單元尾端的相對位置註明為切割點，然後將指標指向第二個字。此處所調虛擬路徑即是對切割點位置的描述。
檢查點(204)檢查是否超過一個在目前指標位置有切割點。如超過，則執行動作(202)，反之，則執行動作(203)。
動作(202)比較所有在目前指標位置有切割點的路徑，從首字至目前之指標位置的切割方式可能發生之綜合機率。綜合機率之算法為將所有相連接的壓縮單元的出現機率相乘。比較後，留下發生機率最大路徑，刪除其餘路徑。這個比較動作使最後的結果一定是發生機率最大的路徑。動作(202)結束後，需檢查是否指標已指到此中文片段尾端。如是，則結束對此中文片段的切割;如否，則往下執行動作(203)。
動作(203)首先將指標往前移動一個位置，指到下一個中文字。然後對所有切割點與目前指標位置相同的路徑做如下動作檢查以目前指標位置之字為首組成不同長度字串是否列於編碼詞典(101)之中，然後將每一個尋得的編碼單元，接在原路徑之後組成一個或數個新路徑，並在每一新路徑尾端註明為切割點。若所有字串皆不列於詞典中。則刪除此路徑，因為此種切割法發生機率為零。動作(202)結束後，執行流程跳回檢查點(204)，然後反覆執行上述之各種動作直到句子結束。最後，將所得的切割結果，標示在文件檔中，儲存在貯存器中，完成切割處理。
以下實例說明第2圖所示壓縮處理單元切割裝置的處理流程。假設在編碼詞典(101)中儲存的部分內容為表一編碼單元發生機率研0.000009研究0.000496研究所0.000018所0.002450的0.054438的確0.000070確0.000077確實0.000067實0.000179實行0.000084行動0.000167動0.000175以上註記的機率為實際值的一兆倍(十的十二次方)。
步驟1動作(200)，從存貯器(104)的中文文件檔中取得一個中文片段，準備處理。
取得的中文片段為「研究所的確實行動」步驟2於(201)系統檢查以此中文片段的首字(研)為首，組成不同長度字串是否列於編碼詞典(101)之中。對每一個尋得的編碼單元，建立一虛擬路徑，並在編碼單元尾端的相對位置註明為切割點。
指標指在「研」字。建立三個起始路徑。
路徑研｜9000000研究｜496000000研究所｜18000000步驟3檢查點(204)檢查是否超過一個路徑在目前指標位置有切割點。
在本例中，檢查點(204)檢查結果發現並沒有超過一個路徑在目標指標位置(研)有切割點。指標移至「究」字。
此時(203)對所有切割點位於目前指標位置(究)的路徑，檢查以目前指標位置的字為首組成的不同長度字串是否列於編碼詞典(101)之中。結果發現以「究」為首的字串如「究」，究所」，「究所的」等皆不在編碼詞典中，刪除此路徑「研｜、剩下路徑研究｜496000000研究所｜18000000步驟4指標移至第三字。重複動作(203)，對所有切割點與目前指標位置相同的路徑做如下之動作檢查以目前指標位置(所)的字為首組成不同長度字串是否列於編碼詞典(101)之中。如有。將每一個尋得的編碼單元，接在原路徑之後組成一個或數個新路徑，並在每一新路徑尾端註明為切割點。
在本實例中，「所」字在編碼詞典(101)之中，故在路徑「研究｜」後接「所」而成為「研究｜所｜」。
路徑研究｜所｜1215200研究所｜18000000步驟5同樣在檢查點(204)檢查是否超過一個路徑在目前指標位置有切割點。如超過，則執行動作(202)，計算所在目前指標位置有切割的路徑，從首字至目前指標的指標位置的切割方式可能發生綜合機率。綜合機率的算法為將所有相連接的壓縮單元的出現機率查乘。比較其大小。比較後，留下發生機率最大的路徑，刪除其餘路徑。
檢查結果發現超過一路徑在目前指標位置有切割點，故比較其發生機率之大小。路徑「研究｜所｜」刪除，因為其發生機率(1215200)低於路徑「研究所｜」之機率(18000000)。結果剩下路徑研究所｜18000000步驟6指標移至第四字。重複(203)動作。得到兩個可能的壓縮單元「的」和「的確」接在「研究所｜」之後，各組成一個新路徑。
路徑研究所｜的｜979884研究所｜的確｜1260步驟7指標移至第五字。重複(203)動作。得到另外兩個可能的壓縮單元「確」和「確實」接在「研究所｜的｜」之後，各組成一個新路徑。
路徑研究所｜的｜確實｜65.652228研究所｜的｜確｜75.451068研究所｜的確｜1260.000000
步驟8依據(204)的判斷，重複(202)動作，發現超過一路徑在目前指標位置有切割點，比較其發生機率。
路徑研究所｜的｜確｜、刪除，因為其發生機率(75.451068)比路徑「研究所｜的確｜」(1260.000000)低。得到路徑研究所｜的｜確實｜65.652228研究所｜的確｜1265.000000步驟9指標移至第六字。依據(204)的判斷，重複(203)的動作。得到另外兩個可能的壓縮單元「實」和「實行」接在「研究所｜的確｜」之後，各組成一個路徑，亦即路徑研究所｜的｜確實｜65.652228研究所｜的確｜實｜0.225540研究所｜的確｜實行｜0.105840步驟10依據(204)的判斷，重複(202)的動作，發現超過一路徑在目前指標位置有切割點，比較其發生機率。
路徑「研究所｜的確｜實｜」刪除，因為其發生機率(0.225540)比路徑「研究所｜的｜確實｜」(65.652228)低。得到路徑研究所｜的｜確實｜65.652228研究所｜的確｜實行｜0.105840步驟11指標移至第七字。檢查點(204)檢查結果發現並沒有超過一個路徑在目前指標位置(動)有切割點。指標移至「動」字路徑研究所｜的｜確實｜行動｜0.010964研究所｜的確｜實行｜0.105840步驟12指標移至第八字路徑研究所｜的｜確實｜行動｜0.010964研究所｜的確｜實行｜動｜0.000019步驟13依據(204)的判斷，重複(202)的動作，發現超過一路徑在目前指標位置有切割點，比較其發生機率。
路徑「研究所｜的確｜實行｜動｜」刪除，因為其發生機率(0.000019)比路徑「研究所｜的｜確實｜行動｜」(0.010964)低。得到路徑研究所｜的｜確實｜行動｜\0.010964步驟14達到句子尾端，壓縮處理單元切割動作結束。
(3)發明效果由上述說明可知，利用本發明的中文文件檔壓縮處理方法及裝置，可得到正確的切割效果，並能達到良好的壓縮效果。
表2顯示利用本發明的中文文件檔壓縮處理方法及裝置處理3個中文文件檔所得的效果。
由該表所示可知，本發明在作中文檔案壓縮處理時，可以得到約35-55%上下的壓縮比率，確具有提高效果。再者，本發明適用的範圍可以包括各種經頻率編碼的資料壓縮或其它處理，亦具有廣泛有用途。
以上是本發明實施例說明。本領域技術人員不難由以上說明中明了本發明精神，並據以作出不同的變化及引伸，但無論如何，均屬本發明之範疇。
權利要求
1.一種中文文件檔的壓縮處理裝置，包含一輸入裝置，用以輸入待處理的中文文件檔；一存貯器，供儲存所處理文件檔；一編碼詞典，記載每一壓縮處理單元的使用機率；一壓縮處理單元切割裝置，可將文件檔切割成低混亂度的壓縮處理單元碼串；一編碼對照表，記載代表各壓縮處理單元的壓縮碼，該對照表系依據各壓縮處理單元在中文文件檔中的平均出現機率編碼，給與出現機率較高者較短的碼，出現機率較低者，給與較長的碼；一壓縮裝置，將該壓縮處理單元切割裝置切割處理過的中文文件檔，參考該編碼對照表，把文件檔中的壓縮處理單元逐一轉換成壓縮碼而得到壓縮檔；其特徵在於，該壓縮處理單元切割裝置系利用該編碼詞典中記載，各壓縮單元的使用機率，計算各種可能的切割結果機率分數，將機率分數最高的切割結果，供壓縮裝置處理。
2.如權利要求第一項的裝置，另含一反壓縮處理裝置，可將該存貯器中的壓縮文件檔，參考該編碼對照表，把代表該文件檔的壓縮碼逐一反轉成原始壓縮單元，而得到原來的文件檔。
3.如權利要求第1項的裝置，其中的壓縮處理單元切割裝置含有一暫存裝置，可從欲處理的中文文件取出一個中文片段第一檢查裝置，檢查以該中文片段的特定字為首組成的不同長度字串是否列於該編碼詞典之中，在尋得的字串尾端註明為切割點，並對所有前後連貫的字串，建立一虛擬路徑;第二檢查裝置，檢查是否超過一路徑在同一位置有切割點，對所有切割點位於該位置的路徑，檢查以該位置的字為首組成的不同長度字串，是否列於編碼詞典之中，無法在詞典中找到該字串，則刪除此路徑;一計算裝置，參考該編碼詞典記載的每一字串的使用機率，計算各路徑機率分數;一比較裝置，比較各路徑的機率分散，以分數最高的路徑，作為切割之結果。
4.如權利要求第3項的裝置，其中該壓縮處理單元切割裝置的暫存裝置，可從欲處理的中文文件檔中取出一個中文句子，作為處理的片段。
5.如權利要求第3項的裝置，其中該壓縮處理單元切割裝置的編碼詞典，記載的壓縮處理單元系中文之詞。
6.如權利要求第3項的裝置，其中該壓縮處理單元切割裝置的計算裝置，系將各路徑所含壓縮處理單元在該編碼詞典記載使用機率相乘，以計算各路徑的機率分數。
7.一種中文文件檔的壓縮處理方法，包含一輸入步驟，輸入待處理中文文件檔，儲存於存貯器中;一切割步驟，將該文件檔切割成低混亂度的壓縮處理單元碼串;一壓縮步驟，將該切割步驟切割處理過的中文文件檔，參考一記載各壓縮處理單元的壓縮碼的編碼對照表，將文件檔中的壓縮處理單元逐一轉換成壓縮曼碼得到壓縮檔;其中，該對照表系依據各壓縮處理單元在中文文件檔中的平均出現機率編碼，給與出現機率較高者較短的碼，出現機率較低者，給與較長的碼;其特徵在於，該切割步驟系利用一編碼詞典中記載的各壓縮單元的使用機率，計算各種可能的切割結果的機率分數，將機率分數最高的切割結果，供壓縮步驟處理。
8.如權利要求第7項的方法，另含一反壓縮步驟，可將該壓縮文件檔，參考編碼對照表，把代表該文件檔的壓縮碼逐一反轉成原始壓縮單元，而得到原來的文件檔。
9.如權利要求第7項的方法，其中的切割步驟含有一暫存步驟，從欲處理的中文文件檔中取出一個中文片段;第一檢查步驟，指標置於中文片段的首字，檢查以該字為首組成的不同長度字串是否列於該編碼詞典之中，並對每一個尋得的字串，建立一虛擬路徑，在字串尾端註明為切割點第二檢查步驟，檢查是否超過一路徑在目前指標位置有切割點，如否，指標往前移動一個位置;第三檢查步驟，對所有切割點與目前指標位置相同之路徑，檢查以目前指標位置的字為首組成的不同長度的字串是否列於編碼詞典之中，將每一個尋得編碼，接在原路徑之後組成新路徑，並在每一新路徑尾端註明為切割點，若無法在該編碼詞典中找到該字串，則刪除該路徑;一計算步驟，對第二檢查步驟檢查出超過一個在目前指標位置有切割點之路徑，參考該編碼詞典記載的每一字串的使用機率，計算該路徑，由首字至目前的指標位置的機率分數;一比較步驟，比較各路徑的機率分數，將分數最高的路徑，供作壓縮處理;第四步驟，檢查是否已處理至該處理中文片段的末字，如否，則重複上述處理，如是，則結束分割處理。
10.如權利要求第9項的方法，其中該切割步驟的暫存步驟是從欲處理的中文文件檔中取出的一中文句子作處理的片段。
11.如權利要求第9項的方法，其中該切割步驟所使用的編碼詞典記載之壓縮處理單元系中文詞。
12.如權利要求第9項的方法，其中該切割步驟的計算步驟，系將各路徑所含壓縮處理單元在該編碼詞典記載使用機率相乘，以計算各路徑之機率分數。
全文摘要
利用中文特點，以中文詞為編碼單元，依據其在中文文件中的出現機率，將中文文件切割成最適合壓縮的不定長度的單元，處理後的文件可以編成包括霍夫曼碼及其同類各種頻率碼。以本發明裝置處理過的中文文件，轉換成霍夫曼碼後，可以得到約35—55％上下的壓縮比率。本發明也提供一種決定中文處理單元的方法。
文檔編號C08F4/646GK1083638SQ9210970
公開日1994年3月9日 申請日期1992年8月22日 優先權日1992年8月22日
發明者張俊盛, 劉顯仲, 柯淑津 申請人:聲寶股份有限公司, 張俊盛