使用貪婪的順序上下文相關文法變換的改進的無損耗數據壓縮方法

2023-09-22 02:19:40 2

專利名稱：使用貪婪的順序上下文相關文法變換的改進的無損耗數據壓縮方法
技術領域：
本發明一般涉及數據壓縮領域，尤其涉及使用順序文法變換(sequential grammar transform)和編碼方法壓縮具有已知上下文的數據。
背景技術：
通用數據壓縮方法可以分為兩類通用無損耗數據壓縮和通用有損耗數據壓縮。傳統的通用無損耗數據壓縮方法通常採用算術編碼算法、Lempel-Ziv算法及其變體。算術編碼算法以待壓縮數據的統計模型為基礎。為了使用算術編碼算法對數據序列進行編碼，需要在編碼過程中動態地建立一個統計模型，或者，假設該模型已經事先存在。現有一些方法可以動態地建立統計模型，包括通過部分匹配算法、動態馬爾可夫建模、上下文收集算法和上下文樹加權的預測。這些方法各使用合適的上下文，預測數據序列中的下一個符號，並使用其估計出的相應條件概率，對這些符號進行編碼。
大多數算術編碼算法及其變體僅對於馬爾可夫階數低於一些設計參數值的馬爾可夫信源類型而言是通用的。並且，算術編碼算法對數據序列進行逐字符編碼。
相比之下，Lempel-Ziv算法及其變體不採用統計模型。Lempel-Ziv算法根據字符串匹配機制，將原始數據序列解析為不重疊的變長短語，然後逐短語地將其編碼。此外，Lempel-Ziv算法對於比有界階數馬爾可夫信源類型要寬廣的信源類型而言是通用的，有界階數馬爾可夫信源是平穩遍歷信源。
其他傳統的通用壓縮方法包括動態霍夫曼(Huffman)算法、移至前端編碼機制和一些利用代碼本傳輸的兩級壓縮算法。這些傳統方法要麼次於算術編碼和Lempel-Ziv算法，要麼太複雜而無法實現。最近提出了一種基於替換表的新型無損耗數據壓縮算法，它包括一個新的編碼框架，但卻沒有引入明確的數據壓縮算法。但是，該方法的缺點在於編碼過程中使用的貪婪順序變換(greedy sequential transformation)很難實現，並且不利於進行高效的編碼，因為解析過程中涉及到了初始符號s0。
此外，這些算法並不需要對壓縮的數據序列具備任何先驗知識。在使它們適合通用數據壓縮需要的同時，這些算法對於數據壓縮特定應用的效率不高。在很多情況下，如壓縮web頁面、java小程序或文本文件時，對於壓縮的數據序列通常要有先驗知識，該知識通常採用所謂的「上下文模型」的形式。
我們需要的是一種充分利用壓縮的數據序列的上下文的先驗知識、並同時克服現有壓縮方法的上述缺點的通用無損耗數據壓縮方法。

發明內容
根據本發明，提供了一種通用無損耗數據壓縮方法。該方法採用信源編碼構造在線的、可調的、上下文相關的壓縮規則。不像以前使用的壓縮單個目標的其他方法，該方法壓縮規則的數字集合。例如，為了實現基於web的數據的在線壓縮，該方法接收數據，動態地構造規則，然後對這些規則進行編碼。因為規則集合是動態的，所以當web文本數據的結構發生改變時，相應的規則也被更新。同樣，當web對象的內容更新時，對應的規則也相應地被更新。該方法對於web頁面編碼尤其高效，因為web頁面的內容經常發生改變，而web頁面的底層結構基本保持恆定。壓縮數據時，該底層結構的相對一致性提供了數據的可預測上下文。
本發明的一個方面涉及一種方法，它將與關聯已知上下文相關聯的原始數據序列順序地轉換為一個不可約的上下文相關文法，並從該文法中恢復原始數據序列。該方法包括以下步驟從該序列中解析子串；根據解析的子串，產生容許的上下文相關文法；將一個約簡規則集合應用於該容許的上下文相關文法，從而產生一個新的不可約上下文相關文法；重複這些步驟，直到將整個序列編碼。此外，基於變量和上下文對的約簡規則集合表示該不可約上下文相關文法，從而使得這些對表示數據序列的不重疊的重複模式和上下文。
根據本發明的另一個方面，該方法涉及使用自適應上下文相關算術編碼，對與來自可數上下文模型集合的已知上下文模型相關聯的不可約上下文相關文法進行編碼。此外，應用一個基於變量和上下文對的約簡規則集合，以表示不可約上下文相關文法，從而使得這些對表示數據序列的不重疊的重複模式和上下文。
根據本發明的另一方面，提供了一種將具有已知上下文模型的數據序列進行編碼的方法，包括將該數據序列變換為不可約上下文相關文法；將該不可約上下文相關文法轉換為其分類形式；從該分類的不可約上下文相關文法中，構造一個產生的序列；並使用自適應上下文相關算術編碼，將產生的序列進行編碼。
本發明還涉及一種方法，它將與已知上下文模型相關聯的原始數據序列順序地變換為不可約上下文相關文法的序列；並且根據每個不可約上下文相關文法，使用自適應上下文相關算術編碼，對該數據序列進行編碼。該方法包括以下步驟從該序列中解析子串；通過利用前一個不可約上下文相關文法的結構和使用自適應上下文相關算術編碼，對該子串進行編碼；根據該子串、當前上下文和前一個不可約上下文相關文法，產生容許的上下文相關文法；將一個約簡規則集合應用於該容許的上下文相關文法，從而產生一個新的不可約上下文相關文法；重複這些步驟，直到該系列所有的符號都被解析和編碼。


通過參考以下結合附圖的描述，可以更好地理解本發明的上述和更多優點圖1是根據本發明實施例的上下文相關文法變換的一系列操作的流程圖；圖2是根據本發明的實施例，在已知上下文情況下解析輸入字符串的子串的一系列操作的流程圖；圖3是根據本發明的實施例，更新不可約上下文相關文法的一系列操作的流程圖；圖4是根據本發明的實施例，將約簡規則集合應用於順序壓縮具有已知上下文和前一個已知上下文相關文法的輸入字符串的一系列操作的流程圖；圖5、圖6、圖7、圖8和圖9是根據本發明的實施例，將約簡規則應用於壓縮具有已知上下文和前一個已知上下文相關文法的輸入字符串的一系列操作的流程圖；圖10是根據本發明的實施例，將產生的序列進行編碼的等級式方法的流程圖；圖11是使用順序上下文相關方法的一個實施例對具有已知上下文的輸入字符串進行編碼的流程圖；圖12是根據本發明的實施例，使用上下文相關文法變換方法的數據壓縮裝置的框圖。
具體實施例方式
本發明的描述中採用了以下符號A用於表示一個基數大於或等於2的信源字母表；A*用於表示從A中提取的所有有限字符串(包括空字符串λ)的集合；A+用於表示從A中提取的所有具有正長度的有限字符串的集合；符號|A|表示A的基數，並且對於任意x∈A*，|x|表示x的長度；對於任意正整數n，An表示A中長度為n的所有序列的集合；由A構成的序列也可以被稱為A序列；x∈A+用於表示待壓縮的序列。信源字母表A是跟應用相關的。定義一個可數的符號集合S＝{s0，s1，s2，…}，它與A∪C不相交。S中的符號被稱為變量；A中的符號被稱為終結符。對於任意j≥1，令S(j)＝{s0，s1，s2，…，sj-1}。
C用於定義任意上下文集合，集合C可以是有限的或無限的。在通常的上下文模型中，對於從字母表A提取的任意序列x＝x1x2…xn，存在一個來自C的上下文序列C1C2…Cn。在這個上下文序列中，每一個Ci表示xi的上下文。對xi進行編碼之前，可通過某種方式，根據所有歷史x1x2…xi-1和C1確定Ci。此關係的表達式為Ci+1＝f(x1，…，xi，C1)，i＝1，2，…，(1)其中C1∈C是初始的固定上下文，f是一種映射關係，在這裡指「下一個上下文函數」。可以將上述性質進一步擴展到所謂的可數上下文模型，其中式(1)式仍成立，並且上下文集合C是可數無限的。
G用來表示從C×S(j)的子集到(S(j)∪A)+的上下文相關文法的映射關係，其中，j≥1。集合S(j)表示G的變量集合，S(j)中的元素被稱為G變量。於是，G的域可表示為ΩG(Ki，ji)C×S(j)，其中K是域中不同上下文的個數。在ΩG(Ki，ji)中，有一個特殊對(C1，s0)∈ΩG(Ki，ji)，它表示初始對，其中C1用於標識初始上下文。
描述變量、其上下文與上下文相關文法之間映射關係的一種方法是對於每對(Ck，si)∈ΩG(Ki，ji)，將關係(si|Ck，G(si|Ck))定義為si|Ck→G(si|Ck)，作為產生規則(production rule)。然後，就可以用一個產生規則集合完全描述上下文相關文法G，即{si|Ck→G(si|Ck)(CK，si)∈ΩG(Ki，ji)，0≤i＜j，0＜k＜∞}。
在一個示例性的實施例中，參照圖1，根據本發明，方法100可用於執行數據壓縮。方法100的輸入為已知的上下文102和輸入字符串104。解析器接收上下文102和輸入字符串104，並將輸入字符串104解析為不重疊子串的集合(步驟106)。圖2中的方法200進一步示出了解析步驟(步驟202)。解析步驟(步驟202)包括確定當前子串的上下文(步驟202)，以及確定是否能在當前上下文下表示當前子串(步驟204)。如果不能由當前上下文下表示當前子串，則設置當前子串等於當前上下文下的下一個符號(步驟206)。或者，如果當前子串能由當前上下文表示，則設置當前子串等於表示該子串的最長前綴(步驟208)。回到圖1，解析器將該子串傳輸到上下文相關文法更新設備，然後其更新上下文相關文法G(步驟108)。圖3中的方法300進一步示出了更新步驟(步驟108)。如果當前解析的字符串的長度大於1(步驟302)，則在前一個不可約的上下文相關文法的末尾添加當前變量(步驟304)，然後應用如下所述的約簡規則集合(步驟308)。或者，如果當前解析的字符串的長度不大於1，則在前一個不可約的上下文相關文法的末尾添加當前符號(步驟306)，然後，應用如下所述的約簡規則集合(步驟308)。再回到圖1，如果輸入字符串沒有被完全解析(步驟110)，則經過一個延時之後重複該方法(步驟112)。然後，上下文相關算術編碼器將該文法壓縮成二進位碼字(步驟114)。
示例1在此示例中，信源字母表被定義為A＝{0，1}。此外，可定義一個可數的上下文模型，使得C＝{0，1}，其下一個上下文函數f為Ci+1＝xi。變量集合為{s0，s1，s2}且初始對為(0，s0)的上下文相關文法G的一個可能例子是s0|0→s1s11s20s1s2s10s1|0→001
s1|1→01s2|1→1s1在上面的示例1中，可以用變量集合S(j)和初始對(C1，s0)定義G。通過從G(s0|C1)中的左邊重複替換第一個變量s的G(s|C)(其中C是根據上面的公式(1)由C1及G(s0|C1)中直到s的前綴進行確定的)，將滿足下列條件之一(1)在有限次數的替換步驟之後，從A中獲得一個序列；(2)因為這樣獲得的每個字符串都包含一個G變量的入口，所以替換過程永不結束；(3)因為s|C對應的產生規則未在G中定義，所以替換過程不能繼續。
繼續來看示例1，如果滿足條件(1)-(3)，可做以下替換 在以上示例1中，通過執行以下過程，可以從A中獲得一個序列。從s0|0→G(s0|0)開始，重複應用連續替換過程。九個步驟之後(每次出現符號 就表示替換過程的一步)，連續替換過程結束。此外，在整個替換過程中，使得si|Ck的產生規則定義於G中的上下文Ck(1≤k≤2)下的每一個變量si(0≤i＜3)至少被G(si|Ck)替換一次。因此，此例中，在上下文0(或G)下，s0表示序列x＝0010111010001101010。每一個其他G變量表示x的一個或更多的子串當上下文0時，s1表示001；當上下文為1時，s1表示01；當上下文為1時，s2表示101。為了進一步說明此方法的上下文相關特徵，應該注意的是子串「01」在上下文相關文法G的範圍內出現了兩次。然而，在上下文相關的意義上來說，這兩個子串並不是重複的字符串，因為每一個子串都有不同的上下文。
如果滿足下列條件，一種容許的上下文相關文法G就可以被定義為不可約的(1)對於任意上下文C，使得(C，s)∈ΩG(K，j)\{(C1，s0)}的每一個G變量s在上下文C下在範圍G內至少出現兩次；(2)就上下文相關意義來說，在範圍G內不存在長度大於或等於2的不重疊的重複模式；(3)在相同上下文C下，每一個不同的G變量s∈{s(C，s)∈ΩG(K，j)}表示不同的A序列。
因此，上述示例1中容許的上下文相關文法是不可約的。
文法變換是將任意的數據序列x∈A+變換為表示x的容許的上下文相關文法Gx的變換。如果對於所有的x∈A+，Gx都是不可約的，則該文法變換就是不可約的。從表示x的一個容許的上下文相關文法G開始，可以重複應用一個約簡規則集合，從而生成另一個容許的上下文相關文法G′，它表示相同的x並滿足以下性質
(1)與x的長度相比，G的大小|G|應該足夠小；(2)當上下文相同時，不同的G變量所表示的A字符串是不同的；(3)在G的範圍內，G的變量和終結符的上下文相關頻率分布應該使得能夠應用有效的上下文相關算術編碼。
圖4示出了應用一個約簡規則集合的示例性方法400，它可以順序構造一個不可約上下文相關文法的序列，通過此序列，可以遞增地恢復原始數據序列。提取出前一個文法約簡比特I(步驟402)。將α定義為前一個不可約的上下文相關文法中的初始變量和上下文對s0|C1所對應的產生規則的最後一個符號(步驟408)。將C定義為α的上下文(步驟410)。將β定義為中間文法G′i-1中的初始變量和上下文對s0|C1所對應的產生規則的最後一個符號(步驟412)。判斷上下文C時αβ是否出現在G′i-1中的兩個不重疊位置(步驟414)。如果否，則設置當前的不可約文法為G′i-1(步驟416)，並設置當前的文法比特I為0(步驟418)。如果αβ在上下文C時出現於G′i-1中的兩個不重疊位置，則進一步判斷前一個文法比特是否等於1(步驟420)。
如果前一個文法比特不等於1，則進一步判斷在相同上下文情況下αβ是否重複自身出現在G′i-1(s0|C1)中兩個不重疊位置(步驟422)。如果重複，則對G′i-1應用一次約簡規則2(步驟428)，將當前不可約上下文相關文法設置為所得的文法(步驟426)，並將當前的文法比特I設置為1(步驟428)。如果不重複，則對G′i-1應用一次約簡規則3(步驟430)，將當前不可約上下文相關文法設置為所得的文法(步驟426)，並將當前的文法比特I設置為1(步驟428)。
回到前一個文法比特等於1的情況(步驟420)，進一步判斷αβ是否在相同上下文情況下重複自身出現在G′i-1(s0|C1)中兩個不重疊位置(步驟432)。如果重複，則對G′i-1先應用約簡規則2一次，然後再應用約簡規則1(步驟434)，將當前不可約的上下文相關文法設置為所得的文法(步驟426)，並將當前的文法比特I設置為1(步驟428)。如果不重複，則對G′i-1應用約簡規則3一次，然後再應用約簡規則1(步驟436)，將當前不可約的上下文相關文法設置為所得的文法(步驟426)，並將當前的文法比特I設置為1(步驟428)。
圖5示出了應用約簡規則1的方法500。將s定義為容許的上下文相關文法G的一個變量，在G範圍內上下文為C時它僅出現一次(步驟502)。定義產生規則 其中，上下文為C時s出現在右邊(步驟504)。定義對(C，s)所對應的產生規則s|C→γ(步驟506)。通過從G中刪除產生規則s|C→γ，並將產生規則 替換為產生規則 來將G約簡為容許的上下文相關文法G′，所得的上下文相關文法G′與G表示相同的序列(步驟508)。
圖6示出了應用約簡規則2的方法600。將G定義為容許的上下文相關文法，其具有形式為s|C→α1βα2βα3的產生規則，其中β的長度至少為2，並且β在這兩個位置的上下文等於相同的上下文C′(步驟602)。定義新的產生規則s′|C′→β，其中(C′，s′)是G域中沒有的新的上下文和變量的對(步驟604)。通過將G的產生規則s|C→α1βα2-βα3替換為s|C→α1s′α2s′α3，並添加產生規則s′|C′→β，來將G約簡為新的上下文相關文法G′，所得的文法G′包括新的上下文和變量的對(C′，s′)，並且，並且與G表示相同的序列x(步驟608)。
圖7示出了應用約簡規則3的方法700。定義G為容許的上下文相關文法，其具有形式分別為s|C→α1βα2和s′|C′→α3βα4的兩個不同的產生規則，其中β的長度至少為2，這兩個位置的β的上下文等於相同的上下文C″，α1或α2不為空，並且α3或α4不為空(步驟702)。定義一個新的產生規則s″|C″→β，其中(C″，s″)是不在G的域中的新的上下文和變量的對(步驟704)。通過用s|C→α1s″α替換產生規則s|C→α1βα2，並用s′|C′→α3s″α4替換產生規則s′|C′→α3βα4，並附加新的規則s″|C″→β，來將G約簡成新的上下文相關文法G′(步驟706)。
圖8示出了應用約簡規則4的方法800。定義G為容許的上下文相關文法，其具有形式為s|C→α1βα2和s′|C′→β的兩個產生規則，其中β的長度至少為2，s|C→α1βα2中β的上下文也等於C′，並且α1和α2中之一不為空(步驟802)。通過用新的產生規則s|C→α1s′α2替換所述產生規則s|C→α1βα2，將G約簡為上下文相關文法G′(步驟804)。
圖9示出了應用約簡規則5的方法900。定義G為容許的上下文相關文法，其中，給定上下文C情況下兩個變量s和s′表示由G所表示的A序列的相同子串(步驟902)。在G範圍內，只要s′的上下文等於C，就用s替換每一個s′的出現，並刪除(C，s′)所對應的產生規則，從而將G約簡成新的上下文相關文法G′(步驟904)。判斷文法G′是否為容許的上下文相關文法(步驟906)。文法G′可能不是容許的，因為在G′的連續替換過程中可能沒有包括一些G′變量。如果這是真的，則通過刪除連續約簡過程中不包括的變量G′所對應的所有產生規則，來進一步把G′約簡為上下文相關文法G″ (步驟908)，否則，解析下一字符串(步驟910)。
本發明的一個方面包括一個貪婪的上下文相關文法變換，在一個實施例中，此文法變換將壓縮A中的數據序列x＝x1，x2，…xn。不可約的上下文相關文法變換被描述為貪婪的，它把序列x解析成不重疊的子串{x1，x2…xn2，…，xni-1+1…xni}並順序為每個x1…xni建立不可約的上下文相關文法，其中1≤i≤t，n1＝1且ni＝n。在這種情況下，第一個子串x1和相應的不可約上下文相關文法G1隻包含一個產生規則s0|C1→x1，其中C1是初始上下文。假設{x1，x2…xn2，…，xni-1+1…xni}已經被解析且x1…xni相應的不可約上下文相關文法Gi已經建立。假設G1的變量集合是S(ji)={s0,s1,sji-1},]]>其中j1＝1，Gi的域是ΩG(Ki，ji)。令Cni+1是由可數上下文模型生成的xni+1的上下文。如果xni+1…xn存在最長前綴，其在上下文Cni+1時能由sj{s:(Cni+1,s)G(Ki,ji)}]]>表示，則下一子串xni+1…xni+1就是該最長前綴。否則，ni+1＝ni+1時，Xni+1…xni+1＝Xni+1。如果ni+1-ni＞1且在上下文Cni+1時Xni+1…xni+1由sj表示，那麼在Gi(s0|C1)右端添加sj；否則，在Gi(s0|C1)右端添加符號xni+1。所得的上下文相關文法是容許的，但未必是不可約的。應用約簡規則1至5，將該上下文相關文法約簡成不可約的上下文相關文法Gi+1。約簡之後，Gi+1表示序列x1…xni+1。重複該過程，直到整個序列x被處理得到表示序列x的最終不可約上下文相關文法Gt。
示例2下面的示例說明上述方法。定義A＝{0，1}且x＝0001001100001111001111。使用可數上下文模型C＝{0，1}以及下一個上下文函數f為Ci+1＝xi對x應用上述不可約的上下文相關文法變換。前三個解析的子串是0，0和0。假設初始上下文C1＝0，相應的不可約上下文相關文法G1，G2和G3分別用{s0|0→0}，{s0|0→00}和{s0|0→000}表示。由於j3＝1，第四個解析的子串為x4＝1。在G3(s0|0)的末尾添加符號1，得到由{s0|0→0001}表示的容許的上下文相關文法G3′。G3′本身是不可約的，因此沒有約簡規則能被應用，並且G4等於G3′。
繼續上面的示例2，第五和第六個解析短語分別是x5＝0和x6＝0。G6表示為{s0|0→000100}。第七個解析短語是x7＝1。在G6(s0|0)的末尾添加符號1，所得容許的上下文相關文法G6′表示為s0|0→0001001。G7′不是不可約的，因為在G6′範圍內同樣的上下文0時有不重疊的重複模式01。應用約簡規則2一次，我們可得到不可約的上下文相關文法G7，表示為s0|0→00s10s1s1|0→01根據G7，接下來的五個解析短語分別是x8＝1，x9＝1，x10＝1，x11＝0和x12＝0。在G7(s0|0)的末端添加解析的短語，依次產生不可約的上下文相關文法G9至G12。第十三個解析的短語是x13＝0。在G12(s0|0)的末尾添加符號0並應用一次約簡規則2，得到以下不可約的上下文相關文法G13s0|0→s2s10s11110s2s1|0→01s2|0→00當前上下文為0的情況下，剩下未解析的字符串為01111001111。在此例中，由於上下文為0時由s1表示的來自A的序列匹配上下文同樣為0情況下x的剩餘部分的前綴，所以，下一個解析短語是x14x15＝01。在G13(s0|0)的末端添加符號s1，得到容許的上下文相關文法G13′s0|0→s2s10s11110s2s1s1|0→01s2|0→00因為上下文為0時s2s1重複，所以G13′不是不可約的。應用約簡規則2，得到不可約的上下文相關文法G13″s0|0→s30s11110s3s1|0→01s2|0→00s3|0→s2s1在上面的文法中，在G13″的範圍內上下文為0時，變量s2隻出現了一次，因此應用一次約簡規則1，得到不可約的上下文相關文法G14
s0|0→s20s11110s2s1|0→01s2|0→00 s1繼續該方法，產生最終不可約的上下文相關文法G22s0|0→s20s1s1s2s1s1s2s1|0→01s1|1→s20s2|0→00s1s2|1→111這樣，不可約的上下文相關文法變換將x解析成{0，0，0，1，0，0，1，1，1，1，0，0，0，0，1，1，1，1，0，0，1，1，1，1}。
本發明的另一方面(表示為1000)如圖10所示，在這裡表示為「等級式上下文相關方法」。此方法包括一個貪婪的不可約上下文相關變換，然後對最終不可約上下文相關文法Gt進行上下文相關算術編碼。數據序列首先被變換為不可約的上下文相關文法(步驟1002)，然後再被轉換成其分類形式(步驟1004)。從該分類文法構造產生的序列(步驟1006)，並使用具有動態字母表的自適應上下文相關算術編碼對該產生的序列進行編碼(步驟1008)。
作為一個示例，令χ為待編碼的A序列，令G1為表示由我們的不可約上下文相關文法變換提供的χ的最終不可約上下文相關文法。在等級式上下文相關方法中，具有動態字母表的上下文相關算術編碼用於對G1(或其等價形式)進行編碼。接收到二進位碼字之後，解碼器恢復G1(或其等價形式)，然後執行如示例1所示的連續替換過程，從而得到χ。
一個實施例首先示出了容許的上下文相關文法G如何推導出序列χ∈An的一部分，然後進一步描述了分類的上下文相關文法的概念。令ΩG表示ΩG(K，j)動態變化的子集；開始時，ΩG為空。令u(0)＝G(s0|C1)；其中u(0)是來自(S(j)∪A)的序列。如果j＝1，或等價為如果u(0)中沒有變量，那麼，u(0)本身指由G所推導出的部分序列。否則，執行下面的步驟步驟1設置i＝0；步驟2對於i≥0，從左向右讀取u(i)，用G(s|C)替換不在ΩG中的第一對(C，s)，其中C是由上下文模型確定的s的上下文，所得的序列用u(i+1)表示；步驟3將對(C，s)插入ΩG，從而更新ΩG；步驟4對於i＝0，1，…，|ΩG(K，j)|-1，重複步驟2和步驟3，以使每一對(C，s)∈ΩG(K，j)\{(C1，s0)}正好被G(s|C)替換一次。
最終的序列u(|ΩG(|(K，j)|-1)被稱為由G導出的部分序列。如果在上面的過程中，動態集合ΩG以這樣的方式擴增對每個出現在ΩG(K，j)中的上下文C，對於任何有意義的i＞0，(C，si)出現於(C，si+1)之前，那麼，上下文相關文法G被稱為分類形式。
在示例2所示的G22中，|ΩG(K，j)|＝5。五個序列u(0)，…，u(4)為
u(0)＝s20s1s1s2s1s1s2，u(1)＝00s10s1s1s2s1s1s2，u(2)＝00010s1s1s2s1s1s2，u(3)＝00010s1s20s2s1s1s2，u(4)＝00010s11110s2s1s1s2。
部分序列u(4)將序列x解析為0，0，0，1，0，01，1，1，1，0，0001，1110，01，111。將以上子串連接，重建原始序列x。動態集合ΩG按照(0，s2)，(0，s1)(1，s1)和(1，s2)的順序擴增。因而，在此例中，G22不是分類形式。
現在，可以使用等級式上下文相關方法，對序列進行編碼，其如例2所示。如上所述，最終不可約的上下文相關文法G22不是分類形式。通過下式，將G22轉換成分類形式G22ss0|0→s10s2s1s1s1s2s2s1|0→00s2s1|1→s20s2|0→01s2|1→111.
在例2中，為了從G22獲得G22s，可將G22中上下文0時的變量s1、s2分別重命名為G22s中上下文0時的s2、s1。需要注意的是，G22和G22s表示相同的序列x。現在，將G22s而非G22進行編碼和傳輸。對G22s應用上面步驟1-4中所述的過程，得到由G22s導出的部分序列u(4)＝00010S21110S1S1S2S2令α是Gi(s0|C1)的最後一個符號， 是α的上下文。為了解決G22s無法從部分序列恢復的事實，將該過程稍做修改。具體為，在步驟2中，用[G(s|C)]替換不在ΩG中的一對的第一個變量s及其上下文C，並且相應的序列被表示為(i)，i＝0，…，|ΩG(K，j)|-1。將修改的過程應用於G22s，得到來自(S(j)A){[,]}]]>的以下序列u(4)＝
]0S2[[111]0]S1S1S2S2該序列被稱為由G22或其分類形式G22s產生的序列。由於引入了符號[和]，對關聯的可數上下文模型的下一個上下文函數f稍做修改，使得對於每一個C∈C，C＝f(C，[)和C＝f(C，])，即[和]僅僅接替(relay)上下文。因此，可以從由G22s所產生的序列 中恢復G22s和序列x。 中合法的括號對[和]的個數等於除(C1，s0)之外G22s的域中的變量和上下文對的個數；上下文C時第i個合法的括號對[和]內的內容產生對應於si|C的產生規則。因此，可以從 推斷出每一個變量s在給定的上下文時表示什麼，因此使用分類的CDG G22s而非原始的CDGG22。為了壓縮G22s或序列x，使用具有動態字母表的上下文相關算術編碼對由G22s生成的序列進行編碼。需要注意的是編碼器和解碼器都知道關聯的可數上下文模型。每一對(C,)(CS)(C(A{[,]}))]]>與一個計數器c(C，β)相關聯，如果c(C,)C(A{[,]}),]]>設置c(C，β)為1，否則設置c(C，β)為0。按照下列步驟，對根據G22s所生成的序列中的每一個符號β進行編碼並更新相關的計數器步驟1在上下文C(初始時C＝C1)的情況下，使用概率c(C，β)/∑c(C，α)對β進行編碼，其中求和符號 針對使c(C，α)≠0的所有符號SA{[,]}]]>進行求和；步驟2將c(C，β)加1；步驟3 在由G生成的序列中，如果β＝]且對應於β的合法的括號對是上下文C′時的第i個括號對(其中，C′是此括號對中[的上下文]，則將計數器c(C′，si)由0增加到1；步驟4確定產生的序列中下一短語的下一個上下文C。
重複以上過程直到將整個產生的序列編碼。對於上面所示的產生的序列 算術編碼處理中所使用的概率積是141526273819142516112172819210311312214113114116215117]]>總之，要對最終的不可約CDG Gi編碼，首先要把Gi轉換成它的分類形式Gis，然後根據Gi構造生成的序列，最後使用具有動態字母表的上下文相關算術編碼，對生成的序列進行編碼。
圖11還示出了本發明的另一方面，即方法1100，在這裡表示為「順序上下文相關方法」，其包括使用具有動態字母表的上下文相關算術編碼對解析短語序列x1，x2…xn2，…，xni-1+1…xni進行編碼。已知的上下文102和輸入字符串104作為輸入，並被解析為不重疊的字符串(步驟106)。使用前一個不可約上下文相關文法的結構並使用具有動態字母表的自適應上下文相關算術編碼，對每一個解析的子串進行編碼(步驟1101)。生成和更新上下文相關文法(步驟108)，直到該字符串被完全解析(步驟110)。
與等級式上下文相關方法一樣，各對(C，β)∈(C×S)∪(C×A)都與計數器c(C，β)相關聯，如果(C，β)∈C×A，此計數器初始值被設置為1，否則被設置為0。每個短語在給定的上下文條件下被編碼。假設x1，x2，…xn2，…，xni-1+1…xni已被編碼且所有相應的計數器已被更新。進一步假設Gi是x1…xni的相應不可約上下文相關文法且Gi的變量集合等於S(ji)={s0,s1,...,sji-1}.]]>使用貪婪的上下文相關文法變換解析xni+1…xni+1並用{s1,...,sji-1}A]]>表示解析的字符串。按照下列步驟對β進行編碼，並更新相關計數器步驟1確定β的上下文C；步驟2在給定上下文C的條件下使用概率 對β進行編碼，其中求和符號 針對使c(C，α)≠0的所有符號S(ji)A]]>進行求和；步驟3將c(C，β)加1；步驟4根據添加的Gi得到Gi+1；步驟5如果Gi+1引入了新對(C′，S)所對應的新產生規則，則將計數器c(C′，S)從0增加到1。對所有的解析短語重複上面的過程，直到整個序列被處理並編碼。
本發明的另外一方面，在這裡被稱作「改進的順序上下文相關方法」，它包括使用一階算術編碼對序列 進行編碼，並使用序列 和 的結構改進解析短語x1,x2xn2,,xni-1+1xni]]>的序列的編碼。除了上面所定義的計數器c(C,),(C,)C(SA)]]>外，還定義了計數器cI(0，0)、cI(0，1)、cI(1，0)、cI(1，1)和 計數器cI(0，0)、cI(0，1)、cI(1，0)和cI(1，1)用於對序列 進行編碼，並且初始時都被設置為等於1。在I(i)＝0且I(i+1)＝1時，計數器 對第(i+1)個解析的短語進行編碼；在I(i+1)＝0時，則用計數器c(C，γ)來編碼。與c(C，γ)一樣，如果(C，γ)∈C×A，則初始時設置C^(C,)=1,]]>否則設置為0。與順序上下文相關方法中一樣，開始的三個解析短語x1，x2和x3被編碼。而且，因為I(1)，I(2)和I(3)全是0，沒有必要對它們進行編碼。從第四個短語開始，首先對I(i+1)進行編碼，然後將其與Gi的結構一起用作附加上下文信息，對第(i+1)個解析短語進行編碼。
作為進一步的說明，假設x1，x2…xn2，…，xni-1+1…xni和I(4)……I(i)已經被編碼並且所有相應的計數器已經被更新。進一步假設Gi是x1…xni相應的不可約上下文相關文法，且Gi的變量集合等於S(ji)＝{s0，s1，…，sj-1}。Gi的域是ΩG(Ki，ji)，令j(c，i)為與ΩG(Ki，ji)中任意C相關聯的變量(除去s0)的數目。此外，令α是Gi(s0|C1)的最後一個符號， 是α的上下文。使用貪婪的上下文相關文法變換解析xni+1…xni+1，並用{s1,...,sji-1}A]]>表示解析的字符串。使用下面的步驟對I(i+1)和β進行編碼並更新相關計數器步驟1使用概率cI(I(i)，I(i+1))/(cI(I(i)，0)+cI(I(i)，1))對I(i+1)進行編碼；步驟2將cI(I(i)，I(i+1))加1；步驟3確定β的上下文 步驟4如果I(i+1)＝0，使用概率 對上下文 的β進行編碼，其中求和符號 對所有使得c(C^,)0]]>的符號S(ji)A-L2(|C^)]]>求和，然後將 加1。否則，如果I(i)＝0且I(i+1)＝1，則使用概率 對上下文 的β進行編碼，然後將 加1。相反，如果I(i)＝1且I(i+1)＝1，則不發送信息，因為 僅包含一個元素，解碼器知道β是什麼。這裡所說的列表 包含具有以下性質的所有符號S(ji)A:]]>a)在上下文 時，模式αγ出現於Gi範圍內；b)上下文 時的模式αγ不是Gi(s0|C1)的兩個符號；c)Gi中沒有變量sj使得 等於αγ；以及d)所述列表 包括具有a)和b)性質的所有符號 S(ji)A.]]>步驟5從附加的Gi獲得Gi+1，相應地更新所有列表L1(γ|C)和L2(γ|C)；步驟6如果j(C^,j+1)>j(C^,i),]]>這說明Gi+1引入了對應於 的新的產生規則，因而將 和 都加1。重複此過程直到整個序列x被處理和編碼。
示例3對示例2中序列被解析為{0，0，0，1，0，0，1，1，1，1，0，0，0，0，1，1，1，1，0，0，1，1，1，1}的序列x，應用上述改進的順序上下文相關方法，進行壓縮，其中，相應的序列{I(i)}是{0000001000001101110011}。用於對序列{I(i)}22i＝4進行編碼的概率積是122334151246576879210132431125363781241348,]]>用於對解析短語進行編碼的概率積是122334111246121124352257124412195823.]]>對於那些將本發明提供為軟體程序的實施例，該程序可以用多種高級語言中的任意一種進行編寫，如FORTRAN、PASCAL、JAVA、C、C++、C#或BASIC。此外，該軟體可以用彙編語言實現，彙編語言專用於駐留在目標計算機上的微處理器，例如，如果該軟體被配置為運行於IBM PC或其它類似PC上，該軟體可用Intel 80x86彙編語言來實現。該軟體可以被收錄在製造的產品中，包括、但不限於軟盤、硬碟、光碟、磁帶、PROM、EPROM、EEPROM、現場可編程門陣列(FPGA)或CD-ROM。
在這些實施例中，該軟體可以被安裝運行在任何個人類型的計算機或工作站上，例如PC或PC兼容機、Apple Macintosh、Sun工作站等等。總之，可以使用任何設備，只要它能夠實現這裡描述的所有功能和能力。對於本發明來說，計算機或工作站的具體類型不是重點。
圖12示出了一個實施例，其中本發明為執行上述方法的設備1200。設備1200包括解析器1206，上下文相關文法更新設備1210和上下文相關文法編碼器1214。解析器1206接收輸入字符串1204和已知的上下文1202作為輸入，並把輸入字符串1204解析成一系列不重疊的子串1208。解析器將子串1208發送給上下文相關文法更新設備1210，上下文相關文法更新設備1210產生更新的上下文相關文法G。上下文相關文法更新設備1210將更新的文法G發送到上下文相關文法編碼器1214，然後，上下文相關文法編碼器1214將文法G編碼成壓縮的二進位碼字1216。
例如，設備1200可以是一個或多個專用集成電路(ASIC)、現場可編程門陣列(FPGA)、電可擦除可編程只讀存儲器(EEPROM)、可編程只讀存儲器(PROM)、可編程邏輯電路(PLD)或只讀存儲設備(ROM)。在一些實施例中，可以用一個或多個微處理器實現設備1200，例如，加利福尼亞州聖克拉拉的英特爾(Intel)公司製造的奔騰系列晶片，或者，伊利諾斯州紹姆堡(Schaumburg)的摩託羅拉(Motorola)公司製造的PowerPC系列晶片。
上面結合具體的優選實施例對本發明進行了詳細顯示和描述，但是，本領域技術人員應該理解，在不脫離所附權利要求書定義的本發明精神和保護範圍內，可以對本發明進行各種形式和細節上的改變。
權利要求
1.一種將原始數據序列順序地變換為不可約上下文相關文法的方法，所述原始數據序列包括多個符號且與已知上下文模型相關聯，根據所述不可約上下文相關文法可完全恢復所述原始數據，其中，所述不可約上下文相關文法是由產生規則集合表示的，這些產生規則是使用表示所述數據序列中的不重疊重複模式和上下文的變量和上下文的對的集合所形成的，所述方法適用於任何可數上下文模型，並包括以下步驟(a)從所述序列中解析子串，其中，如果所述序列以前未解析的符號的字符串的最長前綴存在，則所述子串是所述最長前綴，否則，所述子串是所述序列以前未解析的符號的字符串的第一個符號，其中，在當前時間點的上下文時，所述序列以前未解析的符號的字符串用前一個不可約上下文相關文法的變量集合中的變量、而不是變量和上下文對的集合的初始對中的初始變量來表示；(b)根據所述子串、當前上下文和所述前一個不可約上下文相關文法，產生容許的上下文相關文法；(c)將至少一個約簡規則集合應用於所述容許的上下文相關文法，以產生新的不可約上下文相關文法；(d)重複步驟(a)至(c)，直到用最終不可約上下文相關文法表示所述序列的所有符號。
2.如權利要求1所述的方法，其中，所述應用步驟還包括執行約簡規則的步驟，該約簡規則包括以下步驟(a)將s定義為在容許的上下文相關文法G的範圍內在某上下文C時出現一次的G的變量；(b)定義產生規則s|C^s,]]>其中，在上下文C時，s出現在一組符號的右邊；(c)定義與對(C，s)相對應的產生規則s|C→γ；以及(d)通過從G中刪除所述產生規則s|C→γ，並將所述產生規則s|C^s]]>替換為產生規則s|C^.,]]>來將G約簡為容許的上下文相關文法G′，所得的容許的上下文相關文法G′和G表示等價的數據序列。
3.如權利要求1所述的方法，其中，所述應用步驟還包括執行約簡規則的步驟，該約簡規則包括以下步驟(a)將G定義為具有形式為s|C→α1βα2βα3的產生規則的容許的上下文相關文法，其中，β的長度至少為2，並且β在這兩個位置的主要上下文等於相同的上下文C′；(b)定義新的產生規則s′|C′→β，其中，(C′，s′)是G的域中沒有的上下文和變量的新對；以及(c)通過將G的產生規則s|C→α1βα2βα3替換為s|C→α1s′α2s′α3，並添加產生規則s′|C′→β，來將G約簡為新的上下文相關文法G′，所得的文法G′具有上下文和變量的新對(C′，s′)，並表示與G等價的數據序列x。
4.如權利要求3所述的方法，其中，當在G′的範圍內，G′具有所述符號和上下文的不重疊重複模式時，執行所述約簡步驟，以替代所述產生規則集合中的其他規則。
5.如權利要求1所述的方法，其中，所述應用步驟還包括執行約簡規則的步驟，該約簡規則包括以下步驟(a)將G定義為具有形式為s|C→α1βα2和s′|C′→α3βα4的兩個產生規則的容許的上下文相關文法，其中，β的長度至少為2，β在這兩個位置的主要上下文等於相同的上下文C″，α1和α2之一不為空，並且α3和α4之一不為空；(b)定義新的產生規則s″|C″→β，其中，(C″，s″)是G的域中沒有的上下文和變量的新對；以及(c)通過將產生規則s|C→α1βα2替換為s|C→α1s″α，並將產生規則s′|C′→α3βα4替換為s′|C′→α3s″α4，並添加新規則s″|C″→β，來將G約簡為新的上下文相關文法G′。
6.如權利要求1所述的方法，其中，所述應用步驟還包括執行約簡規則的步驟，該約簡規則包括以下步驟(a)將G定義為具有形式為s|C→α1βα2和s′|C′→β的兩個產生規則的容許的上下文相關文法，其中，β的長度至少為2，s|C→α1βα2中的β的上下文也等於上下文C′，並且α1和α2之一不為空；(b)通過將所述產生規則s|C→α1βα2替換為新的產生規則s|C→α1s′α2，來將G約簡為上下文相關文法G′。
7.如權利要求1所述的方法，其中，所述應用步驟還包括執行約簡規則的步驟，該約簡規則包括以下步驟(a)將G定義為容許的上下文相關文法，其中，在給定的上下文C時的兩個變量s和s′表示由G表示的A序列的相同的子串；(b)通過在G的範圍內，當s′的上下文等於C時，將s′的每次出現替換為s，並刪除(C，s′)所對應的產生規則，來將G約簡為新的上下文相關文法G′。
8.如權利要求7所述的方法，其中，所述約簡步驟還包括以下步驟如果所述文法G′是不容許的，則通過將G′的連續替換過程中未涉及到的G′的上下文和變量對所對應的各所述產生規則刪除，來將G′進一步約簡為容許的上下文相關文法G″。
9.一種將原始數據序列x＝x1x2……xn順序地變換為不可約上下文相關文法{Gi}i＝1i的序列的方法，所述原始數據序列包括多個符號並與已知上下文模型相關聯，所述已知上下文模型由可數上下文集合C和下一個上下文函數f給出，可從所述不可約上下文相關文法的序列中遞增地完全恢復所述原始數據序列x，其中，每個上下文相關文法Gi是由產生規則si|Ci→Gi(si|Ci)的集合表示的，所述產生規則是由變量集合S(j1)={s0,s1,...,sji-1}]]>以及上下文和變量對的集合ΩG(Ki，ji)形成的，j1＝1，K1＝1，並且ΩG(K1，j1)＝{(C1，s0)}，所述方法包括以下步驟(a)將序列x＝x1x2……xn解析為t個不重疊的子串{x1，x2…xn2，...，xni-1+1…xn1}，其中n1＝1，n1＝n，並且對於每個1＜i≤t，如果以前未解析的符號的剩餘序列xni-1+1…xn存在最長前綴，則子串xni-1+1…xni(用βi表示)是所述最長前綴，否則，所述子串就是以前未解析的符號的剩餘序列的第一個符號xni-1+1，其中在上下文為Cni-1+1時，該以前未解析的符號的剩餘序列可以由 給出的變量子集中的變量sj來表示，其中，ΩG(Ki-1，ji-1)是前一個不可約上下文相關文法Gi-1的上下文和變量對的集合；以及(b)根據當前解析的子串i=xni-1+1xni,]]>從所述上下文模型確定的當前上下文Cni-1+1和所述前一個不可約上下文相關文法Gi-1，來為每個x1…xni產生不可約上下文相關文法Gi，其中，G1隻包括一個產生規則{s0|C1→x1}，並且(C1，s0)是初始上下文和變量對。
10.如權利要求9所述的方法，其中，將所述序列x＝x1x2……xn解析為多個不重疊子串{x1，x2…xn2，...，xni-1+1…xn1}的步驟還包括以下步驟(a)對於每個1＜i≤t，確定在時間點ni-1+1的上下文Cni-1+1；(b)判斷在當前上下文Cni-1+1時，剩餘未解析的序列xni-1+1……xn的前綴能否由 給出的變量子集中的變量sj表示，其中，ΩG(Ki-1，ji-1)是所述前一個不可約上下文相關文法Gi-1的上下文和變量對的集合；(c)如果xni-1+1…xni在上下文Cni-1+1時用變量sj表示，則設置當前解析的子串βi等於最長前綴xni-1+1…xni；(d)如果在當前上下文Cni-1+1時，沒有xni-1+1……xn的前綴可以用 給出的變量子集中的變量sj表示，則設置當前解析的子串βi等於xni-1+1，其中，ni＝ni-1+1。
11.如權利要求9所述的方法，其中，根據當前解析的子串i=xni-1+1xni,]]>當前上下文Cni-1+1和所述前一個不可約上下文相關文法Gi-1，為每個xi…xni產生不可約上下文相關文法Gi的步驟還包括以下步驟(a)如果ni-ni-1＞1並且i=xni-1+1xni]]>在上下文Cni-1+1時用sj表示，則將變量sj添加到Gi-1(s0|C1)的右端，以產生容許的上下文相關文法Gi-1′；(b)如果ni-ni-1＝1，則將符號xni-1+1添加到Gi-1(s0|C1)的右端，以產生容許的上下文相關文法Gi-1′；以及(c)將約簡規則集合應用於Gi-1′，從而為每個xi…xni產生不可約上下文相關文法Gi。
12.如權利要求11所述的方法，其中，所述將約簡規則集合應用於Gi-1′的步驟還包括以下步驟(a)如果所述容許的上下文相關文法Gi-2′是可約的，則將與第(i-i)個解析的子串相關聯的文法約簡比特I(i-1)設置等於1，如果Gi-2′是不可約的，則將I(i-1)設置為0；(b)將α定義為Gi-1(s0|C1)的最後一個符號；(c)將C定義為Gi-1(s0|C1)中的α的上下文；(d)將β定義為Gi-1′(s0|C1)的最後一個符號；(e)判斷αβ在上下文C時是否出現在Gi-1′的範圍內的兩個不重疊的位置；(f)如果αβ在上下文C時沒有出現在Gi-1′的範圍內的兩個不重疊的位置，則設置Gi等於Gi-1′；(g)如果I(i-1)＝0並且αβ在相同的上下文C時在Gi-1′(s0|C1)中的兩個不重疊的位置重複自身，則對Gi-1′應用第一約簡規則，以產生Gi，其中，所述第一約簡規則包括以下步驟(1)將G定義為具有形式為s|C^123]]>的產生規則的容許的上下文相關文法，其中，γ的長度至少為2，並且γ在這兩個位置的主要上下文等於相同的上下文C′；(2)定義新的產生規則s′|C′→γ，其中，(C′，s′)是G的域中沒有的上下文和變量的新對；以及(3)通過將G的產生規則s|C^123]]>替換為s|C^1s2s3,]]>並添加所述產生規則s′|C′→γ，來將G約簡為新的上下文相關文法 所得的文法 具有上下文和變量的新對(C′，s′)，且表示與G等價的數據序列x；(h)如果I(i-1)＝0並且αβ在相同的上下文C時在Gi-1′而非Gi-1′(s0|C1)的範圍內的兩個不重疊的位置重複自身，則對Gi-1′應用第二約簡規則，以產生Gi，其中，所述第二約簡規則包括以下步驟(1)將G定義為具有形式為s|C^12]]>和s′|C′→α3γα4的兩個產生規則的容許的上下文相關文法，其中，γ的長度至少為2，γ在這兩個位置的主要上下文等於相同的上下文C″，α1和α2之一不為空，並且α3和α4之一不為空；(2)定義新的產生規則s″|C″→γ，其中，(C″，s″)是G的域中沒有的上下文和變量的新對；以及(3)通過將產生規則s|C^12]]>替換為s|C^1s2,]]>並將所述產生規則s′|C′→α3γα4替換為s′|C′→α3s″α4，並添加新規則s″|C″→γ，來將G約簡為新的上下文相關文法 (i)如果I(i-1)＝1並且αβ在相同的上下文C時在Gi-1′的範圍內的兩個不重疊的位置重複自身，則應用所述第一約簡規則和第二約簡規則之一，然後應用第三約簡規則，其中，所述第三約簡規則包括以下步驟(1)將s定義為在G的範圍內在某上下文 時出現一次的容許的上下文相關文法G的變量；(2)定義產生規則s′|C′→α1sβ1，其中，在上下文 時s出現在一組符號的右邊；(3)定義與對 相對應的產生規則s|C^,]]>並通過從G中刪除所述產生規則s|C^,]]>並將所述產生規則s′|C′→α1sβ1替換為所述產生規則s′|C′→α1γβ1，來將G約簡為容許的上下文相關文法G，所得的容許的上下文相關文注 和G表示等價的數據序列。
13.如權利要求12所述的方法，其中，所述判斷步驟(e)還包括以下步驟(a)對於除初始對(C1，s0)之外的每對(C^,)G(Ki-1,ji-1),]]>定義兩個列表 和 其中，所述列表 包括具有如下性質的所有符號η∈A∪S(ji-1)(1)在上下文 時，模式γη出現在Gi-1的範圍內；(2)模式γη不是Gi-1(s0|C1)的最後兩個符號；以及(3)沒有Gi-1的變量sj，使得 等於γη，並且，其中所述列表 包括具有性質(1)和(2)的所有符號η∈A∪S(ji-1)；(b)如果β出現在列表L1(α|C)中，則表示在上下文C時，αβ出現在Gi-1′的範圍內的兩個不重疊的位置。
14.一種通過使用自適應上下文相關算術編碼來編碼原始數據序列以編碼不可約上下文相關文法的方法，所述原始數據序列包括多個符號且與由可數上下文集合C和下一個上下文函數f給出的已知上下文模型相關聯，根據所述不可約上下文相關文法可完全恢復所述原始數據序列，其中，所述不可約上下文相關文法是由產生規則集合表示的，所述產生規則是由表示所述數據序列中的不重疊重複模式和上下文的變量和上下文對的集合形成的，所述方法包括以下步驟(a)將所述數據序列變換為所述不可約上下文相關文法，可從該不可約上下文相關文法中完全恢復所述原始數據序列；(b)將所述不可約上下文相關文法轉換為其分類形式，產生分類的不可約上下文相關文法；(c)從所述分類的不可約上下文相關文法構造一個產生的序列；以及(d)使用具有動態字母表的自適應上下文相關算術編碼，對該產生的序列進行編碼。
15.如權利要求14所述的方法，其中，所述變換步驟(a)還包括以下步驟(1)從所述序列中解析子串，其中，如果所述序列中以前未解析的符號的字符串的最長前綴存在，則所述子串是所述最長前綴，否則，所述子串是所述序列以前未解析的符號的字符串的第一個符號，其中，在當前時間點的上下文時，所述序列中以前未解析的符號的字符串可用前一個不可約上下文相關文法的變量集合中的一變量，而不是變量和上下文對的集合的初始對中的初始變量來表示；(2)根據所述子串、當前上下文和所述前一個不可約上下文相關文法，來產生容許的上下文相關文法；(3)將至少一個約簡規則集合應用於所述容許的上下文相關文法，以產生新的不可約上下文相關文法；以及(4)重複步驟(1)至(3)，直到所述序列的所有符號被處理，並獲取了所期望的最終不可約上下文相關文法。
16.如權利要求14所述的方法，其中，如果對於每個合法的上下文C，具有變量集合S(j)＝{s0，s1，…sj-1}以及上下文和變量對的集合ΩG(K，j)的不可約上下文相關文法G是分類形式，則對於任何有意義的i＞0，(C，si)的替換總是按照以下遞歸替換過程發生在(C，si+1)的替換之前(1)令ΩG表示ΩG(K，j)的動態變化的子集，開始時，ΩG為空；(2)設置u(0)＝G(s0|C1)以及i＝0；(3)對於i≥0，從左到右讀取u(i)，將ΩG中沒有的第一對(C，s)替換為G(s|C)，其中，C是由所述上下文模型確定的s的上下文；(4)通過將對(C，s)插入到ΩG來更新ΩG；(5)對於i＝0，1，……，|ΩG(K，j)|-1，重複步驟(3)和(4)，從而使得除(C1，s0)之外的每對(C，s)∈ΩG(K，j)正好被替換為G(s|C)一次；以及所述轉換步驟(b)還包括以下步驟在每個合法的上下文C時，重新命名變量si，從而使得對於重命名的變量，對於任何有意義的i＞0，(C，si)的替換總是按照所述遞歸替換過程發生在(C，si+1)的替換之前。
17.如權利要求14所述的方法，其中，所述構造步驟(c)還包括以下步驟(1)定義具有變量集合S(j)＝{s0，s1，…sj-1}以及上下文和變量對的集合ΩG(K，j)的分類的不可約上下文相關文法G；(2)將ΩG初始化為空集；(3)設置u(0)＝G(s0|C1)以及i＝0；(4)對於i≥0，從左向右讀取u(i)，並將ΩG中沒有的第一對(C，s)替換為[G(s|C)]，其中，C是由上下文模型確定的s的上下文；(5)將對(C，s)插入到ΩG，以更新ΩG；(6)對於i＝0，1，……|ΩG(K，j)|-1，重複步驟(4)和(5)，從而使得除(C1，s0)之外的每對(C，s)∈ΩG(K，j)正好被替換為[G(s|C)]一次，最終序列u(|ΩG(K，j)|-1)是從G產生的序列。
18.如權利要求14所述的方法，其中，所述編碼步驟(d)還包括以下步驟(1)對於任何上下文C，將下一個上下文函數f擴展以包括C＝f(C，[)和C＝f(C，])；(2)將每對(C，α)與計數器c(C，α)相關聯，其中，C是上下文，並且α是符號、變量或括號([或])；(3)如果α是所述原始數據序列中的符號或者是括號([或])，則將c(C，α)初始化為1，否則，將其初始化為0；(4)在其上下文C的情況下，根據被所有滿足c(C，α)≠0的α的所有計數器c(C，α)的和所除的計數器c(C，β)，對所述產生的序列的每個符號β進行編碼；(5)將c(C，β)加1；(6)只要β等於括號]並且與β相對應的合法的括號對是在上下文C′時從所述產生的序列的左邊計數的第i個括號對，則將c(C′，si)從0增加到1，其中，C′是該括號對的左括號[的上下文；(7)確定所述產生的序列中的下一個符號的上下文；以及(8)重複步驟(4)至(7)，直到所述產生的序列中的所有符號都被編碼。
19.一種將原始數據序列x＝x1x2……xn順序地變換為不可約上下文相關文法{Gi}i＝1t的序列，並通過使用自適應上下文相關算術編碼對所述數據序列進行編碼以編碼最終不可約上下文相關文法Gt的方法，其中，所述數據序列x＝x1x2……xn包括多個符號且與已知上下文模型相關聯，所述已知上下文模型由可數上下文集合C和下一個上下文函數f給出，並且每個上下文相關文法Gi是由產生規則si|Ci→Gi(si|Ci)的集合表示的，所述產生規則是由變量集合S(ji)={s0,s1,...,sji-1}]]>和上下文和變量對的集合ΩG(Ki，ji)形成的，j1＝1，K1＝1，並且ΩG(K1，j1)＝{(C1，s0)})，所述方法包括以下步驟(a)將所述序列x＝x1x2……xn解析為t個不重疊的子串{x1，x2…xn2，...，xni-1+1…xni}，其中n1＝1，ni＝n，對於各1＜i≤t，如果以前未解析的符號的剩餘序列xni-1+1…xn的最長前綴存在，則子串xni-1+1…xni(用βi表示)是所述最長前綴，否則，該子串就是以前未解析的符號的剩餘序列的第一個符號xni-1+1，在上下文Cni-1+1時，所述以前未解析的符號的剩餘序列可以用 給出的變量子集中的變量sj來表示，其中，ΩG(Ki-1，ji-1)是前一個不可約上下文相關文法Gi-1的上下文和變量的對的集合；以及(b)根據當前解析的子串i=xni-4+1xni,]]>從所述上下文模型確定的當前上下文Cni-1+1和所述前一個不可約上下文相關文法Gi-1，為每個x1…xni產生不可約上下文相關文法Gi，其中，Gi只包括一個產生規則{s0|C1→x1}，並且(C1，s0)是初始的上下文和變量對；(c)將所述最終不可約上下文相關文法Gt轉換為其分類形式Gls；(d)從所述分類的不可約上下文相關文法Gls，構造一個產生的序列；以及(e)使用具有動態字母表的自適應上下文相關算術編碼，對所述產生的序列進行編碼。
20.一種將數據序列順序地變換為不可約上下文相關文法的序列，並通過使用自適應上下文相關算術編碼對基於每個不可約上下文相關文法的所述數據序列進行編碼的方法，其中，所述數據序列包括多個符號且與已知上下文模型相關聯，所述已知上下文模型由可數上下文集合C和下一個上下文函數f給出，並且每個不可約上下文相關文法是由產生規則集合表示的，所述產生規則是使用表示所述數據序列中不重疊重複模式和上下文的變量和上下文對的集合所形成的，所述方法包括以下步驟(a)從所述序列中解析子串，其中，如果所述序列以前未解析的符號的字符串的最長前綴存在，則所述子串是所述最長前綴，否則，所述子串是所述序列以前未解析的符號的字符串的第一個符號，在當前時間點的上下文時，所述序列以前未解析的符號的字符串可用前一個不可約上下文相關文法的變量的集合中的變量，而不是變量和上下文對的集合的初始對中的初始變量來表示；(b)通過利用所述前一個不可約上下文相關文法的結構並使用自適應上下文相關算術編碼，對所述子串進行編碼；(c)根據所述子串、當前上下文和所述前一個不可約上下文相關文法，產生容許的上下文相關文法；(d)將至少一個產生規則集合應用於所述容許的上下文相關文法，以產生新的不可約上下文相關文法；以及(e)重複步驟(a)至(d)，直到所述序列中的所有符號都被解析和編碼。
21.一種用於將原始數據序列x＝x1x2……xn順序地變換為不可約上下文相關文法{Gi}i＝1i的序列，並通過使用自適應上下文相關算術編碼，基於每個所述不可約上下文相關文法{Gi}i＝1i對所述數據序列進行編碼的方法，其中，所述數據序列x＝x1x2……xn包括多個符號且與已知上下文模型相關聯，所述已知上下文模型是由可數上下文集合C和下一個上下文函數f給出的，並且每個上下文相關文法Gi由產生規則si|Ci→Gi(si|Ci)的集合表示，所述產生規則是由變量集合S(ji)={s0,s1,...,sji-1}]]>和上下文和變量對的集合ΩG(Ki，ji)形成的，j1＝1，K1＝1，並且ΩG(K1，j1)＝{(C1，s0)}，所述方法包括以下步驟(a)將各對(C，α)與兩個計數器c(C，α)和 相關聯，其中，C是上下文，並且α是符號或變量；(b)如果α是所述原始數據序列中的符號，則將c(C，α)和c(C，α)初始化為1，否則，將其初始化為0；(c)對於每個1＜i≤t，從所述序列中解析子串xni-1+1…xni，其中n1＝1，ni＝n，並且對於各1＜i≤t，如果以前未解析的符號的剩餘序列xni-1+1…xn的最長前綴存在，則子串xni-1+1…xni(用βi表示)是所述最長前綴，否則，該子串是以前未解析的符號的剩餘序列的第一個符號xni-1+1，在上下文Cni-1+1時，所述以前未解析的符號的剩餘序列可用 給出的變量子集中的變量sj來表示，其中，ΩG(Ki-1，ji-1)是前一個不可約上下文相關文法Gi-1的上下文和變量的對的集合，並且其中，G1隻包括一個產生規則{s0|C1→x1}，(C1，s0)是初始的上下文和變量對；(d)根據所述前一個不可約上下文相關文法Gi-1、當前子串βi和當前上下文Cni-1+1，產生容許的上下文相關文法Gi-1′；(e)如果所述容許的上下文相關文法Gi-1′是可約的，則設置當前文法約簡比特I(i)為1，如果Gi-1′是不可約的，則設置當前文法約簡比特I(i)為0；(f)使用一階或更高階自適應算術編碼，對所述當前文法約簡比特I(i)進行編碼；(g)使用自適應上下文相關算術編碼，根據所述前一個不可約上下文相關文法Gi-1、文法約簡比特I(i)和I(i-1)以及當前上下文Cni-1+1，對當前子串βi進行編碼；(h)將至少一個約簡規則集合應用於所述容許的上下文相關文法Gi-1′，以產生新的不可約上下文相關文法Gi；以及(i)重複步驟(c)至(h)，直到所述序列x的所有符號都被解析和編碼。
22.如權利要求21所述的方法，其中，所述編碼步驟(g)還包括以下步驟(1)將α定義為Gi-1(s0|C1)的最後一個符號；(2)將 定義為Gi-1(s0|C1)中α的上下文；(3)如果ni-ni-1＞1並且i=xni-1+1xni]]>在上下文Cni-1+1時用sj表示，則將β定義為變量sj；如果ni-ni-1＝1，則將其簡單定義為符號xni-1+1；(4)將 定義為上下文Cni-1+1；(5)對於除初始對(C1，s0)之外的每對(C^,)G(Ki-1,ji-1),]]>定義兩個列表L1(γ|C)和L2(γ|C)，其中，所述列表L1(γ|C)包括具有如下性質的所有符號η∈A∪S(ji-1)a)在上下文C時，模式γη出現在Gi-1的範圍內；b)在上下文C時，模式γη不是Gi-1(s0|C1)的最後兩個符號；c)沒有Gi-1的變量sj，使得Gi-1(sj|C)等於γη，並且，其中所述列表L2(γ|C)包括具有性質a)和b)的所有符號η∈A∪S(ji-1)；(6)如果I(i)＝0，則在其上下文 的情況下，根據被滿足c(C^,)0]]>的所有AS(ji-1)\L2(|C^)]]>的所有計數 的和所除的計數器 對β進行編碼，然後將 加1；(7)如果I(i-1)＝0且I(i)＝1，則在其上下文 的情況下，根據被所有L1(|C^)]]>的所有計數器 的和所除的計數 對β進行編碼，然後將 加1；
23.如權利要求21所述的方法，其中，所述步驟(h)還包括相應地更新列表L1(γ|C)和L2(γ|C)的步驟。
全文摘要
本發明提供了一種無損耗數據壓縮方法，它使用文法變換順序地構造一個貪婪的上下文相關文法的序列，可以從該序列中逐步恢復原始數據序列。使用順序上下文相關方法、改進的順序上下文相關方法和等級式上下文相關方法中的任意一種，對該數據序列進行編碼。
文檔編號H03M7/30GK1682448SQ03821724
公開日2005年10月12日 申請日期2003年7月11日 優先權日2002年7月12日
發明者楊恩輝, 何大可 申請人:斯利普斯特裡姆數據公司