Pattern search method, pattern search apparatus and computer program therefor, and storage medium thereof

• US 20020123995A1
• Filed: 01/11/2002
• Published: 09/05/2002
• Est. Priority Date: 01/11/2001
• Status: Active Grant

• Current Assignee: Tetsuo Shibuya
• Original Assignee: Tetsuo Shibuya
• Inventors: Shibuya, Tetsuo
• Granted Patent: US 7,016,896 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A fast search is performed of a large text database, while suppressing an increase in the data size of the data structure used for the process. A pattern search method for searching a target character string for a desired pattern includes: a range search step and a character string extraction step. At the range search step, intermediate patterns are obtained by adding characters in order, one by one, from the last character of the pattern to the first, and a range is determined for a suffix array, which corresponds to the target character string, wherein the first character of each of the intermediate patterns is present. Then, at the character string extraction step, elements of the character string are designated that correspond to elements included in the range of the suffix array, and character string segments are extracted consisting of the same number of elements as the elements of the pattern and having the elements of the character string as their first characters.

Claims

1. A pattern search method for searching a target character string for a desired pattern comprising:

a range search step of obtaining intermediate patterns by adding characters in order, one by one, from the last character of said pattern to the first, and determining a range for a suffix array, which corresponds to said target character string, wherein the first character of each of said intermediate patterns is present; and

a character string extraction step of designating elements of said character string that correspond to elements included in said range of said suffix array obtained for said pattern by said search, and extracting character string segments consisting of the same number of elements as said elements of said pattern and having said elements of said character string as their first characters.

2. The pattern search method according to claim 1, wherein said range search step includes the steps of:

designating a preposition character positioned immediately before said characters of said character string that correspond to said elements of said suffix array that is consonant with said target character string;

obtaining the appearance count for a desired character, in said pattern, that is included among said preposition characters for the elements positioned before a specific element in said suffix array; and

employing said obtained appearance count for said desired character to determine the position of said desired character in said suffix array.

3. A pattern search method for finding a desired pattern in a search target array comprising the steps of:

finding the location, in said array, of the last element of said desired pattern; and

obtaining intermediate patterns, when said pattern consists of a plurality of elements, by adding elements one by one, beginning with an element located immediately before said last element, and determining the locations of said intermediate patterns in said array.

4. A pattern search method for searching a target character string for a desired pattern comprising:

a range search step of obtaining intermediate patterns by adding characters in order, one by one, from the first character of said pattern to the last, and determining a range for a prefix array, which corresponds to said target character string, wherein the last character of each of said intermediate patterns is present; and

a character string extraction step of designating elements of said character string that correspond to elements included in said range of said prefix array obtained for said pattern by said search, and extracting character string segments consisting of the same number of elements as said elements of said pattern and having said elements of said character string as their last characters.

5. A pattern search method for searching a target genetic array for a desired pattern comprising:

a range search step of obtaining intermediate patterns by adding elements in order, one by one, from the last element of said pattern to the first, and determining a range for a suffix array, which corresponds to said target genetic array, wherein the first element of each of said intermediate patterns is present; and

an array extraction step of designating elements of said genetic array that correspond to elements included in said range of said suffix array obtained for said pattern by said search, and extracting array segments consisting of the same number of elements as said elements of said pattern and having said elements of said genetic array as their first characters.

6. A pattern search apparatus for searching a search target character string for a desired pattern comprising:

a pre-processor, for constructing a data structure to search for a pattern base in a suffix array for said target character string; and

a search unit, for employing said data structure constructed by said pre-processor to search for said desired pattern,

wherein, to construct said data structure, said pre-processor designates a preposition character positioned immediately before each character of said character string that corresponds to elements of said suffix array, and obtains, for each type of character forming said target character string, the number of preposition characters in the elements preceding a predetermined element in said suffix array.

7. The pattern search apparatus according to claim 6, wherein said pre-processor includes a table in which the number of said preposition characters are correlated with the locations of said elements in said suffix array and with the types of characters forming said target character string.

8. The pattern search apparatus according to claim 7, wherein said table is a table generated to reflect the locations of elements in accordance with every predetermined count in said suffix array.

9. The pattern search apparatus according to claim 8, wherein, said pre-processor includes another table in which, based on predetermined locations in said suffix array for which information is managed by said table, information is stored that relates to said preposition characters for said elements in said suffix array lying between said predetermined locations.

10. The pattern search apparatus according to claim 6, wherein said search unit obtains intermediate patterns by adding characters in order, one by one, from the last character of said pattern to the first, based on the number of preposition characters in the elements preceding a predetermined element in said suffix array, and determines a range for a suffix array, which corresponds to said target character string, wherein the first character of each of said intermediate patterns is present;

and wherein said search unit designates elements of said character string that correspond to elements included in said range of said suffix array obtained for said pattern by said search, and extracts character string segments consisting of the same number of elements as said elements of said pattern and having said elements of said character string as their first characters.

11. A computer program, which permits a computer to conduct a search of a target array for a desired pattern, comprising:

a process for obtaining intermediate patterns by adding elements in order, one by one, from the last element of said pattern to the first, and for determining the range of a suffix array, which corresponds to said target array, wherein the first element of each of said intermediate patterns is present; and

a process for designating elements of said array that correspond to elements included in said range of said suffix array obtained for said pattern by said search, and for extracting an array segment that consists of the same number of elements as said elements of said pattern and that has the same elements of said array as have the first elements.

13. The computer program according to claim 12, wherein a table is generated in which the number of said preposition elements are correlated with the locations of said elements in said suffix array and with the types of elements forming said target array.

12. A computer program, which permits a computer to search a target array for a desired pattern, comprising:

a process for designating a preposition element positioned immediately before said elements of said array that correspond to said elements of said suffix array that is consonant with said target array;

a process for obtaining, for each type of element of said array, the number of preposition elements for elements that are located before a predetermined element in said suffix array;

a process for, based on said number of preposition elements of said elements located before said predetermined element in said suffix array, obtaining intermediate patterns by adding elements in order, one by one, from the last element of said pattern to the first, and determining a range for said suffix array, which corresponds to said target array, wherein the first element of each of said intermediate patterns is present; and

a process for designating said elements of said array that correspond to elements included in said range of said suffix array that is obtained for said desired pattern by the search, and for extracting an array segment that consists of the same number of elements as said elements of said pattern and that has the same elements of said array as have the first elements.

14. A storage medium on which input means of a computer stores a computer-readable program that permits said computer to perform the processing for searching a target array for a desired pattern, and that includes, as said processing for searching a desired pattern:

a process for obtaining intermediate patterns by adding elements in order, one by one, from the last element of said pattern to the first, and for determining the range of a suffix array, which corresponds to said target array, wherein the first element of each of said intermediate patterns is present; and

a process for designating elements of said array that correspond to elements included in said range of said suffix array obtained for said pattern by said search, and for extracting an array segment that consists of the same number of elements as said elements of said pattern and that has the same elements of said array as have the first elements.

15. A storage medium on which input means of a computer stores a computer-readable program that permits said computer to perform the processing for searching a target array for a desired pattern, and that includes, as said processing for searching a desired pattern:

a process for designating a preposition element positioned immediately before said elements of said array that correspond to said elements of said suffix array that is consonant with said target array;

a process for obtaining, for each type of element of said array, the number of preposition elements for elements that are located before a predetermined element in said suffix array;

a process for, based on said number of preposition elements of said elements located before said predetermined element in said suffix array, obtaining intermediate patterns by adding elements in order, one by one, from the last element of said pattern to the first, and determining a range for said suffix array, which corresponds to said target array, wherein the first element of each of said intermediate patterns is present; and

a process for designating said elements of said array that correspond to elements included in said range of said suffix array that is obtained for said desired pattern by the search, and for extracting an array segment that consists of the same number of elements as said elements of said pattern and that has the same elements of said array as have the first elements.