Document search method wherein stored documents and search queries comprise segmented text data of spaced, nonconsecutive text elements and words segmented by predetermined symbols

• US 5,748,953 A
• Filed: 05/18/1995
• Issued: 05/05/1998
• Est. Priority Date: 06/14/1989
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Kato, Kanji, Hatakeyama, Atsushi, Asakawa, Satoshi, Tada, Katsumi, Kawaguchi, Hisamitsu, Mizutani, Natsuko
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/444,842
• Time in Patent Office: 1,083 Days
• Field of Search: 395/606, 395/601-605, 395/611-612, 395/761, 395/793, 364/DIG. 1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• 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/99936 Pattern matching access

Abstract

A neighboring plural-character occurrence bitmap of a practical capacity capable of eliminating noises by hashing is realized, and a high speed full text search is realized equivalently, by greatly reducing the number of documents to be searched even if a search term constituted by a combination of English characters and words is used. Text data is segmented into words, and n-character strings at every (m+l)-th character positions are extracted from each word. A neighboring plural-character occurrence bitmap is created which stores data representing a presence of each neighboring plural-character string at a certain entry thereof. N-character strings at every (m+l)-th character positions are extracted from a search term and the neighboring plural-character occurrence bitmap is searched by using a search control program. Since the neighboring plural-character occurrence bitmap is searched prior to searching condensed texts, documents not relevant to the search term can be discarded and a high speed full text search can be realized.

Claims

1. A document search method in a data base of stored documents comprising the steps of:

extracting a partial character string in a predetermined form from each of the stored documents;

creating a neighboring plural-character occurrence bitmap for indicating whether each of said documents contains any of said partial character strings;

extracting a search term partial character string in a predetermined form from a search term inputted for searching for a desired document from said stored documents; and

referring to said neighboring plural-character occurrence bitmap for said extracted search term partial string to search if any of said stored documents contains said search term partial character string, and to discard any of said stored documents not containing said search term partial character string,

wherein;

said partial character string and said search term partial character string comprise predetermined n-character strings selected from predetermined (m+1)-th character positions from each of said stored documents and exclude intermediate elements between said predetermined (m+1)-th character positions where n is an integer of 2 or larger and m is an integer of 1 or larger.

2. The document search method according to claim 1, wherein said extracting said partial character string from each of said documents further comprises segmenting each of said documents into words.

3. The document search method according to claim 2, wherein said partial character string is extracted from each of said segmented words;

and

said search term partial character string is extracted from said search term.

4. The document search method according to claim 2, further comprising adding a predetermined code before and after each of said segmented words;

and,

extracting said partial character string from each of said segmented words added with said predetermined codes.

5. The document search method according to claim 4, further comprising adding said predetermined code before and after said search term;

and

extracting said search term partial character string from said search term added with said predetermined codes.

6. The document search method according to claim 1, wherein:

character strings of predetermined consecutive i-character strings and character strings of predetermined n-character strings at every predetermined (m+1)-th character positions are extracted from each of said segmented words, as said partial character strings, where i is an integer of 2 or larger, n is an integer of 2 or larger, and m is an integer of 1 or larger; and

character strings of predetermined consecutive i-character strings and character strings of predetermined n-character strings at every predetermined (m+1)-th character positions are extracted from said search term, as said search term partial character strings, where i is an integer of 2 or larger, n is an integer of 2 or larger, and m is an integer of 1 or larger.

7. The document search method according to claim 6 further comprising segmenting each of said documents into words before extracting said partial character string from each of said documents,

extracting said partial character strings of predetermined consecutive i-character strings and character strings of predetermined n-character strings at every predetermined (m+1)-th character positions from each of said segmented words, where i is an integer of 2 or larger, n is an integer of 2 or larger, and m is an integer of 1 or larger;

and

extracting said search term partial character strings of predetermined consecutive i-character strings and character strings of predetermined n-character strings at every predetermined (m+1)-th character positions from said search term, where i is an integer of 2 or larger, n is an integer of 2 or larger and m is an integer of 1 or larger.

8. The document search method according to claim 7, further comprising adding a predetermined code before and after each of said words segmented from each of said documents;

extracting said partial character string from each of said segmented words added with said predetermined codes;

adding said predetermined code before and after said search term; and

,

extracting said search term partial character string from said search term added with said predetermined codes.

9. The document search method according to claim 7 wherein

said segmenting comprises segmenting each of said documents into words in respective character classes;

said extracting said search term partial character strings from said search term comprises segmenting said search term into words in respective character classes;

wherein said character string of predetermined consecutive i-character strings is extracted from said words segmented from each of said documents, as said partial character string, where i is an integer or 2 or larger; and

said character string of predetermined n-character strings at every predetermined (m+1)-th character position are extracted from said words segmented from said search term, as said search term partial character string, where n is an integer of 2 or larger and m is an integer of 1 or larger.

10. The document search method according to claim 9, wherein when each of said documents is segmented into words and when said search term is segmented into words or words are detected from said search term, division into said words is performed only when two consecutive character classes take a particular combination.

11. The document search method according to claim 7, wherein

said segmenting comprises segmenting each of said documents into words in respective character classes;

adding a predetermined code before and after said words segmented from each of said documents;

extracting a partial character string of predetermined consecutive i-character strings and character strings of predetermined n-character strings at every predetermined (m+1)-th character positions from each of said segmented words, where i is an integer of 2 or larger, n is an integer of 2 or larger, and m is an integer of 1 or larger;

detecting words from said search term in respective classes;

adding said predetermined code before and after each of said words of said search term; and

extracting a search term partial character string of predetermined consecutive i-character strings from said search term where m is an integer of 2 or larger.

12. The document search method according to claim 7, wherein said segmenting comprises segmenting each of said documents is segmented into words in respective character classes;

wherein a character string of predetermined consecutive m-character strings is extracted from said words segmented from each of said documents, as said partial character string, where m is an integer of 2 or larger;

in extracting said search term partial character string from said search term, segmenting said search term into words in respective character classes; and

wherein said character string of predetermined consecutive m-character strings is extracted from said words segmented from said search term, as said search term partial character string.

13. A document search method according to claim 7, wherein;

in segmenting each of said documents into words, each of said documents is segmented into words in respective character classes;

a predetermined code is added before and after said words segmented from each of said documents;

character strings of predetermined consecutive m-character strings are extracted from each of said segmented words, as said partial character strings, where m is an integer of 2 or larger;

words are detected from said search term in respective classes;

said predetermined code is added before and after each of said words of said search term; and

character strings of predetermined consecutive m-character strings are extracted from said search term, as said search term partial character strings, where m is an integer of 2 or larger.

14. The document search method according to claim 13, wherein when each of said documents is segmented into words and when said search term is segmented into words or words are detected from said search term, at least one of a dictionary containing word information and a language processing based on a characteristic of language describing each of said documents, is used.

15. The document search method according to claim 14, wherein:

said neighboring plural-character occurrence bitmap includes a bit list and a document number list, said bit list storing appearance information of a character string by setting a "1" at a bit position corresponding to a document number containing a neighboring plural-character string having an appearance frequency higher than a predetermined threshold value, and said document number list for a neighboring plural-character string having an appearance frequency lower than a predetermined threshold value, storing a document number containing a neighboring plural-character string having an appearance frequency lower than the predetermined threshold value, in the form of a binary data list;

the type of each neighboring plural-character constituent appearing in each of said documents and the number of documents in which each neighboring plural-character constituent appears being calculated in advance;

whether the number of occurrence documents in which texts each neighboring plural-character string appears is larger than said threshold value is judged from the calculated results;

if the number of occurrence documents is judged to be larger than said predetermined threshold value, appearance information of each neighboring plural-character constituent is registered by setting the "1" at a bit position of said bit list corresponding to a document number in which the associated neighboring plural-character string appears;

if the number of occurrence documents is judged to be smaller than said predetermined threshold value, appearance information of each neighboring plural-character constituent is registered by writing a binary data list of a document number in which the associated neighboring plural-character string appears, in said document number list; and

the bit list corresponding to a neighboring plural-character string extracted from said search term is read from said neighboring plural-character occurrence bitmap or said document number list corresponding to a neighboring plural-character string extracted from said search term is read from said neighboring plural-character occurrence bitmap and said document number list is converted into a bit list.

16. The document search method according to claim 15, wherein:

a neighboring plural-character string having a high appearance frequency is selected by using statistics information;

each neighboring plural-character string appearing in each said documents is judged whether said neighboring plural-character is selected as having a high appearance frequency;

if the selecting indicates a high appearance frequency, appearance information of each neighboring plural-character constituent is registered by setting the "1" at a bit position of said bit list corresponding to a document number in which the associated neighboring plural-character string appears; and

if the selecting indicates a low appearance frequency, appearance information of each neighboring plural-character constituent is registered by writing a binary data list of a document number in which the associated neighboring plural-character string appears, in said document number list.

17. The document search method according to claim 16, wherein:

dividing said registered documents into groups of a predetermined number of documents in accordance with a predetermined rule;

extracting a neighboring plural-character string from each of said divided groups, and creating said bit list and said document number list for each neighboring plural-character string; and

merging said bit list and said document number list created for each of said groups to create said neighboring plural-character occurrence bitmap for all of said stored documents.

18. The document search method according to claim 17, wherein further comprising outputting documents not discarded by a search of said neighboring plural-character occurrence bitmap as a search result.