Method for compressed data with reduced dictionary sizes by...

Details Method for compressed data with reduced dictionary sizes by... Method for compressed data with reduced dictionary sizes by...

2008-01-08

2009-10-27

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

C341S050000

Reexamination Certificate

active

07609179

ABSTRACT:
The speed of dictionary based decompression is limited by the cost of accessing random values in the dictionary. If the size of the dictionary can be limited so it fits into cache, decompression is made to be CPU bound rather than memory bound. To achieve this, a value prefix coding scheme is presented, wherein value prefixes are stored in the dictionary to get good compression from small dictionaries. Also presented is an algorithm that determines the optimal entries for a value prefix dictionary. Once the dictionary fits in cache, decompression speed is often limited by the cost of mispredicted branches during Huffman code processing. A novel way is presented to quantize Huffman code lengths to allow code processing to be performed with few instructions, no branches, and very little extra memory. Also presented is an algorithm for code length quantization that produces the optimal assignment of Huffman codes and show that the adverse effect of quantization on the compression ratio is quite small.

REFERENCES:
patent: 5363098 (1994-11-01), Antoshenkov
patent: 6518895 (2003-02-01), Weiss et al.
patent: 6529912 (2003-03-01), Satoh et al.
patent: 7088271 (2006-08-01), Marpe et al.

Affiliated with

Also associated with

Rating

Method for compressed data with reduced dictionary sizes by... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for compressed data with reduced dictionary sizes by..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for compressed data with reduced dictionary sizes by... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4135574