System for plural-string search with a parallel collation of a first partition of each string followed by finite automata matching of second partitions

• US 5,452,451 A
• Filed: 12/01/1994
• Issued: 09/19/1995
• Est. Priority Date: 06/15/1989
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd., Hitachi Maxell Limited (Hitachi, Ltd.)
• Original Assignee: Hitachi, Ltd., Hitachi Maxell Limited (Hitachi, Ltd.)
• Inventors: Hatakeyama, Atsushi, Noguchi, Kouki, Fujisawa, Hiromichi, Kato, Kanji, Kawaguchi, Hisamitsu, Akizawa, Mitsuru
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/349,124
• Time in Patent Office: 292 Days
• Field of Search: 395/600, 395/800
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A parallel comparator for performing a parallel and high-speed processing for collation of partial character strings which are partially taken out of a plurality of character strings of interest to be searched out with a character string to be searched in which document data to be searched is arranged sequentially from a leading character, is provided in a front stage of an automaton executing device. Only when a part of the character string to be searched coincides with the partial character string set in the comparator, the collation of the remaining portion of the character string to be searched is performed by the automaton executing device. Also, it is possible to set "don'"'"'t care" in which a character at any position in the partial character string is ignored at the time of comparison by the comparator and to set a negation condition in which the comparison by the comparator is made taking the negation of a character at any position in the partial character string.

Claims

1. In a symbol string search apparatus a symbol string search method for making a judgement of whether or not a plurality of symbol strings of interest to be searched for exist in a symbol string to be searched which is composed of symbols represented by codes, the method comprising the steps of:

dividing each of the plurality of symbol strings of interest into a first partial symbol string and a second partial symbol string;

performing for each of said first partial symbol strings of the plurality of symbol strings of interest a leading collation processing using a parallel collation means for collating, in parallel, symbols constituting said first partial symbol string with symbols constituting the symbol string to be search on a symbol basis, said parallel collation means generating a coincidence signal when there is a coincidence for at least one first partial symbol string;

responsive to said coincidence signal, activating, for a second partial symbol string corresponding to said coincidence, a posterior collation processing with a subsequent symbol string to be searched, the posterior collation processing being performed by use of a finite state automaton executing means including a state transition table which stores control data referred to during the posterior collation processing, the plurality of symbol strings of interest to be searched for being judged as having been successfully searched for in a case where said subsequent symbol string to be searched completely satisfies a search condition for the second partial symbol string corresponding to said coincidence during the posterior collation processing.

2. A symbol string search method according to claim 1, further comprising the step of performing the leading collation in such a manner that a negation condition meaning the presence of all symbols other than a specified symbol can be set at any position in the partial symbol string as the search condition on the partial symbol string at the leading collation processing.

3. A symbol string search apparatus comprising:

(a) first external information accessing means for input of a symbol string code to be searched which is composed of symbols represented by codes;

(b) leading collation processing means for performing leading collation processing between the symbol string to be searched and a first partial symbol string of each of a plurality of symbol strings of interest which are to be searched for, said leading collation processing means including a parallel collation means for collating, in parallel, symbols constituting each of the first partial symbol strings of interest to be searched for with the symbol string to be searched on a symbol basis, said parallel collation means generating a coincidence signal when there is a coincidence for at least one first partial symbol string;

(c) posterior collation processing means including a finite state automaton execution means and being responsive to said coincidence signal, for activating posterior collation processing between a subsequent symbol string to be searched and a second partial symbol string corresponding to said coincidence, by performing finite state automaton processing from a current state indicated by said coincidence signal, said finite state automaton executing means generating an output indicating that the plurality of symbol strings of interest to be searched for are judged as having been successfully searched for in a case where said subsequent symbol string to be searched completely satisfies a search condition for the second partial symbol string corresponding to said coincidence;

(d) data storage means for storing data for control of the finite state automaton processing when said posterior collation processing is performed; and

(e) second external information accessing means for input of said output from said finite state automaton executing means.

4. A symbol string search apparatus according to claim 3, wherein access by said first external information accessing means and access by said second external information accessing means are made independent of reference to each other.

5. A symbol string search apparatus according to claim 4, wherein access to external information by said first external information accessing means is greater in number than that of access to external information by said second external information accessing means.

6. A symbol string search apparatus according to claim 4, wherein the access to external information by said first external information accessing means is made prior to the access to external information by said second external information accessing means.

7. A symbol string search apparatus according to claim 3, further comprising:

(f) input buffering means for holding the symbol string to be searched inputted from said first external information accessing means;

(g) said parallel collation means for collating partial symbol strings of the plurality of preset symbol strings of interest to be searched out with the symbol string to be searched sent from said input buffering means in parallel with each other to perform the leading collation processing;

(h) a state transition table for storing control data to which reference is to be made when the posterior collation processing is performed;

(i) said finite automaton executing means for executing a finite automaton on the basis of the symbol string to be searched sent from said input buffering means and the control data stored in said state transition table to perform the posterior collation processing;

(j) state transition table accessing means for referring to said state transition table when the posterior collation processing is performed;

(k) code converting means for converting the result of the leading collation processing by said parallel collation means into a code to be transferred to said finite automaton executing means;

(l) data selecting means for selecting which of the code generated by said code converting means and a state obtained from said state transition table is to be transferred to said finite automaton executing means; and

(m) output buffering means for holding the result of search from said finite automaton executing means,

said apparatus performing a symbol string search processing in which in making a processing for search for the plurality of symbol strings of interest in response to the input of the symbol string to be searched, each of the plurality of symbol strings of interest is divided into at least two partial symbol strings at any position, each of the plurality of symbol strings of interest is subjected to the leading collation processing for one of the partial symbol strings of the symbol string of interest by said parallel collation means, and each of those of the plurality of symbol strings of interest which satisfy search conditions on the partial symbol strings subjected to the leading collation processing is subjected to the posterior collation processing for the remaining partial symbol string of the symbol string of interest by said finite automaton executing means, the symbol string of interest being judged as having been searched out in the case where it satisfies a search condition on the partial symbol string subjected to the posterior collation processing.

8. A symbol string search apparatus according to claim 7, further comprising termination code setting means for setting any termination code into said symbol string search apparatus and termination code detecting means for detecting the termination code, the symbol string search processing being terminated by detecting the termination code in the symbol string to be searched.

9. A symbol string search apparatus according to claim 8, further comprising a valid flag register for indicating the validity/invalidity of the termination code set in said termination code setting means and composed of a plurality of symbols for at least every symbol upon collation of the termination code with the symbol string to be searched and means for setting or resetting any constituent bit of said valid flag register, whereby the reference to said valid flag register is made upon collation to validate a symbol in the termination code corresponding to a constituent bit of said valid flag register in a set condition upon collation with the symbol string to be searched and to invalidate a symbol in the termination code corresponding to a constituent bit of said valid flag register in a reset condition upon collation with the symbol string to be searched, thereby making it possible to set "don'"'"'t care" at any position in the termination code.

10. A symbol string search apparatus according to claim 7, wherein said parallel collation means and said finite automaton executing means operate in parallel with each other for the same input symbol to process the symbol.

11. A symbol string search apparatus according to claim 7, wherein said finite automaton executing means includes a central processing unit.

12. A symbol string search apparatus according to claim 7, wherein said parallel collation means includes a content addressable memory.

13. A symbol string search apparatus according to claim 7, wherein said parallel collation means includes a plurality of sets of register and comparing circuits.

14. A symbol string search apparatus according to claim 7, further comprising a valid flag register for indicating the validity/invalidity of the partial symbol string of each symbol string of interest set in said parallel collation means for at least every symbol upon collation and means for setting or resetting any constituent bit of said valid flag register, whereby the reference to said valid flag register is made upon collation to validate a symbol in the partial symbol string corresponding to a constituent bit of said valid flag register in a set condition upon collation with the symbol string to be searched and to invalidate a symbol in the partial symbol string corresponding to a constituent bit of said valid flag register in a reset condition upon collation with the symbol string to be searched, thereby making it possible to set "don'"'"'t care" at any position in the partial symbol string.

15. A symbol string search apparatus according to claim 14, wherein there is provided means which, in the case where all of symbols in the partial symbol string of the symbol string of interest are set in said parallel collation means in the form of "don'"'"'t care", makes the judgement of anti-coincidence for all input symbols as the result of collation with the partial symbol string.

16. A symbol string search apparatus according to claim 7, wherein in the case where the collation of the partial symbol strings of the symbol strings of interest set in said parallel collation means with the symbol string to be searched results in that all of the set symbol strings of interest do not satisfy a search condition, means for detecting such a case is provided.

17. A symbol string search apparatus according to claim 7, wherein in the case where the collation of the partial symbol strings of the symbol strings of interest set in said parallel collation means with the symbol string to be searched results in that at least one of the set symbol strings of interest satisfies a search condition, means for detecting such a case is provided.

18. A symbol string search apparatus according to claim 7, further comprising additional information storage means for storing information which is to be added to the result of search as a part thereof when the result of search is outputted from said finite automaton executing means and means for setting the contents of said additional information storage means, thereby making it possible to add arbitrarily presettable information to the result of search outputted to said output buffering means which holds the result of search.

19. A symbol string search apparatus according to claim 3, wherein said leading collation processing means performs the leading collation in such a manner that a negation condition meaning the presence of all symbols other than a specified symbol can be set at any position in the partial symbol string as the search condition on the partial symbol string at the leading collation processing.

20. A symbol string search apparatus according to claim 3, wherein at least said first external information accessing means (a) and said second external information accessing means (e) of said constituent elements (a) to (e) are provided and access by said first external information accessing means (a) and access by said second external information accessing means (e) are made independent of each other.

21. A symbol string search apparatus according to claim 20, wherein access to external information by said first external information accessing means is greater in number than that of access to external information by said second external information accessing means.

22. A symbol string search apparatus according to claim 20, wherein the access to external information by said first external information accessing means is made prior to the access to external information by said second external information accessing means.

23. A semiconductor integrated circuit comprising:

(a) first external information accessing means for input of a symbol string which is to be searched and which is composed of symbols represented by codes;

(b) leading collation processing means for performing leading collation processing between said symbol string to be searched and a first partial symbol string of each of a plurality of symbol strings of interest which are to be searched for, said leading collation processing means including a parallel collation means for collating, in parallel, symbols constituting each of the first partial symbol strings of interest to be searched for with the symbol string to searched on a symbol basis, said parallel collation means generating a coincidence signal when there is a coincidence for at least one first partial symbol string;

(c) posterior collation processing means including a finite state automaton execution means and being responsive to said coincidence signal, for activating a processing for posterior collation between a subsequent symbol string to be searched input from said first external information accessing means and a second partial symbol string corresponding to said coincidence, said finite state automaton executing means generating an output indicating that the plurality of symbol strings of interest to be searched for are judged as having been successfully searched for in a case where said subsequent symbol string to be searched completely satisfies a search condition for the second partial symbol string corresponding to said coincidence;

(d) data storage means for storing data for control of the finite state automaton processing when the posterior collation processing is performed; and

(e) second external information accessing means for input of said output from said finite state automaton executing means,

wherein as least two kinds of elements (a) to (e) are integrated on the same semiconductor chip.

24. A semiconductor integrated circuit according to claim 23, wherein at least said first external information accessing means (a) and said second external information accessing means (e) of said constituent elements (a) to (e) are integrated on the same semiconductor chip, and access by said first external information processing means and access by said second external information accessing means are made independent of reference to each other.

25. A semiconductor integrated circuit according to claim 24, wherein access to external information by said first external information accessing means is greater in number than that of access to external information by said second external information accessing means.

26. A semiconductor integrated circuit according to claim 24, wherein the access to external information by said first external information accessing means is made prior to the access to external information by said second external information accessing means.

27. A semiconductor integrated circuit according to claim 23, wherein at least two kinds of said constituent elements (a) to (e) including said leading collation processing means (b) are integrated on the same semiconductor chip with the element for each of said at least two kinds being at least one in number, and there is provided means for storing a plurality of said symbol strings of interest or partial symbol strings thereof in said semiconductor integrated circuit.

28. A semiconductor integrated circuit according to claim 23, wherein said leading collation processing means performs the leading collation in such a manner that a negation condition meaning the presence of all symbols other than a specified symbol can be set at any position in the partial symbol string as the search condition on the partial symbol string at the leading collation processing.

29. A semiconductor integrated circuit according to claim 23, wherein at least said first external information accessing means (a) and said second external information accessing means (e) of said constituent elements (a) to (e) are integrated on the same integrated circuit and access by said first external information accessing means (a) and access by said second external information accessing means (e) are made independent of each other.

30. A semiconductor integrated circuit according to claim 29, wherein at least said first external information accessing means (a) and said second external information accessing means (e) of said constituent elements (a) to (e) are integrated on the same integrated circuit and access to external information by said first external information accessing means (a) is greater in number than that of access to external information by said second external information accessing means (e).

31. A semiconductor integrated circuit according to claim 29, wherein the access to external information by said first external information accessing means is made prior to the access to external information by said second external information accessing means.