Patent ID: 9026427
Filing Date: 2015-05-05
Classification: G06F,H03M

Abstract:
1. A computer-implemented method for generating side information for grammar-based data compression systems, the method comprising: obtaining an admissible grammar (G) for an input sequence (A(S constructing a graph representation of the admissible grammar (G), the graph representation including nodes for each variable in the finite set of variables and each terminal symbol in the finite set of terminal symbols, including a root node representing the starting variable (S pruning, from the graph representation, a directed edge having a lowest expansion frequency to generate a pruned graph representation; deriving a pruned grammar (Gi); expanding a starting variable (S storing the side information in a computer memory device; wherein constructing the graph representation of the admissible grammar further comprises determining, for each non-terminal node, a shortest path from the root node to the non-terminal node, and assigning a shortest distance (SD) value to each non-terminal node in accordance with its respective shortest path; wherein, when two or more directed edges are identified as having the same lowest expansion frequency, pruning the directed edge having the lowest expansion frequency comprises applying tie-breaking rules to select the directed edge to prune; wherein the tie-breaking rules comprise at least one of selecting the one of the two or more directed edges with the greatest shortest distance (SD) value, selecting the one of the two or more directed edges leading to a node with the shortest expanded sequence length.