US5978801A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Character and/or character-string retrieving method and storage medium for use for this method
Assignee: Sharp Corp
•
Filing: 1997-11-18
•
Granted: 1999-11-02
•
Expires: 2017-11-18
Abstract
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 1 , r 2 , . . . , r n to be simultaneously retrieved by pattern matching are prepared, and then augmented to form an augmented regular expression ((r 1 )# 1 ,)|((r 2 )# 2 )| . . . ((r n )# n ). A deterministic finite automaton is constructed so that it treats states including positions corresponding to # 1 , # 2 , . . . , n, thereby simultaneously retrieving a plurality of regular expression patterns by distinguishing matches from one another.
Inventors
- 👤 Natsuki Yuasa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 11:29
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
196 words
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 1 )# 1 )|((r 2 )# 2 )| . . . |((r n )# n ) on the basis of an augmented regular expression (r 1 )# 1 , (r 2 )# 2 . . . , (r n )# n obtained by concatenating end-markers # 1 , # 2 , . . . # n to respective regular expressions r 1 , r 2 , . . . , 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 1 , r 2 , . . . r n by means of each of the end-markers # 1 , # 2 . . . # n attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 2
Dependent Claim
196 words
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 1 )# 1 )|((r 2 )# 2 )| . . . |((r n )# n ) on the basis of an augmented regular expression (r 1 )# 1 , (r 2 )# 2 . . . , (r n )# n obtained by concatenating end-markers # 1 , # 2 , . . . # n to respective regular expressions r 1 , r 2 , . . . , 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 1 , r 2 , . . . r n by means of each of the end-markers # 1 , # 2 . . . # n attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 3
Dependent Claim
28 words
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.
Claim 4
Dependent Claim
171 words
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 1 )#)|((r 2 )#)| . . . |((r n )#) on the basis of an augmented regular expression (r 1 ) #, (r 2 ) # . . . , (r n )# by concatenating an end-marker # to respective regular expressions r 1 , r 2 , . . . , 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 1 , r 2 , . . . r n by means of each of the end-markers # attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 5
Dependent Claim
171 words
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 1 )#)|((r 2 )#)| . . . |((r n )#) on the basis of an augmented regular expression (r 1 ) #, (r 2 ) # . . . , (r n )# by concatenating an end-marker # to respective regular expressions r 1 , r 2 , . . . , 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 1 , r 2 , . . . r n by means of each of the end-markers # attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 6
Dependent Claim
81 words
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 1 , r 2 . . . 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.
Claim 7
Dependent Claim
64 words
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 1 , F 2 , . . . , F n ) corresponding to accepting states 1, 2, . . . , n and a group corresponding to non-accepting states other than accepting states.
Claim 8
Dependent Claim
89 words
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.
Claim 9
Dependent Claim
29 words
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.
Claim 10
Dependent Claim
29 words
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.
Claim 11
Dependent Claim
29 words
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.
Claim 12
Dependent Claim
29 words
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.
Claim 13
Dependent Claim
217 words
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 1 )# 1 )|((r 2 )# 2 )| . . . |((r n )# n ) on the basis of an augmented regular expression (r 1 )# 1 , (r 2 )# 2 . . . , (r n )# n obtained by concatenating end-markers # 1 , # 2 , . . . # n to respective regular expressions r 1 , r 2 , . . . 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 1 , r 2 , . . . r n by means of each of the end-markers # 1 , # 2 . . . # n attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 14
Dependent Claim
217 words
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 1 )# 1 )|((r 2 )# 2 )| . . . |((r n )# n ) on the basis of an augmented regular expression (r 1 )# 1 , (r 2 )# 2 . . . , (r n )# n obtained by concatenating end-markers # 1 , # 2 , . . . # n to respective regular expressions r 1 , r 2 , . . . 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 1 , r 2 , . . . r n by means of each of the end-markers # 1 , # 2 . . . # n attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 15
Dependent Claim
191 words
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 1 )#)|((r 2 )#)| . . . |((r n )#) on the basis of an augmented regular expression (r 1 ) #, (r 2 ) # . . . , (r n )# by concatenating an end-marker # to respective regular expressions r 1 , r 2 , . . . , 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 1 , r 2 , . . . r n by means of each of the end-markers # attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 16
Dependent Claim
191 words
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 1 )#)|((r 2 )#)| . . . |((r n )#) on the basis of an augmented regular expression (r 1 ) #, (r 2 ) # . . . , (r n )# by concatenating an end-marker # to respective regular expressions r 1 , r 2 , . . . , 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 1 , r 2 , . . . r n by means of each of the end-markers # attached thereto for representing accepting states 1, 2, . . . n of the regular expressions respectively.
Claim 17
Dependent Claim
90 words
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 1 , r 2 . . . 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.
Claim 18
Dependent Claim
68 words
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 1 , F 2 , . . . , F n ) corresponding to accepting states 1, 2, . . . , n and a group corresponding to non-accepting states other than accepting states.
Claim 19
Dependent Claim
86 words
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.
References Cited (Backward Citations)
US5379420A
Cited
US5511159A
Cited
US5495409A
Cited
US5835100A
Cited
US5778356A
Cited
US5764974A
Cited
US5778359A
Cited
US5761686A
Cited
US5765176A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |