Method for character string collation with filtering function and apparatus

• US 5,471,610 A
• Filed: 03/15/1993
• Issued: 11/28/1995
• Est. Priority Date: 06/14/1989
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Tada, Katsumi, Kato, Kanji, Kawaguchi, Hisamitsu, Shinozaki, Masatsugu
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WANG, PETER
• Application Number:
  US08/031,625
• Time in Patent Office: 988 Days
• Field of Search: 395/600, 364/419-420
• US Class Current: 707/610
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Character string retrieval method and system for deciding en bloc whether or not a plurality of search terms as designated exist in a text composed of characters expressed in the form of character codes is characterized by inclusion of a character string storage unit for storing a text, a filtering unit for fetching character codes from a text read out from the character string storage unit to thereby output only those character codes that are included in the search term, and a character string matching unit for matching en bloc to decide whether or not the aforementioned search term exists in the string of character codes outputted from the filtering unit.

Claims

1. A text search system for deciding en bloc whether or not a plurality of user-designated search terms exist in a text composed of characters expressed in the form of character codes,

characterized in that said system comprises:

character string storage means for storing a text;

filtering means for fetching character codes from the text read out from said character string storage means to thereby output only those character codes that are included in said search terms;

character string matching means for matching en bloc a string of character codes outputted from said filtering means with said search terms to thereby decide whether or not said search terms exist in said string of character codes outputted from said filtering means; and

synchronizing means provided between said filtering means and said character string matching means for buffering differences in processing speed while transferring data from said filtering means to said character string matching means.

2. A text search system set forth in claim 1,

characterized in that said filtering means includes flag storage means for setting a value of "1" indicating "ON" in slots corresponding to the character codes of the characters included in the search terms designated previously while setting a value of "0" indicating "OFF" in slots corresponding to the other character codes;

and

output select means for referencing said flag storage means in correspondence to a character code inputted on a one-by-one Character code basis from said character string storage means to thereby output to said character string matching means a character code only when a relevant flag as read out from said flag storage means is "ON".

3. A text search system set forth in claim 2,

characterized in that said output select means further includes delimiter code output means for referencing said flag storage means in correspondence to a character code inputted from said character string storage means to thereby inhibit the character code from being outputted when the relevant flag is "OFF" while outputting to said character string matching means a particular delimiter code only when an output flag of said flag storage means which corresponds to an immediately preceding input character code is "ON".

4. A text search system set forth in claim 1,

characterized in that said filtering means include leading character flag storage means for setting a value indicating "ON" in a slot corresponding to a leading character code of a search term designated previously while setting a value indicating "OFF" in slots corresponding to the other character codes, and trailing character flag storage means for setting a value indicating "ON" in slots corresponding to other character codes than said leading character code of those character codes which are included in said search term while setting a value indicating "OFF" in slots corresponding to the other character code;

and that

said system further comprises output select means for referencing said leading character flag storage means and said trailing character flag storage means in correspondence to a character code inputted from said character string storage means to thereby output the character code to said character string matching means only when the relevant leading character flag as read out is "ON", while when said leading character flag once assumed "ON", said output select means outputs an input character code to said character string matching means only when either the relevant leading character flag or trailing character flag is "ON" before both of said leading character flag and said trailing character flag become "OFF".

5. A text search system set forth in claim 4,

characterized in that said output select means further includes delimiter code output means for outputting a particular delimiter code to said character string matching means only when said leading character flag and trailing character flag corresponding to character codes as inputted are "OFF" and when said leading character flag and trailing character flag corresponding to character codes inputted in precedence by one character are "ON".

6. A text search system set forth in claim 1 further comprising,

text search system further comprises first-in/first-out type buffering means for storing a string of character codes outputted from said filtering means and then outputting said stored string of character codes to said character matching means in dependence on the processing state of said character string matching means.

7. A text search system set forth in claim 6,

characterized in that said buffering means includes first-in/first-out type buffer means.

8. A text search system set forth in claim 6,

characterized in that said buffering means includes exchange buffering means.

9. A text search system for deciding en bloc whether or not a plurality of user-designated search terms exist in a text composed of characters expressed in the form of character codes,

characterized in that said system comprises:

character string storage means for storing a text;

concatenate filtering means for fetching character codes sequentially from the text read out from said character string storage means to thereby make decision as to whether or not n, where n represents an integer not smaller than 2, character codes as fetched are included in said search terms as a concatenate character string and output said n concatenate character codes only when said codes are included in said search terms;

character string matching means for deciding by matching en bloc whether or not said search terms exist in a compound character string composed of a chain of the character strings each constituted by n concatenate character codes outputted from said concatenate filtering means; and

synchronizing means provided between said concatenate filtering means and said character string matching means for buffering differences in processing speed while transferring data from said concatenate filtering means to said character string matching means.

10. A text search system set forth in claim 9,

characterized in that the n concatenate character codes fetched from said character string storage means are divided into a first character code string, referred to as a leading text code string including m character codes as counted from the leading one of said n concatenate character codes, inclusive of said leading code, and a second character code string, referred to as a trailing text code string, including n-m character codes succeeding to said leading text code string,

said concatenate filtering means including:

offset storage means which is accessed with an address represented by said leading text code string and which stores therein undermentioned offset values;

offset adding means for determining a sum of an offset value outputted from said offset storage means and said trailing text code string;

verify storage means for storing n concatenate character codes contained in the search terms as designated, said verify storage means being accessed by using the output of said offset addition means as an address; and

character code string comparing means for comparing the n concatenate character codes read out from said verify storage means with n concatenate character codes read out from said character string storage means, to thereby output a coincidence signal when said comparison results in coincidence;

wherein said offset storage means stores the offset values in slots which are accessed by using as addresses m character codes, referred to as a leading term code string, as counted from the start of the n concatenate character codes, referred to as a term code string, contained in the designated search term, said offset values being obtained by subtracting from address values of the slots of said verify storage means in which said term code string is stored the values of n-m character code strings, referred to as trailing term code strings, which succeed to the leading term code string of said term code string.

11. A text search system set forth in claim 9,

characterized in that said concatenate filtering means is comprised of a pointer table for storing order numbers, referred to as serial numbers, allotted in correspondence to the character codes included in the search term designated previously in slots which can be accessed with addresses indicated by said character codes, and a concatenate filtering table storing flags indicating "ON" in slots accessed by using as addresses therefor codes each represented by a string of the serial numbers corresponding to n concatenate character codes, respectively, which are included in the designated search term while storing "OFF" in the other slots.

12. A text search system set forth in claim 9,

characterized in that said concatenate filtering means includes flag storage means for setting a value indicating "ON" in slots corresponding to the character codes of the n concatenate characters included in the search term designated previously while setting a value indicating "OFF" in slots corresponding to the character codes of the other n concatenate characters;

and that

said system further comprises output select means for referencing said flag storage means in correspondence to n concatenate character codes inputted from said character string storage means to thereby output n concatenate character codes to said character string matching means only when the flag as read out from said flag storage means is "ON".

13. A text search system set forth in claim 12,

characterized in that said output select means further includes delimiter code output means for outputting to said character string matching means a particular delimiter code only when said flag corresponding to the n concatenate character codes as inputted is "OFF" and when said flag corresponding to n concatenate character codes inputted immediately before is "ON".

14. A text search system set forth in claim 9,

characterized in that said filtering means includes leading concatenate character flag storage means for setting a value indicating "ON" in slots corresponding to concatenate character codes of a leading portion, referred to as leading concatenate character code, of the search term designated previously while setting a value indicating "OFF" in slots corresponding to the other character codes, and trailing concatenate character flag storage means for setting a value indicating "ON" in slots corresponding to other concatenate character codes, referred to as trailing concatenate character codes, than said leading concatenate character codes contained in said search term while setting a value indicating "OFF" in a slot corresponding to the other concatenate character codes;

said system further comprising output select means for referencing said leading concatenate character flag storage means and said trailing concatenate character flag storage means in correspondence to n concatenate character codes inputted from said character string storage means sequentially, to thereby output said concatenate character codes to said character string matching means only when the relevant leading concatenate character flag as read out is "ON" while when said leading character flag once assumed "ON", said output select means outputs the input character codes to said character string matching means only when either the relevant leading character flag or trailing character flag is "ON" before both of said leading character flag and said trailing character flag become "OFF".

15. A text search system set forth in claim 14,

characterized in that said output select means further includes delimiter code output means for outputting to said character string matching means a particular delimiter code only when said leading character string flag and said trailing character string flag corresponding to the n input concatenate character codes are "OFF" and when said leading character string flag and said trailing character string flag corresponding to n concatenate character codes immediately preceding to said n input character codes of "OFF" are "ON".

16. A text search system set forth in claim 9,

wherein every time an input character code is fetched on a one-by-one character basis sequentially from the text read out from said character string storage means, said concatenate filtering means makes a decision as to whether or not the character codes of n characters fetched till then inclusive of said input character code are included in said search terms as a string of concatenate characters, for thereby outputting the character code fetched first of said n concatenate character codes to said character string matching means only when said character codes of n characters are decided as being included in said search terms as a concatenate character string.

17. A text search system set forth in claim 16,

characterized in that said concatenate filtering means includes flag storage means for setting a value indicating "ON" in slots corresponding to the character codes of n concatenate characters which are included in the search terms designated previously while setting a value indicating "OFF" in slots corresponding to the character codes of the other n concatenate characters;

and

output select means, wherein every time the input character code is fetched on a one-by-one character basis sequentially from the text read out from said character string storage means, said output select means references said flag storage means in correspondence to the character codes of n characters fetched till then inclusive of said input character code, for thereby outputting the character code fetched first of said n concatenate character codes to said character string matching means only when the flag as read out is "ON".

18. A text search system set forth in claim 17,

characterized in that said output select means further includes delimiter code output means, wherein every time an input character code is fetched on a one-by-one character basis sequentially from the text read out from said character string storage means, said delimiter code output means outputs a particular delimiter code to said character string matching means only when the flag corresponding to the character codes of n characters fetched till then inclusive of said input character code is "OFF" and when the flag corresponding to n character codes fetched up to a time when an input character code immediately preceding to the first mentioned input character code is fetched, inclusive of the second mentioned input character code, is "ON".

19. A text search system for deciding en bloc whether or not a plurality of user-designator search terms exist in a text composed of characters expressed in the form of character codes,

characterized in that said system comprises:

character string storage means for storing the text;

parallel filtering means for fetching character codes sequentially on an n-by-n character basis from the text read out from said character string storage means to thereby make decision for m, where m represents a divisor of n, characters in parallel as to whether or not n, where n represents an integer not smaller than 2, character codes as fetched are included in said search terms as concatenate character strings and output said n concatenate character codes only when they are included in said search term;

character string matching means for deciding by matching en bloc whether or not said search terms exist in a compound character string constituted by a chain of character strings each composed of n concatenate character codes outputted from said parallel filtering means; and

synchronizing means provided between said parallel filtering means and said character string matching means for buffering differences in processing speed while transferring data from said parallel filtering means to said character string matching means.

20. A text search system set forth in claim 19,

characterized in that said parallel filtering means includes:

character codes distributing means for outputting distributively input character codes every time the character code is fetched on a one-by-one character basis in sequence from the text read out from said character string storage means;

m filtering means connected in parallel with one another for making decision as to whether or not the character codes outputted from said distributing means are included in said search terms; and

collecting means for fetching and arraying the character codes outputted from said m filtering means to thereby output the arrayed character codes to said character string matching means.

21. A text search system set forth in claim 19,

characterized in that said filtering means includes parallel filtering means,

wherein every time an input character code is fetched on a one-by-one character basis sequentially from the text read out from said character string storage means, said parallel filtering means makes decision for m, where m represents a divisor of n, characters in parallel as to whether or not the character codes of n characters fetched till then inclusive of said input character code are included in the search terms as a string of concatenate characters, for thereby outputting the character code fetched first of said n concatenate character codes to said character string matching means only when said character codes of n characters are decided as being included in said search terms as a concatenate character string.

22. A text search system set forth in claim 21,

characterized in that said system further includes collecting means for storing once the character codes outputted from the m filtering means in a buffer in dependence on a processing state of said character string matching means, wherein said character codes are outputted to said character string matching means in accordance with the order in which said character codes were inputted to said distributing means.

23. A text search system set forth in claim 19,

characterized in that said parallel filtering means includes distributing means for fetching n character codes at one time from the text read out form said character string storage means to thereby output said character codes while dividing them;

m filtering means connected in parallel for making decision as to whether or not the character codes outputted from said distributing means are those character codes which are included in said search terms; and

collecting means for fetching and arraying the character codes outputted from said m filtering means to thereby output the arrayed character codes to said character string matching means.

24. A text search system set forth in claim 23,

characterized in that said filtering means include leading concatenate character flag storage means for setting a value indicating "ON" in a slot corresponding to concatenate character codes of a leading portion, referred to as leading concatenate character codes, of the search term designated previously while setting a value indicating "OFF" in slots corresponding to the other character codes, and trailing concatenate character flag storage means for setting a value indicating "ON" in slots corresponding to other concatenate character codes, referred to as trailing concatenate character codes, than said leading concatenate character codes contained in said search term while setting a value indicating "OFF" in slots corresponding to the other concatenate character codes;

said system further comprising output select means for referencing said leading concatenate character flag storage means and said trailing concatenate character flag storage means in correspondence to n concatenate character codes inputted from said character string storage means sequentially, to thereby output said concatenate character codes to said character string matching means only when the relevant leading concatenate character flag as read out is "ON" while when said leading character flag once assumed "ON", said output select means outputs the input character codes to said character string matching means only when either the relevant leading character flag or trailing character flag is "ON" before both of said leading character flag and said trailing character flag become "OFF".

25. A text search system set forth in claim 23,

characterized in that said filtering means includes delimiter output means for fetching n concatenate character codes sequentially from the text read out from said character string storage means to thereby output said n concatenate character codes to said character string matching means only when said n concatenate character codes are included in the designated search terms, while outputting a particular delimiter code to said character string matching means when said n concatenate character codes are not included in the designated search terms and when n concatenate characters inputted immediately before are included in said search terms.

26. A text search system set forth in claim 25,

characterized in that said filtering means further includes delimiter code output means, wherein every time an input character code is fetched on a one-by-one character basis sequentially from the text read out from said character string storage means, said delimiter code output means outputs a particular delimiter code to said character string matching means only when the flag correspond to the character codes of n characters fetched till then inclusive of said input character code is "OFF" and when the flag corresponding to n character codes fetched up to a time point when an input character code immediately preceding to the first mentioned input character code is fetched, inclusive of the second mentioned input character code, is "ON".

27. A text search method for deciding en bloc whether or not a plurality of user-designated search terms exist in a text composed of characters expressed in the form of character codes,

characterized in that character codes are fetched from said text to output only those character codes that are included in said search terms by extracting said character codes, referred to as filtering;

matching is performed en bloc for deciding whether or not said search terms exist in the string of said character codes as outputted; and

synchronizing between said filtering and said matching for buffering differences in processing speed while transferring data from said filtering to said matching.

28. A text search method set forth in claim 27,

characterized in that in said filtering, a value indicating "ON" is set as a flag to a leading character code of the search term designated previously with a value indicating "OFF" being set as a flag to other character codes, the flags being referred to as leading character flags, while a value indicating "ON" is set as a flag to other character code than said leading character code of those included in said search term with a value indicating "OFF" being set as a flag to the other character code then said those codes, the flags being referred to as trailing character flags, and that

said leading character flag and trailing character flag are referenced in correspondence to character codes inputted on a one-by-one character code basis to thereby output a character code only when the relevant leading character flag as read out is "ON" and wherein an input character code is outputted when either the relevant leading character flag or trailing character flag is "ON" before both of said leading character flag and trailing character flag become "ON", when said leading character flag is once assumed "ON".

29. A text search method set forth in claim 27,

characterized in that in said selective outputting, a particular delimiter code is outputted only when said leading character flag and trailing character flag corresponding to character codes as inputted are "OFF" and when said leading character flag and trailing character flag corresponding to character codes inputted immediately before are "ON".

30. A text search method set forth in claim 27,

characterized in that in said filtering, a value indicating "ON" is set as a flag for the character codes of the characters which are included in the search terms designated previously while a value indicating "OFF" is set as a flag for the other character codes, and that

said flags are referenced in correspondence to a character code inputted on a one-by-one character basis from said text to thereby output a character code only when a relevant flag is "ON", said character code as outputted being then subjected to a character string matching.

31. A text search method set forth in claim 30,

characterized in that said flags are referenced in correspondence to a character code as inputted to thereby inhibit the character code from being outputted when the relevant flag is "OFF" while outputting a particular delimiter code only when the flag which corresponds to an immediately preceding input character code is "ON".

32. A text search method for deciding en bloc whether or not a plurality of user-designated search terms exist in a text composed of characters expressed in the form of character codes,

characterized in that character codes are sequentially fetched from said text to thereby make a decision as to whether or not n, where n represents an integer not smaller than 2, character codes as fetched are included in said search terms as a concatenate character string and output by extracting said n concatenate character codes, referred to as concatenate filtering, only when they are included in said search terms, and that

matching is performed en bloc for deciding whether or not said search terms exist in a compound character string constituted by a chain of character strings each composed of the n concatenate character codes as outputted, and

synchronizing between said filtering step and said matching step for buffering differences in processing speed while transferring data from said filtering step to said matching step.

33. A text search method set forth in claim 32,

characterized in that in said filtering, a value indicating "ON" is set as a flag for the character codes of the n concatenate characters included in the search terms designated previously while setting a value indicating "OFF" as a flag for the character codes of the other n concatenate characters, and that

said flags are referenced in correspondence to n concatenate character codes as inputted to thereby output selectively n concatenate character codes only when the relevant flag as read out is "ON".

34. A text search method set forth in claim 32,

characterized in that in said selective outputting, a particular delimiter code is outputted only when said flag corresponding to the n concatenate character codes as inputted is "OFF" and when said flag corresponding to n concatenate character codes inputted immediately before is "ON".

35. A text search method set forth in claim 32,

characterized in that in said concatenate filtering is effected by using a pointer table storing order numbers, referred to as serial numbers, allotted in correspondence to the character codes included in the search term designated previously in slots indicated by said character codes, and a concatenate filtering table storing flags indicating "ON" in slots accessed by using as addresses therefore codes each represented by a string of the serial numbers corresponding to n concatenate character codes, respectively, which are included in the designated search term while storing "OFF" in the other slots.

36. A text search method set forth in claim 32,

characterized in that in said concatenate filtering;

for the n concatenate character code string, referred to as a leading text code string, including m character codes as counted from the leading one of said n concatenate character codes and a character code string, referred to as a trailing text code string, including n-m character codes succeeding to said leading text code string;

offset values mentioned below are stored in an offset table which is accessed with an address represented by said leading text code string;

a sum of the offset value read out from said offset table and said trailing text code string is determined as an offset-added value;

n concatenate character codes contained in the search term as designated are stored in slots of a verify table which can be accessed by using said offset-added value as an address; and

n concatenate character codes read out from said verify table are compared with n concatenate character codes read out from said text, to thereby output a coincidence signal when said comparison results in coincidence;

wherein the offset values are stored in slots which are accessed by suing as addresses m character codes, referred to as a leading term code string, from the start of the n concatenate character codes, referred to as a term code string, contained in the designated search term, said offset values being obtained by subtracting from an address value of the slot of said verify table in which said term code string is stored the values of n-m character code strings, referred to as trailing term code strings, which succeed to the leading term code string of said term code string.

37. A text search method set forth in claim 32,

characterized in that in said filtering, a value indicating "ON" is set as a flag for concatenate character codes, referred to as leading concatenate character codes, of a leading portion of the search term designed previously with a value indicating "OFF" being set as a flag to other character codes, referred to as trailing concatenate character codes, then said leading concatenate character codes in those included in said search term, while a value indicating "ON" is set as a flag to the other concatenate character codes, and that

said leading concatenate character flag and said trailing concatenate character flag are referenced in correspondence to n concatenate character codes inputted sequentially to thereby output concatenate character codes to said character string matching only when the relevant leading concatenate character flag as read out is "ON" and selectively output n input concatenate character codes to said character string matching only when either the relevant leading concatenate character flag or designated concatenate character flag is "ON" before both of said leading concatenate character flag and said trailing concatenate character flag become "OFF", when said leading concatenate character flag is once assumed "ON".

38. A test search method set forth in claim 37,

characterized in that in said selective outputting, a particular delimiter code is outputted to said character string matching means only when said leading character string flag and trailing character string flag corresponding to the n concatenate character codes as inputted are "OFF" and when said leading character string flag and said trailing character string flag corresponding to n concatenate character codes as inputted immediately before are "ON".