1992-04-17
1999-01-19
Amsbury, Wayne
395603, G06F 1730
Patent
active
058623744
DESCRIPTION:
BRIEF SUMMARY
The present invention relates to a method of searching and a search circuit. The invention is particularly, but not exclusively, useful for searching text which has been compressed according to the method described in International Publication No WO 88/09586.
The method of the present invention is used for searching a token stream for at least one predetermined token. A token, in the context of this specification, is a binary code representation of a character, word or phrase. The character may be an alphanumeric character or a control character, such as carriage return or end of line, or a symbol, which is recognisable by a computer. A word may be a word as defined in International Publication WO 88/09586, and a phrase may include two or more words. A token stream is a sequence of tokens, which may represent a text, such as the Bible or a dictionary.
If one wishes to search for a particular word in a text which has been compressed, according to the method of International Publication WO 88/09586, it is not sufficient to merely search for the token representative of the word because the word may form part of a number of phrases which are represented by corresponding phrase tokens in the compressed text. In searching for a word in a token stream, the corresponding word token must be searched for, together with a number of phrase tokens which represent phrases that include the word. If N is the number of tokens which need to searched for for any given word, then in performing a normal access and compare search, each token access from the token stream as it is read needs to be compared with N tokens, which would require N comparators. Depending on the text which the token stream represents, N can be very large and therefore a searching method and circuit is required which enables a large number of comparisons to be performed at once, without using excessive circuitry.
In accordance with the present invention there is provided a method of searching a token stream for at least one predetermined token, comprising: token read from said stream; and data stored therein at a location corresponding to said predetermined token; and predetermined token has been found in said stream.
Preferably said access address includes said accessed token or a part thereof.
Preferably said hit data is a single bit, which is the complement of other data stored in said memory means.
Preferably said method further comprises recording the location of said accessed token in said token stream when said hit data is read, said location corresponding to a location of said predetermined token in said token stream. Preferably the reading steps are then interrupted to enable a display operation to be performed.
Preferably the method involves searching for a plurality of predetermined tokens and thus storing a plurality of hit data at locations corresponding to said predetermined tokens, respectively.
In accordance with the present invention there is also provided a search circuit for use in searching a token stream for at least one predetermined token comprising: an access address using said accessed token; corresponding to a predetermined token; is read.
Preferably said access address includes said accessed token or a part thereof.
Preferably said hit data is a single bit which is the complement of other data stored, in use, in said memory means.
Preferably said search circuit includes input alignment means for ensuring tokens are accessed correctly when tokens in the stream have different bit lengths.
Preferably said memory, in use, has a plurality of hit data stored therein at locations corresponding to a plurality of respective predetermined tokens.
Preferably said search circuit further includes means for accessing and reading said token stream.
Preferred embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings wherein:
FIG. 1 is a block diagram of a first preferred embodiment of a search circuit;
FIG. 2 is a flow diagram of a first preferred embodiment of a searching m
REFERENCES:
patent: 4903018 (1990-02-01), Wiebach et al.
patent: 5070478 (1991-12-01), Abbott
patent: 5146560 (1992-09-01), Goldberg et al.
patent: 5175860 (1992-12-01), Yamada
patent: 5224038 (1993-06-01), Bespalko
Amsbury Wayne
Megaword International Pty. Ltd.
LandOfFree
Search method and circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Search method and circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search method and circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1254647