Method for lossless data compression using greedy sequential context-dependent grammar transform

A method of sequentially transforming an original data sequence x=x1x2 . . . xn comprising a plurality of symbols and associated with a known context model given by a countable context set C and a next context function ƒ into a sequence of irreducible context-dependant grammars {Gi}′i=1 from which the original data sequence x can be fully recovered incrementally, wherein each context-dependent grammar Gi is represented by a set of production rules si|C1→Gt(si|C1) formed from a variable set S(ji)={s0,s1, . . . sji−1} and a set ΩG(Ki,ji) of pairs of contexts and variables with j1=1, K1=1, and ΩG(K1,j1)={(C1,s0)}, the method comprising the steps of:

• (a) parsing the sequence x=x1x2 . . . xn into t non-overlapping substrings {x1,x2 . . . xn2, . . . , xni−1+1 . . . xni}, wherein n1=1, nt=n, and for each 1<i≦t, the substring xni−1+1 . . . xnt (denoted by βi) is the longest prefix of the remaining sequence of previously unparsed symbols xni−1+1 . . . xn that can be represented under the context Cni−1+1 by a variable si within a variable subset given by {s:s≠s0&(Cni−1+1,s)∈ΩG(Ki−1,ji−1)} if such a prefix exists, and otherwise the first symbol xni−1+1 of the remaining sequence of previously unparsed symbols, wherein ΩG(Ki−1,ji−1) is the set of pairs of contexts and variables of the previous irreducible context-dependent grammar Gi−1, and (b) generating an irreducible context-dependent grammar Gi for each xi . . . xni based on the current parsed substring βi=xni−1+1 . . . xni, the current context Cni−1+1 determined from the context model, and the previous irreducible context-dependent grammar Gi−1, where G1 consists of only one production rule {s0|C1→x1} and (C1,s0) is the initial context and variable pair.

A method of encoding an original data sequence comprising a plurality of symbols and associated with a known context model given by a countable context set C and a next context function ƒ by using an adaptive context-dependent arithmetic code to encode an irreducible context-dependent grammar from which the original data sequence can be fully recovered, wherein the irreducible context-dependent grammar is represented by a set of production rules which are formed using a set of pairs of variables and contexts representing non-overlapping repeated patterns and contexts in the data sequence, the method comprising the steps of:

• (a) transforming the data sequence into the irreducible context-dependent grammar from which the original data sequence can be fully recovered;
• (b) converting the irreducible context-dependent grammar into its sorted form, yielding a sorted irreducible context-dependent grammar;
• (c) constructing a generated sequence from the sorted irreducible context-dependent grammar;
• and
• (d) encoding the generated sequence using an adaptive context-dependent arithmetic code with dynamic alphabets.

A method of sequentially transforming an original data sequence x=x1x2 . . . xn into a sequence of irreducible context-dependant grammars {Gi}′i=1 and encoding the data sequence by using an adaptive context-dependent arithmetic code to encode the final irreducible context-dependent grammar Gi, wherein the data sequence x=x1x2 . . . xn comprises a plurality of symbols and is associated with a known context model given by a countable context set C and a next context function ƒ, and each context-dependent grammar Gi is represented by a set of production rules si|C1→Gi(si|C1) formed from a variable set S(ji)={s0,s1, . . . sji−1} and a set ΩG(Ki,ji) of pairs of contexts and variables with j1=1, K1=1, and ΩG(K1,j1)={(C1,s0)}, the method comprising the steps of:

• (a) parsing the sequence x=x1x2 . . . xn into t non-overlapping substrings {x1,x2 . . . xn1, . . . , xni−1+1 . . . xnt}, wherein n1=1, nt=n, and for each 1<i≦t, the substring xni−1+1 . . . xni (denoted by βi) is the longest prefix of the remaining sequence of previously unparsed symbols xni−1+1 . . . xn that can be represented under the context Cni−1+1 by a variable sj within a variable subset given by {s:s≠s0&(Cni−1+1,s)∈ΩG(Ki−1,ji−1)} if such a prefix exists, and otherwise the first symbol xni−1+1 of the remaining sequence of previously unparsed symbols, wherein ΩG(Ki−1,ji−1) is the set of pairs of contexts and variables of the previous irreducible context-dependent grammar Gi−1, and
• (b) generating an irreducible context-dependent grammar Gi for each x1 . . . xni based on the current parsed substring βi=xni−1+1 . . . xni, the current context Cni−1+1 determined from the context model, and the previous irreducible context-dependent grammar Gi−1, where G1 consists of only one production rule {s0|C1→x1} and (C1,s0) is the initial context and variable pair;
• (c) converting the final irreducible context-dependent grammar Gi into its sorted form Gts;
• (d) constructing a generated sequence from the sorted irreducible context-dependent grammar Gts;
• and
• (e) encoding the generated sequence using an adaptive context-dependent arithmetic code with dynamic alphabets.

A method of sequentially transforming a data sequence into a sequence of irreducible context-dependent grammars and encoding the data sequence based on each of the irreducible context-dependent grammars by using adaptive context-dependent arithmetic coding, wherein the data sequence comprises a plurality of symbols and is associated with a known context model given by a countable context set C and a next context function ƒ, and each irreducible context-dependent grammar is represented by a set of production rules which are formed using a set of pairs of variables and contexts representing non-overlapping repeated patterns and contexts in the data sequence, the method comprising the steps of:

• (a) parsing a substring from the sequence, wherein the substring is the longest prefix of a string of previously unparsed symbols of the sequence that can be represented, under the context of the current time instant, by a variable within the set of variables of a previous irreducible context-dependent grammar other than the initial variable in the initial pair of the set of pairs of variables and contexts if such a prefix exists, and otherwise a first symbol of the string of the previously unparsed symbols in the sequence;
• (b) encoding the substring by utilizing the structure of the previous irreducible context-dependent grammar and by using adaptive context-dependent arithmetic coding;
• (c) generating an admissible context-dependent grammar based on the substring, the current context, and the previous irreducible context-dependent grammar;
• (d) applying at least one set of reduction rules to the admissible context-dependent grammar to generate a new irreducible context-dependent grammar;
• and
• (e) repeating steps (a) through (d) until all of the symbols of the sequence are parsed and encoded.

A method of sequentially transforming an original data sequence x=x1x2 . . . xn into a sequence of irreducible context-dependant grammars {Gi}′i=1 and encoding the data sequence based on each of the irreducible context-dependent grammars {Gi}′i=1 by using adaptive context-dependent arithmetic coding, wherein the data sequence x=x1x2 . . . xn comprises a plurality of symbols and is associated with a known context model given by a countable context set C and a next context function ƒ, and each context-dependent grammar G1 is represented by a set of production rules si|C1→Gi(si|C1) formed from a variable set S(ji)={s0,s1, . . . sji−1} and a set ΩG(Ki,ji) of pairs of contexts and variables with j1=1, K1=1, and ΩG(K1,j1)={(C1,s0)}, the method comprising the steps of:

• (a) associating each pair (C,α) with two counters c(C,α) and ĉ(C,α), where C is a context and α is a symbol or variable;
• (b) initializing c(C,α) and ĉ(C,α) to be 1 if α is a symbol in the original data sequence, and 0 otherwise;
• (c) parsing, for each 1<i≦t, a substring xni−1+1 . . . xnt from the sequence, wherein n1=1, nt=n, and for each 1<i≦t, the substring xni−1+1 . . . xnt (denoted by βi) is the longest prefix of the remaining sequence of previously unparsed symbols xni−1+1 . . . xn that can be represented under the context Cni−1+1 by a variable sj within a variable subset given by {s:s≠s0&(Cni−1+1,s)∈ΩG(Ki−1,ji−1)} if such a prefix exists, and otherwise the first symbol xni−1+1 of the remaining sequence of previously unparsed symbols, wherein ΩG(Ki−1,ji−1) is the set of pairs of contexts and variables of the previous irreducible context-dependent grammar Gi−1, and wherein G1 consists of only one production rule {s0|C1→x1} with (C1,s0) being the initial context and variable pair;
• (d) generating an admissible context-dependent grammar G′i−1 based on the previous irreducible context-dependent grammar Gi−1, the current substring βi, and the current context Cni−1+1;
• (e) setting the current grammar reduction bit I(i) to be 1 if the admissible context-dependent grammar G′i−1 is reducible, and 0 if G′i−1 is irreducible;
• (f) encoding the current grammar reduction bit I(i) using an adaptive order one or higher order arithmetic code;
• (g) encoding the current substring βi based on the previous irreducible context-dependent grammar Gi−1, grammar reduction bits I(i) and I(i−1), and the current context Cni−1+1 using adaptive context-dependent arithmetic coding;
• (h) applying at least one set of reduction rules to the admissible context-dependent grammar G′i−1 to generate a new irreducible context-dependent grammar Gi;
• and
• (i) repeating steps (c) through (h) until all of the symbols of the sequence x are parsed and encoded.