Method and apparatus for finding repeated substrings in pattern recognition

• US 7,103,750 B2
• Filed: 03/20/2003
• Issued: 09/05/2006
• Est. Priority Date: 03/20/2003
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Helsley, Matthew L., Kravec, Kerry A., Saidi, Ali G., Slyfield, Jan M., Tannhof, Pascal R.
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Chery, Mardochee
• Application Number:
  US10/393,139
• Publication Number:
  US 20040186977A1
• Time in Patent Office: 1,265 Days
• Field of Search: 711/2, 711/218, 711/219, 711/104, 712/245, 714/743, 707/7, 382/209, 382/233
• US Class Current: 711/217
• 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

Abstract

A method and apparatus for compressing a reference pattern (RP) with repeated substrings by encoding produce compressed reference patterns (CRPs) with reduce storage requirements. Operation codes and a flag are stored with the CRPs. During comparison of reference elements of the CRP to input elements (IEs) of an input pattern (IP), the operation codes are read and the reference pattern is decoded allowing all reference elements including those of the repeated substrings to be compared to IEs in the IP to determine if the RP appears within the IP.

Claims

1. A method for comparing a K element reference pattern with repeating substrings to an N element input pattern comprising the steps of:

compressing said reference pattern, forming a compressed reference pattern, by encoding repeating substrings within said reference pattern into encoded substrings according to a first protocol;

storing said compressed reference pattern in an addressable storage unit;

reading reference elements of said compressed reference pattern from said storage unit, wherein an order of reading said reference elements is modified in response to decoding said encoded substrings according to said first protocol;

processing reference elements read from said compressed reference pattern; and

modifying addresses for reading said reference elements of said compressed reference pattern in response to said processing step.

2. The method of claim 1, further comprising the step of reading an input element of said input pattern.

3. The method of claim 2, wherein said step of processing reference elements read from said compressed reference pattern comprises comparing a reference element of said reference pattern to said input element of said input pattern.

4. The method of claim 1, wherein said first protocol comprises the steps of:

storing a first reference element in a repeating substring of said compressed reference pattern with a first operation code;

storing a repeat number, corresponding to a number of times said repeating substring is sequentially repeated after its first appearance in said reference pattern, with a second operation code;

storing subsequent reference elements of said repeating substring with a third operation code, said subsequent reference elements stored following said repeat number; and

storing a flag with a third reference element of said repeating substring.

5. The method of claim 4, wherein said first protocol further comprises the steps of:

reading said first reference element of said repeating substring;

processing said first reference element in response to said first operation code;

generating an address for reading a second reference element of said repeating substring in response to said first operation code and a result of said step of processing said first reference element;

processing said second reference element in response to said third operation code;

processing reference elements subsequent to said second reference element in response to a result of said step of processing said second reference element; and

generating an address for reading said repeat number of said substring in response to a result from processing said reference elements subsequent to said second reference element and to a result from processing said third reference element having said flag.

6. The method of claim 4, wherein said first protocol further comprises the steps of:

loading said repeat number into a repeat counter in response to said result of processing said third reference element with said flag;

comparing an input element of said input pattern to said saved first reference element in response to said result of processing said third reference element with said flag;

decrementing said counter by one in response to each of said results of processing said third reference element with said flag; and

generating an address for reading a reference element of said compressed reference pattern not in said repeating substring in response to said counter having a count of zero.

7. The method of claim 1, further comprising the step of stopping a compare of input elements of said input pattern to reference elements read from said compressed reference pattern when a sequence of reference elements in said reference pattern matches a sequence of input elements in said input pattern.

8. A system for comparing a K element reference pattern with repeating substrings to an N element input pattern comprising:

an addressable storage unit for storing data defining said reference pattern;

circuitry for compressing said reference pattern, forming a compressed reference pattern, by encoding repeating substrings within said reference pattern into encoded substrings according to a first protocol;

circuitry for storing said compressed reference pattern sequentially in said addressable storage unit;

circuitry for reading reference elements of said compressed reference pattern from said addressable storage unit, wherein an order of reading said reference elements is modified in response to operational signals generated from decoding said encoded substrings according to said first protocol;

circuitry for processing reference elements read from said compressed reference pattern; and

circuitry for modifying addresses for reading said reference elements of said compressed reference pattern in response to first signals generated as a result of said circuit processing reference elements read from said compressed reference pattern.

9. The system of claim 8, further comprising circuitry for reading an input element of said input pattern.

10. The system of claim 9, wherein said first signals result from comparing a reference element of said reference pattern to said input element of said input pattern.

11. The system of claim 8, wherein said first protocol comprises:

circuitry for storing a first reference element of a repeating substring of said encoded reference pattern and storing a first operation code for processing said first reference element;

circuitry for storing a repeat number, corresponding to a number of times said repeating substring is sequentially repeated after its first appearance in said reference pattern and storing a corresponding second operation code for processing said second reference element;

circuitry for storing subsequent reference elements of said repeating substring and storing a third operation code for each of said subsequent reference elements stored following said repeat number; and

circuitry for storing a flag indicating a third reference element of said repeating substring is a last reference element.

12. The system of claim 11, wherein said first protocol further comprises:

circuitry for reading said first reference element of said repeating sub string;

circuitry for processing said first reference element in response to a signal state generated by reading said first operation code;

circuitry for generating an address for reading a second reference element of said repeating substring in response to said signal state generated by reading said first operation code and a signal state generated from processing said first reference element;

circuitry for processing said second reference element in response to signal states generated by reading said third operation code;

circuitry for processing reference elements subsequent to said second reference element in response to signal states generated by processing said second reference element; and

circuitry for generating an address for reading said repeat number of said substring in response to signal states generated by processing said reference elements subsequent to said second reference element and in response to signal states generated from processing said third reference element having said flag.

13. The system of claim 12, wherein said first protocol further comprises:

circuitry for loading said repeat number into a counter in response to said result of processing said third reference element with said flag;

circuitry for comparing an input element of said input pattern to said saved first reference element in response to said signal states generated from processing said third reference element having said flag;

circuitry for decrementing said counter by one in response to each processing of said third reference element with said flag; and

circuitry for generating an address for reading a reference element of said compressed reference pattern not in said repeating substring in response to a signal generated when said counter has a count of zero.

14. The system of claim 8 further comprising circuitry for stopping a compare of input elements of said input pattern to reference elements read from said compressed reference pattern when a sequence of reference elements in said reference pattern matches a sequence of input elements in said input pattern.

15. A data processing system comprising:

a central processing system (CPU);

a random access memory (RAM);

an input/output device (I/O) interface coupled to an I/O unit;

a user interface for inputting user requests to said CPU;

a bus system coupling said CPU, RAM, and said I/O interface, and circuitry for compressing a reference pattern, forming a compressed reference pattern, by encoding repeating substrings within said reference pattern into encoded substrings according to a first protocol;

circuitry for storing said compressed reference pattern sequentially in said addressable storage unit;

circuitry for reading reference elements of said compressed reference pattern from said addressable storage unit, wherein an order of reading said reference elements is modified in response to operational signals generated from decoding said encoded substrings according to said first protocol;

circuitry for processing reference elements read from said compressed reference pattern; and

circuitry for modifying addresses for reading said reference elements of said compressed reference pattern in response to first signals generated as a result of said circuit processing reference elements read from said compressed reference pattern.

16. The data processing system of claim 15, further comprising circuitry for reading an input element of said input pattern.

17. The data processing system of claim 16, wherein said first signals result from comparing a reference element of said reference pattern to said input element of said input pattern.

18. The data processing system of claim 15, wherein said first protocol comprises:

circuitry for storing a first reference element of a repeating substring of said encoded reference pattern and storing a first operation code for processing said first reference element;

circuitry for storing a repeat number, corresponding to a number of times said repeating substring is sequentially repeated after its first appearance in said reference pattern and storing a corresponding a second operation code for processing said second reference element;

circuitry for storing subsequent reference elements of said repeating substring and storing a third operation code for each of said subsequent reference elements stored following said repeat number; and

circuitry for storing a flag indicating a third reference element of said repeating substring is a last reference element.

19. The data processing system of claim 18, wherein said first protocol further comprises:

circuitry for reading said first reference element of said repeating substring;

circuitry for processing said first reference element in response to a signal state generated by reading said first operation code;

circuitry for generating an address for reading a second reference element of said repeating substring in response to said signal state generated by reading said first operation code and a signal state generated from processing said first reference element;

circuitry for processing said second reference element in response to signal states generated by reading said third operation code;

circuitry for processing reference elements subsequent to said second reference element in response to signal states generated by processing said second reference element; and

circuitry for generating an address for reading said repeat number of said substring in response to signal states generated by processing said reference elements subsequent to said second reference element and in response to signal states generated from processing said third reference element having said flag.

20. The data processing system of claim 19, wherein said first protocol further comprises:

circuitry for loading said repeat number into a counter in response to said result of processing said third reference element with said flag;

circuitry for comparing an input element of said input pattern to said saved first reference element in response to said signal states generated from processing said third reference element having said flag;

circuitry for decrementing said counter by one in response to each processing of said third reference element with said flag; and

circuitry for generating an address for reading a reference element of said compressed reference pattern not in said repeating substring in response to a signal generated when said counter has a count of zero.

21. The data processing system of claim 15 further comprising circuitry for stopping a compare if input elements of said input pattern to reference elements read from said compressed reference pattern when a sequence of reference elements if said reference pattern matches a sequence of input elements in said input pattern.