Data compression method and apparatus performing high-speed comparison between data stored in a dictionary window and data to be compressed

• US 5,936,560 A
• Filed: 07/18/1997
• Issued: 08/10/1999
• Est. Priority Date: 12/24/1996
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Fujitsu Limited
• Inventors: Higuchi, Taihoh
• Primary Examiner(s): Young, Brian
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US08/896,658
• Time in Patent Office: 753 Days
• Field of Search: 341/50, 341/51, 341/60, 341/63, 341/106, 341/65
• US Class Current: 341/106
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A dictionary window storing a history of data to be compressed is compared with data to be compressed, and, when a data match is found, a code indicating a length of the data match and a code indicating a relative position of data in the dictionary window that produced the data match are generated. In the comparison, m groups of data in the dictionary window, each of the m groups including a total of n data, are compared substantially simultaneously with a total of n data in the data to be compressed, where m=2, 3, . . . and n=2, 3, . . . , and the compressed data is generated by encoding the data that produced the longest data match.

Claims

1. A data compression method for generating compressed data by comparing a dictionary window, storing a history of data to be compressed, with said data to be compressed and by generating, when a data match is found, a code indicating a length of the data match and a code indicating a relative position of data in said dictionary window that produced the data match, comprising the steps of:

a) comparing m groups of data in said dictionary window, each of the m groups comprising a total of n data, with a total of n data in said data to be compressed substantially simultaneously, where m=2, 3, . . . and n=2, 3, . . . ; and

b) generating said compressed data by encoding data that produced a longest data match as a result of step a).

2. The data compression method as claimed in claim 1, wherein step a) further comprises:

c) incrementing n to n1, where n1=3, 4, . . . , when a n-data match is found; and

d) comparing m groups of data in said dictionary window, each of the m groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

3. The data compression method as claimed in claim 2, where step a) further comprises:

e) decrementing m to m1, where m1=1, 2, . . . , when the n-data match is found; and

f) comparing m1 groups of data in said dictionary window, each of the m1 groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

4. The data compression method as claimed in claim 3, wherein step a) further comprises:

g) incrementing n to i×

n and decrementing m to m/i when the n-data match is found, where i=2, 3, . . . ; and

h) comparing m/i groups of data in said dictionary window, each of the m/i groups comprising a total of i×

n data, with a total of i×

n data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

5. A data compression method based on the LZ77 method invented by Lampel and Ziv, the improvement comprising the steps of:

a) comparing m groups of data in a dictionary window, each of the m groups comprising a total of n data, with a total of n data in said data to be compressed substantially simultaneously, where m=2, 3, . . . and n=2, 3, . . ; and

b) generating said compressed data by encoding data that produced a longest data match as a result of step a).

6. The data compression method as claimed in claim 5, wherein said total of n data is n bytes, and a 1-byte shift occurs from group to group in said m groups of n data in said dictionary window.

7. The data compression method as claimed in claim 5, wherein said total of n data in said data to be compressed is a total of n bytes and said total of n data in each of the m groups is a total of n bytes, a shift of one byte being provided from one group to another.

8. A data compression apparatus for generating compressed data comprising:

comparing means for comparing a dictionary window storing a history of data to be compressed with said data to be compressed, said comparing means being provided with a plurality of comparison circuits for comparing m groups of data in said dictionary window, each of the m groups comprising a total of n data, with a total of n data in said data to be compressed substantially simultaneously, where m=2, 3 . . . and n=2, 3, . . . ; and

processing means for generating, when a data match is found, a code indicating a length of the data match and a code indicating a relative position of data in said dictionary window that produced the data match, said processing means being provided with generating means for generating said compressed data by encoding data that produced a longest data match as a result of a comparison by said comparing means.

9. The data compression apparatus as claimed in claim 8, wherein:

said comparing means further comprises incrementing means for incrementing n to n1, where n1=3, 4, . . . , when a n-data match is found; and

said plurality of comparison circuits compare m groups of data in said dictionary window, each of the m groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

10. The data compression apparatus as claimed in claim 9, wherein:

said comparing means further comprises decrementing means for decrementing m to m1, where m1=1, 2, . . . , when the n-data match is found; and

said plurality of comparison circuits compare m1 groups of data in said dictionary window, each of the m1 groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data is found.

11. The data compressing apparatus as claimed in claim 10, wherein:

said comparing means further comprises incrementing and decrementing means for incrementing n to i×

n and decrementing m to m/i when n-data match is found, where i=2, 3, . . . ; and

said plurality of comparison circuits compare m/i groups of data in said dictionary window, each of the m/i groups comprising a total of i×

n data, with a total of i×

n data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

12. A data compression apparatus for generating compressed data based on the LZ77 method invented by Lampel and Ziv, the improvement comprising:

comparing means for comparing a dictionary window storing a history of data to be compressed with data to be compressed; and

processing means for generating, when a data match is found, a code indicating a length of the data match and a code indicating a relative position of data in said dictionary window that produced the data match;

wherein

said comparing means further comprises a plurality of comparison circuits for comparing m groups of data in said dictionary window, each of the m groups comprising a total of n data, with a total of n data in said data to be compressed substantially simultaneously, where m=2, 3, . . . and n=2, 3, . . . ; and

said processing means further comprises generating means for generating said compressed data by encoding data that produced a longest data match as a result of a comparison by said comparing means.

13. The data compression apparatus as claimed in claim 12, wherein said total of n data in said data to be compressed is a total of n bytes and said total of n data in each of the m groups is a total of n bytes, a shift of one byte being provided from one group to another.

14. A data compression method for generating compressed data, comprising:

comparing a dictionary window, storing a history of data to be compressed, with said data to be compressed in accordance with comparing m groups of data in said dictionary window, each of the m groups comprising a total of n data, with a total of n data in said data to be compressed substantially simultaneously, where m=2, 3, . . . and n=2, 3, . . . ; and

generating, when a data match is found, a code indicating a length of the data match and a code indicating a relative position of data in said dictionary window that produced the data match, and generating said compressed data by encoding data that produced a longest data match as a result of the comparing step.

15. The data compression method as claimed in claim 14, wherein step a) further comprises:

c) incrementing n to n1, where n1=3, 4, . . . , when a n-data match is found; and

d) comparing m groups of data in said dictionary window, each of the m groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

16. The data compression method as claimed in claim 15, where step a) further comprises:

e) decrementing m to m1, where m1=1, 2, . . . , when the n-data match is found; and

f) comparing m1 groups of data in said dictionary window, each of the m1 groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

17. The data compression method as claimed in claim 16, wherein step a) further comprises:

g) incrementing n to i×

n and decrementing m to m/i when the n-data match is found, where i=2, 3, . . . ; and

h) comparing m/i groups of data in said dictionary window, each of the m/i groups comprising a total of i×

n data, with a total of i×

n data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

18. A data compression apparatus, comprising:

a comparator comparing a dictionary window storing a history of data to be compressed with data to be compressed, said comparator further comprising a plurality of comparator circuits substantially simultaneously comparing m groups of data in said dictionary window, each of the m groups comprising a total of n data, with a total of n data in said data to be compressed, where m=2, 3, . . . and n=2, 3, . . ; and

a processor generating, when a data match is found, a code indicating a length of the data match and a code indicating a relative position of data in said dictionary window that produced the data match, said processor further comprising a generator generating compressed data by encoding data that produced a longest data match as a result of the comparison by said comparator.

19. The data compression apparatus as claimed in claim 18, wherein:

said comparator further comprises an incrementing unit incrementing n to n1, where n1=3, 4, . . . , when a n-data match is found; and

said plurality of comparator circuits compare m groups of data in said dictionary window, each of the m groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

20. The data compression apparatus as claimed in claim 19, wherein:

said comparator further comprises a decrementing unit decrementing m to m1, where m1=1, 2, . . . , when the n-data match is found; and

said plurality of comparator circuits compare m1 groups of data in said dictionary window, each of the m1 groups comprising a total of n1 data, with a total of n1 data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data is found.

21. The data compressing apparatus as claimed in claim 20, wherein:

said comparator further comprises an incrementing and decrementing unit incrementing n to i×

n and decrementing m to m/i when n-data match is found, where i=2, 3, . . . ; and

said plurality of comparator circuits compare m/i groups of data in said dictionary window, each of the m/i groups comprising a total of i×

n data, with a total of i×

n data in said data to be compressed substantially simultaneously, the comparison being started at a position in said dictionary window at which the n-data match is found.

22. A data compression method comprising:

a) comparing, substantially simultaneously, m groups of data in a dictionary window, each of the m groups comprising a total of n data, with a total of n data in data to be compressed, where m=2, 3, . . . and n=2, 3, ; and

b) identifying the compared data that produced longest data match as a result of step a); and

c) encoding the identified data and outputting same as compressed data.

23. The data compression method as claimed in claim 22, wherein said total of n data is n bytes, and a 1-byte shift occurs from group to group in said m groups of n data in said dictionary window.

24. The data compression method as claimed in claim 22, wherein said total of n data in said data to be compressed is a total of n bytes and said total of n data in each of the m groups is a total of n bytes, a shift of one byte being provided from one group to another.

25. A data compression apparatus, comprising:

a comparator comparing, substantially simultaneously, m groups of data in a dictionary window, each of the m groups comprising a total of n data, with a total of n data in data to be compressed, where m=2, 3, . . . and n=2, 3, . . . ;

an identifying unit identifying the compared data that produced a longest data match as a result of the comparing by the comparator; and

an encoder encoding the identified, compared data that produced the longest data match and outputting same as compressed data.

26. The data compression apparatus as claimed in claim 25, wherein said total of n data is n bytes, and a 1-byte shift occurs from group to group in said m groups of n data in said dictionary window.

27. The data compression apparatus as claimed in claim 25, wherein said total of n data in said data to be compressed is a total of n bytes and said total of n data in each of the m groups is a total of n bytes, a shift of one byte being provided from one group to another.