Method and apparatus for data compression utilizing efficient pattern discovery

• US 5,977,890 A
• Filed: 02/13/1998
• Issued: 11/02/1999
• Est. Priority Date: 06/12/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rigoutsos, Isidore, Floratos, Aristidis
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US09/023,759
• Time in Patent Office: 627 Days
• Field of Search: 341/50, 341/59, 341/51, 341/55, 341/60, 341/107, 341/106, 341/63, 707/101, 382/181, 382/209
• US Class Current: 341/55
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

The method of the present invention discovers patterns in an sequence of characters in two phases. In a sampling phase, preferably proper templates corresponding to the sequence of characters are generated. Patterns are then generated corresponding to the templates and stored in memory. In a convolution phase, the patterns stored in memory are combined to identify a set of maximal patterns. A subset of the maximal patterns is selected. Compressed data representing the sequence of characters is generated. The compressed data includes first data data representing each selected pattern of the subset, and second data representing the sequence of characters wherein occurrences of each selected pattern within the sequence of characters is replaced by a reference to first data corresponding to the selected pattern. The method is useful in compressing information stored in a database or compressing information communicated over a communication link.

Claims

1. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compression of a sequence of characters, said method steps comprising:

identifying a set of proper templates;

identifying a first set of patterns based on said set of proper templates and said sequence of characters, wherein each pattern within said first set of patterns is contained within said sequence of characters; and

combining patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters;

selecting a subset of said second set of patterns; and

generating compressed data representing said sequence of characters, said compressed data comprising first data and second data, said first data representing each selected pattern of said subset, and second data representing said sequence of characters wherein occurrences of each selected pattern within said sequence of characters is replaced by a reference to first data corresponding to the selected pattern.

2. The program storage device of claim 1, wherein said sequence of characters comprise data stored in a database, and said method steps further comprise storing said compressed data in said database.

3. The program storage device of claim 1, wherein said sequence of characters comprise data that is to be communicated from a first network device to a second network device over a communication link, and said method steps further comprise communicating said compressed data from said first network device to said second network device over said communication network.

4. The program storage device of claim 1, wherein said second set of patterns is non-redundant.

5. The program storage device of claim 1, wherein said second set of patterns comprise a set of all non-redundant patterns contained within said sequence of characters.

6. The program storage device of claim 1, wherein each pattern within said second set of patterns satisfies a predetermined criterion.

7. The program storage device of claim 6, wherein said predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.

8. The program storage device of claim 6, wherein said predetermined criterion comprises one of a minimum length and a maximum length.

9. The program storage device of claim 1, further comprising the step of reporting a subset of said second set of patterns to a user via an input/output device.

10. The program storage device of claim 1, wherein each template within said proper set of proper templates is defined by data representing a sequence of characters over an alphabet {0,1}.

11. The program storage device of claim 1, wherein each pattern is associated with a first field that identifies characters of said pattern.

12. The program storage device of claim 1, wherein each pattern is associated with a an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of characters of said pattern within said sequence of characters.

13. The program storage device of claim 1, wherein convolvable patterns within said first set of patterns are combined to form said second set of patterns.

14. The program storage device of claim 13, further comprising the step of identifying a third set of patterns within said second set of patterns, wherein each pattern within said third set satisfies a predetermined criterion, and wherein the selecting step selects a subset of said third set of patterns.

15. The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is greater than a predetermined minimum number of occurrences.

16. The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is less than a predetermined maximum number of occurrences.

17. The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern P has a length greater than a predetermined minimum length.

18. The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern has a length less than a predetermined maximum length.

19. The program storage device of claim 14, further comprising the step of reporting said third set of patterns to a user via an input/output device.

20. The program storage device of claim 14, wherein patterns within said first set of patterns that are convolvable under the operator ⊕

_R are combined to form said second set of patterns.

21. The program storage device of claim 14, further comprising the step of identifying a value L, and wherein patterns within said first set of patterns that are convolvable under the operator ⊕

_L-1 are combined to form said second set of patterns.

22. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compression of a sequence of characters, said method steps comprising:

identifying a first set of patterns, wherein each pattern within said first set of patterns is contained within said sequence of characters; and

combining convolvable patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters;

selecting a subset of said second set of patterns; and

generating compressed data representing said sequence of characters, said compressed data comprising first data and second data, said first data representing each selected pattern of said subset, and second data representing said sequence of characters wherein occurrences of each selected pattern within said sequence of characters is replaced by a reference to first data corresponding to the selected pattern.

23. The program storage device of claim 22, wherein said sequence of characters comprise data stored in a database, and said method steps further comprise storing said compressed data in said database.

24. The program storage device of claim 22, wherein said sequence of characters comprise data that is to be communicated from a first network device to a second network device over a communication link, and said method steps further comprise communicating said compressed data from said first network device to said second network device over said communication network.

25. The program storage device of claim 22, further comprising the step of:

identifying a third set of patterns within said second set of patterns, wherein each pattern within said third set satisfies a predetermined criterion, and wherein the selecting step selects a subset of said third set of patterns.

26. The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is greater than a predetermined minimum number of occurrences.

27. The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is less than a predetermined maximum number of occurrences.

28. The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern P has a length greater than a predetermined minimum length.

29. The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern has a length less than a predetermined maximum length.

30. The program storage device of claim 25, further comprising the step of reporting said third set of patterns to a user via an input/output device.

31. The program storage device of claim 22, wherein the combining step combines patterns that are convolvable under the operator ⊕

_R.

32. The program storage device of claim 31, further comprising the steps of:

i) storing at least one pattern belonging to said first set of patterns in a stack;

ii) selecting a pattern P stored in a top entry of said stack;

iii) identifying a set Q of patterns, wherein each pattern within said set Q is convolvable with said pattern P under said operator ⊕

_R ;

iv) ordering said set Q of patterns according to a predetermined ordering scheme;

v) traversing through said ordered set of patterns and determining whether a given pattern within said set of ordered patterns satisfies a first predetermined criterion; and

vi) if said given pattern satisfies said first predetermined criterion,

combining said given pattern with said pattern P to form a combined pattern,

storing said combined pattern as a top entry in said stack, and

returning to step ii) to process said combined pattern.

33. The program storage device of claim 32, wherein said first predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.

34. The program storage device of claim 33, wherein each pattern is associated with an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said pattern within said sequence of characters;

and

wherein number of occurrences of a pattern is determined by number of offset identifiers in said offset list associated with said pattern.

35. The program storage device of claim 32, wherein said first predetermined criterion comprises one of a minimum length and a maximum length.

36. The program storage device of claim 35, wherein each pattern is associated with a first field that identifies characters of said pattern;

wherein length of a pattern is determined by calculating number of characters in said first field associated with said pattern.

37. The program storage device of claim 32,

wherein each pattern is associated with a first field that identifies characters of said pattern and is associated with an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said pattern within said sequence of characters;

and

wherein, for a combined pattern corresponding to patterns P1 and Q1, said first field identifies characters of said patterns P1 and Q1 that make up said combined pattern, and said offset list comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said combined pattern within said sequence of characters.

38. The program storage device of claim 32, further comprising the steps of:

vi) if the set of ordered patterns is empty or no pattern within the ordered set of patterns satisfies said first predetermined matching criterion,

adding pattern P to said third set of patterns if pattern P satisfies a second predetermined criterion,

removing the entry corresponding to the pattern P from the stack, and

returning to step ii) to process the top entry of the stack until the stack is empty.

39. The program storage device of claim 35, wherein, for each pattern P'"'"' within said third set of patterns, said second predetermined criterion requires that said pattern P'"'"' is maximal.

40. The program storage device of claim 32, wherein, in step iv), said predetermined ordering scheme orders said set Q of patterns such that maximal patterns are generated before non-maximal patterns.

41. The program storage device of claim 40, wherein said predetermined ordering scheme orders said set Q of patterns according to a prefix relation.

42. The program storage device of claim 41, wherein said prefix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1≦

_pf Q1.

43. The program storage device of claim 40, wherein said predetermined ordering scheme orders said set Q of patterns according to a suffix relation.

44. The program storage device of claim 43, wherein said suffix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1 ≦

_sf Q1.

45. The program storage device of claim 22, wherein said first set of patterns are identified by:

identifying a set of templates;

identifying a set of patterns based on said set of templates and said sequence of characters, wherein each pattern within said set of patterns is contained within said sequence of characters.

46. The program storage device of claim 45, wherein each template within said set of templates is a proper template.