Data compression/coding method and device for implementing said method

Claim 1

An improved coding method for adaptively encoding a flow of data symbols x(t)=x 1 , x 2 , . . . , x t taken within a "d" long symbol family, into a compressed bit string c(s), said method including so-called modelling operations whereby the number of times or counts each symbol of the flow occurs, is collected in a tree architecture denoting past symbols of the flow considered in a predefined order according to a reordering context function f(t), said tree including at least one node (root) from which tree branches might be derived, said method being characterized by: providing each node with: "d" symbol counters respectively assigned to each symbol of the family and to be selectively incremented according symbol occurrences within the flow being currently processed ; a Relative Efficiency Counter (REC) to store the considered node efficiency, i.e. so-called difference of coding length, to coding versus parent node ; reading sequentially the flow of symbols ; searching for each currently considered symbol xt the optimal coding node, by climbing the tree and visiting successive nodes, based on said predefined order consideration, and up to an optimal coding node being the first decreasing REC node preceding a node with an increasing REC ; coding x t by feeding a so-called arithmetic coding device with the optimal node counts ; updating the visited node counts and extending the tree from the coding node.

Claim 13

A device for adaptively encoding a flow of symbols x(t)=x 1 , x 2 , . . . , x t individually taken within a "d" long symbol family, into a compressed bit string c(s), said device including a so-called Modelling Unit for performing modelling operations whereby the number of times each symbol of the considered flow of symbols occurs, is collected in a tree architecture denoting past symbols of the flow considered in a predetermined order according to a reordering context function f(t), said tree including at least one node (root) from which tree branches would be derived while feeding the successive symbols x t , said Modelling Unit feeding an Encoding Unit using so-called arithmetic coding techniques, said device being characterized in that said Modelling Unit includes: scheduler means for sequentially inputting the current symbol x t to be encoded ; Model Managing means sensitive to said scheduler means and including: means for assigning each generated tree node with "d" individual counting means and a so-called Relative Efficiency Counter (REC) ; testing means for testing existing tree architecture versus current symbol x t , starting with the root node and visiting selected nodes ; optimal coding node detection means sensitive to said testing means for detecting a so-called optimal coding node based on node REC variation testing.

Claim 14

A device for adaptively encoding a flow of symbols x(t)=x 1 , x 2 , . . . , x t individually taken within a "d" long symbol family, into a compressed bit string c(s), said device including a so-called Modelling Unit for performing modelling operations whereby the number of times each symbol of the considered flow of symbols occurs, is collected in a tree architecture denoting past symbols of the flow considered in a predetermined order according to a reordering context function f(t), said tree including at least one node (root) from which tree branches would be derived while feeding the successive symbols x t , said Modelling Unit feeding an Encoding Unit using so-called arithmetic coding techniques, said device being characterized in that said Modelling Unit includes: scheduler means for sequentially inputting the current symbol x t to be encoded ; Model Managing means sensitive to said scheduler means and including: means for assigning each generated tree node with "d" individual counting means and a so-called Relative Efficiency Counter (REC) ; testing means for testing existing tree architecture versus current symbol x t , starting with the root node and visiting selected nodes ; optimal coding node detection means sensitive to said testing means for detecting a so-called optimal coding node based on node REC variation testing.