Information search method, information search device, and storage medium for storing an information search program

Abstract

A system and a method for searching does not rely on prior compiled vocabulary information or grammatical information to perform a search. The search may accommodate new words or phrases, and perform a document search using a request of a user for document search. A unique character string is extracted from an input document and a similarity search is performed by using the unique character string. The extraction of the unique character string is performed by calculating and evaluating an amount of feature of a character string through comparison between appearance frequency appearing in the input document and appearance frequency in a set of documents to be searched. Then, the extracted unique character string is used as the basis for the search. Documents found by the search are evaluated and arranged in the order of evaluation. The similarity factor of document is evaluated by using the appearance frequency of each unique character string in the input document so that higher evaluation is provided to a document in which unique character strings with higher weight appears many times.

Claims

What is claimed is:

1. A method for identifying at least one unique character string in an input document which is input into a computer system, said computer system being operable to search one or more documents which are searchably stored in a storage medium, and said unique character string is used as a search string, the method comprising:

associating and managing position information for a position in said searchably stored documents where one or more partial comparison document character strings are extracted from said searchably stored documents;

extracting a partial input character string from said input document, and determining whether said partial input character string is a candidate character string;

identifying a partial comparison document character string which matches at least a part of said candidate character string with a predetermined similarity factor or higher;

identifying position data associated with said partial comparison document character string which matches with said predetermined similarity factor or higher; and

recognizing said candidate character string as the unique character string by comparing appearance frequency information of at least a part of said candidate character string appearing in said input document with the position data and evaluating an amount of feature of said candidate character string.

2. A method for identifying at least one unique character string as said search string according to claim 1, wherein in recognizing said candidate character string as the unique character string, said amount of feature is a point allocation for said candidate character string and points are allocated according to the equation: ##EQU11## where: count i=appearance frequency of an i-th candidate character string in the input document;

Ncount i j=appearance frequency of a j-th partial input character string of the i-th candidate character string in the input document;

Nsize i j=position data corresponding to the j-th partial input character string of the i-th candidate character string;

Nnum i=a number of partial input character strings contained in an i-th candidate character string;

Max (Nsize i j)=maximum Nsize i j for all searchably stored documents;

Max (Ncount i j)=maximum Ncount i j for all searchably stored documents.

3. A method for searching for a document to be searched from one or more documents searchably stored in a computer, said document to be searched having a character string similar to a partial input character string existing in an input document input in the computer, the method comprising:

extracting a partial character string from said input document, and determining whether said partial character string is a candidate character string;

evaluating an amount of feature of said candidate character string through comparison between appearance frequency information of at least a part of said candidate character string appearing in said input document and appearance frequency information of at least a part of said candidate character string appearing in said searchably stored documents to recognize said candidate character string as a unique character string; and

searching for said document to be searched from said searchably stored documents, wherein said document to be searched has a character string similar to said unique character string.

4. The method for searching for a document according to claim 3, wherein in evaluating the amount of feature of said candidate character string, said amount of feature is a point allocation for said candidate character string and points are allocated according to the equation: ##EQU12## where: count i=appearance frequency of an i-th candidate character string in the input document;

Ncount i j=appearance frequency of a j-th partial input character string of the i-th candidate character string in the input document;

Nsize i j=position data corresponding to the j-th partial input character string of the i-th candidate character string;

Nnum i=a number of partial input character strings contained in an i-th candidate character string;

Max (Nsize i j)=maximum Nsize i j for all searchably stored documents;

Max (Ncount i j)=maximum Ncount i j for all searchably stored documents.

5. A method for identifying at least one unique character string in an input document which is input into a computer system, said computer system being operable to search one or more documents stored in a storage medium, and using said unique character is used as a search string, the method comprising:

extracting a partial input character string from said input document, and determining whether said partial input character string is a candidate character string; and

evaluating an amount of feature of said candidate character string through comparison between appearance frequency information of at least a part of said candidate character string appearing in said input document and appearance frequency information of at least a part of said candidate character string appearing in said searchably stored documents to recognize said candidate character string as said unique character string.

6. A method for identifying at least one unique character string as the search string of claim 5, wherein in evaluating the amount of feature, said amount of feature is a point allocation for said candidate character string and points are allocated according to the equation: ##EQU13## where: count i=appearance frequency of an i-th candidate character string in the input document;

Ncount i j=appearance frequency of a j-th partial input character string of the i-th candidate character string in the input document;

Nsize i j=position data corresponding to the j-th partial input character string of the i-th candidate character string;

Nnum i=a number of partial input character strings contained in an i-th candidate character string;

Max (Nsize i j)=maximum Nsize i j for all searchably stored documents;

Max (Ncount i j)=maximum Ncount i j for all searchably stored documents.

7. A method for evaluating similarity between a comparison document and an input document which contains a first unique character string and a second unique character string input in a computer, said computer system being operable to search for said comparison document stored in a storage medium, the method comprising:

calculating a first weight value corresponding to said first unique character string from appearance frequency information of at least a part of said first unique character string of said input document;

calculating a second weight value corresponding to said second unique character string from appearance frequency information of at least a part of said second unique character string of said input document;

calculating a first appearance frequency value of at least a part of said first unique character string appearing in said comparison document;

calculating a second appearance frequency value of at least a part of said second unique character string appearing in said comparison document; and

calculating a similarity factor between said input document and said comparison document from the first appearance frequency value taking said first weight value into account and the second appearance frequency value taking said second weight value into account.

8. A method for evaluating similarity between a comparison document and a unique character string input in a computer system, said computer system being operable to search for said comparison document stored in a storage medium, the method comprising:

calculating a weight value corresponding to said unique character string from appearance frequency information of at least a part of said unique character string appearing in an input document; and

calculating a similarity factor between said unique character string and said comparison document from the appearance frequency information of at least a part of said unique character string appearing in said comparison document and said weight value.

9. An apparatus for identifying at least one unique character string in an input document which is input into a computer system, said computer system containing one or more documents which are searchably stored by the computer, the apparatus comprising:

a storage device for storing a position information file which associates and manages position information for a position in said searchably stored documents where one or more partial comparison document character strings are extracted from said searchably stored documents;

means for extracting a candidate character string from said input document;

means for identifying a partial comparison document character string which matches part of said candidate character string with a predetermined similarity factor or higher;

means for identifying position data which is associated to said partial comparison document character string having the predetermined similarity factor or higher in said position information file; and

means for recognizing said candidate character string as the unique character string by comparing appearance frequency information of at least a part of said candidate character string appearing in said input document with said position information, and evaluating an amount of feature of said candidate character string.

10. The apparatus for identifying at least one unique character string in an input document according to claim 9, wherein in said means for recognizing the candidate string as the unique string, said amount of feature is a point allocation for said candidate character string and points are allocated according to the equation: ##EQU14## where: count i=appearance frequency of an i-th candidate character string in the input document;

Ncount i j=appearance frequency of a j-th partial input character string of the i-th candidate character string in the input document;

Nsize i j=position data corresponding to the j-th partial input character string of the i-th candidate character string;

Nnum i=a number of partial input character strings contained in an i-th candidate character string;

Max (Nsize i j)=maximum Nsize i j for all searchably stored documents;

Max (Ncount i j)=maximum Ncount i j for all searchably stored documents.

11. An apparatus for searching for a document to be searched from one or more documents searchably stored in a computer, said document to be searched having a character string similar to a partial input character string which exists in an input document input in the computer, the apparatus comprising:

an input device for identifying said input document and instructing execution of a search;

means for detecting from said input device that said input document is identified and that said instruction of a search is input;

means for extracting a candidate character string from said input document in response to the detection that said input document is identified and that said instruction of a search is input;

means for calculating an amount of feature of said candidate character string through comparison between appearance frequency information at least a part of said candidate character string appearing in said input document and appearance frequency information of at least a part of said candidate character string appearing in said searchably stored documents;

means for determining whether said candidate character string is a unique character string by evaluating said amount of feature;

means for searching for the document to be searched from said searchably stored documents, wherein said document to be searched has a character string similar to said unique character string; and

a display device for displaying the document to be searched having a character string similar to said unique character string.

12. An apparatus for searching for a document according to 11, wherein in said means for determining the unique character string, said amount of feature is a point allocation for said candidate character string and points are allocated according to the equation: ##EQU15## where: count i=appearance frequency of an i-th candidate character string in the input document;

Ncount i j=appearance frequency of a j-th partial input character string of the i-th candidate character string in the input document;

Nsize i j=position data corresponding to the j-th partial input character string of the i-th candidate character string;

Nnum i=a number of partial input character strings contained in an i-th candidate character string;

Max (Nsize i j)=maximum Nsize i j for all searchably stored documents;

Max (Ncount i j)=maximum Ncount i j for all searchably stored documents.

13. An apparatus for identifying at least one unique character string in an input document which is input into a computer system, said computer system containing one or more documents which are searchably stored by the computer, and said unique character string is used as a search string, the apparatus comprising:

means for extracting a candidate character string from said input document; and

means for determining whether said candidate character string is a unique character string by evaluating an amount of feature of said candidate character string through comparison between appearance frequency information of at least a part of said candidate character string appearing in said input document and appearance frequency information of at least a part of said candidate character string appearing in said searchably stored documents.

14. An apparatus for evaluating similarity between a comparison document and an input document containing a unique character string input into a computer system, said computer system containing a comparison document searchably stored by the computer, the apparatus comprising:

means for calculating a weight value corresponding to said unique character string from appearance frequency information of at least a part of said unique character string appearing in said input document; and

means for calculating a similarity factor between said input document and said comparison document from the appearance frequency information of at least a part of said unique character string appearing in said comparison document and said weight value.

15. A storage medium readable by a computer for storing a program operable to identify a document input into a computer system based on an input document, said computer system containing one ore more documents which are searchably stored by the computer, the program comprising:

program code means for directing said computer to extract a partial character string from said input document and determining whether the partial character string is a candidate character string; and

program code means for directing said computer to determine whether the candidate character string is a unique character string by evaluating an amount of feature of said candidate character string through comparison between appearance frequency information of at least a part of said candidate character string appearing in said input document and appearance frequency information of at least a part of said candidate character string appearing in said searchably stored documents.

16. The storage medium readable by a computer for storing a program operable to identify a document according to claim 15, wherein in said program code means for determining whether the candidate character string is a unique character string, said amount of feature is a point allocation for said candidate character string and points are allocated according to the equation: ##EQU16## where: count i=appearance frequency of an i-th candidate character string in the input document;

Ncount i j=appearance frequency of a j-th partial input character string of the i-th candidate character string in the input document;

Nsize i j=position data corresponding to the j-th partial input character string of the i-th candidate character string;

Nnum i=a number of partial input character strings contained in an i-th candidate character string;

Max (Nsize i j)=maximum Nsize i j for all searchably stored documents;

Max (Ncount i j)=maximum Ncount i j for all searchably stored documents.

17. The storage medium readable by a computer according to claim 15 further comprising:

program code means for searching for a document to be searched from said searchably stored documents, wherein said document to be searched has a character string similar to said unique character string.

18. A storage medium readable by a computer for storing a program which is operable to evaluate similarity between a comparison document and an input document containing a unique character string input into a computer system, said comparison document being searchably stored by the computer, the program comprising:

program code means for directing said computer to calculate a weight value corresponding to said unique character string from appearance frequency information of at least a part of said unique character string appearing in said input document; and

program code means for directing said computer to calculate a similarity factor between said input document said comparison document from the appearance frequency information of at least a part of said unique character string appearing in said comparison document and the weight value.

19. A medium readable by a computer for storing a program operable to identify at least one unique character string in an input document which is input into a computer system, said computer system being operable to search one or more documents which are searchably stored in a storage medium, and said unique character string is used as a search string, the program comprising:

program code means for associating and managing position information for a position in said searchably stored documents where one or more partial comparison document character strings are extracted from said searchably stored documents;

program code means for extracting a partial input character string from said input document, and determining whether said partial input character string is a candidate character string;

program code means for identifying a partial comparison document character string which matches at least a part of said candidate character string with a predetermined similarity factor or higher;

program code means for identifying position data associated with said partial comparison document character string which matches with said predetermined similarity factor or higher; and

program code means for recognizing said candidate character string as the unique character string by comparing appearance frequency information of at least a part of said candidate character string appearing in said input document with the position data and evaluating an amount of feature of said candidate character string.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a system and method for searching a large volume of documents stored in a computer. More particularly, the invention relates to a system and method for searching for stored documents that are similar to a document having one or more particular string characteristics at a high speed while allowing desired ambiguity in the search of the stored documents.

2. Background Art

In known search methods for locating a document of interest from a set of electronic document texts, it is common practice to input a search expression in which character strings indicative of the subject matter of interest are connected by logical operators such as AND, OR, or NOT. An example of a search expression follows.

(computer OR personal computer) AND search

This method gives all operation and discretion to the user in converting the subject matter of interest into the search expression. It is often troublesome to formulate suitable search character strings and to input the suitable search expression. In addition, the quality of the search results greatly depends on skill of the user in constructing the search expression.

A method is also known where each search character string of the search expression is weighted according to importance of the string. A result of such a search comprises sequentially output documents corresponding to those containing higher weight of the search character strings. An example of a weighted search expression follows.

Computer, 60 personal computer, 60 search, 100

Like the first conventional method, this weighting method also gives all operation and discretion for converting the subject matter of interest to the search expression to the user. The above methods further require the user to fully understand the contents of documents to be searched and the terms being used in the search expression. Therefore, if a user vaguely thinks "I want to read sentences with such sense", it is difficult to construct a meaningful search expression from this general statement.

On the other hand, there is a technology as described in Published Unexamined Patent Application (PUPA) No. 6-124305 to is input natural language expressions for a search, to extract search keys, and to perform the search based on the extracted search keys. Such a search requires a search key dictionary. In a method performing extraction based on vocabulary information (word dictionary) such as the search key dictionary or grammatical connection rules, the word dictionary or the grammatical connection rules are generally non-dynamic. Therefore, a new word such as "TOYSARUS" ("TOYSARUS" is a trademark of Toysarus Inc.) or a phrase such as "footprint of dinosaur" cannot be extracted as a unique character string without great difficulty. In addition, the concepts or perceived "features" of the contents of a document may change over time. For example, in the past, white-collar workers always wore suits when they came to the office. More recently, there are many cases where white-collar workers may not wear suits because many companies have adopted a "casual day" system. To keep pace with such changes, it is necessary to continuously update the word dictionary to include new words, new trademarks, trade name, and product names, etc. However, such updating requires enormous labor, and the region for storing the word dictionary or the like is increased as new words as added. This, in turn, would adversely affect search speed.

In addition, PUPA 6-223114 describes a method for processing character strings based on the frequency of the appearance of a word. However, such technology is used to determine the type of a document, or to extract keywords for a search by searching a registered word list (word dictionary) to determine whether words in the document exist in the word dictionary. Unlike these conventional search methods, the present invention investigates the frequency of the appearance of a word or character string in an input document and a comparison document, and utilizes the frequency of appearance in both of them. (In the word list-based method, one word appears only once in the dictionary so that it is meaningless to investigate the frequency of appearance in the list). Accordingly, in PUPA 6-223114, a stationary word dictionary is still necessary so that there still remains the above-mentioned problem that a new word or phrase cannot be easily extracted as a unique character string. In addition, since the known technology detects keywords based on stationary word dictionaries by category, if there are multiple documents describing "methods for searching documents" for example, there is a high possibility that the keywords being extracted are very similar ones such as "search", "character string", and "high speed". Therefore, it is difficult to extract keywords for differentiating each document, introducing inefficiencies in the search document.

An object of the present invention is build a search system which enables the user to a input a complicated search concept with a very simple operation, such as the clicking of a button, without requiring the user to think up or to input a search expression.

Another object of the present invention is to provide a search method which parallels a human thought process to enable a user to easily input complicated and abstract concepts for a search.

Another object of the present invention is to provide a search method which reduces labor of the user to think up or to input a search character string or a search expression, to provide a search method which can be easily used by everybody, and enables a user to perform search even if the user does not accurately understand a keyword to be used for the search.

Another object of the invention is to provide a search method which relatively and dynamically extracts a unique character string without using vocabulary information or grammar information.

Another object of the present invention is to provide a search method which requires less storage capacity and extracts a unique character string at a high speed.

SUMMARY OF THE INVENTION

The present invention solves the above problems by 1) extracting a unique character string (a character string characterizing the sentence when viewing the character string with respect to the entire set of documents) from an input sentence; 2) allocating a suitable matching factor to each unique character string for an ambiguity search; and 3) evaluating the located documents of a search request by using appearance frequency information in the input sentence as a weight factor, and rearranging the located documents in the order of evaluation.

"Input sentence" described herein means one or more sentences in a language such as Japanese or English, and may comprise the entire content of a sentence or a paragraph. In addition, it may be a sentence in which multiple languages such as Japanese and English are intermixed.

The "unique character string" means a character string characterizing the sentence when viewing the character string with respect to the entire set of documents, or comparing it with another sentence. To provide an analogy, the unique characteristic string corresponds to a word(s) in a input sentence in the same way that a physical feature corresponds to a person to distinguish the person from other individuals in a group. If most people in a group wear glasses, then the feature "wearing glasses" is not the feature of a specific person. On the other hand, if most people in a group are in casual clothes and a specific person wears a suit, then the feature "wearing a suit" is a significant feature of that person.

A unique character string extracted from the input sentence is weighted by the appearance frequency information of the unique character string. An ambiguous search is made based on the weighted unique character string. When a set of sentences are previously arranged as an index file by extracting appearance position information of N-character chains, a high speed search can be performed with reference to character strings in a document. Since extraction of word by morpheme analysis is not performed, "dictionary maintenance" is unnecessary, documents can be registered at a high speed, and ambiguity search can be performed for searching character strings in stored documents with a similar arrangement of characters as the unique character string.

An aspect of the present invention provides a method for identifying a unique character string contained in an input document which is input into a computer system, said computer system being operable to search comparison documents stored in a storage medium, the method comprising:

associating and managing position information for a position in the comparison document where a partial comparison document character string extracted from the comparison document exists with the partial comparison document character string;

extracting a partial input character string from the input document, and determining whether the partial input character string is candidate character string; identifying a partial comparison document character string which coincides with a part of the candidate character string at a predetermined similarity factor or higher;

identifying position data associated with the partial comparison document character string which coincides with the predetermined similarity factor; and

recognizing the candidate character string as the unique character string by comparing appearance frequency information on a part of the candidate character string appearing in the input document with the position data, and evaluating an amount of feature of the candidate character string. When such a unique character string is recognized, the type of the document can be intuitively understood.

"Comparison document stored in the storage medium" described herein includes not only a document stored in a storage device in the computer system, but also a document stored in another system but searchable by this computer. In addition, the comparison document may be a single document, or multiple documents, or parts of single or multiple documents (e.g., a title, a body excluding the title, a footnote or the like). Moreover, in the case of multiple documents, it may be a set of documents including the input document, or a set of document extracted by search or the like. The contents of document may be of a natural language or a program language.

In addition, "input document" includes not only an entire document in a natural or program language stored in the storage device in the computer, but also a document which is stored in another system, but parts of which are extracted and input in this computer. In addition, the document may be a single document, or multiple documents, or parts of single or multiple documents. Moreover, the input document may be extracted parts of the comparison document.

"A partial input character string being extracted from the input document" may be not only a fixed character string of N characters of a non-delimiter language (N is a natural number of 1 or more) or a variable character string of N or more characters of a non-delimiter language, but also one or more words of a delimiter language. The partial input character string may comprise keywords extracted from the input document based on the vocabulary information (word dictionary) or the grammatical connection rules, but is not necessarily extracted from such information.

"A part of the candidate character string" may include all of a candidate character string, while "appearance frequency information" means information relating to the number of appearances of a part of the candidate character string in the input document, the comparison document or the like, and may be not only the number of appearances derived by investigating all of a document, but also information based on the number of appearance in a sample of each document. In addition, as described with respect to a preferred embodiment of the present invention, appearance frequency information may be information which is a value relating to the number of appearances in the document, the value including a size of position information data (size of position information file shown in FIG. 3 in bytes) corresponding to the N-character chain in the candidate character string quantized to Q level (Q is a constant), or a value which corresponds to such value as compressed.

"Associating and managing position information for a position in the comparison document with a partial comparison document character string" is desirably management by a position information file as shown in FIG. 3 of the preferred embodiment of the present invention. However, management may be implemented by using a table or information for pointing to an information storage position as long as the position information in the comparison document is associated with the partial comparison document character string and managed.

Although "an amount of feature" corresponds to points of the candidate character string as indicated in the preferred embodiment of the present invention, the concept is not limited to such. During calculation of points of a candidate character string, it may be possible to detect that the candidate character string satisfies a criterion such that it is recognized as a unique character string, and to recognize the string as a unique character string based on this criterion.

For "evaluating an amount of feature", it is possible to set various conditions such as a case where upper X character strings with a high amount of feature (becoming a feature of input document) are evaluated as the unique character string of the input document in question, a case where a candidate character string with an amount of feature exceeding a threshold is evaluated as the unique character string of the input document in question, or a case where a candidate character string including upper X character string and having an amount of feature exceeding a threshold is evaluated as the unique character string of the input document in question. The identified unique character string may be used for search as is, or further selected by other conditions (for example, adopted or rejected based on the degree of overlapping in the input document).

Another aspect of the present invention provides a method for searching for a comparison document, which has character strings similar to a partial input character string existing in an input document. The search is performed on a plurality of documents to be searched which are searchably stored in a computer, the method comprising: extracting a partial character string from the input document, and determining whether the partial character string is a candidate character string;

evaluating an amount of feature of the candidate character string through comparison between appearance frequency information on a part of the candidate character string appearing in the input document and appearance frequency information on a part of the candidate character string appearing in the comparison document to recognize the candidate character string as a unique character string; and

searching a document to be searched having character strings similar to the unique character string from the plurality of documents to be searched.

"Character strings similar to the unique character string" means character strings resembling the unique character string with a predetermined similarity factor or higher, including a character string with a similarity factor of 100%, or complete matching. "Search" described herein includes not only a search method for an ambiguity search described in the preferred embodiment of the present invention, but also any and all search methods which can search a document from character strings.

"Comparison between appearance frequency information" described herein is calculated based on "appearance frequency information in input document/appearance frequency information in comparison document" as the simplest example, but may be replaced by various calculation formulae as described in the preferred embodiment of the invention.

Another aspect of the present invention provides a method for identifying a unique character string contained in an input document which is input into a computer system, said computer system being able to search a comparison document stored in a storage medium, the method comprising:

extracting a partial input character string from the input document, and determining whether the partial input character string is a candidate character string; and evaluating an amount of feature of the candidate character string through comparison between appearance frequency information on a part of the candidate character string appearing in the input document and appearance frequency information on a part of the candidate character string appearing in the comparison document to recognize the candidate character string as a unique character string.

Another aspect of the present invention provides a method for evaluating similarity between a comparison document and an input document which contains a first unique character string and a second unique character string input in a computer system, said computer system being operable to search a comparison document stored in a storage medium, the method comprising the steps of: calculating a first weight value corresponding to the first unique character string from appearance frequency information on a part of the first unique character string appearing in the input document;

calculating a second weight value corresponding to the second unique character string from appearance frequency information on a part of the second unique character string appearing in the input document;

calculating a first appearance frequency value on a part of the first unique character string appearing in the is comparison document;

calculating a second appearance frequency value on a part of the second unique character string appearing in the comparison document; and

calculating the similarity factor of the comparison document from the first appearance frequency value taking the first weight value into account and the second appearance frequency value taking the second weight value into account.

Another aspect of the present invention provides an apparatus for evaluating similarity between a comparison document and a unique character string input in a computer system, said computer system being able to search a comparison document stored in a storage medium, the apparatus comprising:

means for calculating a weight value corresponding to the unique character string from appearance frequency information on a part of the unique character string appearing in the input document; and

means for calculating the similarity factor of the comparison document from the appearance frequency information on a part of the unique character string appearing in the comparison document.

Another aspect of the present invention provides an apparatus for identifying a unique character string contained in an input document which is input into a computer system, said computer system containing a comparison document searchably stored by the computer, the apparatus comprising:

a storage device for storing a position information file which associates and manages position information for a position in the comparison document where a partial comparison document character string extracted from the comparison document exists with the partial comparison document character string;

extracting means for extracting a candidate character string from the input document;

means receiving an output of the extracting means, for identifying a partial comparison document character string which matches a part of the candidate character string with a predetermined similarity factor or higher;

means for identifying position information which is associated with the partial comparison document character string with the predetermined similarity factor or higher in the position information file; and

means for recognizing the candidate character string as the unique character string by comparing appearance frequency information on a part of the candidate character string appearing in the input document with the position information, and evaluating an amount of feature of the candidate character string.

Another aspect of the present invention provides an apparatus for searching a document to be searched, said document having a character string similar to a partial input character string which exists in an input document input in a computer, said document being searched from a plurality of documents which are searchably stored in the computer, the apparatus comprising:

an input device for identifying the input document and for instructing execution of search; means for detecting from the input device the fact that the input document is identified and that the instruction of search is input;

means for extracting a candidate character string from the input document in response to the detection of the condition that the input document is identified and that the instruction of search is input;

means for calculating an amount of feature through comparison between appearance frequency information on a part of the candidate character string appearing in the input document and appearance frequency information on a part of the candidate character string appearing in the comparison document;

means for determining the candidate character string as a unique character string by evaluating the amount of feature; means for searching the document to be searched having a character string similar to the unique character string from a plurality of documents to be searched; and

a display device for displaying the document to be searched having a character string similar to the unique character string.

Another aspect of the present invention provides an apparatus for identifying a unique character string contained in an input document which is input into a computer system, said computer system containing a comparison document searchably stored by the computer, the apparatus comprising:

means for extracting a candidate character string from the input document; and

means for determining the candidate character string as a unique character string by evaluating an amount of feature of the candidate character string through comparison between appearance frequency information on a part of the candidate character string appearing in the input document and appearance frequency information on a part of the candidate character string appearing in the comparison document.

Another aspect of the present invention provides an apparatus for evaluating similarity between a comparison document and an input document containing a unique character string input into a computer system, said computer system containing a comparison document searchably stored by the computer, the apparatus comprising:

means for calculating a weight value corresponding to the unique character string from appearance frequency information on a part of the unique character string appearing in the input document; and

means for calculating a similarity factor of the comparison document from appearance frequency information on a part of the unique character string appearing in the comparison document and the weight value.

Another aspect of the present invention provides a storage medium readable by a computer for storing a program which identifies an input document input into a computer system, said computer system containing a comparison document searchably stored by the computer, the program comprising:

program code means for directing the computer to extract a partial character string from the input document and making the partial character string a candidate string; and

program code means for directing the computer to determine whether the candidate character string is a unique character string by evaluating an amount of feature of the candidate character string through comparison between appearance frequency information on a part of the candidate character string appearing in the input document and appearance frequency information on a part of the candidate character string appearing in the comparison document.

The storage medium includes a floppy disk, a CD-ROM, an MO, a PD or a storage device connected to a network. The program code may be divided into a plurality of segments and stored in a plurality of media. In addition, the program may be compressed and stored in a floppy disk. The medium is loaded on the system through various drives such as a floppy disk drive, a modem, or a serial port.

Another aspect of the present invention provides a storage medium readable by a computer for storing a program which evaluates similarity between a comparison document and an input document containing a unique character string input into a computer system, said computer system containing a comparison document searchably stored by the computer, the program comprising:

program code means for directing the computer to calculate a weight value corresponding to the unique character string from appearance frequency information on a part of the unique character string appearing in the input document; and

program code means for directing the computer to calculate a similarity factor of the comparison document from the appearance frequency information on a part of the unique character string appearing in the comparison document and the weight value.

DESCRIPTION OF THE DRAWINGS

A preferred embodiment of the present invention will be explained with reference to the drawings, where:

FIG. 1 is a block diagram showing a hardware configuration of a preferred embodiment of the present invention;

FIG. 2 is a block diagram of the system configuration processing components for the hardware of FIG. 1;

FIG. 3 is a diagram showing the character chain file and position information file structure of an index file for searching documents;

FIG. 4 is a diagram showing an extended character chain file and extended position the structure of an index file for searching documents;

FIGS. 5-6 illustrate a flowchart showing an index file creation process;

FIG. 7 is a flowchart of a character search process using the index file;

FIG. 8 is a flowchart of an ambiguity search process using the index file;

FIG. 9 is a flowchart of an ambiguity search process using the index file;

FIG. 10 is a flowchart showing extraction of a unique character string from an input document;

FIGS. 11-15 are diagrams showing user interfaces in a preferred embodiment of the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT

A. Hardware Configuration

Referring to FIG. 1, there is shown a schematic view of a system configuration for implementing the present invention. In the configuration, a bus 101 is connected to a central processing unit (CPU) 102 having capabilities of arithmetic operation and input/output control, a main memory (RAM) 104 for loading a program and providing an operating environment for the CPU 102, a keyboard 106 for key inputting a command or a character string to be searched, a hard disk 108 storing an operating system, a database file, a search engine, an index file or the like, a display device 110 for displaying the result of search for the database, and a pointing device (including a mouse or a track ball) 112 for pointing to any location on the screen and transmitting its position information.

Therefore, it can be easily understood that the present invention can be implemented on an ordinary personal computer (PC), a workstation, or combination thereof. In addition, there is shown a storage medium 114 for storing program codes which provide instructions to the CPU or the like in cooperation with an operating system to implement the method of the present invention. The storage medium may include a floppy disk, a CD-ROM, an MO, a PD, and a storage device connected to a network. The program codes may be divided into a plurality of segments or compressed, and stored in a plurality of media. The storage medium 114 is loaded on the system through various drives such as a floppy disk drive, a modem, or a serial port, whereby the system shown in FIG. 1 is constituted as the system of the present invention.

The operating system is desirably those supporting a GUI multiwindow environment as a standard feature such as Windows (trademark of Microsoft), OS/2 (trademark of IBM) or X-Window system on AIX (trademark of IBM), but may be implemented on a character base environment such as PC-DOS (trademark of IBM) or MS-DOS (registered trademark of Microsoft). The invention is not limited to a specific operating system environment. In addition, while FIG. 1 shows a system in stand alone environment, because the database file generally requires a disk device with a large capacity, it may be possible to implement the present invention as a client/server system in which the database file and the search engine are placed on the server machine, and the client machine is LAN connected to the server machine through Ethernet or token ring, and arranged to have only an input control function for identifying an input document and a display controller for viewing the result of search.

B. System Configuration

Referring to FIG. 2, a system configuration of the present invention is described. It should be noted that components represented by respective blocks in FIG. 2 are separately or collectively stored as a data file or program file in the hard disk 108 of FIG. 1. Database 202 stores a plurality of documents such as a database of newspaper accounts, or a database of patent publications. However, it should be noted the application of the present invention is not limited to search of a database consisting of a plurality of documents, but includes searching in a single document.

Contents of individual documents are searchably stored, for example, in a text file form. In addition, each document is provided with a unique document number. While preferable document numbers are ascending sequential numbers starting with 1, in the case of a patent publication database, application numbers or laid-open numbers may be used as unique document numbers. In addition, symbols such as "AB" or "&XYZ" may be used to identify individual documents in place of the sequential number. However, since such identification symbols generally require more bytes than numeric identifiers, it is preferable in practice to identify documents with the sequential numbers.

A preferred embodiment of the present invention can attain a high speed search for a document written in either a language which has a large number of characters, but does not have an explicit word delimiter such as Japanese and Chinese (non-delimiter language), or a language which has relatively small number of characters, and is expressed with explicit delimiters such as English (delimiter language).

In general, since it takes a long processing time to directly search enormous contents such as news articles or patent specifications stored in the database 202, an index file 204 is previously created by an index creation/update module 206 for the contents of all news articles. According to an embodiment of the present invention, the created index file comprises four files including a character chain file, a position information file, an extended character chain file, and an extended position information file.

Where the character chain file stores fixed length chains and delimiter patterns, the position information file comprises position numbers in the document and document numbers corresponding thereto. The extended character chain file stores extended fixed length chains, and the extended position information file stores variable length chain numbers and position numbers in the variable length chain. In the preferred embodiment of the present invention, search can be performed at a high speed by using such search files. However, since appearance frequency of a character string can be calculated regardless of the format for storing the document, use of such a search file is not an essential requirement of the present invention.

In addition, the database 202 may store individual documents as separate files, or may sequentially arrange all documents in a consecutive single file. In the former case, the database 202 manages a table which causes the unique numbers for individual documents to correspond to actual file names storing the documents. In the latter case, the database 202 manages a table which causes the unique numbers for individual documents to correspond to offset in the single database file and the size of document. In summary, it is essential that individual documents are provided with unique numbers, and the content of individual documents can be accessed with such unique numbers.

A search engine 208 has capabilities to search the index file 204 with a search character string given by a search character input module 210 as an input, and to return a document number(s) of the document(s) containing the input search character string and a position(s) at which the input search character string appears in the document. The search character input module 210 preferably consists of a dialog box in the multiwindow environment, where the desired character(s) to be searched is input through the keyboard 106 and displayed in the input box. According to a feature of the present invention, the search character input module 210 identifies an input document from which a unique character string is extracted. Specifically, titles of input documents are displayed on a display screen, and when the user selects a title with the pointer of the pointing device 112 such as a mouse, the system recognizes that a document corresponding to the displayed title is selected. The input document may be specified by directly entering information sufficient to identify the document to be input through the keyboard 106.

In addition, the search character string input module 210 can set the amount of feature of a unique character string (extracting a candidate character string as a unique character string when the points of the candidate character string exceeds a preset threshold) to be described later, or the number of character strings in a unique character string (extracting candidate character strings as the unique character string from those with higher point values). Furthermore, the search character string input module 210 enables input of the similarity factor for an ambiguity search in a numerical value of 0-1 (which may be a value of 0-100 on the basis of percentage). Thus, the search character string input module 210 displays a slider or scroll bar having a handle which indicates any position between 0 and 1. The handle of slider may indicate, for example, 1 as the default, and may be operated to indicate another value by dragging and moving the handle with the mouse 112.

A result display module 212 accesses the database 202 based on the document number as the result of search given by the search engine 208 and the value of position at which the search character appears in the document, and displays a line corresponding to that position in the document. The line is preferably output in a separate display window. If the search result cannot be contained in one screen of the window, a scroll bar appears so that the user can sequentially view the search results by clicking the scroll bar. In the preferred embodiment of the present invention, the result display module 212 has a capability to display the extracted unique character string once on the display 110. The user may add, delete or modify the unique character string, change weighting on each unique character string, or set a condition such as AND or OR on the unique character string, and then may perform search by using the unique character string after such modification.

C. Operation

FIG. 10 shows the steps of the search method in the preferred embodiment of the present invention. First, the process starts with step 801. Then, a sentence is input (step 803). Then, a candidate character string is determined by extracting a partial character string which appears multiple times from this input sentence (step 805). Then, character strings which divide alphanumeric/katakana are eliminated from the candidate character strings (step 807). Subsequently, points (an amount of feature) are marked on the remaining candidate character strings to indicate how much each of the candidate character string constitutes the feature of the input document (step 809). Then, the character strings are adopted or rejected as unique character strings based their relationship to the candidate character strings and their point values (step 811). In addition, the unique character strings are determined, for example, in the descending order of point assignments (step 813). Then, the entire set of documents is searched by using the determined unique character strings as the search character strings (step 815). Then, the documents found by the search are evaluated (step 817), and the titles of documents or the like are output in the order of evaluation (step 819).

Prior to the detailed description of each process step in the preferred embodiment of the present invention, examples of operations available to the user will be described with reference to FIGS. 11 through 15. This example illustrates a search of a database containing a plurality of news articles. Here, the example uses a database of news articles of Nihon Keizai Shimbun for one year for which IBM ("IBM" is a trademark of IBM Corporation, U.S.A.) is granted a license for use of copyright from Nihon Keizai Shimbun-sha ("Nihon Keizai Shimbun" is a trademark of Nihon Keizai Shimbun-sha).

(1) The user inputs "Olympics" in an entry area 901 shown in FIG. 11 via the keyboard 106, and presses the Enter key, or clicks the button for Execute Search 931.

(2) The system detects the user input, and searches articles containing a character string "Olympics" by a conventional search process or the ambiguity search process to be described later.

(3) Then, the system outputs the result of search on the screen. Specifically, a list of titles 927 on various articles relating to Olympics such as Mathematics Olympics, a store called Olympic, or Nagano Olympics is output a window 909 in the order of matching factor together with serial numbers 921, matching factor 923 and the date of articles 925. In this embodiment, a document with a high matching factor 100 is selected, and data identifying that document is stored. In addition, the content of a document with the highest matching factor is caused to be displayed in a window 907, and its title or the like is displayed in a window 905. Also, the title or the like of the document currently displayed in the window 907 is highlighted and displayed in a window 909.

(4) The user causes the content of the document in the window 907 to change by clicking the title in the list of titles in the window 909 or the like. Then, after reading several articles, the user selects an article "Olympics Edition--Successful Olympic Winter Games, Appealing Environment Conscious Nation" from the window 909, and clicks the button. While the user wishes to read articles on Olympic Winter Games held several years ago, he or she is informed that the keyword for articles he or she wishes to read is "Lille Hammer" after viewing this article.

(5) The user clicks Search Similar button 947 to read articles resembling this article (it may be possible to perform the search again for the set of documents extracted in the search for Olympics by entering "Lille Hammer" in the entry 100).

(6) The system detects this input, and performs the search with the method according to the present invention using "Olympics Edition--Successful Olympic Winter Games, Appealing Environment Conscious Nation" as the input. Specifically, a unique character string is extracted from that article, and the similarity search is performed by using that unique character string.

(7) The system displays the result of the search on the screen. Specifically, the list of titles is sequentially output in the window 909 in descending order from the highest matching factor. While, in the embodiment, the content of the document with the highest matching factor is displayed in the window 907, and its document number, title or the like are displayed in the window 905, it may be possible to display the content of a document with the next highest matching factor in the window 907. The input title is displayed first because the document with the highest matching factor corresponds to the input document used for the search. In the window 907, a character string matching or similar to the unique character string in the content of the searched document is highlighted. Displayed in the window 903 is a title of the search for accessing the result of search. Here, information such as the serial number, the number of documents, and the searched titles is displayed. When the title of "Olympics" previously searched is clicked, information similar to that in FIG. 11 is displayed again in the windows 907 and 909.

(8) After the user reads several articles output as the result of search by scrolling the window 909, then he or she may wish to read articles on snow-boarding. The user thus selects the article of "Issue on Olympics: Snow-board--Discussion on Adoption as Formal Event . . . " in the window 909, and clicks the button.

(9) The user clicks Search Similar button 947 to read articles similar to that article on snow boarding.

(10) The system detects this input, and performs again the search with the method according to the present invention using "Issue on Olympics: Snow-board--Discussion on Adoption as Formal Event . . ." as the input.

(11) The system outputs the result of search as shown in FIG. 15 on the screen.

The user interface in the preferred embodiment of the present invention has various additional functions. For example, a pull-down menu 911 is one for inputting a search condition such as AND or OR, or selecting the number of documents set to be extracted as the set of search results, or an allowable similarity factor. A pull-down menu 913 is one for selecting a matching factor of a character string in performing the ambiguity search. In addition, a pull-down menu 915 is one for selecting whether the subject of search is an entire document or a set of partial documents such as a set of searched documents. When the search is performed again for the set of searched documents, unique character strings are extracted by comparing the input document and a set of documents as the result of search limited to a category. Thus, it is possible to extract a character string which is a feature of the input document from a plurality of documents containing similar contents. In addition, the pull-down menu 915 enables selective searching for a limited part of a document such as searching for only titles, instead of the entire document. In this case, such a search can be attained by creating an index file only with titles, by embedding characters or symbols in the document for distinguishing the title and the body and detecting the embedded characters to exclude the body from the subject of the search, or by causing the title to exist at a fixed area in the document and performing the search only for that area. A pull-down menu 917 is a one for selecting whether search is performed by differentiating between the upper and lower case of alphabet.

A button 933 initializes the pull-down menus 911 to 917. For example, when the user has changed the pull-down menu 913 to 80%, and the pull-down menu 915 to the document set 1 (the set of documents as the result of search by the character string "Olympics"), the pull-down menus 913 and 915 are returned to the initial state of 100% and the entire document, respectively, by clicking the initialization button 933. A button 935 is a delete search result button. While the system stores information for identifying a document set as the result of search, clicking of this button causes the system to release the information on the document set inversely displayed in the window 903 at present, and to delete the titles of the document set from the window 903.

A button 941 scrolls through the document so as to display a next unique character string (or matched character string, or similar character string) in the document. A button 943 is used to display a document with the next higher similarity factor, while a button 945 is to display a document with the next lower similarity factor.

In the sequence of steps, (1) through (4) are performed by a known search approach, or an approach for ambiguity search described later. Steps (5) through (11) in accordance with the present invention are described in the following section.

D. Extraction of Unique Character String

In the search method of the present invention, a unique character string is first extracted from an input document. The unique character string is extracted in accordance with two strategies: (1) extracting a character string with an appearance frequency in the input sentence that is relatively higher than that in the entire set of documents; (2) extracting a character string which is meaningful even if it is solely extracted.

For Strategy 1, the above-mentioned index file is used. The index file holds all N-character strings in the entire set of documents, and position information data of their appearance in a unique format. The quantity of position information data changes in a substantially proportional way with respect to the appearance frequency of corresponding N-character strings in the entire set of documents. The index file can be searched at a high speed in view of the unique structure of its index. During the search, the size of position information data is utilized as a value indicating the appearance frequency of N-character string in the entire set of documents.

Detailed steps for extracting the unique character string are described below.

D1. Creation of Candidate Set for Unique Character String

A candidate set for the unique character string is formed in accordance with the following rules.

Extraction Rule 1 Partial character strings of N characters or more appearing in the input document two or more times are extracted, and added to a candidate set of the unique character string. Symbol characters such as ".", ",", and "(" are excluded during the extraction. N is the number of characters in the character chains held in the index file. In a delimiter language such as English, a word may be extracted as a partial character string. In the extraction, it is permissible that a plurality of words are converted to one conceptual word when the words have a common meaning. An example of words that may be converted include "display""display device", "CRT" or the like to "display device", and then the partial character strings are extracted. In addition, if desired, it may be possible to perform normalization such as conversion from upper case to lower case, conversion from double byte characters to single byte characters, conversion from the plural to the singular, or conversion of tense from the past or past perfect to the present. In addition, it is possible to perform effective extraction of the unique character string at a high speed by excluding character strings such as "a", "the", or "is" which generally do not constitute a feature of the document.

Exception Rule 2 When the partial character string extracted by the extraction rule 1 divides continuation of an alphanumeric into K characters or less at its start or end position, the partial character string is excluded from the candidate set for the unique character string. For example, if K is 4, it is possible to prevent "vision" from being extracted from "television".

The purpose of this step is to extract character strings which compose a significant character set based on the relationship among its characters. In other words, a character string is preserved if it is meaningful even if it is solely extracted as defined by Strategy 2. The exception rule 2 is based on experimental knowledge that when an alphanumeric string is too finely divided, it becomes meaningless. In addition, with the above rules it becomes possible to take into account different forms of English words.

D2. Assigning Points to Determine a Unique Character String Candidate

A higher point is accorded to a candidate unique character string (hereinafter "a candidate character string") with a relatively lower appearance frequency in the entire set of documents and higher appearance frequency in the input sentence. Thus, the simplest calculation formula is:

EQUATION 1

Amount of feature=Appearance frequency of candidate character string in input sentence/Appearance frequency of candidate character string in entire set of documents

In addition, when the number of characters in the input sentence and the entire set of documents is taken into account, it can be replaced by the following calculation formula.

EQUATION 2

Amount of feature=(Appearance frequency of candidate character string in input sentence*number of characters in entire set of documents)/(Appearance frequency of candidate character string in entire set of documents*number of characters in input sentence)

Since the position information file shown in FIG. 3 is used in the preferred embodiment of the present invention, points can be assigned according to Equation (1) in such a manner that (1) a higher point is given to a candidate character string containing an N-character chain with less appearance frequency in the entire set of documents, but higher appearance frequency in the input sentence, and (2) a higher point is given to a candidate character string with a higher appearance frequency in the input sentence. Point assignment is performed according to Equation 3, with the variables described below.

count i: Appearance frequency of i-th candidate character string in input sentence

Ncount i j: Appearance frequency of j-th N-character chain of i-th candidate character string in input sentence (In the case of a delimiter language such as English, appearance frequency of a word in an input sentence.)

Nsize i j: Value (number of bytes) of position information data corresponding to j-th N-character chain of i-th candidate character string (the number of position numbers in document of the position information file shown in FIG. 3 can be utilized as the appearance frequency information of N-character chain in the entire set of documents) quantized to Q levels (Q being a constant) (in the case of a delimiter language such as English, the position information of that word is used)

Nnum i: Number of N-character chains contained in i-th candidate character string.

EQUATION 3

Point of i-th candidate character string (amount of feature 1)= ##EQU1##

This point assignment strategy corresponds to Strategy 1. As described above, the position information data is substituted for the appearance frequency of an N-character chain in the entire set of documents, and the quantization is to adjust for the difference of granularity between the units for Ncount and Nsize. The purpose of multiplication by Max (Nsize i j) and division by Max (Ncount i) is to adjust for the difference between the total amount of input sentence and the set of documents. For example, a lower point would be given to common character strings such as "the", "a", and "an".

The method for assigning points on the candidate character string may be modified by those skilled in the art. For example, the number of appearances may be effected such that 1.5 is added to each appearance of a character string at a position in a document with higher importance such as a heading or title in the input document, while a smaller value of 0.5 is added to the number appearances at a position in a document with less importance such as a footnote or a quotation.

Application of this equation is described on the following sample of English document. While an English example is set forth here, the equation may also be applied in searching Japanese language documents. An example of the application of the equation to a Japanese language text is set forth in JPA 8-095691.

The following example is based on one document in a database of news articles of Yomiuri Shimbun for which IBM is granted a license for use of copyright from Yomiuri Shimbun-sha ("Yomiuri Shimbun" is a trademark of Yomiuri Shimbun-sha). The values of MAX (NCount ij); MAX (NSIZE ij); NSIZE 1,1; and NSIZE 2,1 are based on the database contents.

Sample of English document

Ranking Search and Fuzzy Operation

Ranking Search returns a list of documents in the order of the score which is level of relevance to specified search condition. The maximum number of the returned documents is specified by the user program. The Ranking Search allows the user to start looking into documents with the most desirable one, which realizes efficient and effective search task. The following three factors are selectable among the factors to decide the score of documents:

a. Frequency of search terms in the document As the search term appears more frequently in the document, the score of the document gets higher.

b. Frequency of search terms in the whole set of documents As the search term appears less frequently in the whole set of documents (all the documents indexed), the search term contributes to the score of the document more.

c. Weight parameter specified explicitly by the user program As the weight of the search term is larger, the search term contributes to the score of the document more.

The user program can specify which factors to use: one of them, two of them, or all of them. It is allowed to use none of them, and in that case the score is decided by whether the document contains the search term or not. Usually, specifying a and b is recommended.

The way to choose the documents to be scored is selectable from the following two:

Strict Boolean operation

Scoring is done for the set of documents as a result of the traditional Boolean operation.

Fuzzy operation

Scoring is done for all the documents containing at least one search term. In this case, the operator is said to be a Fuzzy operator such as "Fuzzy AND".

Fuzzy Operation

By Fuzzy AND operation, for example, the result of "A AND B AND C" is evaluated higher in the following order:

The document containing all of the three

The document containing two of the three

The document containing one of the three

By Fuzzy NOT operation, for example, the result of "A NOT B" is evaluated higher in the following order:

The document containing "A" and not containing "B"

The document containing both "A" and "B"

The traditional strict Boolean operation has an advantage in the speed, but it does not allow to evaluate the intermediate status.

By using Fuzzy operation, the intermediate status, such as "The document contains not all search terms but almost all" is evaluated, therefore the result is natural to the way of human thinking. Fuzzy operation can be used in Ranking Search only.

In the above example, the extracted character strings are "fuzzy", "search", "document", "operation", "score", "term", "contain", "rank", and "evaluate".

Here, if the first candidate character string is "fuzzy", and the second candidate character string is "and", the point allocation for each of these candidate strings can be determined according to equation 3 as follows.

Calculation of points for "fuzzy" is based

    ______________________________________
             Max (Nsize i, j) = 390612
             i, j
             Nsize 1, 1 = 3028
             Nsize 2, 1 = 169568,
             then
             Ncount 1, 1 = 9
             Nnum 1 = 1
             count 1 = 9
             Max (Ncount i, j) = 59.
             i, j
    ______________________________________

                  TABLE 1
    ______________________________________
    Position number in document
                   1234   5678   9 10111213141516171819
    for characters
    Normalized character string
                   data   base   s y s t e m - 1 2 3.
    Delimiter method 1
    ______________________________________

                  TABLE 2
    ______________________________________
                    Document Position number
    Fixed length chain
                    number   in document
    ______________________________________
    -1              1        15
    12              1        16
    23              1        17
    3.              1        18
    3               1        19
    Delimiter pattern 1
                    1        19
    ______________________________________

                  TABLE 3
    ______________________________________
    Variable      Document Position number
    length chain  number   in document
    ______________________________________
    data          1        1
    base          1        5
    system        1        9
    ______________________________________

    ______________________________________
    Extended      Variable Position
    fixed         length   number in
    length        chain    variable
    chain         number   length chain
    ______________________________________
    dat           1        1
    ata           1        2
    ta            1        3
    a             1        4
    bas           2        1
    ase           2        2
    se            2        3
    e             2        4
    sys           3        1
    yst           3        2
    ste           3        3
    tem           3        4
    em            3        5
    m             3        6
    ______________________________________

    ______________________________________
    Character string to be searched: communication
    Document text: . . . the communi- . . .
    ______________________________________