Encoder/decoder and method for efficient string handling in data compression

Claim 1

A method for efficiently providing a longest matched string for a plurality of input symbols in a data compression encoder/decoder, wherein a `string` begins as a null string/a first input/received symbol and a `character` is, correspondingly, a first/next input/received symbol, utilizing a string matching procedure comprising, for each cycle, the steps of: 1A) appending the `character` onto the `string` to form a `string+character`, 1B) searching for an entry in a dictionary that matches the `string+character` in the dictionary, 1B1) where there is a successful match, testing whether the entry is created by the string matching procedure executed immediately previously, 1B1a) where the entry is other than the entry created by the immediately previous string matching procedure, determining whether a length of the `string+character` is equal to a predetermined maximum string length, and one of 1B1a1-1B1a2: 1B1a1) where the string length is less than the predetermined maximum string length, recycling to step 1A, and continuing the string matching procedure with `string+character` as the `string` and `character` as the next input symbol, 1B1a2) where the string length is equal to the predetermined maximum string length, terminating the cycle of the string matching procedure, 1B1b) where the `string+character` is the string created by the immediately previous string matching procedure, terminating the cycle of the string matching procedure, 1B2) where there is an unsuccessful match, terminating the cycle of the string matching procedure.

Claim 2

A method for efficiently providing a longest matched string for a plurality of input symbols in a data compression encoder/decoder, wherein a `string` begins as a null string/a first input/received symbol and a `character` is, correspondingly, a first/next input/received symbol, utilizing a string matching procedure comprising, for each cycle, the steps of: 1A) appending the `character` onto the `string` to form a `string+character`, 1B) searching for an entry in a dictionary that matches the `string+character` in the dictionary, 1B1) where there is a successful match, testing whether the entry is created by the string matching procedure executed immediately previously, 1B1a) where the entry is other than the entry created by the immediately previous string matching procedure, determining whether a length of the `string+character` is equal to a predetermined maximum string length, and one of 1B1a1-1B1a2: 1B1a1) where the string length is less than the predetermined maximum string length, recycling to step 1A, and continuing the string matching procedure with `string+character` as the `string` and `character` as the next input symbol, 1B1a2) where the string length is equal to the predetermined maximum string length, terminating the cycle of the string matching procedure, 1B1b) where the `string+character` is the string created by the immediately previous string matching procedure, terminating the cycle of the string matching procedure, 1B2) where there is an unsuccessful match, terminating the cycle of the string matching procedure.

Claim 23

A device for utilizing a string matching procedure to efficiently provide a longest matched string for a plurality of input symbols in a data compression encoder/decoder, wherein a `string` begins as a null string/a first input/received symbol and a `character` is, correspondingly, a first/next input/received symbol, comprising: 22A) an appender, operably coupled to receive the input symbols, for appending the `character` onto the `string` to form a `string+character`, 22B) a match searching unit, operably coupled to the apppender, for searching for an entry in a dictionary that matches the `string+character` in the dictionary, and, where there is an unsuccessful match, for terminating the string matching procedure for the `string+character`, 22C) a previous string match tester, operably coupled to the match searching unit, for, where there is a successful match in the dictionary, testing whether the `string+character` is an entry created by the string matching procedure executed immediately previously, and where the `string+character` is the entry created by the immediately previous string matching procedure, for terminating the string matching procedure for the `string+character` and, where selected, signalling the appender to begin a next string matching procedure, 22D) a maximum string length comparator, operably coupled to the previous string match tester, for, where the `string+character` is an entry other than the entry created by the immediately previous string matching procedure, determining whether a length of the `string+character` is equal to a predetermined maximum string length, and one of: where the string length is less than the predetermined maximum string length, for signalling the appender to begin a next string matching procedure with `string+character` as the `string` and `character` as the next input symbol, and where the string length is equal to the predetermined maximum string length, for terminating the string matching procedure for the `string+character`.

Claim 24

A device for utilizing a string matching procedure to efficiently provide a longest matched string for a plurality of input symbols in a data compression encoder/decoder, wherein a `string` begins as a null string/a first input/received symbol and a `character` is, correspondingly, a first/next input/received symbol, comprising: 22A) an appender, operably coupled to receive the input symbols, for appending the `character` onto the `string` to form a `string+character`, 22B) a match searching unit, operably coupled to the apppender, for searching for an entry in a dictionary that matches the `string+character` in the dictionary, and, where there is an unsuccessful match, for terminating the string matching procedure for the `string+character`, 22C) a previous string match tester, operably coupled to the match searching unit, for, where there is a successful match in the dictionary, testing whether the `string+character` is an entry created by the string matching procedure executed immediately previously, and where the `string+character` is the entry created by the immediately previous string matching procedure, for terminating the string matching procedure for the `string+character` and, where selected, signalling the appender to begin a next string matching procedure, 22D) a maximum string length comparator, operably coupled to the previous string match tester, for, where the `string+character` is an entry other than the entry created by the immediately previous string matching procedure, determining whether a length of the `string+character` is equal to a predetermined maximum string length, and one of: where the string length is less than the predetermined maximum string length, for signalling the appender to begin a next string matching procedure with `string+character` as the `string` and `character` as the next input symbol, and where the string length is equal to the predetermined maximum string length, for terminating the string matching procedure for the `string+character`.

Claim 45

A method for efficiently providing a longest matched string for an input symbol character in a data compression encoder/decoder, wherein a `string` begins as one of: a first input/received symbol and a null string and a `character` is, correspondingly, one of: a next input/received symbol and a first input/received symbol, utilizing a string matching procedure comprising, for each single character processing in a compressed mode, the steps of: 43A) appending the `character` onto the `string` to form a `string+character`, 43B) searching for an entry in a dictionary that matches the `string+character` in the dictionary, 43B1) where there is a successful match, testing whether the `string+character` is the entry created by the string matching procedure executed immediately previously, 43B1a) where the `string+character` is an entry other than the entry created by the immediately previous string matching procedure, setting `string` equal to `string+character` and determining whether a length of the `string+character` is equal to a predetermined maximum string length (N7), and one of 43B1a1-43B1a2: 43B1a1) where the string length is less than the predetermined maximum string length, where selected, maintaining a preselected escape character and ending the single character processing, 43B1a2) where the string length is equal to the predetermined maximum string length, setting a codeword to a codeword for the `string` and string=NULL, checking the codeword size, sending the codeword, maintaining the preselected escape character where selected, and ending the single character processing, 43B1b) where the `string+character` is the entry created by the immediately previous string matching procedure, setting the codeword to a codeword for the `string` and string=character, checking the codeword size, sending the codeword, maintaining the preselected escape character where selected, and ending the single character processing, 43B2) where there is an unsuccessful match, adding `string+character` to the dictionary, setting the codeword to a codeword for the `string` and string=character, checking the codeword size, sending the codeword, maintaining the preselected escape character where selected, and ending the single character processing.

Claim 46

A method for efficiently providing a longest matched string for an input symbol character in a data compression encoder/decoder, wherein a `string` begins as one of: a first input/received symbol and a null string and a `character` is, correspondingly, one of: a next input/received symbol and a first input/received symbol, utilizing a string matching procedure comprising, for each single character processing in a compressed mode, the steps of: 43A) appending the `character` onto the `string` to form a `string+character`, 43B) searching for an entry in a dictionary that matches the `string+character` in the dictionary, 43B1) where there is a successful match, testing whether the `string+character` is the entry created by the string matching procedure executed immediately previously, 43B1a) where the `string+character` is an entry other than the entry created by the immediately previous string matching procedure, setting `string` equal to `string+character` and determining whether a length of the `string+character` is equal to a predetermined maximum string length (N7), and one of 43B1a1-43B1a2: 43B1a1) where the string length is less than the predetermined maximum string length, where selected, maintaining a preselected escape character and ending the single character processing, 43B1a2) where the string length is equal to the predetermined maximum string length, setting a codeword to a codeword for the `string` and string=NULL, checking the codeword size, sending the codeword, maintaining the preselected escape character where selected, and ending the single character processing, 43B1b) where the `string+character` is the entry created by the immediately previous string matching procedure, setting the codeword to a codeword for the `string` and string=character, checking the codeword size, sending the codeword, maintaining the preselected escape character where selected, and ending the single character processing, 43B2) where there is an unsuccessful match, adding `string+character` to the dictionary, setting the codeword to a codeword for the `string` and string=character, checking the codeword size, sending the codeword, maintaining the preselected escape character where selected, and ending the single character processing.

Claim 47

A method for efficiently providing a longest matched string for an input symbol character in a data compression encoder/decoder, wherein a `string` begins as a null string/a first input/received symbol and a `character` is, correspondingly, a first/next input/received symbol, utilizing a string matching procedure comprising, for each single character processing in a transparent mode, the steps of: 44A) appending the `character` onto the `string` to form a `string+character`, 44B) searching for an entry in a dictionary that matches the `string+character` in the dictionary, 44B1) where there is a successful match, testing whether the `string+character` is the entry created by the string matching procedure executed immediately previously, 44B1a) where the `string+character` is an entry other than the entry created by the immediately previous string matching procedure, setting `string` equal to `string+character` and determining whether a length of the `string+character` is equal to a predetermined maximum string length (N7), and one of 44B1a1-44B1a2: 44B1a1) where the string length is less than the predetermined maximum string length, sending the character and maintaining a preselected escape character and ending the single character processing, 44B1a2) where the string length is equal to the predetermined maximum string length, setting string=NULL, sending the character, maintaining the preselected escape character, and ending the single character processing, 44B1b) where the `string+character` is the entry created by the immediately previous string matching procedure, setting string=character, sending the character, maintaining the preselected escape character, and ending the single character processing, 44B2) where there is an unsuccessful match, adding `string+character` to the dictionary, setting string=character, sending the character, maintaining the preselected escape character, and ending the single character processing.

Claim 48

A method for efficiently providing a longest matched string for an input symbol character in a data compression encoder/decoder, wherein a `string` begins as a null string/a first input/received symbol and a `character` is, correspondingly, a first/next input/received symbol, utilizing a string matching procedure comprising, for each single character processing in a transparent mode, the steps of: 44A) appending the `character` onto the `string` to form a `string+character`, 44B) searching for an entry in a dictionary that matches the `string+character` in the dictionary, 44B1) where there is a successful match, testing whether the `string+character` is the entry created by the string matching procedure executed immediately previously, 44B1a) where the `string+character` is an entry other than the entry created by the immediately previous string matching procedure, setting `string` equal to `string+character` and determining whether a length of the `string+character` is equal to a predetermined maximum string length (N7), and one of 44B1a1-44B1a2: 44B1a1) where the string length is less than the predetermined maximum string length, sending the character and maintaining a preselected escape character and ending the single character processing, 44B1a2) where the string length is equal to the predetermined maximum string length, setting string=NULL, sending the character, maintaining the preselected escape character, and ending the single character processing, 44B1b) where the `string+character` is the entry created by the immediately previous string matching procedure, setting string=character, sending the character, maintaining the preselected escape character, and ending the single character processing, 44B2) where there is an unsuccessful match, adding `string+character` to the dictionary, setting string=character, sending the character, maintaining the preselected escape character, and ending the single character processing.