Pattern search apparatus and method

• US 5,963,942 A
• Filed: 12/24/1996
• Issued: 10/05/1999
• Est. Priority Date: 01/16/1996
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Igata, Nobuyuki
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/773,295
• Time in Patent Office: 1,015 Days
• Field of Search: 707/3, 707/6, 707/7, 707/5, 395/800.19, 345/326
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A search method selecting unit included in a pattern search apparatus can automatically select a search method with the highest search speed from a plurality of search methods according to the number of search patterns, form, etc., in order to find a search pattern in a search target. An optimum search or replacement can be realized by finding or replacing the search pattern using the selected method.

Claims

1. A pattern search apparatus, to which a search target and a search pattern to be found in the search target are provided, for finding the search pattern in the search target, comprising:

a search method selecting unit automatically and variably selecting one of a plurality of search methods, in correspondence with a search condition on which a search using the search pattern is performed; and

a search unit finding the search pattern in the search target using a search method selected by said search method selecting unit, wherein the one of the plurality of search methods is selected based upon a comparison between the plurality of search methods.

2. The pattern search apparatus according to claim 1, wherein:

the search target is a text comprising character strings, and the search pattern is a keyword comprising a character string.

3. The pattern search apparatus according to claim 2, wherein:

the search condition is based on the keyword.

4. The pattern search apparatus according to claim 3, wherein:

the search condition includes a number of keywords, and a specification of a length of a shortest keyword among at least one of the keywords.

5. The pattern search apparatus according to claim 4, wherein:

said search method selecting unit selects any of the Boyer-Moore, Aho-Corasick, and FAST methods, as the search method.

6. The pattern search apparatus according to claim 5, wherein:

said search method selecting unit selects the Boyer-Moore method as the search method, on the search condition that the number of keywords is 1 and the length of the keyword is at least 2 bytes.

7. The pattern search apparatus according to claim 5, wherein:

said search method selecting unit selects the Aho-Corasick method as the search method, on the search condition that the length of the shortest keyword among the keywords is 1 byte.

8. The pattern search apparatus according to claim 5, wherein:

said search method selecting unit evaluates a determination function, and selects either of the Aho-Corasick and FAST methods according to a result of the evaluation, on the search condition that the number of keywords is plural (two or more), and the length of the shortest keyword among the keywords is 2 bytes or more.

9. The pattern search apparatus according to claim 8, wherein:

said search method selecting unit selects the FAST method if the value of the determination function is less than 1, and selects the Aho-Corasick method if the value of the determination function is equal to or greater than 1, when the determination function is provided as a ratio "k/K" of the number of keywords "k" included in the search condition to a normal experimental value "K" of the number of keywords in a boundary at which an amount of search time according to the Aho-Corasick method is longer than an amount of search time according to the FAST method, in correspondence with the length of the shortest keyword "L" among the keywords.

10. The pattern search apparatus according to claim 8, wherein:

the determination function is selected for each text form of the character string.

11. The pattern search apparatus according to claim 10, wherein:

a text form of the character string is a description language of the character string.

12. The pattern search apparatus according to claim 8, wherein:

a ratio of each of code types in the keyword is further included as the search condition.

13. The pattern search apparatus according to claim 12, wherein:

the code types are 1-byte code and 2-byte code.

14. The pattern search apparatus according to claim 12, wherein:

the determination function is implemented for each of the code types.

15. The pattern search apparatus according to claim 14, wherein:

the determination function is selected based on the ratio of each of the code types.

16. The pattern search apparatus according to claim 1, further comprising:

a storage unit storing the search target, wherein said search unit performs a search for the search target stored in said storage unit.

17. The pattern search apparatus according to claim 1, further comprising:

an output unit performing an output based on a result of a search performed by said search unit.

18. The pattern search apparatus according to claim 17, wherein:

said output unit uses the result of the search performed by said search unit, replaces the search pattern in the search target with a pattern corresponding to each search pattern, and performs an output based on a result of a replacement performed by said search unit.

19. A pattern search apparatus, to which a search target and a search pattern to be found in the search target are provided, for finding the search pattern in the search target, comprising:

a storage unit storing the search target;

a search method selecting unit automatically and variably selecting one of a plurality of search methods, in correspondence with a search condition on which a search using the search pattern is performed;

a search unit finding the search pattern in the search target stored in a said storage unit, using a search method selected by said search method selecting unit; and

an output unit outputting a result of a search performed by said search unit, wherein the one of the plurality of search methods is selected based upon a comparison between the plurality of search methods.

20. A search pattern method for finding a search pattern in a search target, to which the search target and the search pattern to be found in the search target are provided, comprising the steps of:

receiving a search condition on which the search pattern is found; and

automatically and variably selecting one of a plurality of search methods in correspondence with the search condition, wherein the one of the plurality of search methods is selected based upon a comparison between the plurality of search methods.

21. The pattern search method according to claim 20, wherein:

the search target is a text comprising character strings, and the search pattern is a keyword comprising a character string.

22. The pattern search method according to claim 21, wherein:

the search condition is based on the keyword.

23. The pattern search method according to claim 22, wherein:

the search condition includes a number of keywords as search patterns, and a specification of a length of a shortest keyword among the keywords.

24. The pattern search method according to claim 23, wherein:

any of the Boyer-Moore, Aho-Corasick, and FAST methods is selected as a search method.

25. A computer-readable storage medium used to make a computer perform, when used in the computer to which a search target and a search pattern to be found in the search target are provided, for finding the search pattern in the search target, the functions of:

receiving a search condition on which a search using the search pattern is performed; and

automatically and variably selecting one of a plurality of search methods in correspondence with the search condition, wherein the one of the plurality of search methods is selected based upon a comparison between the plurality of search methods.

26. The computer-readable storage medium according to claim 25, wherein:

the search target is a text comprising character strings, and the search pattern is a keyword comprising a character string.

27. The computer-readable storage medium according to claim 26, wherein:

the search condition is based on the keyword.

28. The computer-readable storage medium according to claim 27, wherein:

the search condition includes a number of keywords, and a specification of a length of a shortest keyword among the keywords.

29. The computer-readable storage medium according to claim 28, wherein:

any of the Boyer-Moore, Aho-Corasick, and FAST methods is selected as a search method.