Boots – shoes – and leggings
Patent
1990-06-18
1997-02-18
Shah, Alpesh M.
Boots, shoes, and leggings
3642319, 36423221, 3642376, 364DIG1, 395793, G06F 700
Patent
active
056049102
DESCRIPTION:
BRIEF SUMMARY
TECHNICAL FIELD
The present invention relates to a method and a system for searching for a character string or the like, or more in particular to a data search method and system effective in searching for a specific character string or a key word from a great amount of character strings in a reference or the like.
BACKGROUND ART
In the prior art, in a method known to be effective for a key word search from a great amount of character strings, a state transition diagram is prepared from a key word and each character making up a character string of a text to be searched is checked with the state transition diagram to implement a key word search. See A. Aho et al., "Efficient String Matching: An Aid to Bibliographic Search", Communications of the ACM, Vol. 18, No. 6, June 1975, pp. 33-340.
In the aforementioned prior art (hereinafter called then "FSA method"), assume, for example, that three key words are provided including "HEI RETSU" () (a phrase comprising two kanji characters meaning "parallel"), "KEI SAN KI" () (a phrase comprising three kanji characters meaning "computer") and "SEI GYO HOU HOU" () (a phrase comprising four kanji characters meaning "control method"). A transition diagram is prepared as shown in FIG. 12A which is stored in the form of the state transition table of FIG. 12B. Each character of the text is checked sequentially with this transition table for a search. In the example of FIG. 12A, if the character of the input text is "HEI" (), transition is made to state 1; if the character is "KEI" (), transition is made to state 3; and if the character is "SEI" (), transition is made to state 6. If the text character is "RETSU" in state 1, transition is made to state 2. Since state 2 is the final state, it is known that the key word "HEI RETSU"(), has been searched for. With regard to the other key word "KEI SAN KI" (), or "SEI GYO HOU HOU" (), it is known whether these key words have been searched for or not by determining whether transition is made to state 5 or 9 respectively. In this way, the FSA method is an efficient method capable of searching for a plurality of key words. The actual processing of searching a character string by the FSA method is realized by a program as shown in FIG. 12C. The FSA method, though superior as described above, has the problem of sequential processing. As shown in FIG. 12C, in the FSA method, after initialization (step 1203), whether the present state is the final one is checked (step 1205) at each time of application of one text character (step 1204), and if so, the position and the length of the text in which a key word has been found is produced (step 1206). And the state transition table is checked from the present state and the text characters thereby to determine the state to which the next transition is to be made (steps 1207 to 1211), so that the state and the text position are updated (step 1211). A similar processing is repeated for the next text characters.
Specifically, the state of the destination of transition is determined only at the end (step 1212) of the processing of each text character, and the processing of the next text character cannot be started until the determination of the state of the destination of transition. As a result, the processing becomes essentially sequential. In the case where an attempt is made to increase the search speed by use of a parallel processing technique such as the pipeline processing with an exclusive hardware, however, the above-mentioned sequential characteristic poses the problem of inapplicability of the search by the FSA method.
Accordingly, an object of the present invention is to provide a method and a system for character string search suitable for searching for a key word at high speed from a text character string in a great amount of character strings.
Another object of the present invention is to provide a new method and a system for character string search suitable for increasing the processing speed by parallel processing such as the pipeline processing.
Still another object of the prese
REFERENCES:
patent: 4094001 (1978-06-01), Miller
patent: 4423206 (1988-02-01), Kojima et al.
patent: 4750122 (1988-06-01), Kaji et al.
patent: 4955056 (1990-09-01), Stentiford
patent: 4972349 (1990-11-01), Kleinberges
patent: 4985863 (1991-01-01), Fujisawa et al.
patent: 5014327 (1991-05-01), Potter et al.
patent: 5051947 (1991-09-01), Messenger et al.
patent: 5060143 (1991-10-01), Lee
patent: 5146539 (1992-09-01), Doddington et al.
Efficient String Matching: An aid to bibliographic Search pp. 333-340, date: 1975.
Kojima Keiji
Mishina Yusuke
Hitachi , Ltd.
Shah Alpesh M.
LandOfFree
Method of and vector processor for searching text for key words does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of and vector processor for searching text for key words , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and vector processor for searching text for key words will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1609118