Back to EveryPatent.com
United States Patent | 5,663,721 |
Rossi | September 2, 1997 |
A data compression algorithm in which a word is assigned a code value according to the frequency of the word occurring, for example, in the English language. The code value contains a length field and a code field. The number of bits used to represent the length field is fixed, whereas the length of the code field is variable. The code field can be assigned values between 0b0 and 0b11111111111111. The value 0b0 is assigned for the word having the greatest probability of occurring and the value 0b11111111111111 is assigned for the word having the least probability of occurring. The value of the length field is equal to the number of bits contained in the code field. The code values are stored in a dictionary with their corresponding words. If it is determined that an input word does not exist in the dictionary, then the length field is assigned the value 0b0000 and the word is represented in its ASCII code. Examples of dictionaries that can be used with the compression algorithm are the English dictionary, Spanish dictionary, German dictionary, a dictionary for engineering applications, a dictionary for lawyers, and a dictionary for bioscientists.
Inventors: | Rossi; Markku J. (Houston, TX) |
Assignee: | Compaq Computer Corporation (Houston, TX) |
Appl. No.: | 407195 |
Filed: | March 20, 1995 |
Current U.S. Class: | 341/51; 341/67; 341/95; 341/106; 341/107 |
Intern'l Class: | H03M 007/42 |
Field of Search: | 341/51,65,67,95,106,107 |
4396906 | Aug., 1983 | Weaver | 340/347. |
4862167 | Aug., 1989 | Copeland, III | 341/107. |
4876541 | Oct., 1989 | Storer | 341/51. |
4899148 | Feb., 1990 | Sato et al. | 341/65. |
5034742 | Jul., 1991 | Bond et al. | 341/67. |
J. Ziv & A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, vol. 23, No. 3, May 1977, pp. 337-343. J. Ziv. & A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding," IEEE Transactions on Information Theory, vol. 24, No. 5, Sep. 1978, pp. 530-536. Donald E. Knuth, "Sorting and Searching," The Art of Computer Programming, vol. 3, pp. 506-542, 1973. Terry A. Welch, "A Technique for High-Performance Data Compression," Computer, pp. 8-19. Ross N. Williams, "An Extremely Fast ZIV-Lempel Data Compression Algorithm," Data Compression Conference, 1991, pp. 362-371. Recommendation V.42 bis, "Data Compression Procedures for Data Circuit Terminating Equipment (DCE) Using Error Correcting Procedures," The International Telegraph and Telephone Consultative Committee, 1990, pp. 1-27. |