Patent ID: 7028042

Claim:
A a device comprising a computer comprising means for carrying out a method for forming a maximal tree for compressing information comprising symbols, the method comprising: searching statistical data of different symbols from training data; forming a table comprising rows including strings having a first end and a second end, wherein a special symbol of the training data is at the first end of each string, a remaining portion of each string comprises a minimal number of preceding symbols in the training data to make a context for each special symbol; assigning probabilities to the symbols that have not yet occurred at context s by using the following equation: P ^ i ❘ s = ( m + 1 / 2 ( n s + 1 ) ⁢ ( d - m ) if ⁢ ⁢ 0 < m < d / 2 ⁢ ⁢ and ⁢ ⁢ n s > 1 d - m n s ⁡ ( d - m ) = 1 n s if ⁢ ⁢ d / 2 ≤ m < d 0 if ⁢ ⁢ m = d 1 / d if ⁢ ⁢ n s = 1 , in which d is the number of symbols in the alphabet, and m is the number of distinct symbols among the n s occurrences of symbols at context s; and sorting the contexts in lexical order with priority on the first end.