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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and 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 processor is arranged to provide compressed output data comprising codewords whose lengths are related to the contents of the counters such that the shortest codewords represent the most frequently used nodes.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein the nodes of the search tree are stored in order in the memory and the processor is arranged to re-arrange the order in which they are stored by raising the ordinal value of a node after it has been used whereby rarely used nodes acquire a low ordinal value, and to delete nodes having the lowest ordinal values.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and for encoding input data including spaces between sequences of symbols and wherein the processor is arranged to terminate the process of generating a new stored path of the search tree when such a space is detected.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein the input data is of a stream of binary digits representing characters, wherein the symbols stored in the search tree are each made up of sequences of binary digits, and wherein the processor is arranged to select the number of bits per sequence such as to be different from the number of bits per character of the input data, if known and wherein the processor is arranged to perform the selection in response to an external command signal from a user.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein, in use, the processor is responsive to a command signal received from an associated decoder to reinitialise its dictionary.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein, in use, the processor periodically calculates a checksum for the dictionary and generates a corresponding output signal.

An encoder for compressing input data comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein the dictionary is retained for further use and the processor is arranged to perform a checksum calculation on the dictionary prior to any such further use and to generate a corresponding output signal, to compare this checksum with a corresponding checksum received, in use, from an associated decoder, and to reinitialise the dictionary to an initial state if the checksums are not identical.

A decoder for decoding compressed data comprising a processor capable of receiving successive symbols of compressed data, a memory having indexed memory locations and means for storing in the memory a dictionary in the form of a search tree of symbols, the processor being arranged to build up the search tree from the compressed data and to utilise the search tree to translate the compressed data to decoded data, stored symbols in the search tree being linked by linking pointers of two distinct types;

• a pointer 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 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein each node of the search tree is associated with a respective counter which is associated with a respective counter which is incremented each time the associated node is used, and the processor is arranged to provide compressed output data comprising codewords whose lengths are related to the contents of the counters such that the shortest codewords represent the most frequently used nodes.

A decoder for decoding compressed data comprising a processor capable of receiving successive symbols of compressed data, a memory having indexed memory locations and means for storing in the memory a dictionary in the form of a search tree of symbols, the processor being arranged to build up the search tree from the compressed data and to utilise the search tree to translate the compressed data to decoded data, stored symbols in the search tree being linked by linking pointers of two distinct types;

• a pointer 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 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein the nodes of the search tree are stored in order in the memory and the processor is arranged to re-arrange the order in which they are stored by raising the ordinal value of a node after it has been used whereby rarely used nodes acquire a low ordinal value, and to delete nodes having the lowest ordinal value.

A decoder for decoding compressed data comprising a processor capable of receiving successive symbols of compressed data, a memory having indexed memory locations and means for storing in the memory a dictionary in the form of a search tree of symbols, the processor being arranged to build up the search tree from the compressed data and to utilise the search tree to translate the compressed data to decoded data, stored symbols in the search tree being linked by linking pointers of two distinct types;

• a pointer 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 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein, in use, the processor is arranged to detect when received compressed data corresponds to empty or free memory locations and to generate a corresponding output signal for transmission to an associated encoder.

A decoder for decoding compressed data comprising a processor capable of receiving successive symbols of compressed data, a memory having indexed memory locations and means for storing in the memory a dictionary in the form of a search tree of symbols, the processor being arranged to build up the search tree from the compressed data and to utilise the search tree to translate the compressed data to decoded data, stored symbols in the search tree being linked by linking pointers of two distinct types;

• a pointer 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 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and wherein the dictionary is retained for further use and the processor is arranged to perform a checksum calculation on the dictionary prior to any such further use and to generate a corresponding output signal for transmission to an associated encoder, to compare this checksum with a corresponding checksum received, in use, from said encoder, and to reinitialise the dictionary if the checksums are not identical.

Data processing apparatus comprising an encoder comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries, a corresponding decoder comprising a processor capable of receiving successive symbols of compressed data, a memory having indexed memory locations and means for storing in the memory a dictionary in the form of a search tree of symbols, the processor being arranged to build up the search tree from the compressed data and to utilise the search tree to translate the compressed data to decoded data, stored symbols in the search tree being linked by linking pointers of two distinct types;
• a pointer 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 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and a data link for transmitting the compressed data between the encoder and decoder.

Data processing apparatus comprising an encoder comprising a processor capable of receiving successive symbols of input data, a memory having indexed memory locations, means for storing in the memory a search tree of symbols which has paths representative of strings of symbols in the input data, and means for matching symbol strings in the input data with previously stored paths in the search tree and for 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries, a corresponding decoder comprising a processor capable of receiving successive symbols of compressed data, a memory having indexed memory locations and means for storing in the memory a dictionary in the form of a search tree of symbols, the processor being arranged to build up the search tree from the compressed data and to utilise the search tree to translate the compressed data to decoded data, stored symbols in the search tree being linked by linking pointers of two distinct types;
• a pointer 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 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 said processor is arranged to determine when the memory is full, to test sequential indexed memory locations of the search tree, and to delete a memory location if it contains a node of the search tree which does not have a linking pointer of the second type pointing to another node so as to make the resulting freed memory locations available for new dictionary entries and a mass storage medium accessible by the encoder and decoder.