Method of and vector processor for searching text for key words based on candidate character strings obtained from the text using parallel processing

• US 5,604,910 A
• Filed: 06/18/1990
• Issued: 02/18/1997
• Est. Priority Date: 10/18/1988
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kojima, Keiji, Mishina, Yusuke
• Primary Examiner(s): Shah, Alpesh M.
• Application Number:
  US07/499,424
• Time in Patent Office: 2,437 Days
• Field of Search: 395/600, 395/775, 395/800, 364/715.9, 364/715.1, 364/715.11, 364/419.8, 364/419.13, 364/419.19, 340/146.2
• 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

Abstract

The present invention relates to a method of search in which a plurality of candidate of character strings likely to coincide with a designated key word are detected from a text character string, and it is decided whether the candidate character strings detected include a character string coincident with the key word character string. Further, the sequence of detection of character string candidates is determined in such a manner that a portion having a succession of characters coincident with any of a plurality of characters included in the key word character string is selected as a candidate character string.

Claims

1. A vector processor for searching a text character string for a candidate character string likely to coincide with one of a plurality of key word character strings, comprising:

first generating means for generating, from the text character string, a text vector including elements representing each of the characters in the text character string;

second generating means for generating, from the key word character strings and the text vector, an appearance mode vector including elements representing an appearance mode for each different character in the text character string, the appearance mode for each character indicating at least if the character appears in at least one of the key word character strings;

storing means for storing the text vector and the appearance mode vector;

first reading means for sequentially reading the elements of the text vector from the storing means;

second reading means for reading, from the storing means, the elements of the appearance mode vector corresponding to the elements of the text vector sequentially read from the storing means by the first reading means; and

detecting means for detecting a candidate character string constituted by a sequence of characters in the text character string each appearing in at least one of the key word character strings based on the elements of the text vector sequentially read from the storing means by the first reading means and the elements of the appearance mode vector read from the storing means by the second reading means, the sequence of characters being a continuous series of characters in the text character string.

2. A vector processor according to claim 1, wherein

at least one element of the appearance mode vector represents an appearance mode for a plurality of different characters in the text character string, and

the second reading means includes accessing means for accessing the at least one element of the appearance mode vector representing an appearance mode for a plurality of different characters in the text character string in response to any of the plurality of different characters.

3. A vector processor according to claim 2, wherein the accessing means includes

means for hashing a character code for a character represented by an element read from the text vector into a hashed code having a smaller number of bits than the character code, the hashed code being the same for the plurality of different characters, and

means for reading, from the storing means, the at least one element of the appearance mode vector representing an appearance mode for a plurality of different characters in the text character string using the hashed code to access the at least one element of the appearance mode vector representing an appearance mode for a plurality of different characters in the text character string.

4. A vector processor according to claim 1, wherein the storing means includes a first memory for storing the text vector and a second memory for storing the appearance mode vector.

5. A vector processor according to claim 1, wherein the detecting means includes means for detecting a position in the text character string of a leading character of a candidate character string and a length of the candidate character string, the candidate character string being constituted by a sequence of characters in the text character string each appearing in at least one of the key word character strings, based on the elements of the text vector sequentially read from the storing means by the first reading means and the elements of the appearance mode vector read from the storing means by the second reading means.

6. A method of searching a plurality of candidate character strings for a character string coinciding with a key word character string, the candidate character strings being likely to coincide with the key word character string and having been detected from a text character string, the key word character string being constituted by a sequence of characters, the method being performed by a computer and comprising the steps of:

(a) storing state transition destination information including a state transition destination for each of a plurality of characters which may appear in the text character string for each of a plurality of states determined by the sequence of the characters of the key word character string, the states including a final state indicating that an end of the sequence of the characters of the key word character string has been reached;

(b) determining, based on the state transition destination information stored in the step (a), if the state transition destination for a leading character of each candidate character string is the final state indicating that the end of the sequence of the characters of the key word character string has been reached;

(c) determining, based on the state transition destination information stored in the step (a), if the state transition destination for a second character of each candidate character string is the final state indicating that the end of the sequence of the characters of the key word character string has been reached;

(d) repeating the step (c) for each remaining character of each candidate character string; and

(e) if it is determined in any of the steps (b), (c), and (d) that the state transition destination for one character of one of the candidate character strings is the final state indicating that the end of the sequence of the characters of the key word character string has been reached, detecting a character string constituted by the characters of the one candidate character string from the leading character of the one candidate character string up to and including the one character of the one candidate character string as the character string coinciding with the key word character string.

7. A method according to claim 6, wherein the steps (b), (c), and (d) are performed in an overlapping manner by the computer.

8. A method according to claim 6, wherein

the step (a) includes the substep of storing, as state transition destination information, a state transition destination vector including elements representing a state transition destination for each of a plurality of characters which may appear in the text character string for each of a plurality of states determined by the sequence of the characters of the key word character string, the states including a final state indicating that an end of the sequence of the characters of the key word character string has been reached,

the step (b) includes the substeps of

(b1) sequentially reading elements of the state transition destination vector corresponding to a leading character of each candidate character string, and

(b2) determining if the elements read in the substep (b1) represent the final state indicating that the end of the sequence of the characters of the key word character string has been reached, and

the step (c) includes the substeps of

(c1) sequentially reading elements of the state transition destination vector corresponding to a second character of each candidate character string, and

(c2) determining if the elements read in the substep (c1) represent the final state indicating that the end of the sequence of the characters of the key word character string has been reached.

9. A method according to claim 8, wherein

the substep (b1) includes the substeps of

(b11) generating an input character vector including elements representing a leading character of each candidate character string,

(b12) sequentially reading the elements of the input character vector generated in the substep (b11), and

(b13) sequentially reading elements of the state transition destination vector corresponding to the elements of the input character vector sequentially read in the substep (b12), and

the substep (c1) includes the substeps of

(c11) generating an input character vector including elements representing a second character of each candidate character string,

(c12) sequentially reading the elements of the input character vector generated in the substep (c11), and

(c13) sequentially reading elements of the state transition destination vector corresponding to the elements of the input character vector sequentially read in the substep (c12).

10. A method according to claim 6, wherein

the step (a) includes the substeps of

(a1) storing, as state transition destination information, a state transition destination vector including elements representing a state transition destination for each of a plurality of characters which may appear in the text character string for each of a plurality of states determined by the sequence of the characters of the key word character string, the states including a final state indicating that an end of the sequence of the characters of the key word character string has been reached, and

(a2) generating an acceptance vector including elements corresponding to the plurality of states determined by the sequence of the characters of the key word character string and indicating whether each of the states is the final state indicating that the end of the sequence of the characters of the key word character string has been reached,

the step (b) includes the substeps of

(b1) reading elements of the state transition destination vector corresponding to a leading character of each candidate character string,

(b2) reading elements of the acceptance vector corresponding to the elements of the state transition destination vector read in the substep (b1), and

(b3) determining if any of the elements of the acceptance vector read in the substep (b2) indicate that the corresponding state is the final state indicating that the end of the sequence of the characters of the key word character string has been reached, and

the step (c) includes the substeps of

(c1) reading elements of the state transition destination vector corresponding to a second character of each candidate character string,

(c2) reading elements of the acceptance vector corresponding to the elements of the state transition destination vector read in the substep (c1), and

(c3) determining if any of the elements of the acceptance vector read in the substep (c2) indicate that the corresponding state is the final state indicating that the end of the sequence of the characters of the key word character string has been reached.

11. A method according to claim 10, wherein each element of the acceptance vector which indicates that the corresponding state is the final state indicating that the end of the sequence of the characters of the key word character string has been reached represents a length of the key word character string.

12. A method according to claim 6, wherein the candidate character strings are detected from the text character string by detecting a plurality of sequences of characters from the text character string, wherein each of the characters in each of the sequences appears in the key word character string such that the sequences of characters constitute candidate character strings likely to coincide with the key word character string.

13. A method according to claim 6, wherein the candidate character strings are detected from the text character string by dividing the text character string into a plurality of character strings separated from each other by characters which do not appear in the key word character string, wherein each of the characters in each of the character strings appears in the key word character string such that the character strings constitute candidate character strings likely to coincide with the key word character string.

14. A method of searching a text character string for a candidate character string likely to coincide with one of a plurality of key word character strings, the method being performed by a computer and comprising the steps of:

(a) generating, from the text character string, a text vector including elements representing each of the characters in the text character string, the computer storing the elements of the text vector after the text vector has been generated;

(b) generating, from the key word character strings and the text vector, an appearance mode vector including elements representing an appearance mode for each different character in the text character string, the appearance mode vector for each character indicating at least if the character appears in at least one of the key word character strings, the computer storing the elements of the appearance mode vector after the appearance mode vector has been generated;

(c) sequentially reading the elements of the text vector;

(d) reading the elements of the appearance mode vector corresponding to the elements of the text vector sequentially read in the step (c); and

(e) detecting a candidate character string constituted by a sequence of characters in the text character string each appearing in at least one of the key word character strings based on the elements of the text vector sequentially read in the step (c) and the elements of the appearance mode vector read in the step (d), the sequence of characters being a continuous series of characters in the text character string.

15. A method according to claim 14, wherein the steps (c), (d), and (e) are performed in an overlapping manner by the computer.

16. A method according to claim 14, wherein the step (e) includes the substeps of

(e1) determining if each character in the text character string is to be a leading character of a candidate character string,

(e2) determining if each character in the text character string is to be an intermediate character in a candidate character string including a character in the text character string immediately preceding the character, and

(e3) determining if a character in the text character string immediately preceding each character in the text character string is to be a final character in a candidate character string including the preceding character,

wherein the substeps (e1), (e2), and (e3) are performed for each character in the text character string based on an element read from the text vector in the step (c) representing the character and elements read from the appearance mode vector in the step (d) representing the appearance mode for the character and the appearance mode for a character in the text character string immediately preceding the character.

17. A method according to claim 16, wherein

the substep (e1) includes the substep of determining that a character in the text character string is to be a leading character of a candidate character string when the appearance mode for the character indicates that the character appears in at least one of the key word character strings and the appearance mode for the preceding character indicates that the preceding character does not appear in at least one of the key word character strings,

the substep (e2) includes the substep of determining that a character in the text character string is to be an intermediate character in a candidate character string including a character in the text character string immediately preceding the character when the appearance mode for the character and the appearance mode for the preceding character indicate that the character and the preceding character both appear in at least one of the key word character strings, and

the substep (e3) includes the substep of determining that a character in the text character string immediately preceding each character in the text character string is to be a final character in a candidate character string including the preceding character when the appearance mode for the character indicates that the character does not appear in at least one of the key word character strings and the appearance mode for the preceding character indicates that the preceding character does appear in at least one of the key word character strings.

18. A method according to claim 14, wherein the appearance mode includes position information relating to a position of the character in the at least one of the key word character strings.

19. A method according to claim 18, wherein the position information includes information indicating if the character is a leading character, an intermediate character, or a last character in the at least one of the key word character strings.

20. A method according to claim 18, wherein the position information includes information indicating whether a length of the at least one of the key word character strings from a beginning of the at least one of the key word character strings up to and including the position of the character in the at least one of the key word character strings is less than or equal to a length of a shortest one of the key word character strings.

21. A method according to claim 18, wherein

the position information includes information indicating a position of the character in the at least one of the key word character strings, and

the step (b) includes the substep of determining that a character in the text character string is not to be included in the candidate character string when the appearance mode indicates that the character appears in the at least one of the key word character strings but the position information indicates that the position of the character in the at least one of the key word character strings would conflict with a position of the character in the candidate character string if the character were to be included in the candidate character string.

22. A method according to claim 18, wherein

the position information includes information indicating a position of the character in the at least one of the key word character strings, and

the step (b) includes the substep of determining that a character in the text character string is not to be included in a current candidate character string including a character in the text character string immediately preceding the character in the text character string but is to be included in a new candidate character string when the appearance mode for the character indicates that the character appears in the at least one of the key word character strings and the appearance mode for the preceding character indicates that the preceding character appears in the at least one of the key word character strings but the position information indicates that the position of the character in the at least one of the key word character strings would conflict with a position of the character in the current candidate character string if the character were to be included in the current candidate character string.

23. A method according to claim 14, wherein the step (e) includes the substeps of

(e1) sequentially comparing each element of the appearance mode vector read in the step (d) with an element of the appearance mode vector read in the step (d) immediately before the element of the appearance mode vector was read in the step (d), and

(e2) detecting positions in the text character string of a leading character and a final character of a candidate character string based on results of the comparing performed in the substep (e1).

24. A method according to claim 23, wherein the substep (e1) includes the substeps of

(e11) generating a detection state vector including all of the elements of the appearance mode vector read in the step (d),

(e12) sequentially comparing each element of the detection state vector with an element of the detection state vector immediately preceding the element in the detection state vector, and

(e13) generating a delimiting position vector including elements indicating results of the comparing performed in the substep (e12).

25. A method of searching a text character string for a candidate character string likely to coincide with a key word character string, the method being performed by a computer and comprising the steps of:

(a) determining, for each character in the text character string, an appearance mode indicating at least if the character appears in the key word character string; and

(b) detecting, from the text character string, a candidate character string constituted by a sequence of characters each appearing in the key word character string based on the appearance mode for each character in the text character string, the sequence of characters being a continuous series of characters in the text character string.

26. A method according to claim 25, wherein

the key word character string is one of a plurality of key word character strings,

the step (a) includes the substep of determining, for each character in the text character string, an appearance mode indicating at least if the character appears in at least one of the key word character strings without indicating which of the key word character strings the character appears in, and

the step (b) includes the substep of detecting a sequence of characters from the text character string based on the appearance mode for each character in the text character string, wherein each of the characters in the sequence of characters appears in at least one of the key word character strings such that the sequence of characters constitutes a candidate character string likely to coincide with any of the key word character strings.

27. A method according to claim 26, wherein the step (a) includes the substeps of

(a1) storing, for each of a plurality of characters which may appear in the text character string, an appearance mode indicating at least if the character appears in at least one of the key word character strings without indicating which of the key word character strings the character appears in, and

(a2) reading out the stored appearance mode for each character which actually appears in the text character string, thereby determining, for each character in the text character string, an appearance mode indicating at least if the character appears in at least one of the key word character strings without indicating which of the key word character strings the character appears in.

28. A method according to claim 27, wherein the substep (a1) includes the substeps of:

(a11) storing, for each of a plurality of characters which may appear in the text character string, an appearance mode indicating that the character does not appear in any of the key word character strings, and

(a12) changing, for each character which appears in at least one of the key word character strings, the stored appearance mode indicating that the character does not appear in any of the key word character strings to an appearance mode indicating at least that the character appears in at least one of the key word character strings without indicating which of the key word character strings the character appears in.

29. A method according to claim 25, wherein the step (b) includes the substeps of

(b1) determining if each character in the text character string is to be a leading character of a candidate character string,

(b2) determining if each character in the text character string is to be an intermediate character in a candidate character string including a character in the text character string immediately preceding the character, and

(b3) determining if a character in the text character string immediately preceding each character in the text character string is to be a final character in a candidate character string including the preceding character,

wherein the substeps (b1), (b2), and (b3) are performed based on the appearance mode for each character in the text character string and the appearance mode for a character in the text character string immediately preceding the character.

30. A method according to claim 29, wherein

the substep (b1) includes the substep of determining that a character in the text character string is to be a leading character of a candidate character string when the appearance mode for the character indicates that the character appears in the key word character string and the appearance mode for the preceding character indicates that the preceding character does not appear in the key word character string,

the substep (b2) includes the substep of determining that a character in the text character string is to be an intermediate character in a candidate character string including a character in the text character string immediately preceding the character when the appearance mode for the character and the appearance mode for the preceding character indicate that the character and the preceding character both appear in the key word character string, and

the substep (b3) includes the substep of determining that a character in the text character string immediately preceding each character in the text character string is to be a final character in a candidate character string including the preceding character when the appearance mode for the character indicates that the character does not appear in the key word character string and the appearance mode for the preceding character indicates that the preceding character does appear in the key word character string.

31. A method according to claim 25, wherein the appearance mode includes position information relating to a position of the character in the key word character string.

32. A method according to claim 31, wherein the position information includes information indicating if the character is a leading character, an intermediate character, or a last character in the key word character string.

33. A method according to claim 31, wherein

the key word character string is one of a plurality of key word character strings, and

the position information includes information indicating whether a length of the key word character string from a beginning of the key word character string up to and including the position of the character in the key word character string is less than or equal to a length of a shortest one of the key word character strings.

34. A method according to claim 31, wherein

the position information includes information indicating a position of the character in the key word character string, and

the step (b) includes the substep of determining that a character in the text character string is not to be included in the candidate character string when the appearance mode indicates that the character appears in the key word character string but the position information indicates that the position of the character in the key word character string would conflict with a position of the character in the candidate character string if the character were to be included in the candidate character string.

35. A method according to claim 31, wherein

the position information includes information indicating a position of the character in the key word character string, and

the step (b) includes the substep of determining that a character in the text character string is not to be included in a current candidate character string including a character in the text character string immediately preceding the character in the text character string but is to be included in a new candidate character string when the appearance mode for the character and the appearance mode for the preceding character indicate that the character and the preceding character both appear in the key word character string but the position information indicates that the position of the character in the key word character string would conflict with a position of the character in the current candidate character string if the character were to be included in the current candidate character string.

36. A method according to claim 25, wherein

the step (a) includes the substeps of

(a1) dividing the text character string into a plurality of sets of characters, each set of characters constituting a composite character, and

(a2) determining, for each of the composite characters, an appearance mode indicating at least if the composite character appears in the key word character string, and

the step (b) includes the substep of detecting, from the text character string, a candidate character string constituted by a sequence of composite characters each appearing in the key word character string based on the appearance mode for each composite character in the text character string.

37. A method of searching a text character string for a character string coinciding with a key word character string, the method being performed by a computer and comprising the steps of:

(a) detecting, from the next character string, a plurality of candidate character strings likely to coincide with the key word character string; and

(b) determining if the candidate character strings include a candidate character string coinciding with the key word character string;

wherein the step (a) includes the substep of detecting a plurality of sequences of characters from the text character string, each of the sequences of characters being a continuous series of characters in the text character string, wherein each of the characters in each of the sequences of characters appears in the key word character string such that the sequences of characters constitute respective candidate character strings likely to coincide with the key word character string.

38. A method of searching a text character string for a character string coinciding with a key word character string, the method being performed by a computer and comprising the steps of:

(a) detecting, from the text character string, a plurality of candidate character strings likely to coincide with the key word character string; and

(b) determining if the candidate character strings include a candidate character string coinciding with the key word character string;

wherein

the key word character string is one of a plurality of key word character strings,

the step (a) includes the substep of detecting a sequence of characters from the text character string, the sequence of characters being a continuous series of characters in the text character string, wherein each of the characters in the sequence of characters appears in at least one of the key word character strings such that the sequence of characters constitutes a candidate character string likely to coincide with any of the key word character strings, and

the step (b) includes the substep of determining if the sequence of characters coincides with any of the key word character strings.

39. A method of searching a text character string for a character string coinciding with a key word character string, the method being performed by a computer and comprising the steps of:

(a) detecting, from the text character string, a plurality of candidate character strings likely to coincide with the key word character string; and

(b) determining of the candidate character strings include a candidate character string coinciding with the key word character string;

wherein

the key word character string is one of a plurality of key word character strings,

the step (a) includes the substeps of

(a1) detecting a plurality of candidate character strings likely to coincide with any of the key word character strings from (1) a text vector including elements representing each of the characters in the text character string and (2) a plurality of key word vectors each including elements representing each of the characters in a respective one of the key word character strings, and

(a2) generating a primary result vector including elements each representing a respective one of the candidate character strings, and

the step (b) includes the substep of determining, based on the primary result vector, if each of the candidate character strings coincides with any of the key word character strings.