Patent ID: 7274671

Claim:
A method of encoding symbols, including ordering a set of symbols in a string, wherein said step of ordering includes performing one or more of a Burrows-Wheeler transform and a move-to-front transform; associating each symbol included in said set of symbols with a context, said context including a prefix; generating a prediction table for said prefix that is responsive to said set of symbols; generating a tree responsive to said prediction table, wherein said tree includes a set of nodes, used in the bitwise encoding of said set of symbols; selecting a partition bit associated with a select node included in said set of nodes, wherein said partition bit corresponds to a digit in a binary representation of said set of symbols; partitioning said set of symbols present at said select node based upon a value of said selected partition bit into two down-linked nodes, starting from a root node including said set of symbols with their probabilities and ending with a leaf node, wherein said leaf node includes a single symbol and a probability responsive to said symbol, wherein said down-linked nodes, said root node and said one or more leaf nodes are included in said set of nodes and said single symbol is included in said set of symbols; assigning a probability for each branch in said tree, wherein said probability for a branch that corresponds to Zero group from a node with at least one Hit symbol in the Zero group and at least one Hit symbol in One group is equal to a sum of probabilities of Hit symbols in the Zero group, said probability for a branch that corresponds to the One group from a node with at least one Hit symbol in the Zero group and at least one Hit symbol in the One group is equal to a sum of probabilities of Hit symbols in the One group, said probability for a branch that corresponds to the Zero group from a node in which at least one of the Zero group and the One group is without any Hit symbols is equal to a sum of probabilities of all symbols in the Zero group, and said probability for a branch that corresponds to the One group from a node in which at least one of the One group and the Zero group is without any Hit symbols is equal to a sum of probabilities of all symbols in the One group; and encoding said symbols such that said step of encoding is responsive to the probabilities on said branches that form the path from said root node to said node associated with said symbol; wherein said encoding provides a lossless compression of said symbols for efficient storage and transmission.