EP0375221A1 - Data compression - Google Patents

Data compression Download PDF

Info

Publication number
EP0375221A1
EP0375221A1 EP89312818A EP89312818A EP0375221A1 EP 0375221 A1 EP0375221 A1 EP 0375221A1 EP 89312818 A EP89312818 A EP 89312818A EP 89312818 A EP89312818 A EP 89312818A EP 0375221 A1 EP0375221 A1 EP 0375221A1
Authority
EP
European Patent Office
Prior art keywords
dictionary
string
entry
word
algorithm
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
EP89312818A
Other languages
German (de)
French (fr)
Other versions
EP0375221B1 (en
Inventor
Alan Douglas Clark
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
British Telecommunications PLC
Original Assignee
British Telecommunications PLC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by British Telecommunications PLC filed Critical British Telecommunications PLC
Publication of EP0375221A1 publication Critical patent/EP0375221A1/en
Application granted granted Critical
Publication of EP0375221B1 publication Critical patent/EP0375221B1/en
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method

Definitions

  • the present invention relates to data compression systems which may be used, for example, to reduce the space required by data for storage in a mass storage device such as a hard disc, or to reduce the bandwidth required to transmit data.
  • the invention is particularly concerned with data compression systems using dynamically compiled dictionaries.
  • an input data stream is compared with strings stored in a dictionary.
  • the code for that word is read from the dictionary and transmitted in place of the original characters.
  • the dictionary is updated by making a new entry and assigning a code to the newly encountered character sequence. This process is duplicated on the transmission and reception sides of the compression system.
  • the dictionary entry is commonly made by storing a pointer to a previously encountered string together with the additional character of the newly encountered string.
  • the dictionary is updated by storing a string comprising a word and a part-word, the part-word comprising a plurality of characters from the string immediately following the word in the input data stream.
  • the part-word comprises only two characters.
  • the data compression system compresses data using a Mayne single-pass data compression algorithm.
  • dictionary entries are made either by combining the single unmatched character left over by the process of searching for the longest string match with the preceding matched word or by making entries comprising pairs of matched words.
  • the former is exemplified by the Ziv Lempel algorithm, the latter by the conventional Mayne algorithm.
  • the preferred example of the present invention uses the Mayne data compression algorithm but modifies the process of updating the dictionary so that the entries comprise one word and part of the following word rather than pairs of whole words. The inventor has found that this confers significant advantages in the efficiency of operation of the algorithm and that these advantages are particularly marked in the case where just two characters from the second of the pair of words are taken to form the dictionary entry.
  • the Mayne algorithm (1975) predates the Ziv Lempel algorithm by several years, and has a number of features which were not built in to the Ziv Lempel implementations until the 1980's.
  • the Mayne algorithm was originally proposed as a two pass adaptive compression scheme, but may be adapted to single pass operation. This paper discusses a modified version of the algorithm, however some implementation details are contained in a copending British application no. 8815978.
  • the resource requirements in terms of memory and processing time, are similar to those achieved by the modified Ziv Lempel algorithm.
  • the Mayne algorithm represents a sequence of input symbols by a codeword. This is accomplished using a dictionary of known strings, each entry in the dictionary having a corresponding index number of codeword.
  • the encoder matches the longest string of input symbols with a dictionary entry, and transmits the index number of the dictionary entry.
  • the decoder receives the index number, looks up the entry in its dictionary, and recovers the string.
  • the most complex part of this process is the string matching or parsing performed by the encoder, as this necessitates searching through a potentially large dictionary. If the dictionary entries are structured as shown below however, this process is considerably simplified.
  • the structure shown in the Figure is a tree representation of the series of strings beginning with "t"; the initial entry in the dictionary would have an index number equal to the ordinal value of "t".
  • the initial character “t” is read and the corresponding entry immediately located (it is equal to the ordinal value of "t”).
  • the next character “h” is read and a search initiated amongst the dependents of the first entry (only 3 in this example).
  • the next input character is read and the process repeated. In this manner, the string “the” is rapidly located and when the encoder attempts to locate the next character, " “, it is immediately apparent that the string “the” is not in the dictionary.
  • the index value for the entry “the” is transmitted and the string matching process recommences with the character " ". This is based on principles which are well understood in the general field of sorting and searching algorithms (see ref 4).
  • the dictionary may be dynamically updated in a simple manner.
  • the additional character c may be added to the dictionary and linked to entry S.
  • the above cited application on the modified Ziv Lempel algorithm discusses a trie structure [3] suitable for this application. This has been shown to provide a sufficiently fast method for application in modems.
  • the scheme uses a linked list to represent the alternative characters for a given position in a string, and occupies approximately 7 bytes per dictionary entry.
  • hashing or scatter storage to speed up searching has been known for many years [4-6].
  • the principle is that a mathematical function is applied to the item to be located, in our case a string, which generates an address.
  • searching would simply consist of applying the hashing function and looking up the appropriate entry.
  • the same address may be generated by several different data sets, collision, and hence some searching is involved in locating the desired items.
  • the decoder receives codewords from the encoder, recovers the string of characters represented by the codeword by using an equivalent tree structure to the encoder, and outputs them. It treats the decoded strings as alternately prefix and suffix strings, and updates its dictionary in the same way as the encoder. It is interesting to note that the K w problem described in reference [7] does not occur in the Mayne algorithm. This problem occurs in the Ziv Lempel implementations of Welch, and Miller and Wegman, because the encoder is able to update its dictionary one step ahead of the decoder.
  • the encoder's dictionary is updated after each suffix string is encoded, and the decoder performs a similar function. New dictionary entries are assigned sequentially until the dictionary is full, thereafter they are recovered in a manner described below in section 4.b.
  • the dictionary contains an initial character set, and a small number of dedicated codewords for control applications, the remainder of the dictionary space being allocated for string storage.
  • the first entry assigned is the first dictionary entry following the control codewords.
  • Each dictionary entry consists of a pointer and a character (see for example reference 3), and is linked to a parent entry in the general form shown in section 2. Creating a new entry consists of writing the character and appropriate link pointers into the memory locations allocated to the entry (see reference 6 for an example).
  • the encoder accepts characters from the DTE interface, and passes them on in uncompressed form.
  • the normal encoding process is however maintained, and the encoder dictionary updated, as described above.
  • the encoder dictionary can be adapting to changing data characteristics even when in transparent mode.
  • the decoder accepts uncompressed characters from the encoder, passes the characters through to the DTE interface, and performs the equivalent string matching function. Thus the decoder actually contains a copy of the encoder function.
  • the encoder and decoder maintain a count of the number of characters processed, and the number of bits that these would have encoded in, if compression had been on. As both encoder and decoder perform the same operation of string matching, this is a simple process. After each dictionary character count is tested. When the count exceeds a threshold, axf _ delay , the compression ratio is calculated. If the compression ratio is greater than 1, compression is turned ON and the encoder and decoder enter the compressed mode.
  • the encoder employs the string matching process described above to compress the character stream read from the DTE interface, and sends the compressed data stream to the decoder.
  • the decoder employs the decoding process described in Section 3 to recover character strings from received codewords.
  • the encoder arbitrarily tests its effectiveness, or the compressibility of the data stream, possibly using the test described above. When it appears that the effectiveness of the encoding process is impaired the encoder transmits an explicit codeword to the decoder to indicate a transition to compressed mode. Data from that point on is sent in transparent form, until the test described in (1) indicates that the system should revert to compressed mode. The encoder and decoder revert to prefix mode after switching to transparent mode.
  • a flush operation is provided to ensure that any data remaining in the encoder is transmitted. This is needed as there is a bit oriented element to the encoding and decoding process which is able to store fragments of one byte. The next data to be transmitted will therefore start on a byte boundary.
  • this operation which can only be in compressed mode, an explicit codeword is sent to permit the decoder to realign its bit oriented process. This is used in the following way:-
  • the algorithm is comparable in complexity to the modified Ziv Lempel algorithm.
  • the memory requirement is 2 bytes per dictionary entry for the first 260 dictionary entries, and 7 bytes per entry thereafter giving, for each of the encoder and decoder dictionaries:- 1024 entries: 6k bytes 2048 entries: 13k bytes 4096 entries: 27 kbytes
  • Timeout codeword which permits the encoder to detect intermittent traffic (i.e. keyboard operation) and transmit a partially matched string. This mechanism does not interfere with operation under conditions of continuous data flow, when compression efficiency is maximized.
  • the algorithm described above is ideally suited to the modem environment, as it provides a high degree of compression but may be implemented on a simple inexpensive microprocessor with a small amount of memory.
  • a range of implementations are possible, alowing flexibility to the manufacturer in terms of speed, performance and cost. This realises the desire of some manufacturers to minimise implementation cost, and of others to provide top performance.
  • the algorithm is however well defined and it is thus possible to ensure compatibility between different implementations.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Surgical Instruments (AREA)
  • Diaphragms For Electromechanical Transducers (AREA)
  • Reduction Or Emphasis Of Bandwidth Of Signals (AREA)

Abstract

In a data compression system including a dynamically compiled dictionary the dictionary is updated by storing a string comprising a word and a part-word. The part-word comprises a plurality of characters from the string immediately following the word in the input stream. The system may use a Mayne single-pass data compression algorithm. In a system using the Mayne algorithm after each string is matched the corresponding index is transmitted.

Description

  • The present invention relates to data compression systems which may be used, for example, to reduce the space required by data for storage in a mass storage device such as a hard disc, or to reduce the bandwidth required to transmit data. The invention is particularly concerned with data compression systems using dynamically compiled dictionaries. In such systems an input data stream is compared with strings stored in a dictionary. When characters from the data stream have been matched to a word in the dictionary the code for that word is read from the dictionary and transmitted in place of the original characters. At the same time when the input data stream is found to have character sequences not previously encountered and so not stored in the dictionary then the dictionary is updated by making a new entry and assigning a code to the newly encountered character sequence. This process is duplicated on the transmission and reception sides of the compression system. The dictionary entry is commonly made by storing a pointer to a previously encountered string together with the additional character of the newly encountered string.
  • According to a first aspect of the present invention in a data compression system including a dynamically compiled dictionary, the dictionary is updated by storing a string comprising a word and a part-word, the part-word comprising a plurality of characters from the string immediately following the word in the input data stream.
  • Preferably the part-word comprises only two characters.
  • Preferably the data compression system compresses data using a Mayne single-pass data compression algorithm.
  • In known systems dictionary entries are made either by combining the single unmatched character left over by the process of searching for the longest string match with the preceding matched word or by making entries comprising pairs of matched words. The former is exemplified by the Ziv Lempel algorithm, the latter by the conventional Mayne algorithm. The preferred example of the present invention uses the Mayne data compression algorithm but modifies the process of updating the dictionary so that the entries comprise one word and part of the following word rather than pairs of whole words. The inventor has found that this confers significant advantages in the efficiency of operation of the algorithm and that these advantages are particularly marked in the case where just two characters from the second of the pair of words are taken to form the dictionary entry.
  • According to a second aspect of the present invention, in a data compression system using the Mayne algorithm, during the updating of the dictionary after each string matching process the index for the corresponding dictionary entry is transmitted
  • One embodiment of the present invention is described in detail and contrasted with the prior art in the following technical description.
    • Technical description of BTYZ - a modified Mayne compression algorithm 1. Introduction
  • The Mayne algorithm (1975) predates the Ziv Lempel algorithm by several years, and has a number of features which were not built in to the Ziv Lempel implementations until the 1980's. The Mayne algorithm was originally proposed as a two pass adaptive compression scheme, but may be adapted to single pass operation. This paper discusses a modified version of the algorithm, however some implementation details are contained in a copending British application no. 8815978. The resource requirements in terms of memory and processing time, are similar to those achieved by the modified Ziv Lempel algorithm.
    • 2. Data structure and encoding
  • As with the Ziv Lempel algorithm, the Mayne algorithm represents a sequence of input symbols by a codeword. This is accomplished using a dictionary of known strings, each entry in the dictionary having a corresponding index number of codeword. The encoder matches the longest string of input symbols with a dictionary entry, and transmits the index number of the dictionary entry. The decoder receives the index number, looks up the entry in its dictionary, and recovers the string.
    The most complex part of this process is the string matching or parsing performed by the encoder, as this necessitates searching through a potentially large dictionary. If the dictionary entries are structured as shown below however, this process is considerably simplified. The structure shown in the Figure is a tree representation of the series of strings beginning with "t"; the initial entry in the dictionary would have an index number equal to the ordinal value of "t".
  • To match the incoming string "the quick..", the initial character "t" is read and the corresponding entry immediately located (it is equal to the ordinal value of "t"). The next character "h" is read and a search initiated amongst the dependents of the first entry (only 3 in this example). When the character is matched, the next input character is read and the process repeated. In this manner, the string "the" is rapidly located and when the encoder attempts to locate the next character, " ", it is immediately apparent that the string "the" is not in the dictionary. The index value for the entry "the" is transmitted and the string matching process recommences with the character " ". This is based on principles which are well understood in the general field of sorting and searching algorithms (see ref 4).
  • The dictionary may be dynamically updated in a simple manner. When the situation described above occurs, i.e. string S has been matched, but string S+c has not, the additional character c may be added to the dictionary and linked to entry S. By this means, the dictionary above would now contain the string "the", and would achieve improved compression the next time the string is encountered.
  • The two pass form of the Mayne algorithm operates in the following way:-
    • (a) Dictionary construction
  • Find the longest string of input symbols that matches a dictionary entry, call this the prefix string. Repeat the process and call this second matched string the suffix string. Append the suffix string to the previs string, and add it to the dictionary. This process is repeated until the entire input data stream has been read. Each dictionary entry has an associated frequency count, which is incremented whenever it is used. When the encoder runs out of storage space it finds the least frequently used dictionary entry and re uses it for the new string.
    • (b) Encoding
  • The process of finding the longest string of input symbols that matches a dictionary entry is repeated, however when a match is found the index of the dictionary entry is transmitted. In the two pass scheme the dictionary is not modified during encoding.
  • To make the Mayne algorithm single pass during the dictionary update process, after each string matching process the index for the corresponding dictionary entry is transmitted.
  • With small dictionaries experience has shown that appending the complete string causes the dictionary to fill with long strings which may not suit the data characteristics well. With large dictionaries (say 4096+ entries) this is not likely to be the case. By appending the first two characters of the second string to the first, performance is improved considerably. The dictionary update process is modified to append two characters if the suffix string is 2 or more characters in length, or one character if the suffix string is of length 1.
    Figure imgb0001
  • For example, if the dictionary contains the strings "mo", "us" and the word "mouse" is to be encoded using the single pass version of the Mayne algorithm.
    • (i) Read "m" and the following character "o" giving the extended string "mo".
    • (ii) Search in the dictionary for "mo" which is present, hence let entry be the index number of the string "mo".
    • (iii) Read the next character "u", which gives the extended string "mou".
    • (iv) Search the dictionary for "mou", which is not present.
    • (v) Transmit entry the index number of string "mo".
    • (vi) Reset the string to "u", the unmatched character.
    • (vii) Read the next character "s", giving the string "us".
    • (viii) Search the dictionary, and assign the number of the corresponding dictionary entry to entry.
    • (ix) Read the next character "e", giving the extended string "use".
    • (x) Search the dictionary for "use", which is not present.
    • (xi) Transmit entry the index number of string "us".
    • (xii) Add the string "mo" + "us" to the dictionary.
    • (xiii) Start again with the unmatched "e".
    • (xiv) Read the next character ......
  • Several other aspects of the algorithm need definition or modification before a suitable real time implementation is achieved. These relate to the means by which the dictionary is constructed, the associated algorithm, and storage recovery.
    Many means for implementing the type of dictionary structure defined above are known. Knuth (1968) discusses some of these, others are of more recent origin. Two particular schemes will be outlined briefly:
    • (i) Trie structure
  • The above cited application on the modified Ziv Lempel algorithm discusses a trie structure [3] suitable for this application. This has been shown to provide a sufficiently fast method for application in modems. The scheme uses a linked list to represent the alternative characters for a given position in a string, and occupies approximately 7 bytes per dictionary entry.
    • (ii) Hashing
  • The use of hashing or scatter storage to speed up searching has been known for many years [4-6]. The principle is that a mathematical function is applied to the item to be located, in our case a string, which generates an address. Ideally, there would be a one-to-one correspondence between stored items and hashed adresses, in which case searching would simply consist of applying the hashing function and looking up the appropriate entry. In practice, the same address may be generated by several different data sets, collision, and hence some searching is involved in locating the desired items.
  • The key factor in the modified Mayne algorithm (and in fact in the modified Ziv Lempel algorithm) is that a specific searching technique does not need to be used. As long as the process for assigning new dictionary entries is well defined, an encoder using the trie technique can interwork with a decoder using hashing. The memory requirements are similar for both techniques.
  • Storage recovery is discussed in more detail in Section 4, in which a more efficient alternative to that described by Mayne is discussed.
    • 3. Decoding
  • The decoder receives codewords from the encoder, recovers the string of characters represented by the codeword by using an equivalent tree structure to the encoder, and outputs them. It treats the decoded strings as alternately prefix and suffix strings, and updates its dictionary in the same way as the encoder.
    It is interesting to note that the Kw problem described in reference [7] does not occur in the Mayne algorithm. This problem occurs in the Ziv Lempel implementations of Welch, and Miller and Wegman, because the encoder is able to update its dictionary one step ahead of the decoder.
    Figure imgb0002
    • 4. Dictionary maintenance 4.a Dictionary updating
  • The encoder's dictionary is updated after each suffix string is encoded, and the decoder performs a similar function. New dictionary entries are assigned sequentially until the dictionary is full, thereafter they are recovered in a manner described below in section 4.b.
    The dictionary contains an initial character set, and a small number of dedicated codewords for control applications, the remainder of the dictionary space being allocated for string storage. The first entry assigned is the first dictionary entry following the control codewords.
    Each dictionary entry consists of a pointer and a character (see for example reference 3), and is linked to a parent entry in the general form shown in section 2. Creating a new entry consists of writing the character and appropriate link pointers into the memory locations allocated to the entry (see reference 6 for an example).
    • 4.b Storage recovery
  • As the dictionary fills up it is necessary to recover some storage in order that the encoder may be continually adapting to changes in the data stream. The principal described in reference 6 has been applied to the modified Mayne algorithm, as it requires little processing overhead, and no additional storage.
    When the dictionary is full entries are recovered by scanning the string storage area of the dictionary in simple sequential order. If an entry is a leaf, i.e. is the last character in a string, it is deleted. The search for the next entry to be deleted will begin with the entry after the last one recovered. The storage recovery process is invoked after a new entry has been created, rather than before, this prevents inadvertent deletion of the matched entry.
    • 5. Automatic Transparency
  • Not all data is compressible, and even compressible files can contain short periods of uncompressible data. It is desirable therefore that the data compression function can automatically detect loss of efficiency, and can revert to non-compressed or transparent operation. This should be done without affecting normal throughput if possible.
  • There are two modes of operation, transparent mode, and compressed mode.
    • (i) Transparent mode (a) Encoder
  • The encoder accepts characters from the DTE interface, and passes them on in uncompressed form. The normal encoding process is however maintained, and the encoder dictionary updated, as described above. Thus the encoder dictionary can be adapting to changing data characteristics even when in transparent mode.
    • (b) Decoder
  • The decoder accepts uncompressed characters from the encoder, passes the characters through to the DTE interface, and performs the equivalent string matching function. Thus the decoder actually contains a copy of the encoder function.
    • (c) Transition from transparent mode
  • The encoder and decoder maintain a count of the number of characters processed, and the number of bits that these would have encoded in, if compression had been on. As both encoder and decoder perform the same operation of string matching, this is a simple process. After each dictionary character count is tested. When the count exceeds a threshold, axf_delay, the compression ratio is calculated. If the compression ratio is greater than 1, compression is turned ON and the encoder and decoder enter the compressed mode.
    • (ii) Compressed mode (a) Encoder
  • The encoder employs the string matching process described above to compress the character stream read from the DTE interface, and sends the compressed data stream to the decoder.
    • (b) Decoder
  • The decoder employs the decoding process described in Section 3 to recover character strings from received codewords.
    • (c) Transition to transparent mode
  • The encoder arbitrarily tests its effectiveness, or the compressibility of the data stream, possibly using the test described above. When it appears that the effectiveness of the encoding process is impaired the encoder transmits an explicit codeword to the decoder to indicate a transition to compressed mode. Data from that point on is sent in transparent form, until the test described in (1) indicates that the system should revert to compressed mode.
    The encoder and decoder revert to prefix mode after switching to transparent mode.
    • 6. Operation on DTE timeout, end of frame, or end of message
  • A flush operation is provided to ensure that any data remaining in the encoder is transmitted. this is needed as there is a bit oriented element to the encoding and decoding process which is able to store fragments of one byte. The next data to be transmitted will therefore start on a byte boundary. When this operation is used, which can only be in compressed mode, an explicit codeword is sent to permit the decoder to realign its bit oriented process. This is used in the following way:-
    • (a) DTE timeout
  • When a DTE timeout or some similar condition occurs, it is necessary to terminate any string matching process and flush the encoder. The steps involved are .. exit from string matching process, send codeword corresponding to partially matched string, send FLUSHED codeword and flush buffer.
    • (b) End of Buffer
  • At the end of a buffer the flush process is not used, unless there is no more data to be sent. The effect of this is to allow codewords to cross frame boundaries. If there is no more data to be sent, the action defined in (a) is taken.
    • (c) End of message
  • The process described in (a) is carried out.
    • 7. Examples
  • Figure imgb0003
    Figure imgb0004
    Figure imgb0005
    • 8. Implementation aspects
  • The algorithm is comparable in complexity to the modified Ziv Lempel algorithm. The memory requirement is 2 bytes per dictionary entry for the first 260 dictionary entries, and 7 bytes per entry thereafter giving, for each of the encoder and decoder dictionaries:-
    1024 entries: 6k bytes
    2048 entries: 13k bytes
    4096 entries: 27 kbytes
  • Processing speed is very fast. For operation at speeds up to 38.4 kbits over a 9.6 kbit link only a Z80 family processor should be required.
  • Response time is minimized through the use of a timeout codeword, which permits the encoder to detect intermittent traffic (i.e. keyboard operation) and transmit a partially matched string. This mechanism does not interfere with operation under conditions of continuous data flow, when compression efficiency is maximized.
    • 9. Summary
  • The algorithm described above is ideally suited to the modem environment, as it provides a high degree of compression but may be implemented on a simple inexpensive microprocessor with a small amount of memory.
    A range of implementations are possible, alowing flexibility to the manufacturer in terms of speed, performance and cost. This realises the desire of some manufacturers to minimise implementation cost, and of others to provide top performance. The algorithm is however well defined and it is thus possible to ensure compatibility between different implementations.
    • References
    • [1] Information Compression by Factorizing Common Strings
      A. Mayne, E.B. James
      Computer Journal, Vol 18.2 pp 157 - 160, 1975
    • [2] Compression of Individual Sequences via Variable Rate Coding
      J. Ziv, A. Lempel
      IEEE Trans, IT 24.5, pp 530 = 536, 1978
    • [3] Use of Tree Structures for Processing Files
      E.H. Sussenguth
      CACM, Vol 6.5 pp 272 - 279, 1963
    • [4] The Art of Computer Programming, Vol 3 Sorting and Searching
      D. Knuth, Addison Wesley, 1968
    • [5] Scatter Storage Techniques
      R. Morris
      CACM, Vol 11.1 pp 38 - 44, 1968
    • [6] Technical Description of BTLZ
      British Telecom contribution to CCITT SGXVII
    • [7] A technique for High Performance Data Compression
      T Welch
      Computer, June 1984, pp 8 - 19

Claims (4)

1. A data compression system including a dynamically compiled dictionary, characterised in that the dictionary is updated by storing a string comprising a word and a part-word, the part-word comprising a plurality of characters from the string immediately following the word in the input data stream.
2. A system according to claim 1, in which the part-word comprises only two characters.
3. A system according to claim 1 or 2, in which the data compression system compresses data using a Mayne single-pass data compression algorithm.
4. A data compression system using the Mayne algorithm, in which during the updating of the dictionary after each string matching process the index for the corresponding dictionary entry is transmitted.
EP89312818A 1988-12-09 1989-12-08 Data compression Expired - Lifetime EP0375221B1 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
GB888828796A GB8828796D0 (en) 1988-12-09 1988-12-09 Data compression
GB8828796 1988-12-09

Publications (2)

Publication Number Publication Date
EP0375221A1 true EP0375221A1 (en) 1990-06-27
EP0375221B1 EP0375221B1 (en) 1996-02-28

Family

ID=10648248

Family Applications (1)

Application Number Title Priority Date Filing Date
EP89312818A Expired - Lifetime EP0375221B1 (en) 1988-12-09 1989-12-08 Data compression

Country Status (9)

Country Link
US (1) US5253325A (en)
EP (1) EP0375221B1 (en)
JP (1) JP2771324B2 (en)
AT (1) ATE134780T1 (en)
CA (1) CA2005048C (en)
DE (1) DE68925798T2 (en)
GB (1) GB8828796D0 (en)
HK (1) HK111197A (en)
WO (1) WO1990006560A1 (en)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0595064A3 (en) * 1992-10-29 1995-08-16 Ibm Method and means providing static dictionary structures for compressing character data and expanding compressed data
EP0698862A2 (en) * 1994-02-08 1996-02-28 International Business Machines Corporation Transmission compatibility using custom compression method and hardware
WO2000038049A1 (en) * 1998-12-22 2000-06-29 Systemonic Ag Device and method for generating and executing compressed programs of a very long instruction word processor
AU740957B2 (en) * 1997-10-21 2001-11-15 Fujitsu Limited File processing method, data processing apparatus and storage medium

Families Citing this family (138)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5455943A (en) * 1992-10-08 1995-10-03 Salient Software, Inc. Method and apparatus for finding longest and closest matching string in history buffer prior to current string
US5396595A (en) * 1992-04-24 1995-03-07 Spacelabs Medical, Inc. Method and system for compression and decompression of data
US5530957A (en) * 1992-08-07 1996-06-25 At&T Corp. Storing trees in navigable form
JP3522331B2 (en) * 1994-04-22 2004-04-26 株式会社セタ Data compression method
US5838963A (en) * 1995-10-25 1998-11-17 Microsoft Corporation Apparatus and method for compressing a data file based on a dictionary file which matches segment lengths
US5861827A (en) * 1996-07-24 1999-01-19 Unisys Corporation Data compression and decompression system with immediate dictionary updating interleaved with string search
US5831560A (en) * 1996-09-20 1998-11-03 Sun Microsystems, Inc. S-table approach to data translation
US7898442B1 (en) 1997-05-30 2011-03-01 International Business Machines Corporation On-line data compression analysis and regulation
US6601104B1 (en) 1999-03-11 2003-07-29 Realtime Data Llc System and methods for accelerated data storage and retrieval
US8645137B2 (en) 2000-03-16 2014-02-04 Apple Inc. Fast, language-independent method for user authentication by voice
US8692695B2 (en) 2000-10-03 2014-04-08 Realtime Data, Llc Methods for encoding and decoding data
US9143546B2 (en) 2000-10-03 2015-09-22 Realtime Data Llc System and method for data feed acceleration and encryption
US7640362B2 (en) * 2001-01-31 2009-12-29 Interdigital Technology Corporation Adaptive compression in an edge router
US7386046B2 (en) 2001-02-13 2008-06-10 Realtime Data Llc Bandwidth sensitive data compression and decompression
RU2003131191A (en) * 2001-04-04 2005-04-20 Хонейвелл Интернэшнл Инк. (Us) DEVICE (OPTIONS) AND METHOD FOR UNPACKING DATA
US6683547B2 (en) * 2002-04-22 2004-01-27 Hughes Electronics Corporation Method and system for data compession with dictionary pre-load of a set of expected character strings
US20040267960A1 (en) * 2003-06-25 2004-12-30 International Business Machines Corporation Force master capability during multicast transfers
US7079051B2 (en) * 2004-03-18 2006-07-18 James Andrew Storer In-place differential compression
US20060106870A1 (en) * 2004-11-16 2006-05-18 International Business Machines Corporation Data compression using a nested hierarchy of fixed phrase length dictionaries
JP2007047412A (en) * 2005-08-09 2007-02-22 Toshiba Corp Apparatus and method for generating recognition grammar model and voice recognition apparatus
US8677377B2 (en) 2005-09-08 2014-03-18 Apple Inc. Method and apparatus for building an intelligent automated assistant
US9318108B2 (en) 2010-01-18 2016-04-19 Apple Inc. Intelligent automated assistant
US8074172B2 (en) 2007-01-05 2011-12-06 Apple Inc. Method, system, and graphical user interface for providing word recommendations
US8977255B2 (en) 2007-04-03 2015-03-10 Apple Inc. Method and system for operating a multi-function portable electronic device using voice-activation
US9330720B2 (en) 2008-01-03 2016-05-03 Apple Inc. Methods and apparatus for altering audio output signals
US8232973B2 (en) 2008-01-09 2012-07-31 Apple Inc. Method, device, and graphical user interface providing word recommendations for text input
US8996376B2 (en) 2008-04-05 2015-03-31 Apple Inc. Intelligent text-to-speech conversion
US10496753B2 (en) 2010-01-18 2019-12-03 Apple Inc. Automatically adapting user interfaces for hands-free interaction
US20100030549A1 (en) 2008-07-31 2010-02-04 Lee Michael M Mobile device having human language translation capability with positional feedback
US9959870B2 (en) 2008-12-11 2018-05-01 Apple Inc. Speech recognition involving a mobile device
US20100235780A1 (en) * 2009-03-16 2010-09-16 Westerman Wayne C System and Method for Identifying Words Based on a Sequence of Keyboard Events
US20120309363A1 (en) 2011-06-03 2012-12-06 Apple Inc. Triggering notifications associated with tasks items that represent tasks to perform
US9858925B2 (en) 2009-06-05 2018-01-02 Apple Inc. Using context information to facilitate processing of commands in a virtual assistant
US10241644B2 (en) 2011-06-03 2019-03-26 Apple Inc. Actionable reminder entries
US10241752B2 (en) 2011-09-30 2019-03-26 Apple Inc. Interface for a virtual digital assistant
US9431006B2 (en) 2009-07-02 2016-08-30 Apple Inc. Methods and apparatuses for automatic speech recognition
US10705794B2 (en) 2010-01-18 2020-07-07 Apple Inc. Automatically adapting user interfaces for hands-free interaction
US10679605B2 (en) 2010-01-18 2020-06-09 Apple Inc. Hands-free list-reading by intelligent automated assistant
US10276170B2 (en) 2010-01-18 2019-04-30 Apple Inc. Intelligent automated assistant
US10553209B2 (en) 2010-01-18 2020-02-04 Apple Inc. Systems and methods for hands-free notification summaries
US8977584B2 (en) 2010-01-25 2015-03-10 Newvaluexchange Global Ai Llp Apparatuses, methods and systems for a digital conversation management platform
US8682667B2 (en) 2010-02-25 2014-03-25 Apple Inc. User profiling for selecting user specific voice input processing information
US10762293B2 (en) 2010-12-22 2020-09-01 Apple Inc. Using parts-of-speech tagging and named entity recognition for spelling correction
US9262612B2 (en) 2011-03-21 2016-02-16 Apple Inc. Device access using voice authentication
US10057736B2 (en) 2011-06-03 2018-08-21 Apple Inc. Active transport based notifications
US8994660B2 (en) 2011-08-29 2015-03-31 Apple Inc. Text correction processing
US10134385B2 (en) 2012-03-02 2018-11-20 Apple Inc. Systems and methods for name pronunciation
US9483461B2 (en) 2012-03-06 2016-11-01 Apple Inc. Handling speech synthesis of content for multiple languages
US8930813B2 (en) * 2012-04-03 2015-01-06 Orlando McMaster Dynamic text entry/input system
US9280610B2 (en) 2012-05-14 2016-03-08 Apple Inc. Crowd sourcing information to fulfill user requests
US9721563B2 (en) 2012-06-08 2017-08-01 Apple Inc. Name recognition system
US9495129B2 (en) 2012-06-29 2016-11-15 Apple Inc. Device, method, and user interface for voice-activated navigation and browsing of a document
US9576574B2 (en) 2012-09-10 2017-02-21 Apple Inc. Context-sensitive handling of interruptions by intelligent digital assistant
US9547647B2 (en) 2012-09-19 2017-01-17 Apple Inc. Voice-based media searching
AU2014214676A1 (en) 2013-02-07 2015-08-27 Apple Inc. Voice trigger for a digital assistant
US9368114B2 (en) 2013-03-14 2016-06-14 Apple Inc. Context-sensitive handling of interruptions
WO2014144579A1 (en) 2013-03-15 2014-09-18 Apple Inc. System and method for updating an adaptive speech recognition model
US9922642B2 (en) 2013-03-15 2018-03-20 Apple Inc. Training an at least partial voice command system
WO2014197334A2 (en) 2013-06-07 2014-12-11 Apple Inc. System and method for user-specified pronunciation of words for speech synthesis and recognition
US9582608B2 (en) 2013-06-07 2017-02-28 Apple Inc. Unified ranking with entropy-weighted information for phrase-based semantic auto-completion
WO2014197336A1 (en) 2013-06-07 2014-12-11 Apple Inc. System and method for detecting errors in interactions with a voice-based digital assistant
WO2014197335A1 (en) 2013-06-08 2014-12-11 Apple Inc. Interpreting and acting upon commands that involve sharing information with remote devices
US10176167B2 (en) 2013-06-09 2019-01-08 Apple Inc. System and method for inferring user intent from speech inputs
EP3937002A1 (en) 2013-06-09 2022-01-12 Apple Inc. Device, method, and graphical user interface for enabling conversation persistence across two or more instances of a digital assistant
KR101809808B1 (en) 2013-06-13 2017-12-15 애플 인크. System and method for emergency calls initiated by voice command
US10791216B2 (en) 2013-08-06 2020-09-29 Apple Inc. Auto-activating smart responses based on activities from remote devices
US9977802B2 (en) * 2013-11-21 2018-05-22 Sap Se Large string access and storage
US9977801B2 (en) 2013-11-21 2018-05-22 Sap Se Paged column dictionary
US10235377B2 (en) 2013-12-23 2019-03-19 Sap Se Adaptive dictionary compression/decompression for column-store databases
US9620105B2 (en) 2014-05-15 2017-04-11 Apple Inc. Analyzing audio input for efficient speech and music recognition
US10592095B2 (en) 2014-05-23 2020-03-17 Apple Inc. Instantaneous speaking of content on touch devices
US9502031B2 (en) 2014-05-27 2016-11-22 Apple Inc. Method for supporting dynamic grammars in WFST-based ASR
US9715875B2 (en) 2014-05-30 2017-07-25 Apple Inc. Reducing the need for manual start/end-pointing and trigger phrases
US9734193B2 (en) 2014-05-30 2017-08-15 Apple Inc. Determining domain salience ranking from ambiguous words in natural speech
US9760559B2 (en) 2014-05-30 2017-09-12 Apple Inc. Predictive text input
US10078631B2 (en) 2014-05-30 2018-09-18 Apple Inc. Entropy-guided text prediction using combined word and character n-gram language models
US10170123B2 (en) 2014-05-30 2019-01-01 Apple Inc. Intelligent assistant for home automation
US9785630B2 (en) 2014-05-30 2017-10-10 Apple Inc. Text prediction using combined word N-gram and unigram language models
US9842101B2 (en) 2014-05-30 2017-12-12 Apple Inc. Predictive conversion of language input
US9633004B2 (en) 2014-05-30 2017-04-25 Apple Inc. Better resolution when referencing to concepts
US10289433B2 (en) 2014-05-30 2019-05-14 Apple Inc. Domain specific language for encoding assistant dialog
US9430463B2 (en) 2014-05-30 2016-08-30 Apple Inc. Exemplar-based natural language processing
TWI566107B (en) 2014-05-30 2017-01-11 蘋果公司 Method for processing a multi-part voice command, non-transitory computer readable storage medium and electronic device
US9338493B2 (en) 2014-06-30 2016-05-10 Apple Inc. Intelligent automated assistant for TV user interactions
US10659851B2 (en) 2014-06-30 2020-05-19 Apple Inc. Real-time digital assistant knowledge updates
US10446141B2 (en) 2014-08-28 2019-10-15 Apple Inc. Automatic speech recognition based on user feedback
US9818400B2 (en) 2014-09-11 2017-11-14 Apple Inc. Method and apparatus for discovering trending terms in speech requests
US10789041B2 (en) 2014-09-12 2020-09-29 Apple Inc. Dynamic thresholds for always listening speech trigger
US9668121B2 (en) 2014-09-30 2017-05-30 Apple Inc. Social reminders
US9886432B2 (en) 2014-09-30 2018-02-06 Apple Inc. Parsimonious handling of word inflection via categorical stem + suffix N-gram language models
US10127911B2 (en) 2014-09-30 2018-11-13 Apple Inc. Speaker identification and unsupervised speaker adaptation techniques
US10074360B2 (en) 2014-09-30 2018-09-11 Apple Inc. Providing an indication of the suitability of speech recognition
US9646609B2 (en) 2014-09-30 2017-05-09 Apple Inc. Caching apparatus for serving phonetic pronunciations
US10552013B2 (en) 2014-12-02 2020-02-04 Apple Inc. Data detection
US9711141B2 (en) 2014-12-09 2017-07-18 Apple Inc. Disambiguating heteronyms in speech synthesis
US9865280B2 (en) 2015-03-06 2018-01-09 Apple Inc. Structured dictation using intelligent automated assistants
US9886953B2 (en) 2015-03-08 2018-02-06 Apple Inc. Virtual assistant activation
US9721566B2 (en) 2015-03-08 2017-08-01 Apple Inc. Competing devices responding to voice triggers
US10567477B2 (en) 2015-03-08 2020-02-18 Apple Inc. Virtual assistant continuity
US9899019B2 (en) 2015-03-18 2018-02-20 Apple Inc. Systems and methods for structured stem and suffix language models
US9842105B2 (en) 2015-04-16 2017-12-12 Apple Inc. Parsimonious continuous-space phrase representations for natural language processing
US10083688B2 (en) 2015-05-27 2018-09-25 Apple Inc. Device voice control for selecting a displayed affordance
US10127220B2 (en) 2015-06-04 2018-11-13 Apple Inc. Language identification from short strings
US10101822B2 (en) 2015-06-05 2018-10-16 Apple Inc. Language input correction
US11025565B2 (en) 2015-06-07 2021-06-01 Apple Inc. Personalized prediction of responses for instant messaging
US10186254B2 (en) 2015-06-07 2019-01-22 Apple Inc. Context-based endpoint detection
US10255907B2 (en) 2015-06-07 2019-04-09 Apple Inc. Automatic accent detection using acoustic models
US10747498B2 (en) 2015-09-08 2020-08-18 Apple Inc. Zero latency digital assistant
US10671428B2 (en) 2015-09-08 2020-06-02 Apple Inc. Distributed personal assistant
US9697820B2 (en) 2015-09-24 2017-07-04 Apple Inc. Unit-selection text-to-speech synthesis using concatenation-sensitive neural networks
US10366158B2 (en) 2015-09-29 2019-07-30 Apple Inc. Efficient word encoding for recurrent neural network language models
US11010550B2 (en) 2015-09-29 2021-05-18 Apple Inc. Unified language modeling framework for word prediction, auto-completion and auto-correction
US11587559B2 (en) 2015-09-30 2023-02-21 Apple Inc. Intelligent device identification
US10691473B2 (en) 2015-11-06 2020-06-23 Apple Inc. Intelligent automated assistant in a messaging environment
US10169361B2 (en) 2015-11-16 2019-01-01 International Business Machines Corporation Columnar database compression
US10049668B2 (en) 2015-12-02 2018-08-14 Apple Inc. Applying neural network language models to weighted finite state transducers for automatic speech recognition
US10223066B2 (en) 2015-12-23 2019-03-05 Apple Inc. Proactive assistance based on dialog communication between devices
US10446143B2 (en) 2016-03-14 2019-10-15 Apple Inc. Identification of voice inputs providing credentials
US9934775B2 (en) 2016-05-26 2018-04-03 Apple Inc. Unit-selection text-to-speech synthesis based on predicted concatenation parameters
US9972304B2 (en) 2016-06-03 2018-05-15 Apple Inc. Privacy preserving distributed evaluation framework for embedded personalized systems
US10249300B2 (en) 2016-06-06 2019-04-02 Apple Inc. Intelligent list reading
US10049663B2 (en) 2016-06-08 2018-08-14 Apple, Inc. Intelligent automated assistant for media exploration
DK179588B1 (en) 2016-06-09 2019-02-22 Apple Inc. Intelligent automated assistant in a home environment
US10192552B2 (en) 2016-06-10 2019-01-29 Apple Inc. Digital assistant providing whispered speech
US10067938B2 (en) 2016-06-10 2018-09-04 Apple Inc. Multilingual word prediction
US10490187B2 (en) 2016-06-10 2019-11-26 Apple Inc. Digital assistant providing automated status report
US10586535B2 (en) 2016-06-10 2020-03-10 Apple Inc. Intelligent digital assistant in a multi-tasking environment
US10509862B2 (en) 2016-06-10 2019-12-17 Apple Inc. Dynamic phrase expansion of language input
DK179343B1 (en) 2016-06-11 2018-05-14 Apple Inc Intelligent task discovery
DK179049B1 (en) 2016-06-11 2017-09-18 Apple Inc Data driven natural language event detection and classification
DK201670540A1 (en) 2016-06-11 2018-01-08 Apple Inc Application integration with a digital assistant
DK179415B1 (en) 2016-06-11 2018-06-14 Apple Inc Intelligent device arbitration and control
US10593346B2 (en) 2016-12-22 2020-03-17 Apple Inc. Rank-reduced token representation for automatic speech recognition
DK179745B1 (en) 2017-05-12 2019-05-01 Apple Inc. SYNCHRONIZATION AND TASK DELEGATION OF A DIGITAL ASSISTANT
DK201770431A1 (en) 2017-05-15 2018-12-20 Apple Inc. Optimizing dialogue policy decisions for digital assistants using implicit feedback
CN108563796A (en) * 2018-05-04 2018-09-21 蔷薇信息技术有限公司 Data compressing method, device and the electronic equipment of block chain
US11122095B2 (en) 2019-09-23 2021-09-14 Netapp, Inc. Methods for dictionary-based compression and devices thereof
CN118381513A (en) * 2024-06-21 2024-07-23 上海禹创智能科技有限公司 Data compression transmission method based on data object

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0127815A2 (en) * 1983-06-01 1984-12-12 International Business Machines Corporation Data compression method
EP0280549A2 (en) * 1987-02-25 1988-08-31 Oki Electric Industry Company, Limited Data compression method and apparatus

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4876541A (en) * 1987-10-15 1989-10-24 Data Compression Corporation Stem for dynamically compressing and decompressing electronic data
GB8815978D0 (en) * 1988-07-05 1988-08-10 British Telecomm Method & apparatus for encoding decoding & transmitting data in compressed form

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0127815A2 (en) * 1983-06-01 1984-12-12 International Business Machines Corporation Data compression method
EP0280549A2 (en) * 1987-02-25 1988-08-31 Oki Electric Industry Company, Limited Data compression method and apparatus

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
COMPUTER JOURNAL, vol. 18, no. 2, 1975, pages 157-160; A. MAYNE et al.: "Information compression by factorising common strings" *
PROC. VERY LARGE DATABASES, Cannes, 9th - 11th September 1981, pages 435-447, IEEE, New York, US; C.A. LYNCH et al.: "Application of data compression techniques to a large bibliographic database" *

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0595064A3 (en) * 1992-10-29 1995-08-16 Ibm Method and means providing static dictionary structures for compressing character data and expanding compressed data
EP0698862A2 (en) * 1994-02-08 1996-02-28 International Business Machines Corporation Transmission compatibility using custom compression method and hardware
EP0698862A3 (en) * 1994-02-08 1996-04-03 Ibm
AU740957B2 (en) * 1997-10-21 2001-11-15 Fujitsu Limited File processing method, data processing apparatus and storage medium
WO2000038049A1 (en) * 1998-12-22 2000-06-29 Systemonic Ag Device and method for generating and executing compressed programs of a very long instruction word processor

Also Published As

Publication number Publication date
ATE134780T1 (en) 1996-03-15
JPH04502377A (en) 1992-04-23
CA2005048A1 (en) 1990-06-09
WO1990006560A1 (en) 1990-06-14
DE68925798T2 (en) 1996-09-19
CA2005048C (en) 1999-01-12
GB8828796D0 (en) 1989-01-18
DE68925798D1 (en) 1996-04-04
JP2771324B2 (en) 1998-07-02
EP0375221B1 (en) 1996-02-28
US5253325A (en) 1993-10-12
HK111197A (en) 1997-08-29

Similar Documents

Publication Publication Date Title
EP0375221B1 (en) Data compression
US6489902B2 (en) Data compression for use with a communications channel
US4906991A (en) Textual substitution data compression with finite length search windows
US5058144A (en) Search tree data structure encoding for textual substitution data compression systems
US5293379A (en) Packet-based data compression method
US5229768A (en) Adaptive data compression system
US5532694A (en) Data compression apparatus and method using matching string searching and Huffman encoding
JP3571079B2 (en) Data compression method and system
US5999949A (en) Text file compression system utilizing word terminators
US6121903A (en) On-the-fly data re-compression
US5239298A (en) Data compression
JP2863065B2 (en) Data compression apparatus and method using matching string search and Huffman coding, and data decompression apparatus and method
JPH0368219A (en) Data compressor and method of compressing data
JPH09121168A (en) Compressor, compressing method, expander and context serving device
JPS6356726B2 (en)
US5610603A (en) Sort order preservation method used with a static compression dictionary having consecutively numbered children of a parent
Bell A unifying theory and improvements for existing approaches to text compression
US6292115B1 (en) Data compression for use with a communications channel
EP0435802B1 (en) Method of decompressing compressed data
EP0340039B1 (en) Search tree data structure encoding for textual substitution data compression systems
US5564045A (en) Method and apparatus for string searching in a linked list data structure using a termination node at the end of the linked list
EP0340041B1 (en) Start, step, stop unary coding for data compression
US7580429B1 (en) System and methods for improving data compression
Yu Data compression for PC software distribution
Thomborson et al. Systolic implementations of a move-to-front text compressor

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE CH DE ES FR GB GR IT LI LU NL SE

17P Request for examination filed

Effective date: 19901217

17Q First examination report despatched

Effective date: 19930628

GRAH Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOS IGRA

GRAA (expected) grant

Free format text: ORIGINAL CODE: 0009210

AK Designated contracting states

Kind code of ref document: B1

Designated state(s): AT BE CH DE ES FR GB GR IT LI LU NL SE

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: LI

Effective date: 19960228

Ref country code: GR

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 19960228

Ref country code: ES

Free format text: THE PATENT HAS BEEN ANNULLED BY A DECISION OF A NATIONAL AUTHORITY

Effective date: 19960228

Ref country code: CH

Effective date: 19960228

Ref country code: BE

Effective date: 19960228

Ref country code: AT

Effective date: 19960228

REF Corresponds to:

Ref document number: 134780

Country of ref document: AT

Date of ref document: 19960315

Kind code of ref document: T

ITF It: translation for a ep patent filed
REF Corresponds to:

Ref document number: 68925798

Country of ref document: DE

Date of ref document: 19960404

ET Fr: translation filed
REG Reference to a national code

Ref country code: CH

Ref legal event code: PL

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: LU

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 19961231

PLBE No opposition filed within time limit

Free format text: ORIGINAL CODE: 0009261

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: NO OPPOSITION FILED WITHIN TIME LIMIT

26N No opposition filed
PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: NL

Payment date: 20001123

Year of fee payment: 12

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: FR

Payment date: 20011112

Year of fee payment: 13

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: SE

Payment date: 20011116

Year of fee payment: 13

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: GB

Payment date: 20011119

Year of fee payment: 13

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: DE

Payment date: 20011126

Year of fee payment: 13

REG Reference to a national code

Ref country code: GB

Ref legal event code: IF02

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: NL

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20020701

NLV4 Nl: lapsed or anulled due to non-payment of the annual fee

Effective date: 20020701

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: GB

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20021208

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: SE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20021209

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: DE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20030701

EUG Se: european patent has lapsed
GBPC Gb: european patent ceased through non-payment of renewal fee
PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: FR

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20030901

REG Reference to a national code

Ref country code: FR

Ref legal event code: ST

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: IT

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20051208

OSZAR »