Character and/or character-string retrieving method and storage medium for use for this method

• US 5,978,801 A
• Filed: 11/18/1997
• Issued: 11/02/1999
• Est. Priority Date: 11/21/1996
• Status: Expired due to Fees

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Yuasa, Natsuki
• Primary Examiner(s): Fetting, Anton
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/972,456
• Time in Patent Office: 714 Days
• Field of Search: 707/514, 707/529, 707/530, 707/6, 707/3, 345/348, 345/349, 345/350, 382/232, 382/229, 382/228, 382/227, 382/181
• 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/99936 Pattern matching access

Abstract

A character and/or character-string retrieving method with retrieves a plurality of patterns at a time by using a single deterministic finite automaton prepared from a plurality of different patterns. There is also a method for optimizing the number of states for the above-mentioned retrieving method, and a storage medium having records of programs and data necessary for executing the above-mentioned character and/or character-string retrieving and a state number optimizing method. A plurality of regular expressions r₁, r₂, . . . , r_n to be simultaneously retrieved by pattern matching are prepared, and then augmented to form an augmented regular expression ((r₁)#₁,)|((r₂)#₂)| . . . ((r_n)#_n). A deterministic finite automaton is constructed so that it treats states including positions corresponding to #₁, #₂, . . . , n, thereby simultaneously retrieving a plurality of regular expression patterns by distinguishing matches from one another.

Claims

1. A character and/or character-string retrieving method for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched, comprising:

preparing a syntax ((r₁)#₁)|((r₂)#₂)| . . . |((r_n)#_n) on the basis of an augmented regular expression (r₁)#₁, (r₂)#₂ . . . , (r_n)#_n obtained by concatenating end-markers #₁, #₂, . . . #_n to respective regular expressions r₁, r₂, . . . , r_n containing a plurality of characters and/or character-strings (2, . . . , n); and

constructing a deterministic infinite automaton for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched by distinguishing each of the characters and/or character-strings contained in the plurality of regular expressions r₁, r₂, . . . r_n by means of each of the end-markers #₁, #₂ . . . #_n attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.

2. A storage medium storing a program and data which are necessary for executing the character and/or character-string retrieving method defined claim 1 and readable therefrom by a computer.

4. The character and/or character-string retrieving method as defined in claim 1 or claim 3, wherein the plurality of specific patterns of characters and/or character-strings contained in the plurality of regular expressions r₁, r₂ . . . r_n are used simultaneously as the objects to be searched by preparing a set of states {state 1, state 2 . . . } and a state-transition table on the set of states from syntax based on the augmented regular expression.

5. The character and/or character-string retrieving method as defined in claim 4, wherein a number of states is optimized by splitting the set of states into (n+1) groups including groups (F₁, F₂, . . . , F_n) corresponding to accepting states 1, 2, . . . , n and a group corresponding to non-accepting states other than accepting states.

6. The character and/or character-string retrieving method as defined in claim 5, wherein each of the (n+1) groups is split into subgroups until a state s in a group "a" has transition on a character and/or a character-string input M to a state in a group "b" and any other state t in the same group "a" has a transition on the same input M to a state in the same group "b" and a state-transition table is rewritten according to a partition obtained as an effect of the splitting.

7. A storage medium storing a program and data which are necessary for executing the character and/or character-string retrieving method defined in claim 6 and readable therefrom by a computer.

8. A storage medium storing a program and data which are necessary for executing the character and/or character-string retrieving method defined in claim 5 and readable therefrom by a computer.

9. A storage medium storing a program and data which are necessary for executing the character and/or character-string retrieving method defined in claim 4 and readable therefrom by a computer.

3. A character and/or character-string retrieving method for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched, comprising:

preparing a syntax ((r₁)#)|((r₂)#)| . . . |((r_n)#) on the basis of an augmented regular expression (r₁) #, (r₂) # . . . , (r_n)# by concatenating an end-marker # to respective regular expressions r₁, r₂, . . . , r_n, containing a plurality of characters and/or character-strings (2, . . . , n); and

constructing a deterministic infinite automaton for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched by distinguishing each of the characters and/or the character-strings contained in the plurality of regular expressions r₁, r₂, . . . r_n by means of each of the end-markers # attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.

10. A storage medium storing a program and data which are necessary for executing the character and/or character-string retrieving method defined in claim 3 and readable therefrom by a computer.

11. An article of manufacture taking the form of a computer-readable medium for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched, the article of manufacture comprising:

a syntax source code segment for preparing a syntax ((r₁)#₁)|((r₂)#₂)| . . . |((r_n)#_n) on the basis of an augmented regular expression (r₁)#₁, (r₂)#₂ . . . , (r_n)#_n obtained by concatenating end-markers #₁, #₂, . . . #_n to respective regular expressions r₁, r₂, . . . r_n containing a plurality of characters and/or character-strings (2, . . . , n); and

an automaton source code segment for constructing a deterministic infinite automaton for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched by distinguishing each of the characters and/or the character-strings contained in the plurality of regular expressions r₁, r₂, . . . r_n by means of each of the end-markers #₁, #₂ . . . #_n attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.

13. The article of manufacture as defined in claim 11 or claim 12, wherein the plurality of specific patterns of characters and/or character-strings contained in the plurality of regular expressions r₁, r₂ . . . r_n are used simultaneously as the objects to be searched, the article of manufacture further comprising:

a state source code segment for preparing a set of states {state 1, state 2 . . . } and a state-transition table on the set of states from syntax based on the augmented regular expression.

14. The article of manufacture as defined in claim 13, further comprising an optimization source code segment for optimizing a number of states by splitting the set of states into (n+1) groups including groups (F₁, F₂, . . . , F_n) corresponding to accepting states 1, 2, . . . , n and a group corresponding to non-accepting states other than accepting states.

15. The article of manufacture as defined in claim 14, wherein each of the (n+1) groups is split into subgroups until a state s in a group "a" has transition on a character and/or character-string input M to a state in a group "b" and any other state t in the same group "a" has a transition on the same input M to a state in the same group "b" and a state-transition table is rewritten according to a partition obtained as an effect of the splitting.

12. An article of manufacture taking the form of a computer-readable medium for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched, the article of manufacture comprising:

a syntax source code segment for preparing a syntax ((r₁)#)|((r₂)#)| . . . |((r_n)#) on the basis of an augmented regular expression (r₁) #, (r₂) # . . . , (r_n)# by concatenating an end-marker # to respective regular expressions r₁, r₂, . . . , r_n containing a plurality of characters and/or character-strings (2, . . . , n); and

an automaton source code segment for constructing a deterministic infinite automaton for simultaneously retrieving a plurality of specific patterns of characters and/or character-strings from objects to be searched by distinguishing each of the characters and/or the character-strings contained in the plurality of regular expressions r₁, r₂, . . . r_n by means of each of the end-markers # attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.