Arrangement for data compression

摘要

For reducing the redundancy ratio of an entity key set, from very high ratios when encoded into conventional I/O code-words, down to a ratio close to zero, a non-redundant number code representation is employed in an encoder/decoder in lieu of a conventional multiple code-word representation, each member of the number code representing a member of the entity key set. Such a number code encoder/decoder may hold in store and provide access to an entity key set representing a set of 65535 different textual or lexical words, thereby using a 16 bit fixed length number code. Code-words representing such code numbers would require 16 bits of storage each if being held in store, however, such code numbers are produced using two alternative methods, (i) as relative address values of individual storage locations within a string of storage locations, e.g., a string of 8 bit byte locations, or (ii) as marked bit counts within a bit map representing the stored set. An embodiment using a byte string representation would require just a little more than 8 bits of storage for each entity key, while an embodiment using the bit map representation would require just a little more than 1 bit of storage for each entity key. These extreme values are achieved for entity key sets having low redundancy ratios prior to redundancy reduction. In many applications, the degree of compression may be maximized by combining the two types of representation, using the bit mapping technique in those parts of the system where the redundancy ratio is lowest. To enable a compressed representation of files within a file handling system, for example, the 16 bit code-words mentioned above may be applied to represent repeatedly occurring file segments for compact file storage as well as for fast file transfer. Provided the relative frequencies of occurrence can be statistically determined for the different code-words, a variable length type of code may be designed to further reduce average code length. The well-known Huffman code is an optimum code for this purpose.