Method and apparatus for encoding, decoding and transmitting data in compressed form

Claim 1

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries.

Claim 2

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries.

Claim 10

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries modified by the proviso that recently created nodes of the search tree are protected against deletion.

Claim 11

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries modified by the proviso that recently created nodes of the search tree are protected against deletion.

Claim 12

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein each node of the search tree is associated with a respective counter which is incremented each time the associated node is used, and the compressed output data comprises codewords whose lengths are related to the contents of the counters such that the shortest codewords represent the most frequently used nodes.

Claim 13

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein each node of the search tree is associated with a respective counter which is incremented each time the associated node is used, and the compressed output data comprises codewords whose lengths are related to the contents of the counters such that the shortest codewords represent the most frequently used nodes.

Claim 14

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the nodes of the search tree are stored in order in the memory and the order in which they are stored is re-arranged by raising the ordinal value of a node after it has been used whereby rarely used nodes acquire a low ordinary value, and are deleted.

Claim 15

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the nodes of the search tree are stored in order in the memory and the order in which they are stored is re-arranged by raising the ordinal value of a node after it has been used whereby rarely used nodes acquire a low ordinary value, and are deleted.

Claim 19

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the input data includes spaces between sequences of symbols and the process of generating a new stored path of the search tree is terminated when such a space is detected.

Claim 20

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the input data includes spaces between sequences of symbols and the process of generating a new stored path of the search tree is terminated when such a space is detected.

Claim 21

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the input data consists of a stream of binary digits representing characters, and the symbols stored in the search tree are each made up of sequences of binary digits, and wherein the number of bits per sequence is selected by the processor, the number of bits per character of the input data either being unknown or being different from the number of bits per sequence selected by the processor and wherein the processor is arranged to perform the selection in response to an external command signal from a user.

Claim 22

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the input data consists of a stream of binary digits representing characters, and the symbols stored in the search tree are each made up of sequences of binary digits, and wherein the number of bits per sequence is selected by the processor, the number of bits per character of the input data either being unknown or being different from the number of bits per sequence selected by the processor and wherein the processor is arranged to perform the selection in response to an external command signal from a user.

Claim 23

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the input data consists of a stream of binary digits representing characters, and the symbols stored in the search tree are each made up of sequences of binary digits, and wherein the number of bits per sequence is selected by the processor, the number of bits per character of the input data either being unknown or being different from the number of bits per sequence selected by the processor and wherein the number of bits per sequence is initially varied and the resulting compression ratio between the input data and the output data is measured, and the number of bits per sequence for the stored symbols of the search tree is selected on the basis of the measured compression ratio.

Claim 24

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the input data consists of a stream of binary digits representing characters, and the symbols stored in the search tree are each made up of sequences of binary digits, and wherein the number of bits per sequence is selected by the processor, the number of bits per character of the input data either being unknown or being different from the number of bits per sequence selected by the processor and wherein the number of bits per sequence is initially varied and the resulting compression ratio between the input data and the output data is measured, and the number of bits per sequence for the stored symbols of the search tree is selected on the basis of the measured compression ratio.

Claim 25

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the dictionary is reinitialised in response to a command signal received, in use, from an associated decoder.

Claim 26

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the dictionary is reinitialised in response to a command signal received, in use, from an associated decoder.

Claim 27

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein, in use, a checksum for the dictionary is periodically calculated and a corresponding output signal generated.

Claim 28

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein, in use, a checksum for the dictionary is periodically calculated and a corresponding output signal generated.

Claim 29

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the dictionary is retained for further use, and including performing a checksum calculation on the dictionary prior to any such further use, receiving a corresponding checksum from another such dictionary, comparing the checksums and reinitalising the dictionary if the checksums are not identical.

Claim 30

A method of compressing input data comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the dictionary is retained for further use, and including performing a checksum calculation on the dictionary prior to any such further use, receiving a corresponding checksum from another such dictionary, comparing the checksums and reinitalising the dictionary if the checksums are not identical.

Claim 31

A method of storing data comprising compressing the data by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries, and storing the compressed data in a mass storage medium.

Claim 32

A method of storing data comprising compressing the data by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries, and storing the compressed data in a mass storage medium.

Claim 33

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries, reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries.

Claim 34

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries, reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries.

Claim 39

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries modified by the proviso that recently created nodes of the search tree are protected against deletion.

Claim 40

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries modified by the proviso that recently created nodes of the search tree are protected against deletion.

Claim 41

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein each node of the search tree is associated with a respective counter which is incremented each time the associated node is used, the shortest codewords are allocated to the most frequently used nodes, and the compressed data to be decoded comprises codewords of which the shortest codewords represent the most frequently used nodes of the search tree of a corresponding encoder.

Claim 42

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein each node of the search tree is associated with a respective counter which is incremented each time the associated node is used, the shortest codewords are allocated to the most frequently used nodes, and the compressed data to be decoded comprises codewords of which the shortest codewords represent the most frequently used nodes of the search tree of a corresponding encoder.

Claim 43

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the nodes of the search tree are stored in order in the memory and the order in which they are stored is re-arranged by raising the ordinal value of a node after it has been used whereby rarely used nodes acquire a low ordinary value, and are deleted.

Claim 44

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the nodes of the search tree are stored in order in the memory and the order in which they are stored is re-arranged by raising the ordinal value of a node after it has been used whereby rarely used nodes acquire a low ordinary value, and are deleted.

Claim 48

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries including detecting when received compressed data corresponds to empty or free memory locations and generating a corresponding output signal.

Claim 49

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries including detecting when received compressed data corresponds to empty or free memory locations and generating a corresponding output signal.

Claim 50

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the dictionary is retained for further use, and including performing a checksum calculation on the dictionary prior to any such further use, receiving a corresponding checksum from another such dictionary, comparing the checksums and reinitialising the dictionary if the checksums are not identical.

Claim 51

A method of decoding compressed data which has been compressed by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries wherein the dictionary is retained for further use, and including performing a checksum calculation on the dictionary prior to any such further use, receiving a corresponding checksum from another such dictionary, comparing the checksums and reinitialising the dictionary if the checksums are not identical.

Claim 52

A method of transmitting data comprising encoding the data by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries, transmitting the resulting compressed data to a remote location, and decoding the compressed data by a corresponding method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries.

Claim 53

A method of transmitting data comprising encoding the data by a method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries, transmitting the resulting compressed data to a remote location, and decoding the compressed data by a corresponding method comprising reading successive symbols of the data with a processor provided with a memory having indexed memory locations, generating from strings of symbols in the input data a dictionary in the form of a search tree of symbols in the memory, which search tree has paths representative of said strings, matching symbol strings in the input data with previously stored paths in the search tree and generating from the stored paths compressed output data corresponding to the input data, stored symbols in the search tree being linked to form said paths by linking pointers of two distinct types; a pointer of the first type between stored symbols indicating that those stored symbols are alternative possible symbols at a given position in an input symbol sequence and a pointer of the second type between stored symbols indicating that those stored symbols both occur, in order, in a possible input symbol sequence, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries comprising reading successive characters of the compressed data with a processor provided with a memory, storing in the memory a dictionary in the form of a search tree of symbols which is built up from the compressed data, and utilising the search tree to translate the compressed data to decoded data, stored symbol in the search tree being linked by linking pointers of two distinct types; a point of the first type between stored symbols indicating that those symbols are associated with different decoded strings of symbols having the same number of symbols and the same prefix and are the respective last symbols of such different strings and a pointer of the second type between stored symbols indicating that those symbols are successive symbols in a string of decoded output symbols, determining when the memory is full, testing and deleting sequential indexed memory locations of the search tree if they contain a node of the search tree which does not have a linking pointer of the second type pointing to another node whereby the resulting freed memory locations are made available for new dictionary entries.