Patent ID: 8487791

Claim:
A method for encoding of an input sequence of symbols using a processor, the symbols belonging to a finite alphabet, the method comprising: for each symbol in the input sequence, assigning, with the processor, the symbol to one of N subsequences of symbols based on an estimated probability given by a context model; merging, using the processor, a first subsequence of symbols with a second subsequence of symbols to create a merged subsequence, thereby reducing the N subsequences of symbols to d subsequences, wherein merging includes determining an overhead associated with the first subsequence of symbols, wherein the first subsequence of symbols is associated with a first estimated probability, calculating a ratio of the overhead to the number of symbols in the first subsequence and determining that the ratio is greater than a relative entropy between the first subsequence of symbols and the second subsequence of symbols, wherein the second subsequence of symbols is associated with a second estimated probability, and associating the merged subsequence with the second estimated probability, encoding the d subsequences in parallel by using d respective entropy coders to generate d respective encoded subsequences; and outputting a bitstream, wherein the bitstream includes the d encoded subsequences and information for locating each of the d encoded subsequences.