Efficient coding of small integer sets

The present invention relates generally to data compression. More particularly, this invention relates to methods for efficient coding of small integer sets.

Small sets of integers of distinct sizes (e.g., an 8 bit set and a 16 bit set) arise in a variety of computing applications, such as entropy encoders. However, certain conventional methods put requirements on the values, or the relationship between the values, of the integers themselves, or are not quite as efficient.

In the following description, numerous details are set forth to provide a more thorough explanation of the embodiments of the present invention. It will be apparent, however, to one skilled in the art, that embodiments of the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form, rather than in detail, in order to avoid obscuring embodiments of the present invention.

Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification do not necessarily all refer to the same embodiment.

According to one embodiment, an encoding method is provided to allow an encoder to code integer sequences without regard to the relationship between the values themselves. As a result, a sequence can be coded where some values repeat and where the values are not non-increasing.

FIG. 1 illustrates an exemplary network architecture 100 in which embodiments of the present invention may operate. The network architecture 100 may include a first computing device 105 and a second computing device 110 connected via a network 130. The network may be a public network (e.g., the Internet) or a private network (e.g., a local area network (LAN), intranet, intraweb, etc.).

Each of the first computing device 105 and second computing device 110 may be a desktop computer, notebook computer, cellular phone, personal digital assistant (PDA), or other device capable of processing machine-executable code. Moreover, the first computing device 105 and second computing device 110 may each operate as a client or server in a client-server environment, or as a peer in a peer-to-peer environment. In one embodiment, the first computing device 105 and second computing device 110 each include data 115, an encoder 120, and an input/output unit 125.