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

• US 5,153,591 A
• Filed: 12/27/1990
• Issued: 10/06/1992
• Est. Priority Date: 07/05/1988
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Clark, Alan D.
• Primary Examiner(s): HOFF, MARC S
• Application Number:
  US07/623,809
• Time in Patent Office: 649 Days
• Field of Search: 341/51, 341/65, 341/67, 341/79, 341/87
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

Data compression and decompression utilizing, e.g., the Ziv-Lempel algorithm is simplified by utilizing a tree structure for the dictionary in which alternative symbols at a given position in a symbol sequence (a,b,c) are linked by linking pointers R of a first type and successive symbols (ab,bc,ca,aba,abb,abc) are linked by linking pointers D of a second type. For example, the sequence ab may continue with any one of the symbols a,b, and c grouped together by R pointers in a list below the final symbol of the sequence ab. Each symbol is defined by an associated pair of D and R pointers, in conjunction with a parent pointer P which identifies its parent. Symbols having no D pointers extending therefrom are pruned from the tree and transferred to a free list as shown in FIG. 8(b).

Claims

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.

2. A method as claimed in claim 1 wherein all the indexed memory locations forming the dictionary are tested before the next symbol to be stored is stored in a freed memory location.

3. A method as claimed in claim 1 wherein those indexed memory locations which do not contain nodes of the search tree are linked by pointers to form a free list and nodes of the search tree are deleted by re-setting points to bypass the deleted nodes and connecting them to the free list, whereby the search tree is maintained as a connected whole.

4. A method as claimed in claim 1 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.

5. A method as claimed in claim 1 wherein each linking pointer of the second type points to a first stored symbol of an ordered list of alternative stored symbols of the search tree and successive stored symbols in said ordered list are connected by linking pointers of the first type which point to each succeeding stored symbol in said list.

6. A method as claimed in claim 5 wherein linking pointers of the first type are used to search through the list of alternative stored symbols to find a match for the most recently read input symbol and, if a match is found, to obtain the pointer of the second type, if present.

7. A method as claimed in claim 1 wherein each linking pointer of the second type points to any one of a list of alternative stored symbols of the search tree, the stored symbols in said list being connected to each other by pointers of the first type pointing in one direction and also by pointers of the first type pointing in the opposite direction so as to enable any stored symbol in the list to be accessed.

8. A method as claimed in claim 1 wherein, before the input data is processed, the memory is initially provided with stored symbols each of which corresponds to a sequence of symbols likely to occur in the input data, said initially provided stored symbols being stored as nodes in the search tree.

9. 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.

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 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.

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 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.

12. A method as claimed in claim 11 wherein the ordinal value of the used node is increased by one, and the ordinal value of the node immediately above the used node is decreased by one, whereby these two nodes exchange ordinal values.

13. A method as claimed in claim 11 wherein the ordinal value of the used node is increased to the maximum value, and the ordinal values of all the nodes above the used node are decreased by one.

14. A method as claimed in claim 11 wherein each node of the search tree has an associated length index and the compressed output data comprises codewords whose lengths are related to the length indices such that the shortest codewords represent nodes with highest ordinal values.

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 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.

16. 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.

17. 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.

18. 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.

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, in use, a checksum for the dictionary is periodically calculated and a corresponding output signal generated.

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 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.

21. 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.

22. 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.

23. A method as claimed in claim 22 wherein all the indexed memory locations forming the dictionary are tested before the next symbol to be stored is stored in a freed memory location.

24. A method as claimed in claim 22 wherein those indexed memory locations which do not contain nodes of the search tree are linked by pointers to form a free list and nodes of the search tree are deleted by re-setting pointers to bypass the deleted nodes and connecting them to the free list, whereby the search tree is maintained as a connected whole.

25. A method as claimed in claim 22 wherein each linking pointer of the second type points to a first stored symbol of an ordered list of alternative stored symbols of the search tree and successive stored symbols in said ordered list are connected by linking pointers of the first type which point to each succeeding stored symbol in said list.

26. A method as claimed in claim 22 wherein each linking pointer of the second type points to any one of a list of alternative stored symbols of the search tree, the stored symbols in said list being connected to each other by pointers of the first type pointing in one direction and also by pointers of the first type pointing in the opposite direction so as to enable any stored symbol in the list to be accessed.

27. 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.

28. 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.

29. 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.

30. A method as claimed in claim 29 wherein each node of the search tree has an associated length index such that the shortest codewords represent nodes with the highest ordinal values and the compressed data to be decoded comprisee codewords whose lengths are related to the length indices such that the shortest codewords represent highest ordinal value nodes of the search tree of a corresponding encoder.

31. A method as claimed in claim 29 wherein the ordinal value of the used node is increased by one, and the ordinal value of the node immediately above the used node is decreased by one, whereby these two nodes exchange ordinal values.

32. A method as claimed in claim 29 wherein the ordinal value of the used node is increased to the maximum value, and the ordinal values of all the nodes above the used code are decreased by one.

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 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.

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 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.

35. 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.

36. 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.

37. An encoder as claimed in claim 36 wherein the processor is further arranged to test all the indexed memory locations forming the dictionary before the next symbol to be stored is stored in a freed memory location.

38. An encoder as claimed in claim 36 wherein each linking pointer of the second type points to a first stored symbol of an ordered list of alternative stored symbols of the search tree and successive stored symbols in said ordered list are connected by linking pointers of the first type which point to each succeeding stored symbol in said list.

39. An encoder as claimed in claim 36 wherein the processor is arranged to link by pointers those indexed memory locations which do not contain nodes of the search tree to form a free list and to delete nodes of the search tree by re-setting pointers to bypass the deleted nodes and connecting them to a free list, whereby the search tree is maintained as a connected whole.

40. An encoder as claimed in claim 36 for encoding input data consisting 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.

41. An encoder as claimed in claim 40 wherein the number of bits per sequence selected by the processor 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.

42. An encoder as claimed in claim 36 wherein each linking pointer of the second type points to any one of a list of alternative stored symbols of the search tree, the stored symbols in said list being connected to each other by pointers of the first type pointing in one direction and also by pointers of the first type pointing in the opposite direction so as to enable any stored symbol in the list to be accessed.

43. 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 process is arranged to protect recently created nodes of the search tree against deletion.

44. 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.

45. 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.

46. An encoder as claimed in claim 45 wherein the ordinal value of the used node is increased by one, and the ordinal value of the node immediately above the used node is decreased by one, whereby these two nodes exchange ordinal values.

47. An encoder as claimed in claim 45 wherein the ordinal value of the used node is increased to the maximum value, and the ordinal values of all the nodes above the used node are decreased by one.

48. An encoder as claimed in claims 45, 46 or 47 wherein each node of the search tree has an associated length index and the processor is arranged to provide compressed output data comprising codewords whose lengths are related to the length indices such that the shortest codewords represent nodes with the highest ordinal values.

49. 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.

50. 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.

51. 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.

52. 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.

53. 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.

54. 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.

55. A decoder as claimed in claim 54 wherein in use, each linking pointer of the second type points to a first stored symbol of an ordered list of alternative stored symbols of the search tree and successive stored symbols in said ordered list are connected by linking pointers of the first type which point to each succeeding stored symbol in said list.

56. A decoder as claimed in claim 54 wherein in use, each linking pointer of the second type points to any one of a list of alternative stored symbols of the search tree, the stored symbols in said list being connected to each other by pointers of the first type pointing in one direction and also by pointers of the first type pointing in the opposite direction so as to enable any stored symbol in the list to be accessed.

57. A decoder as claimed in claim 54 wherein the processor is further arranged to test all the indexed memory locations forming the dictionary before the next symbol to be stored is stored in a freed memory location.

58. A decoder as claimed in claim 54 wherein the processor is arranged to link by pointers those indexed memory locations which do not contain nodes of the search tree link by pointers to form a free list and to delete nodes of the search tree by re-setting pointers to bypass the deleted nodes and connecting them to the free list, whereby the search tree is maintained as a connected whole.

59. 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 processor is arranged to protect recently created nodes of the search tree against deletion.

60. 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.

61. 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.

62. A decoder as claimed in claim 61 wherein the ordinal value of the used node is increased by one, and the ordinal value of the node immediately above the used node is decreased by one, whereby these two nodes exchange ordinal values.

63. A decoder as claimed in claim 61 wherein the ordinal value of the used node is increased to the maximum value, and the ordinal values of all the nodes above the used node are decreased by one.

64. A decoder as claimed in claim 61 wherein each node of the search tree has an associated length index and the processor is arranged to provide compressed output data comprising codewords whose lengths are related to the length indices such that the shortest codewords represent nodes with the highest ordinal values.

65. 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.

66. 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.

67. 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.

68. 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.