Data compression and decompression system

Claim 2

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string units and which do not occur in the stored string; c. searching the stored string for the presence of a plurality of patterns of contiguous string units which patterns are repeated in the string, and identifying such repeated patterns; d. replacing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; e. storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step; and f. storing in the memory a PCORD table containing one pattern from each plurality of identical patterns which have been replaced by a Type 1 code.

Claim 3

Method as in claim 1 including computing and storing in the memory a savings ratio indicative of the saving in the length of the stored string achieved through replacing by a Type 1 code string pattern identical to patterns stored in the PCORD table to thereby associate a savings ratio with each pattern stored in the PCORD table.

Claim 4

Method as in claim 2 including: defining a maximum value for the number of patterns that can be stored in the PCORD table; testing before storing a pattern in the PCORD table if the PCORD table is full; if the PCORD table is full, testing if the savings ratio of the pattern to be stored in the PCORD table is more favorable than the least favorable savings ratio of the patterns already in the PCORD table; and, if the answer is yes, removing the pattern with the least favorable savings ratio from the PCORD table and storing therein the pattern with the more favorable savings ratio.

Claim 5

Method of utilizing a digital computer having memory and control sections to decompress a string compressed by the method of claim 1 comprising: a. storing the compressed string an the decompression information in the memory; b. identifying from the decompression information a Type 2 code and the pattern replaced by it; c. locating in the compressed string Type 2 codes identical to the Type 2 code identified in the preceding step; and d. replacing each Type 2 code located in the preceding step by the pattern identified in the identifying step.

Claim 6

Method of utilizing a digital computer system including memory and control Sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string units and which do not occur in the stored string; c. storing in a PCORD table in the memory a list of PCORD patterns each composed of a plurality of units of the same format as the units of the stored string; d. searching the stored string for a plurality of patterns each composed of contiguous units and each identical to a PCORD pattern; e. identifying such patterns for replacement by Type 1 codes; f. replacing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; and g. storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step.

Claim 7

Method of utilizing a digital computer system including memory and control Sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string units and which do not occur in the stored string; c. storing in a PCORD table in the memory a list of PCORD patterns each composed of a plurality of units of the same format as the units of the stored string; d. searching the stored string for a plurality of patterns each composed of contiguous units and each identical to a PCORD pattern; e. identifying such patterns for replacement by Type 1 codes; f. replacing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; and g. storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step.

Claim 8

Method as in claim 5 including defining prior to the searching step if the stored string is to be subjected to slow mode compression or to a fast mode compression, and - if slow mode compression is defined - searching in the searching step for a plurality of patterns each composed of contiguous units and identifying such patterns for replacement by Type 1 codes without reference to the PCORD patterns stored in the PCORD table, but - if fast mode compression is defined - searching in the searching step only for repeating patterns identical to PCORD patterns from the PCORD table.

Claim 9

Method of utilizing a digital computer system including memory and control sections comprising the steps of storing in the memory a string comprising a set of multibit information units; identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string units and which do not occur in the stored string; searching the stored string for the presence of a plurality of patterns of contiguous string units which patterns are repeated in the string, and identifying such repeated patterns; replacing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step; including in said identifying and storing step the substep of identifying and storing in the LEXICON table Type 2 codes defined as units which are of the same format as the stored string units and which occur in the stored string at least a preselected number of times, and including the additional steps of: searching the stored string for string units identical to Type 2 codes stored in the LEXICON portion of the memory in the preceding step; constructing and storing in the memory a bit map identifying the locations in the stored string of units identical to a Type 2 code and occurring at least a preselected number of times in the string; removing from the string the units identified in the preceding step; and storing in the memory decompression information associated with the string and comprising the bit map and one of the removed string units.

Claim 10

Method of utilizing a digital computer system including memory and control sections comprising the steps of storing in the memory a string comprising a set of multibit information units; identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string units and which do not occur in the stored string; searching the stored string for the presence of a plurality of patterns of contiguous string units which patterns are repeated in the string, and identifying such repeated patterns; replacing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step; including in said identifying and storing step the substep of identifying and storing in the LEXICON table Type 2 codes defined as units which are of the same format as the stored string units and which occur in the stored string at least a preselected number of times, and including the additional steps of: searching the stored string for string units identical to Type 2 codes stored in the LEXICON portion of the memory in the preceding step; constructing and storing in the memory a bit map identifying the locations in the stored string of units identical to a Type 2 code and occurring at least a preselected number of times in the string; removing from the string the units identified in the preceding step; and storing in the memory decompression information associated with the string and comprising the bit map and one of the removed string units.

Claim 11

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string; units and which do not occur in the stored string; c. searching the stored string for the presence of a plurality of patterns of contiguous string units which patterns are repeated in the string, and identifying such repeated patterns; d. replaCing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; and e. storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step; f. storing in the memory a PCORD table containing preselected Type 2 codes each of the same format as the units of the stored string; g. searching the stored string for units which are identical to a Type 2 code and which occur in the string at least a preselected number of times; h. removing from the string units identified in the preceding step; i. constructing a bit map identifying the locations of the removed units; and j. storing in the memory decompression information associated with the string and comprising the bit map and one of the removed string units.

Claim 12

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in the memory a LEXICON table comprising Type 1 codes defined as units which are of the same format as the stored string; units and which do not occur in the stored string; c. searching the stored string for the presence of a plurality of patterns of contiguous string units which patterns are repeated in the string, and identifying such repeated patterns; d. replaCing each of the patterns of a plurality of repeated patterns identified in the preceding step by a unique Type 1 code from the LEXICON table; and e. storing in the memory decompression information associated with the string and defining the replacement carried out in the preceding step; f. storing in the memory a PCORD table containing preselected Type 2 codes each of the same format as the units of the stored string; g. searching the stored string for units which are identical to a Type 2 code and which occur in the string at least a preselected number of times; h. removing from the string units identified in the preceding step; i. constructing a bit map identifying the locations of the removed units; and j. storing in the memory decompression information associated with the string and comprising the bit map and one of the removed string units.

Claim 13

Method as in claim 8 including: defining prior to the step of searching the stored string for units identical to Type 2 codes if the stored string is to be subjected to fast mode compression or to slow mode compression; if slow mode compression is defined identifying and storing in said identifying and storing step in the LEXICON table Type 2 codes defined as identical in format with the units of the stored string and occurring in the string at least a preselected number of times, searching the stored string for string units identical to a Type 2 code from the LEXICON table of the memory and occurring at least a preselected number of times in the stored string, and then proceeding to the bit map constructing step without recourse to the table of Type 2 codes; but if fast mode compression is defined, then searching the stored string for units identical to Type 2 codes from the PCORD table of Type 2 codes without recourse to the LEXICON portion of the memory.

Claim 14

Method of utilizing a digital computer having memory and control sections to decompress a string compressed by the method of claim 8 comprising the steps of: a. storing the compressed string and the decompression information associated with the string in the memory; b. identifying from the decompression information a Type 1 code and the pattern replaced by it; c. locating in the compressed string Type 1 codes identical to the Type 1 code identified in the preceding step; d. replacing each Type 1 code located in the preceding step by the pattern identified in step b; e. identifying from the decompression information a bit map and one of the string units removed in conjunction with constructing the bit map; and f. storing the removed string unit in the places in the string identified by the bit map and expanding the string accordingly.

Claim 15

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. storing in a PCORD table in the memory at least one PCORD pattern composed of a plurality of units which are of the same format as the units of the stored string; c. searching the stored string for the presence of a plurality of patterns each composed of contiguous string units and each identical to a PCORD pattern, and identifying such string patterns if any are found; and d. replacing each of the string patterns identified in the preceding step by a Type 1 code defined as a unit which is of the same format as the string units but which does not occur in the stored string.

Claim 16

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. storing in a PCORD table in the memory at least one PCORD pattern composed of a plurality of units which are of the same format as the units of the stored string; c. searching the stored string for the presence of a plurality of patterns each composed of contiguous string units and each identical to a PCORD pattern, and identifying such string patterns if any are found; and d. replacing each of the string patterns identified in the preceding step by a Type 1 code defined as a unit which is of the same format as the string units but which does not occur in the stored string.

Claim 17

Method of utilizing a digital computer having memory and control sections to decompress a string compressed by the method of claim 11 comprising the steps of: a. identifying a Type 1 code which has replaced a pattern and the pattern replaced by the code; b. replacing each Type 1 code identical to the identified code and occurring in the striNg by the pattern identified in the preceding step; and c. expanding the string by a number of units equal to the difference between the number of units in the replaced patterns and the number of Type 1 codes which have been replaced by patterns.

Claim 18

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in a LEXICON table in the memory Type 2 codes defined as units which are of the same format as the stored string units and which occur in the stored string at least a preselected number of times; c. searching the stored string for units identical to a Type 2 code and identifying the locations in the string of such identical units; d. constructing and storing in the memory a bit map identifying the locations in the stored string of units identified in the preceding step; e. removing from the string the identified units; and f. storing in the memory decompression information associated with the string and comprising the bit map and one of the removed string units.

Claim 19

Method of utilizing a digital computer system including memory and control sections comprising the steps of: a. storing in the memory a string comprising a set of multibit information units; b. identifying and storing in a LEXICON table in the memory Type 2 codes defined as units which are of the same format as the stored string units and which occur in the stored string at least a preselected number of times; c. searching the stored string for units identical to a Type 2 code and identifying the locations in the string of such identical units; d. constructing and storing in the memory a bit map identifying the locations in the stored string of units identified in the preceding step; e. removing from the string the identified units; and f. storing in the memory decompression information associated with the string and comprising the bit map and one of the removed string units.

Claim 20

Method of utilizing a digital computer having memory and control sections to decompress a string compressed by the method of claim 13 comprising the steps of: a. storing the compressed string and the decompression information in the memory; b. identifying from the decompression information a bit map and a string unit removed in conjunction with constructing the bit map; and c. inserting the string unit identified in the preceding step in the locations in the string identified by the bit map and expanding the string accordingly.

Claim 21

Method of utilizing a computer system including memory and control sections comprising the steps of: a. storing in the memory a string composed of a number of multibit information units; b. storing in a PCORD table in the memory Type 2 codes defined as units which are of the same format as the stored string units; c. searching the stored string for units which are identical to a Type 2 code from the PCORD table and which occur at least a pre-selected number of times, and identifying such units if any are found; d. constructing a bit map identifying the locations in the stored string of units identified in the preceding step; and e. removing from the string the identified units and storing in the memory together with the string the bit map and one of the removed string units.

Claim 22

Method of utilizing a computer system including memory and control sections comprising the steps of: a. storing in the memory a string composed of a number of multibit information units; b. storing in a PCORD table in the memory Type 2 codes defined as units which are of the same format as the stored string units; c. searching the stored string for units which are identical to a Type 2 code from the PCORD table and which occur at least a pre-selected number of times, and identifying such units if any are found; d. constructing a bit map identifying the locations in the stored string of units identified in the preceding step; and e. removing from the string the identified units and storing in the memory together with the string the bit map and one of the removed string units.

Claim 23

Method of utilizing a digital computer having byte-oriented memory and control sections to compress information supplied in the form of a string comprising a set of bytes of information bits, comprising the steps of: a. using the value of each byte of the string to address a 256byte table in which each byte address corresponds to a unique one of the 256 possible bit configurations of a byte and each byte address contains a count of the number of times the byte address has been addressed; b. storing an indication of the address of each byte address of the 256 byte table that has not been addressed in the course of step (a) in a LEXICON table to compile thereby a set of Type 1 codes which are bytes that do not occur in the string; c. detecting the occurrence in the string of a group of non-overlapping patterns, if any, of R contiguous bytes (R is an integer greater than 1) which patterns are identical with each other; d. replacing each of the patterns detected in the course of step c. with an identical Type 1 code selected from available Type 1 codes in the LEXICON table and compressing the string to eliminate the space vacated because of the difference in length between each such replaced pattern of R bytes and the one byte Type 1 code replacing it; e. associating with the string decompression information comprising the Type 1 code used in the course of step d and one of the replaced patterns of R bytes; f. changing the value of R and repeating steps c through e for as long as both i the combined length of the Type 1 codes used as pattern replacements and the decompression information is less than the combined length of the replaced patterns and ii. previously unused Type 1 codes are available in the LEXICON table; and g. storing a pattern from each group of patterns of R bytes which has been deleted from the string in a PCORD table.

Claim 24

Method of utilizing a digital computer having byte-oriented memory and control sections to compress information supplied in the form of a string comprising a set of bytes of information bits, comprising the steps of: a. using the value of each byte of the string to address a 256byte table in which each byte address corresponds to a unique one of the 256 possible bit configurations of a byte and each byte address contains a count of the number of times the byte address has been addressed; b. storing an indication of the address of each byte address of the 256 byte table that has not been addressed in the course of step (a) in a LEXICON table to compile thereby a set of Type 1 codes which are bytes that do not occur in the string; c. detecting the occurrence in the string of a group of non-overlapping patterns, if any, of R contiguous bytes (R is an integer greater than 1) which patterns are identical with each other; d. replacing each of the patterns detected in the course of step c. with an identical Type 1 code selected from available Type 1 codes in the LEXICON table and compressing the string to eliminate the space vacated because of the difference in length between each such replaced pattern of R bytes and the one byte Type 1 code replacing it; e. associating with the string decompression information comprising the Type 1 code used in the course of step d and one of the replaced patterns of R bytes; f. changing the value of R and repeating steps c through e for as long as both i the combined length of the Type 1 codes used as pattern replacements and the decompression information is less than the combined length of the replaced patterns and ii. previously unused Type 1 codes are available in the LEXICON table; and g. storing a pattern from each group of patterns of R bytes which has been deleted from the string in a PCORD table.

Claim 25

Method as in claim 16 including storing a pattern from each group of patterns of R bytes which has been deleted from the string in a PCORD TABLE; associating with each pattern in the PCORD table a savings ratio indicative of the degree of compression of the string resulting from the deletion of said pattern from the string.

Claim 26

Method as in claim 17 including: limiting the capacity of the PCORD table; checking whether the PCORD table is full when an attempt is made to include therein a new pattern; and, in case the PCORD table is full, storing the new pattern in the PCORD table and deleting from the PCORD table the pattern having the lowest associated savings ratio, but only if said lowest savings ratio is lower than the savings ratio of the new pattern.

Claim 27

Method of utilizing a digital computer having memory and control sections to decompress a string compressed by the method of claim 16 comprising the steps of: a. storing the compressed string and the decompression information in the memory; b. identifying from the decompression information a Type 1 code and the pattern of R bytes replaced by it; c. locating in the compressed string Type 1 codes identical to the Type 1 code identified in the preceding step; d. replacing each Type 1 code located in the preceding step by the pattern of R contiguous bytes identified in step b; and e. expanding the string by a number of bytes equal to the difference between the number of bytes of the patterns replacing the Type 1 codes and the number of replaced Type 1 codes.

Claim 28

Method of utilizing a digital computer having memory and control sections to compress numeric information supplied in the form of a first string comprising a set of words A, B, C, D, E. . . . , each word containing a number, comprising the steps of: a. recursively differencing by i. adding the absolute value of the contents of the words of the first string to obtain a first sum; ii. generating from the first string a second string having the same number of words, each word except the first having a value equal to the difference between the correspondingly located word of the first string and the next preceding word of the first string, whereby the second string comprises words A, A-B, B-C, C-D, D-E, . . . , and adding the absolute values of the words of the second string to obtain a second sum; iii. comparing the magnitudes of the first and the second sums and, continuing to step (b) if the first sum is less than the second sum, but continuing to substep (iv) if the magnitude of the first sum is greater than or equal to the magnitude of the second sum; iv. generating from the second string generated in substep (ii) a third string in the same manner as in substep (ii), whereby the third string comprises words A, A-(A-B), (A-B)-(B-C), (B-C)-(C-D), (C-D)-(D-E), ... , and repeating substeps i and ii by considering each newly generated string as a second string and considering the previously generated string as a first string; b. detecting sequences of identical words; c. determining if the replacement of such sequences by defined decompression information would result in saving in string length and proceeding to step (d) if saving is indicated but proceeding to step (e) if no saving is indicated; d. deleting each detected sequence of identical wordS and associating with the string decompression information comprising the value of the deleted word, the number of deleted words and the address in the string prior to deletion at which the deleted sequence started, and compressing the string to take up the space vacated by the deleted words; and e. packing the words of the string into double words, each double word having a set of bits designating the total number of and a set of bits storing values of words packed in the double word, each word occupying a fixed number of bit positions, said fixed number determined by the number of significant bits of the highest value word packed in the double word.

Claim 29

Method of utilizing a digital computer having memory and control sections to compress numeric information supplied in the form of a first string comprising a set of words A, B, C, D, E. . . . , each word containing a number, comprising the steps of: a. recursively differencing by i. adding the absolute value of the contents of the words of the first string to obtain a first sum; ii. generating from the first string a second string having the same number of words, each word except the first having a value equal to the difference between the correspondingly located word of the first string and the next preceding word of the first string, whereby the second string comprises words A, A-B, B-C, C-D, D-E, . . . , and adding the absolute values of the words of the second string to obtain a second sum; iii. comparing the magnitudes of the first and the second sums and, continuing to step (b) if the first sum is less than the second sum, but continuing to substep (iv) if the magnitude of the first sum is greater than or equal to the magnitude of the second sum; iv. generating from the second string generated in substep (ii) a third string in the same manner as in substep (ii), whereby the third string comprises words A, A-(A-B), (A-B)-(B-C), (B-C)-(C-D), (C-D)-(D-E), ... , and repeating substeps i and ii by considering each newly generated string as a second string and considering the previously generated string as a first string; b. detecting sequences of identical words; c. determining if the replacement of such sequences by defined decompression information would result in saving in string length and proceeding to step (d) if saving is indicated but proceeding to step (e) if no saving is indicated; d. deleting each detected sequence of identical wordS and associating with the string decompression information comprising the value of the deleted word, the number of deleted words and the address in the string prior to deletion at which the deleted sequence started, and compressing the string to take up the space vacated by the deleted words; and e. packing the words of the string into double words, each double word having a set of bits designating the total number of and a set of bits storing values of words packed in the double word, each word occupying a fixed number of bit positions, said fixed number determined by the number of significant bits of the highest value word packed in the double word.

Claim 30

Method as in claim 20 including converting floating point numbers contained in the words A, B, C, D, E, . . . , into integer numbers by a logical right shift truncation process.

Claim 31

Method as in claim 21 including: placing each integer number in the string into a four byte word; searching the string to find a minimum and maximum value of the words; storing said maximum and minimum values; determining the median value by dividing the sum of the minimum and maximum values by 2; recording said median value; subtracting the recorded median value from each word in the string; associating with the string decompression information defining the above steps; and storing the decompression information.

Claim 32

Method as in claim 21 including: providing a value LSX indicating the degree of accuracy at which the information stored in the string is to be maintained; dividing LSX by 2 and storing the result; finding the minimum value of the words in the string; subtracting from each word of the string the minimum value and dividing the difference by the value LSX over 2; and rounding by removing all digits to the right of the decimal point in the words leaving only the digits to the left of the decimal point.

Claim 33

Method as in claim 21 including: locating in the string composed of integer numbers each contained in a word any patterns of words which patterns are composed of a plurality of contiguous words identical to each other; replacing each such pattern by two new words one of which is a count of the number of the words repeated in the pattern and the other one of which is a copy of the word which is repeated in the pattern, and associating with the string a third new word indicating the location in the string of the pattern which is replaced by said two new words.

Claim 34

Method of utilizing a digital computer having memory and control sections to decompress strings compressed by the method of claim 20 comprising the steps of: a. storing in the memory the packed string and its decompression information; b. unpacking the packed string double words by reference to the set of bits designating the total number of words packed in the double words and to the set of bits storing the values of words to generate unpacked words; c. if sequences of words were deleted in the course of compressing the string, utilizing the decompression information to replace in the string the deleted words; and d. if second or subsequent string were generated during compression, carrying out the reverse of the second and subsequent string generating step to regenerate the original string of words A, B, C, D, E, . . . .