Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Reexamination Certificate
1999-08-20
2002-07-02
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
Reexamination Certificate
active
06414610
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of data compression, data decompression, data adaption to a data environment, and to the field of creating, managing and optimizing a data structure and its contents. The invention may also have uses in the fields of data recognition and artificial intelligence.
BACKGROUND OF THE INVENTION
Data compressors read an input stream of symbols and after reading an input symbol or group of input symbols append one or more output codes (“compression code words”) to an output stream (“compressed stream”). The output code or group of output codes represent the input symbol or group of input symbols.
An output code may or may not have the same bit pattern as the last-read input symbol. The quantity of input symbols in an input stream may or may not equal the quantity of output codes in a corresponding compressed stream. When the quantity of bits in a compressed stream is less than the quantity of bits in the corresponding input stream compression is achieved. In a given instance, a compressor may or may not achieve compression.
A decompressor reads a compressed stream and after reading one or more codes in a compressed stream transmits a symbol or group of symbols to an output stream (“decompressed stream”). In lossless compression, the bit pattern of a decompressed stream equals the bit pattern of the original input symbol stream.
If the quantity of codes in a compressed stream equals the quantity of symbols in the corresponding input stream, compression is achieved when the average bit length of output codes is less than the average bit length of input symbols. Output codes may be of invariant or varying bit length and the same goes for input symbols.
If the quantity of codes in a compressed stream does not equal the quantity of symbols in the corresponding input symbol stream, compression is achieved when the quantity of bits in the compressed stream is less than the quantity of bits in the input symbol stream. In such a case there may be more or fewer codes than symbols, and in general there are fewer.
Some compression-decompression (“codec”) systems compress contiguous repetitions of a repetitions. Other codec apparatus does not encode contiguous repetitions of a symbol but assigns to each symbol a code of bit-length inversely proportional to the frequency of occurrence or anticipated frequency of occurrence of the symbol in the input symbol stream. A further type of codec system builds a dictionary of repeated groups of symbols previously found in the present input stream, and where a further group of symbols in the input symbol stream matches to a group of symbols in the dictionary, the dictionary index of that symbol group or its location in the earlier part of the input stream is output as the compression code word. The rules used to compress an input symbol stream and decompress a respective compressed stream are often referred to as a “compression model”.
Codec systems and apparatus may be further characterized as static and adaptive, and static systems use a compression model which is invariant during a compression session and in adaptive systems the model is dynamically modified by the compressor as a function of the symbols encountered so far in the current input symbol stream. Adaptive systems may provide better compression than static systems but not necessarily at lower cost.
For example, when codec systems were first used in computers, computer processing time was very expensive and dictionary-based compression systems typically stored dictionaries for static re-use with later input symbol streams. Today, computer power is much cheaper, and now, typically, adaptive codec systems build dictionaries separately from each input stream which are then discarded after decompression and sometimes after compression. In some cases a dictionary is implicitly embedded in a compressed stream, and in other cases one is transmitted as a header to the transmission of the compressed stream to which it relates.
The objects of codec systems are reduction of information storage space, reduction of information transmission time, and consequent reduction of information processing cost.
Codec systems now common in personal computing may achieve these objectives, increasing available disk space and decreasing data transmission time from disk surface to application program. Furthermore, while digital images typically occupy more storage space than their analog couterparts, compressed digital images may occupy less space and achieve shorter transmission times, and this has important implications in digital storage and transmission over telephone links of motion pictures, which are a sequence of still images.
In order to achieve acceptance in a market place, a codec system typically must meet certain standards compared to its competitors. It should have good compression and decompression speeds, which are a function of the times required for compression and decompression. It should have a high compression ratio, which is a measure of how much space or transmission time is saved as a consequence of compression. It should be capable of adapting to different data environments, which means taking into account changes in the general qualities of data previously received, and increasing speed and compression ratio accordingly. And a lossless codec system must be reversible, which means that the bit pattern of a decompressed stream must be identical to the bit pattern of the respective input symbol stream.
Prior codec systems exist which exhibit the characteristics mentioned above, however, prior dictionary-based codec systems typically build a dictionary in respect of a current input stream which might be one file or one archive or one session, and discard the dictionary after the respective compressed stream is decompressed or even after compression. This has the disadvantage of failing to compress groups of symbols which occur infrequently in the current input stream but which are commonly repeated in input streams in general.
Furthermore, such methods have the disadvantage of failing to compress groups of symbols which typically occur infrequently in input streams in general but which typically do occur in input streams, and when a number of input streams are considered together as a block, do occur frequently within a block.
Moreover, because the adaptivity of prior codec systems typically applies in respect of a current input stream, such systems cannot optimize compression in a network environment where there are many input symbol streams, and where optimization requires identifying and adapting to repeated symbol groups amongst the network traffic as a whole, and retaining and adapting to such information over time.
In addition, prior lossless codec systems typically encode all information in an input symbol stream into a compressed stream or compressed stream plus compression header, and transmit all such information together. Such transmissions contain the entire information content of the original input symbol stream. If the transmission is intercepted and the codec algorithms known, guessed or discovered then the intercepted transmission may be decompressed and the original symbol stream recovered. This is not ideal in today's sensitive business world. It would be better that some information in an original stream were not transmitted in the corresponding compressed stream. This would partly or completely prevent unauthorized decompression where only the compressed stream is in the possession of an interceptor. Were such absent information to change in character and quantity in an unpredictable way over time, and were such changes to be unique both in content and in manner of change to a given network, this would be even more advantageous in a competitive commercial world.
It is held that to store, update and re-use a dictionary would render a codec system uncompetitive, as stored dictionary entries would not be typical of input streams in general and the average compression ratio would suffer, and if the stored dictionary entr
Killworth, Gottman Hagan & Schaeff, L.L.P.
Young Brian
LandOfFree
Data compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2856401