CN1151558A - Information searching method and system - Google Patents

Abstract

A character string retrieval technique that can detect human-like senses through fuzzy retrieval. According to the present invention, a method for high-speed retrieval of documents containing character strings similar to a specified character string and character arrangement is proposed by using an index file containing position information of character string fonts in the document. In this way, the character string to be retrieved and the retrieval precision (greater than 0 but less than 1) can be specified, and the specific "similar character string" containing the "similarity" of the character string to be retrieved exceeds the specified retrieval precision can be determined. The location of the document and the "similar string" within the document.

Description

Information retrieval method and system

The present invention relates to a system and method for searching at high speed and with required allowable ambiguity, for example, searching a large number of documents stored in a disk in the form of text files.

Hitherto, it has been desired to search at high speed a large number of documents such as news reports written in natural language, patent publications, and scientific and technical documents stored in a disk, and various search methods have been proposed. These search methods are broadly classified as follows. (a) Keyword search method

In this method, an index is made in advance for keywords representing each document and the content of the document. At this time, the methods for specifying keywords include automatic detection of keywords based on character shape decomposition, manual key-in, and a combination of both. However, this method can only be retrieved for character strings with keyword indexes, and according to the decomposition of glyphs, the accuracy of automatic keyword detection depends on the accuracy of words and grammar dictionaries, so it takes a lot of work to compile dictionaries Manpower, that is its shortcoming. (b) Non-indexed full-text search method

This is a way to scan the full text of documents that specify the character string to be searched as the search object each time, although no index is used. It is also a way to use special hardware to increase retrieval speed. However, systems using specialized hardware incur additional costs and are subject to customer service environment constraints that limit the availability of certain models. (c) Full-text search by index

The present invention belongs to the full-text search method by index. This is to try to achieve high-speed retrieval of the full text by using an index. There are several known technical methods as shown below.

Japanese Unexamined Patent Publication No. 4-205560 discloses that character strings to be searched are divided into search units used in the search, each search unit is assigned an ascending order symbol, and the divided search unit is assigned an attribute symbol indicating its logical division , and add the character position order symbol indicating the position of each character in the search unit to the character string as the search object, make the character position information composed of the search unit identification symbol, the character position order symbol and the attribute symbol, and put the character The location information is stored in each character area and compiled into a retrieval file.

It is announced in Japanese Patent Laid-Open No. 4-215181 that in order to reduce the number of checks for character strings during retrieval processing, and to enable high-speed checks using a general-purpose information processing device, each character group representing a character string constituting the search object is placed in the The character group position information of the position in the character string is compiled into a search file grouped according to the categories of various character groups.

However, it is often encountered that not only the character string that is exactly the same as the search character string is to be retrieved, but also the documents that contain part of the same character string are expected to be retrieved. For example, the user's memory of the search character string is fuzzy, or there are various deformations of the character string, and it is sometimes difficult to enumerate all these deformations.

A typical method for specifying a partial character string in the prior art is to use a standard expression. According to this method, any character that repeats 0 or more times, any character that repeats 1 or more times, any character at the end of a line, at the beginning of a line, or within an absolute character code range can be specified.

In addition, in the system having the function of partially matching the search character string data and the search character string data disclosed in Japanese Patent Laid-Open No. 63-99830, a data table is provided to store the same language relationship with the search character string data and to indicate the search character string data. Whether the string data appears in any of the retrieved string data in the data table.

It was announced in JP-P-62-221027 that: when a character string that disconnects part of the object character string from the beginning cannot be retrieved in the dictionary, the next character string to be disconnected is obtained by adding 1 to its length. The forward retrieval of strings can not only reduce the number of invalid retrievals, but also can effectively read out words at a higher speed.

It is disclosed in JP-A-4-326164 and JP-A-5-174067 that the autocorrelation information of each event of the retrieval object is stored in the database retrieval system, and the autocorrelation information of the retrieval keyword is obtained for each event A search method that outputs the event numbers in descending order of the degree of coincidence with the above-mentioned autocorrelation information of the search object.

However, in the character string retrieval method of the above-mentioned prior art, it is difficult to specify the ambiguity of the character string to be retrieved, so how many character strings are included in the retrieval result is not what the user requires, or is not suitable. logical string.

It is an object of the present invention to provide a character string search method that can arbitrarily designate the fuzziness of a character string to be searched.

Another object of the present invention is to provide an index structure for realizing a character string search method in which the ambiguity of a character string to be searched can be arbitrarily specified.

Another object of the present invention is to provide a character string retrieval technology that can make retrieval close to human perception through fuzzy retrieval.

According to the present invention, in order to perform a full-text search for a database composed of multiple documents, a unique number (or symbol) is added to each document, and each continuous N character in each document and the location of the N characters Information about the document number and its position in the document is stored in the index file. The index file is suitably composed of two files, a font file and a position information file. The font/delimiter, the document number corresponding to it, and the position of the position number in the document in the position information file are stored in the font file. The document number and the position number in the document are stored in the position information file.

According to the present invention, there is provided a system for performing high-speed retrieval of documents containing character strings similar to a designated character string and character arrangement using the above-mentioned index file. In this way, the character string to be retrieved and the retrieval precision (greater than 0 but less than 1) can be specified, and the "similar character string" containing the "similarity" of the character string to be retrieved exceeds the specified retrieval precision can be determined. document, and the position of the "similar character string" in the document.

This method, specifically, selects "similar character strings" from the literature to be retrieved, and proceeds to "similar character strings" from the two viewpoints of which characters are continuous and consistent and how many redundant characters are sandwiched therein. "similarity" is numerically processed.

At this time, if the highest value of the "similarity" is 1, it means that the character strings are completely consistent, and when the character strings are completely consistent, then the "similarity" must be 1. When there are redundant characters that are not the character string to be retrieved in the similar character strings or only a part of the character string to be retrieved appears in the similar character strings, its "similarity" is a value less than 1, but according to the present invention , if such a "similarity" value is quite in line with human perception, then it is useful.

Since the above-mentioned index file can retrieve any consecutive N characters in the document at high speed, by using the above-mentioned index file and continuously comparing the order of the N characters of the character string to be retrieved, it is possible to quickly detect which characters are consecutive and consistent, and How many extra characters are sandwiched in between.

FIG. 1 is a block diagram showing a hardware configuration.

Fig. 2 is a block diagram of a processing unit.

Fig. 3 is a structural diagram of an index file.

FIG. 4 is a flowchart showing index file creation processing.

FIG. 5 is a flowchart of character string search processing using an index file.

FIG. 6 is a flowchart of fuzzy search processing using an index.

Embodiments of the present invention will be described below with reference to the drawings. A. Hardware composition

Referring to Fig. 1, there is shown a schematic diagram of a system structure for implementing the present invention. This structure is the general structure that the following parts are connected to the bus 101, including a central processing unit (CPU) 102 with computing and input and output control functions, a main memory (RAM) 104 that loads programs and provides a work area for the CPU 102, A keyboard 106 for typing commands and character strings, a hard disk 108 for storing the operating system used to control the central processing unit, database files, retrieval tools, index files, etc., a display 110 for displaying database retrieval results, and for specifying the display 110 any position on the screen and transmit the position information to the mouse 112 of the central processing unit.

It is preferable to support the GUI multi-window environment with standards such as the X-WINDOW system (MIT trademark) upgraded by Windows (Microsoft Corporation trademark), OS/2 (IBM trademark), AIX (IBM trademark) as the operating system, but the present invention also It can be implemented in character-based environments such as PC-DOS (trademark of IBM), MS-DOS (registered trademark of Microsoft Corporation), and is not limited to a specific operating system environment.

In addition, Fig. 1 has shown the system of independent environment, but generally speaking, because database file requires the disk machine of large capacity, if adopt the present invention in client server system, then database file and retrieval tool can be configured in service machine, While the client machine is connected to the server machine through a local area network such as Ethernet, Token Ring, etc., it is also possible to configure only the display control part for checking the retrieval results on the server side. B. System configuration

Next, referring to the block diagram of FIG. 2, the system configuration of the present invention will be described. It should be noted that the units represented by various block diagrams in FIG. 2 are individually or collectively stored in the hard disk 108 in FIG. 1 as data files or program files.

The main idea of the present invention is to consider that the database 202 stores a plurality of documents such as a news report database, a patent publication database, and the like. However, it should be noted that the scope of application of the present invention is not limited to databases composed of multiple documents, and it is also applicable to searches within a single document. At this time, the content of a single document is stored in a retrievable manner, for example, in the form of a text file. In addition, a unique document number is attached to each document. The document number is preferably an ascending number starting from 1, but unique document numbers such as application numbers or publication numbers can also be used for patent publication databases. In order to identify each document, symbols such as "ABC" and "&XYZ" may be used instead of sequential numbers. However, since more bytes than numbers are usually required to represent such identifiers, the method of identifying documents with sequential numbers is actually the most ideal.

Since it takes a long processing time to directly retrieve such huge information content as news reports or patent publications stored in the database 202, usually the index generation/update module 206 is used to compile the content of the news reports stored in the database 202 in advance. into an index file 204. In the embodiment of the present invention described later, the index file 204 compiled in this way is composed of two files: a font file and a position information file. In the font file, the font/delimiter, the document number corresponding thereto, and the position of the position number in the document in the position information file are stored. The document number and the position number in the document are stored in the position information file.

The database 202 can also manage each document as a separate file, or can arrange the entire document into a continuous single file. In short, it is essentially attaching a unique number to each document, and it can number to access the contents of each document. In the case of the former, the database 202 manages a data table corresponding to the unique number of each document and the actual file name of the stored document, while in the case of the latter, the database 202 manages the data table corresponding to the unique number of each document. Manage the data table set corresponding to the bit offset and document size in a single database file. The retrieval tool 208 uses the retrieval string from the retrieval character input module 210 as an input to retrieve the index file 204, and has the document number (can be multiple numbers) of the document containing the input retrieval string and the input retrieval string in the document The position (can also be multiple numbers) in the returned function. The search character input module 210 is preferably composed of a dialog box in a multi-window environment, and has a form in which a desired character to be searched is input into the input box using the keyboard 106 .

In addition, according to the feature of the present invention, the search character input module 210 can input the similarity of fuzzy search by the value of 0-1 (or the number of 0-100 as a percentage). For this, the search character input module 210 displays a slider or a scroll bar having a pointer indicating an arbitrary position between 0˜1. The pointer of the slider can, for example, indicate the system setting value 1, or the mouse 112 can be used to drag and move the pointer to indicate other values.

The result display module 212 accesses the database 202 according to the value of the document number of the search result from the search tool 208 and the position where the search character appears in the document, and displays the row corresponding to the position in the document in an appropriate separate search result display window. When the search results cannot be accommodated in one screen of the window, a scroll bar will be displayed, and the user can move the scroll bar to view the search results one by one. C. Structure and preparation method of index file

In the present invention, all the consecutive N characters and their positions in the document and the segmentation information in the document are compiled into a document, and an index is added to form a file. In the file, the typical segmentation information in the document includes the separators used in articles such as ".", "," and generalized document separators such as "Chapter 1" and "Abstract". C1. Standardization of strings

The initial processing necessary for indexing files involves character string normalization as described below. That is to say, especially when the document to be retrieved is a Japanese text document, and it is a mixed document formed in half-width and full-width. Therefore, a process of replacing half-width characters with corresponding full-width characters is performed. C2. Retrieval of font information

The next step of indexing the file is to intercept all the characters of the standardized string from the beginning to the beginning of the N consecutive characters (hereinafter referred to as fonts), and store them in the index file together with the document number and the position number in the document . However, N≥1 should be taken. For Japanese, N=2 is appropriate.

The position number in the document is the unique serial number inside the document attached to all the characters of the search object in the document. And the position number in the document of the beginning character of the glyph is used as the position number in the document of the glyph. When the number of subsequent characters at the end of the document is less than N in total, prescribed padding characters such as X'00' should be loaded to make the total number N.

In addition, in this embodiment, each individual document is divided into blocks according to a meaningful division method for retrieval, and the division information is stored in the index file. Segmentation information is stored in the same format as the aforementioned font. That is, instead of storing the glyphs from the standardized character string, store the specially specified separator together with the document number of the document and the position information within the document of the block boundary character.

Since there are many types of delimiters, there can be many different splitting methods. However, it must be specified that the delimiter must not duplicate glyphs read as normalized strings. In this embodiment, when the 1-byte code is converted into a 2-byte code through the standardization process, and thus 2 bytes are regarded as 1 word, if the value of the 1 word is below 255, then it is not applicable Commonly used character encodings. Therefore, arbitrary word values from 0 to 255 can be individually assigned to various types of delimiters.

The advantages of storing segment information in the same form as fonts are as follows.

—Easy creation and update of indexes. No separate processing is required for the split information.

— will not significantly increase the capacity of the index.

For example, compared with the method in which the block number to which it belongs is added to each position number in a document, the increase in capacity is very small. C3. Specific examples of position numbers within documents

For example, documents containing such an article at the beginning as "Today is sunny. ただぃま、マイクのテスト." (It is sunny today, and the microphone is being tested.) are stored in the database 202 (FIG. 2). If the position number in the document is added to each character of the paragraph, it will be as follows.

The position number of the character in the document 1 2 3 4 5 6 7 8 9 10111213141516171819202122

Standardized string 今日は晚天なり.ただいま、マイクのテスト中.

Separation method 1 | |

Separation method 2 | | | |

Assume that the document number of this document is No. 1, and the number of characters of the above-mentioned glyphs is N=2. In this way, the related document number and position number in the document are attached to each font (length: 2) as follows. Ghostic Literature Number Literature Internal Literature No. 1 1 は 1 2 は は 1 3 sunny day 1 4 days な 1 5 り 1 6 り. 1 7. 1 1 8 separate symbol 1 1 8 separate symbol 2 1 8 ただ 1 9 だ ぃ ぃ ま ま 11 ま, 1 12, マ 1 13 separator 2 1 13 マ イ ク 1 15 ク の 1 16 の テ 1 17テス 1 18スト 1 19ト中 1 20中. 1 21.                                                                                                                                                   

The utility value of the segmentation information (separation) in the document for retrieval will be described below.・Retrieval targeting only a specific block

For example, when a document consists of so-called title, abstract, and text, it is generally desirable to search only specific parts such as the title and abstract. Such a search can be realized by storing the delimiter and its position information for the end of the title and the end of the abstract. ·Retrieval of documents closely related between multiple character strings

In general, it is desirable to search for those who are aware of the close relationship between texts and texts among a plurality of character strings.

For example, it is conceivable that the relationship between character strings may not be as close as that in the same paragraph if they are compared only in the same document, but the relationship in the same sentence will be closer. By adding a delimiter at the end and storing its location information, documents stored in the same memory block can be searched, enabling search that is aware of the close relationship. C5. Structure of the index file

Glyphs, delimiters and their document numbers, as well as position numbers within documents must be stored in a form that can be retrieved efficiently during retrieval. For this reason, in this embodiment, the index file is composed of font files (files that mainly store fonts and separators) and location information files (files that mainly store document numbers and position numbers in documents). The glyphs, delimiters and corresponding document numbers and the position of the position numbers in the document are stored in the font file. The document number and the position number in the document are stored in the position information file.

An example of such a font file and its corresponding position information file is shown in FIG. 3 .

In FIG. 3 , the items of the font file 302 are the fonts of N consecutive characters (here, N=2) in all the documents in the database 202 . In order to perform a half search, the items of the glyph file 302 are preferably sorted in ascending order by the initial character code values of the standardized glyphs. “Separator 1”, “Separator 2”, “なり”, “は晴” and the like are individual items of the font file 302 . For example, "separator 1" is a general representation of symbols for separating sentences and sentences such as ",", ",", ".", and is assigned a 2-byte value.

The position information file 304 of FIG. 3 stores at least one document number corresponding to each item of the font file 302 and at least one document position number related to each document number.

In order to make the item of the font file 302 and the item of the position information file 304 correspond to each other, although it is not listed in the figure, each item of the font file 302 should have a corresponding item in the position information file 304 information, the displacement amount from the head of the position information file 304, and the corresponding position information file 304 item size information. That is, in FIG. 3, for example, the font file 302 searches from the beginning of the position information file 304 according to the displacement information related to the "delimiter 2" and stored therein, and reads only the item size from the found position. The number of bytes specified in the message for . Thus, the position number values in the document such as 8, 13, 22... in the document number 1 related to "delimiter 2" and the position number values in the document related to the document number 2... (if any words), and the position number value in the document related to the document number n.

The value of the position number in the document related to the document number i is generally, for example, (document number i: 4 bytes) (the number of position numbers in the document k: 4 bytes) (the first position number in the document: 4 bytes )...(position number in the kth document: 4 bytes) is stored. In this example, as the field for storing the position number in the document, although the absolute position of the document is stored, 4 bytes are used, but it is actually stored from the displacement of the position number in the previous document, so it can save 1 ~3 bytes. C6. Preparation and processing of index files

Next, the creation process of the index file will be described with reference to FIG. 4 . Such processing is performed by the index creation/update module 206 in FIG. 2 when the database 202 is initially created, or when it is added to or deleted from the database 202 .

In FIG. 4, first, in step 402, processing for securing a storage area is performed. In this processing, for example, a work area of a predetermined size can be obtained on the RAM 104 by calling a function of the operating system.

At step 404, a document is read from database 202 into the appropriate storage area obtained at step 402 above.

In step 406, normalize the documents read in in step 404.

In step 408, the font-separator is created by scanning the standardized document, and the font-separator is stored in the storage area obtained in step 402 together with the document number of the document and the position number of the font-separator in the document.

In the process of step 408, as the font, document number and position number in the document are stored in the pre-obtained storage area in step 402, the free area of the obtained storage area may not be full yet. Therefore, in step 410, check whether the obtained storage area is full, if it is full, then in step 412, according to, for example, the encoding value of font and separator, document number, position number in the document will store The document numbers of the fonts stored in the district, delimiters and documents and the position information in the documents of fonts and delimiters are classified, and it is written into the disk 108 (Fig. 1) as an intermediate file. The storage area of is also open for use in the following processing. And the subsequent processing enters step 414 .

If it is determined in step 410 that there is still room in the storage area, then the process directly proceeds to step 414 .

In step 414, it is judged whether there are still documents that have not been read in step 404 in the database 202. If so, processing returns to step 404 .

In step 414, if it is judged that all the documents of the database 202 have been read in and processed, then still according to the code value of the font, the separator, the document number, the position number in the document will stay in the storage area obtained in step 402 and have not written yet The document numbers of the fonts, delimiters, and documents, and the position information within the document of the fonts and delimiters are classified into intermediate files and written to the disk 108 (FIG. 1).

Through the intermediate file writing process in step 412 and step 416, there are a plurality of intermediate files in the disk 108. Since these intermediate files have been classified in advance, they are processed in step 418 using well-known merge and classification techniques, and A font file 302 and a position information file 304 shown in FIG. In multiple original intermediate files, fonts may appear repeatedly several times. Therefore, the repeated items of the same font are merged into one, and related processing is performed on the document number and the position number in the document. D. Retrieval processing using index files

Hereinafter, an example of search processing using the index file created above will be described with reference to the flowchart of FIG. 5 . First, in step 502, for example, a dialog box with an input box is displayed, prompting the user to perform input processing, and a search character string is input into the input box.

The user enters the search character string into the input box and presses the OK button, then standardizes the search character string as required, and then uses the above-mentioned index file to perform search processing on the glyphs of N characters from the beginning of the search character string. The length of the font of N characters mentioned here is the same as the character string font length N of the above-mentioned index file, therefore, the font of N characters of the partial character string of the retrieval character string can be used as a key to the above-mentioned index file Perform high-speed half search. An example of a suitable value of N for Japanese documents is to take N=2.

In step 506, if it is judged that the font of N characters at the beginning of the search character string cannot be found, then in step 508, the message that the search character string cannot be found is appropriately displayed in the message box, and the process ends.

In step 506, if it is judged that the font of N characters at the beginning of the search character string has been found, then more than one document number and at least one position number in the document of the document number are returned from the index file, so in order to carry out subsequent processing In step 510, the information is first stored in the main memory or in a specified buffer on the disk.

In step 512, it is judged whether the search character string has been retrieved according to the partial character string of N characters font, if yes, then the process proceeds to step 520. If not, then in step 514, use the above-mentioned index file to perform retrieval processing according to the glyphs of the next N characters of the retrieval character string. The length of the search character string is generally not limited to a multiple of N. Therefore, when the processing of retrieving glyphs of N characters one by one is carried out to a part of the character string near the end of the search character string, the character string of the index file keyword is sometimes longer than Glyphs of N characters are short. In this case, it is advisable to retrieve part of the last N characters of the string. In this way, the result will be repeated with the N characters taken before. When the search string is less than N characters, there are multiple candidate results for the half search, and the subsequent processing is to find multiple candidate results through sequential search.

In step 516, the same as step 506, it is judged whether the glyphs of N characters of the search character string are found in the index file. However, step 516 is substantially different from step 506. In step 516, the meanings of finding and not finding refer to: what you are looking for is related to the first N characters of the search character string, in a certain document number The position number in a certain document only adds the glyph in the position number in the document of N.

In step 516, if it is judged that the glyphs of the N characters of the search character string cannot be found, then in step 508, the message that the search character string cannot be found is displayed in the message box, and the process ends.

In step 516, if it is judged that the font of the first N characters of the search character string has been found, then only one of the document number returned from the index file retrieval result and at least one position number in the document in the document number is sequentially circulated. The font information of the first N characters and the position number in the same document, in step 518, for subsequent processing, the information is first stored in the main memory or in the specified buffer on the magnetic disk.

In step 512, if it is judged that the search character string has all been retrieved, then enter step 520, and determine the document number and its position where the search character string exists by the document number stored in the buffer and the position number in the document, and in step 522, use The document number and the position number in the document access the stored content of the database 202, and display the line in the document in which the document search character string exists appropriately in another window.

In order to check whether the search string appears in a specific block (example: the 3rd block) in the document, the separation position in the above document where the above search string occurs before the occurrence position in the document should be calculated to check the above search string Which block (how many blocks) is located in the above-mentioned document can also be compared with the number of the designated block. E. Fuzzy retrieval processing

The processing shown in Figure 5 using the index file can be said to be rigorous retrieval processing, but according to the present invention, it includes the use of the index file, which can search the database for each high-speed execution of a process called fuzzy retrieval. In particular, in this way, the character string to be retrieved and the retrieval precision (greater than 0 but less than 1) can be specified, and it can be determined that the specific "similarity" contained in the string to be retrieved exceeds the specified retrieval precision. The document of "similar character string" and the position of "similar character string" in the document. E1. Determine the similarity of character strings based on human feeling

According to the feelings of people who understand Japanese, there are the following situations in which Japanese character strings with similar character arrangement and similar meaning are found. (1) Katakana expressions are different. Small fonts and large fonts. "ソフトウエフ" and "ソフトウエア" (software) have a long sound "-" ""アイビ-エム","アイ·ビ-·エム"(IBM)Others

"Suing at Home" "Suing at Home のまま"

"Politics Reedited" "Politics の Reedited" (3) Phrase Compound Words with Chinese Characters and Partial Phrase Compound Words

"National Museum of Ethnology", "National Museum of Ethnology", "Museum of Ethnology" (4) Some characters are missing due to abbreviation, etc.

"ソフトウエエアdevelopment" "ソフトdevelopment" (software development) (5) misspelling of foreign words

"California" "California" (California)

The common feature of the above situations is that the characters are generally consistent, but there are missing or extra characters.

If we study a few words from the similar point of view, the similar order to "ソフトメ-カ-" includes "ソフトのメ-カ-", "ソフトの发展メ-カ-", "ソフトの攻略メ-カ-”, and if compared with the “Political Funds Regulation Act”, there are “Political Funds Regulation Act”, “Political Funds Regulation”, and “Political Funds” in order of similarity.

In addition, although the characters can be said to be the same, but to say "ソフトクリ-ム Manufacturing Machinery の Manufacturing を Main Business とする机场メ-カ-" (a machinery manufacturing factory with dairy manufacturing machinery as its main business) and "ソフトメ-カ-" is a similar string, that is the illogical feeling.

Whether people feel the string similarity can be summarized as follows: (A) the more consistent characters, the more similar they feel; (B) the more inconsistent characters in the middle, the more dissimilar they feel; (C) the more inconsistent characters in the middle It doesn't feel like a string at most.

At this time, it is necessary to consider the specific situation that the input string repeats at close positions in the document. For example, the input character string is "Minister of Scienceにtake office", but in the document it is "Minister of Scienceにtake office". Although one of the repeated characters of "部" is a superfluous character, compared with the irrelevant character ending "の" of "论学部の长に职交", it should be considered that the former is a close consistent character. is appropriate. E2. Structure and consistency of index files

The index file structure shown in Figure 3 is an index in which a document number and a position number in a document are added to a glyph of N characters. position number. However, when retrieving a character string that is less than N characters, it is necessary to start from the beginning of the character string to be retrieved, and use the characters of all glyphs as the minimum unit to perform retrieval processing, and its number is quite large sometimes. Compared with the retrieval times when the input string contains more than N characters, at most the number of characters in the input string is the minimum unit of retrieval, it can be said that the retrieval load of the input string that is less than N characters is greater. big.

Therefore, it is appropriate to say that the matching of parts less than N characters should be discarded, and similar character strings should be determined based on parts of N characters that are consecutive and matching. E3. Determination rules for similar character strings and similarity

From the strings that have more than M consecutive characters with the input string, collect the similar strings that have the same sequence relationship with the input string and are relatively close to each other as similar strings, and calculate the similarity based on the number of consistent characters and the number of inconsistent characters That's a summary of the rules.

First, define the terms used in the description.

consistent string:

The character string to be retrieved has more than M consecutive characters consistent with the original text of the document. Select the largest length among them starting from the same character.

(Example) String to be searched: Political Fund Regulation Act

The original text of the document: ...Fund regulation のために法のカで...

Let M=2. Therefore, "funding regularization" is a consistent string. At this time, "fund" and "fund rule" cannot be called a consistent character string because the longest one should be selected. And "law" does not belong to the consistent character string because it is less than 2 characters.

Valid consistent strings:

Consistent strings that form similar strings.

Maximum inconsistent string length L:

Inconsistent characters contained in similar character strings are continuous up to L characters. L is a constant of 1 or more.

The selection method of "similar character string" and the numerical method of "similarity" will be described below. (1) Determination of the first effective consistent string

Take the first consistent string as the first valid consistent string according to the order in the literature.

in,

The starting position of the i-th valid consistent string in the document is marked as s(D, i)

The end position of the i-th effective consistent string in the document is marked as e(D, i)

The starting position of the i-th valid consistent string in the string to be retrieved is marked as s(C, i)

The end position of the i-th effective consistent string in the string to be retrieved is marked as e(C, i). (2) Determination of the next valid consistent string

When determining the i-th valid consistent character string, determine the i+1-th valid consistent character string as follows.

When the initial consistent character string satisfies the following two conditions a) and b), it is taken as the i+1th effective consistent character string. a) e(D, i)+1<=s(D, i+1)<=e(D, i)+L+1

The above formula means: when the redundant characters inserted between the i-th effective consistent string and the i+1 effective consistent string are allowed to be less than L characters

(Refer to Example 3 below) b) s(C, i+1)>e(C, i)-(M-1)

Iterates until no valid consistent string matching the criteria is selected. (3) Determination of "similar character strings" and their "similarity" (similarity)

If the above-mentioned valid and consistent character string is not selected, then use the initial character of the first valid consistent character string to the last character of the last valid consistent character string as "similar character string", and calculate "similarity" according to the formula . Similarity =

(The number of characters in the string to be retrieved that are valid consistent strings

/ The number of characters of the string to be retrieved,

The number of characters in "similar strings" that are valid consistent strings

/The number of characters of "similar character string") the minimum value E4. The calculation method of the number of characters belonging to an effective consistent character string in "similar character string"

When there are 2 characters identical to the corresponding characters in the string to be retrieved, the first character is counted as 1, and the second character is counted as 0.5. In other cases, a character is counted as 1. (Refer to example 4 below) E5. Determination sequence of "similar character string"

The first "similar character string" is compared and determined from the beginning of the document. In the process of determining the i-th "similar character string", look backward from the beginning character of the i-th "similar character string", and find out different characters in the effective consistent character strings that constitute the i-th "similar character string". Characters that belong to a valid consistent string, and then start to compare, so as to find the i+1th similar string.

By properly assigning constants L and M, and according to whether the arrangement of characters is similar, the "similarity" that is quite consistent with the general judgment of people can be calculated.

In addition, when the "similarity" is the highest value 1, it means that the character strings are completely consistent, and if the character strings are completely consistent, then the "similarity" must be 1. E6. Flow chart of fuzzy retrieval

If the above processing is represented by a flowchart, it is as shown in FIG. 6 . In FIG. 6, first at step 602, a prompt is prompted to input a search character string. In step 604, a similarity of 0-1 is prompted to be input. The input operation of character strings and values in step 602 and step 604 is usually performed on a dialog box using an input box and a scroll bar.

In step 606, the number i of the valid consistent character string is set to 1, and in step 608, a search for the valid consistent character string is performed. At this time, assuming that the condition that the effective consistent character string length is set to be greater than M is met, then in the processing of FIG. 4 , it is advantageous to compile the index file according to the glyphs of M characters. The reason for this is that if such an index file is prepared in advance, an arbitrary M-shaped search can be performed at high speed by half-searching the index file. Then, use the index file to stagger 1 character from the start position of the font of M characters, and search for the font of M characters in the index file. , moreover, the position numbers in the document are sequential, and an effective consistent character string of length M+1 can be obtained. Using the above method, if the document number is the same as the font search of the previous M characters, and the position numbers in the document are sequential, then every time the above condition is met, the length of the valid consistent character string will be increased by 1. However, if nothing is found in the font search of M characters using the index file, or the document numbers returned are inconsistent, or the position numbers in the documents are not sequential, then the end position of the valid consistent character string has been reached.

Depending on the situation, sometimes the valid consistent character string cannot be found at all. In this case, according to the judgment of step 610, enter step 626, display that it is not found, and end the process.

In step 610, if it is judged that an effective consistent character string is found, then enter step 612 for processing; in the document, from s(D, i) to e(D, i); in the retrieval character string, from s(C, i) to e(C, i), all mark valid character strings.

In step 614, if the following conditions are found: a) e(D, i)+1<=s(D, i+1)<=e(D, i)+L+1

And, b) s(C, i+1)>e(C, i)-(M-1)

Then continue to use the index file to retrieve the i+1th effective consistent character string, if found, return to step 612, for the i+1th effective consistent character string, in the document from s(D, i+1) to e(D, i+1); In the retrieval string, from s(C, i+1) to e(C, i+1), mark valid character strings. (adding i in step 618 represents the next effective consistent character string)

On the other hand, in step 616, if no valid consistent character string found earlier is found, then in step 620, the calculation of the similarity is performed. The method is as described above, for example, with the following formula,

Similarity =

(The number of characters in the string to be retrieved that are valid consistent strings

/ The number of characters of the string to be retrieved,

The number of characters in "similar strings" that are valid consistent strings

/Number of characters of "similar character strings") Minimum value At this time, "similar character strings" are character strings from the start position of the first valid consistent character string to the last position of the last valid consistent character string.

In step 622, the result is selected according to the similarity calculated in step 620 and the similarity input in step 604, and only when the result is greater than the similarity input in step 604, the result is displayed in step 624.

The processing operation in step 624 is to access the document content stored in the database according to the document number and position number in the document returned by the index file retrieval results in steps 608 and 614, and display the row where the position is located.

In addition, a "similar character string" of a search character string may be found in multiple documents at the same time, and may also be found in multiple places in one document. Therefore, it must be noted that steps 606-622 are applicable to such a plurality of "similar character strings", but in step 624, only those satisfying the similarity condition are selected for display among the plurality of "similar character strings". E7. Example of Determining "Similar Strings" and Similarity

The example shown assumes M=2, L=3. (example 1)

        1 2 3 4 5 6 String to be retrieved C: アイビ-エム# (アイビ-エム# is a trademark of IBM Corporation)

                                                                                   

The longest consistent string at the beginning is "アイ", so

The first valid consistent character string is "アイ" s(C, 1)=1e(C, 1)=2

s(D,1)=1e(D,1)=2

Because e(C, 1)-(M-1)=1, the character string starting after the second character of the character string to be retrieved is compared with the character string starting from 3, 4, 5 or 6 of the document Compare to retrieve the second valid consistent character string (because e(D, 1)+1=3, e(D, 1)+L+1=6).

The second valid consistent character string is "ビ-" s(C, 2)=3, e(C, 2)=4s(D, 2)=4e(D, 2)=5

Because e(C, 2)-(M-1)=3, the character string starting after the 4th character of the character string to be retrieved is compared with the character string starting from 5, 6, 7 or 8 of the document Compare to retrieve the third valid consistent character string (because e(D, 2)+1=6, e(D, 2)+L+1=9).

The third valid consistent character string is "エム" s(C, 3)=5e(C, 3)=6

s(D, 3)=7e(D, 3)=8

Since the end of the string to be retrieved has been reached, the third valid consistent string is the last one.

      アイビ-エム

1 2 3

      アイ·ビ-·エム…

1 2 3

number is the number of a valid consistent string. Therefore, the "similar character string" is "アイ·ビ-·エム" from s(D, 1) to e(D, 3). The minimum value of "similarity"=(6/6, 6/8)=6/8=0.75 (example 2)

                                                                             

                                                                                 

ソフトウエエア-カ-

1 2

Soft developed メ-カ-…

1 2 "similar character string" = "soft development メ-カ-" similarity = (7/10, 7/9) minimum value = 0.7 (Example 3)

                                           

                                                                         The longest consistent string at the beginning is "在屋", so the first valid consistent string is "在屋" s(C, 1)=1e(C, 1)=2

s(D,1)=1e(D,1)=2

The character string starting from the second character of the character string to be retrieved (because e(C, 1)-(M-1)=1) is compared with the character string starting from 3, 4, 5 or 6 of the document Compare (because e(D, 1)+1=3, e(D, 1)+L+1=6), and search for the second valid matching character string.

Since the second valid consistent string cannot be found, and because the end of the string to be retrieved has been reached, only the first one is a valid consistent string.

sue at home

1

Sue at the house のままでにふみきつた.

        1 Therefore, the first "similar character string" is "at home" from s(D, 1) to e(D, 3). Similarity = Minimum of (2/4, 2/2) = 0.5

The leading non-valid consistent character after "behind" is "の". Retrieve the second "similar character string" after "の", then

sue at home

1

Sue at the house のままでにふみきつた.

1

However, in the literature, "at home" and "suit" are separated by 4 characters. In this example, since L=3, the above-mentioned "suit" cannot be regarded as a valid consistent character string.

(Example 4)

    1 2 3 String to be retrieved C: Banker

1 2 3 4 5 6 7 8 9

Document D: A bank clerk の Bさん

The longest consistent string at the beginning is "bank", so

The first valid consistent character string is "bank" s(C, 1)=1e(C, 1)=2

s(D,1)=2e(D,1)=3

(Formula 7)

Compare the character string starting from the second character of the character string to be retrieved (because e(C, 1)-(M-1)=1) with the character string starting from 4, 5, 6 or 7 of the document (Because e(D, 1)+1=4, e(D, 1)+L+1=7), the second valid matching character string is retrieved.

The second effective consistent character string is "member" s(C, 2)=2e(C, 2)=3

s(D,2)=4e(D,2)=5

Because the end of the string to be retrieved has been reached, there are two valid consistent strings.

banker

1

2

A bank clerk の Bさん

1 2

1.1. 0.5 1→3.5 "similar character string" is "bank clerk" from s(D, 1) to e(D, 2). The minimum value of "similarity" = (3/3, 3.5/4) = 3.5/4 = 0.875E8. Fuzzy example close to people's feeling

    ソフトウエエアDevelopment メ-カ- 0.833

      ソフトウエアのDevelopment メ-カ- 0.769

This example shows that "similarity" decreases with the inclusion of redundant characters.

    ニツトウエエアメ-カ- 0.800

        ソフトメ-カ-   0.700

          ソフトウエエア 0.600

This example shows that "similarity" decreases as the number of identical characters decreases. Science Minister Election Science Minister Election 1.000

     Election of Minister of Science 0.929

The relationship between the structure of the index and the retrieval of "similar strings"

By properly setting the value of M, the index structure of the present invention can be used to realize the fuzzy retrieval of "similar character strings" at high speed. The determination method of constant N, M N: the number of characters of the font stored in the index M: the minimum length of the effective consistent string of fuzzy retrieval L: in the fuzzy retrieval, the maximum length of the non-effective consistent string in "similar character string" length.

If N is made large, the number of font types increases and the amount of font data detected decreases, so the retrieval speed is faster, but the capacity of the index file will increase. In general Japanese documents, sufficient retrieval speed can be obtained with N=2.

If M is determined according to the condition of M≥N, sufficient retrieval speed can be obtained in fuzzy retrieval. Considering that the smaller M is, the finer the fuzzy retrieval can be, it is considered satisfactory to take M=N. E10. Second embodiment of determining similarity

In the fuzzy retrieval process of the second embodiment, it is particularly considered that "the more inconsistent characters are mixed in, the more dissimilar they feel" and "the more inconsistent characters are mixed in, the less likely they are the same character string", taking into account both both aspects. If the strings entered in the literature are arranged in the order of consistent strings, inconsistent strings, and consistent strings, and similar strings are extracted before the following consistent strings, the degree of similarity will be reduced. , which is illogical. For example, when the input character string is "Zaizhai sue", and document 1 is "Zaizhai の ままで sue", and document 2 is "Zai Zhai", as said "Document 1 "Zaizhai の ままで sue", Document 2" "Zai Zhai" has similar character strings, but the similarity is based on the rule that "Zai Zhai" is the highest", and the result is contrary to people's feelings. If it is judged that the similarity of "Zai Zhai の ままで sue" is higher than that of "Zai Zhai", or there are two similar strings of "Zai Zhai" and "Sue" in Document 1, it is logical.

Next, the processing of the second embodiment will be described. Referring to the flow chart of FIG. 6 , in this embodiment, steps 602 to 612 are the same, but step 614 representing the i+1th effective matching character string retrieval condition has the following changes.

s(C, i+1)>e(C, i)-(M-1) ... (Formula 1)

s(D, i+1) > e(D, i) ... (Formula 2)

and,

s(D, i+1)-e(D, i)-1

+max(e(C, i)-s(C, i+1)+1.0)≤L...(Formula 3)

The definitions of s(C, i), e(C, i), s(D, i), e(D, i) etc. are still as above.

Formula 1 allows repeated characters like the "Department" of the aforementioned "Department of Science" to be less than M-1. In addition, this means that all character strings that appear in the same order as the characters in the input string are Effective.

Equation 2 means that valid consistent strings do not repeat in the literature.

Formula 3 means that the inconsistency characters sandwiched in between and the recurring characters like "Department" of "Department of Science" are allowed to be less than L characters.

In this embodiment, as in the previous embodiment, the proportion of effective and consistent character strings among the character strings similar to the search character string in the document is calculated, and those with a small proportion are not selected as similar characters. degree, and add points to similar character strings, by dividing by the full score, (the points given when they are completely consistent) to find the ratio and calculate. Add points to each character according to the following rules, and calculate the scores of similar character strings after accumulation. Therefore, the following processing is performed in step 620 of FIG. 6 . Characters belonging to the 1st valid consistent string ... 1 point characters belonging to the i-th (i>1) valid consistent string

Position in the search string ≥ e(C, i-1)+1 (Formula 4)...1 point

The position in the search string ≤ e(C, i-1)+1 (formula 5)...-1/(2*L) points are not characters in a valid consistent string ...-1/L points

In this embodiment, in the process of determining the i-th similar character string, look backward from the beginning character of the i-th similar character string, and find characters that do not belong to an effective consistent character string in forming the i-th similar character string , and then start the comparison to find the i+1th similar string.

The negative points for characters that do not belong to a valid consistent string are to take into account that "the more inconsistent characters are mixed in, the more dissimilar they feel" and "the more inconsistent characters are mixed in, the less they feel that they are the same string". set by two aspects. The maximum negative score of a non-consistent character string is 1/L*L=1, so take the minimum value of the positive score of the next consistent character string, and when N≥1 (especially recommended 2 for Japanese), the negative score will not exceed its positive score. In addition, Equation 5 represents a repeated character such as "Department" of the above-mentioned "Minister of Faculty of Science", and Equation 4 represents a simple coincident character that is not a repeated character. For the characters represented by formula 5, a negative score smaller than that of simple non-consistent characters should be added to address the situation of repeated characters. E11. Example of determining similar character strings and similarity in the second embodiment

As an example, still set N=2, L=3

(Example 5)

Input string C: アイビ-エム

                                                  

Part of the document D: ...アイ·ビ-·エム...

The initial longest consistent string is "アイ", so the first valid consistent string is "アイ"

s(C,1)=1e(C,1)=2

s(D, 1) = 1e(D, 1) = 2 From Formula 1, Formula 2, and Formula 3, it can be seen that the second valid consistent character string is "ビ-"

s(C,2)=3e(C,2)=4

s(D, 2)=4e(D, 2)=5 From Formula 1, Formula 2, and Formula 3, it can be seen that the third valid consistent character string is "エム"

s(C,3)=5e(C,3)=6

s(D, 3)=7e(D, 3)=8 Since the end of the character string to be retrieved has been reached, there are 3 valid consistent character strings.

C: アイビ-エム

1 2 3

D: アイ·ビ-·エム

1 2 3

Score 1.-1.1.1.1.1.

-1/3 -1/3

The similar character string is "アイ·ビ-·エム" from s(D, 1) to e(D, 3). Similarity = ((1*6+(-1/3*2)/6) = 0.88 (Example 6)

                    1 2 3 4 5 6 7 8 9 10

Input string C: ソフトウエアメ-カ-

                                  1 2 3 4 5 6 7 8 9…

Part D of the document: ...ソフト develops メ-カ-...

C: ソフトウエアメ-カ-

1 2

D: Soft developed メ-カ-…

1 2 Similar character strings = "Soft development メ-カ-" similarity = ((1*7+(-1/3)*2)/10) = 0.63 (Example 7)

1 2 3 4

Enter the string C: sue at home

                  1 2 3 4 5 6 7 8 91011121314…

Part D of the document: In the house の ま ま で sue にふみきつた.

The initial consistent character string is "in the house", so the first valid consistent character string is "in the house", because the next consistent character string is "sued" which does not satisfy formula 3, so only the first one is a valid consistent character string.

C: sue at home

1

D: Sue にふみきつた in the house のままで.

1 A similar character string is "at home". Similarity = 2/4 = 0.5

The leading non-valid consistent character after "behind" is "の". The second similar character string should be retrieved backward from "の".

C: sue at home

1

D: Sue にふみきつた in the house のままで.

          1 Therefore, the second similar character string is "prosecution". (Example 8)

1 2 3 4 5 6 7

Input character string C:  

1 2 3 4 5 6 7 8

A part D of the document: ... the head of the Faculty of Science に taking office... The effective consistent character strings are "Faculty of Science" and "Minister に taking office".

C: The Minister of Science takes office

1

>2

D: The head of the Faculty of Science takes office

1 2

1.1.1. 1.1.1.1

-1/6 The similar character string is "Minister of the Faculty of Science takes office". The second "part" satisfies Equation 5. Therefore, similarity=((1*7+(−1/6)*1)/7)=0.97. E12. Summary of Results of the Second Example

input string in the literature similarity

ソフトメ-カ- ソフトのメ-カ- 0.95

    ソフトの发展メ-カ- 0.85 Political Fund Regulation Act Political Fund Regulation Act 0.87

                                                                                                 

                                                                0.95

As described above, according to the present invention, it is possible to obtain the effect of high-speed realization of fuzzy retrieval based on human perception by using a unique index structure for text files or databases.

Claims (56)

1. An information retrieval method for finding out, by computer processing, a similarity of document character strings similar to a retrieval character string among documents stored in a retrievable manner, the method comprising the steps of:

(a) inputting a search string;

(b) a step of extracting a partial character string having a length of M characters or more ((M is a predetermined integer of 2 or more) from the beginning of the search character string and detecting a start position and an end position matching the extracted partial character string in the document (hereinafter, a partial character string having a length of M characters or more determined by the start position and the end position is referred to as an effective matching character string);

(c) searching for the valid matching character string if a response indicating that no valid matching character string is detected occurs in step (b), by shifting a character from the start position of the partial character string of the search character string, and then by selecting a partial character string having a length of at least M characters (M is a predetermined integer of at least 2);

(d) searching for a valid matching character string having a starting position within a distance of L characters (L is a predetermined integer of 1 or more) from a partial character string starting position of the search character string and a search starting position in the document, respectively, by a length corresponding to the valid matching character string just detected, if a response for detecting the valid matching character string occurs;

(e) continuing the step (d) as long as the valid matching character string is detected;

(f) and calculating a similarity between the search string and a string from the start position of the first valid matching string of the document to the end position of the last valid matching string of the document based on information existing in the valid matching strings at least in the string from the start position of the first valid matching string of the document to the end position of the last valid matching string of the document.

2. The information retrieval method according to claim 1, characterized in that: m is 2, and L is 3 or more.

3. The information retrieval method according to claim 1, characterized in that: the calculation of the similarity takes a small value among the proportion of valid matching character strings in the search character string and the proportion of valid matching character strings between the start position of the first valid matching character string of the document and the end position of the last valid matching character string of the document.

4. The information retrieval method according to claim 1, characterized in that: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and a score is subtracted when it does not belong to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the perfect matching score.

5. An information retrieval method for finding, by computer processing, a position where a retrieval string appears in a document stored in a retrievable manner, the method comprising the steps of:

(a) inputting a search string;

(b) inputting similarity;

(c) a step of extracting a partial character string having a length of one or more than M characters (M is a predetermined integer of 2 or more) from the head of the search character string, and detecting a start position and an end position that match the partial character string in the above document, hereinafter, a partial character string having a length of one or more than M characters, which is determined by the start position and the end position, is referred to as a valid matching character string one;

(d) searching for the valid matching character string if a response indicating that no valid matching character string is detected occurs in step (c), by shifting a character from a start position of a partial character string of the search character string, and by selecting a partial character string of a predetermined integer having a length of at least M characters and having a length of at least M2;

(e) a step of searching for a valid matching character string from a partial character string start position of the search character string and a search start position in the document, if a response to the detection of the valid matching character string occurs, by a length corresponding to the valid matching character string just detected, and from a predetermined integer having a distance from the start position to the valid matching character string just detected within L characters, L being 1 or more;

(f) continuing the step (e) as long as the valid matching character string is detected;

(g) and calculating a similarity between the search string and the character string from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document based on information present in the valid matching character string at least in the character string from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document.

(h) If a response is obtained by the calculation that the similarity is greater than the similarity input in the step (b), the contents of the valid matching character string contained in the document are displayed.

6. The information retrieval method according to claim 5, characterized in that: m is 2, and L is 3 or more.

7. The information retrieval method according to claim 5, characterized in that: the calculation of the similarity takes a small value among the proportion of the valid matching character strings in the search character string and the proportion of the valid matching character strings in the character strings between the start position of the first valid matching character string of the document and the end position of the last valid matching character string of the document.

8. The information retrieval method according to claim 5, characterized in that: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and a score is subtracted when it does not belong to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the perfect matching score.

9. The information retrieval method according to claim 8, characterized in that: the above-mentioned addition is divided into a character 1, and the above-mentioned subtraction is divided into a character 1/L.

10. An information retrieval method for detecting, by computer processing, a similarity of a document character string similar to a retrieval character string in a database of a plurality of documents stored in a retrievable manner, the method comprising the steps of:

(a) inputting a retrieval character string;

(b) a step of extracting a partial character string having a length of M characters or more and M being a predetermined integer of 2 or more from the beginning of the search character string and detecting a start position and an end position matching the extracted partial character string in the same document in the database, wherein the partial character string having a length of M characters or more determined by the start position and the end position is referred to as an effective matching character string-;

(c) if no valid matching character string is detected in the step (b), searching the valid matching character string by shifting a character from the starting position of the partial character string of the search character string, and then taking a partial character string of which the length is more than M characters and M is a predetermined integer more than 2;

(d) searching for a valid matching character string having a distance between a start position and a valid matching character string detected immediately before, within L characters, L being a predetermined integer of 1 or more, by shifting only a length corresponding to the valid matching character string detected immediately before from a partial character string start position of the search character string and a search start position in the same document, if a response for detecting a valid matching character string occurs;

(e) continuing the step of step (d) as long as the valid consistent character string is found;

(f) and calculating a similarity between the search string and the character string from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document based on information present in the valid matching character string at least in the character string from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document.

11. The information retrieval method according to claim 10, characterized in that: m is 2 and L is 3.

12. The information retrieval method according to claim 10, characterized in that: the calculation of the similarity takes a small value between the proportion of the valid matching character strings in the search character string and the proportion of the valid matching character strings in the character strings from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document.

13. The information retrieval method according to claim 10, characterized in that: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and a score is subtracted when it does not belong to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the perfect matching score.

14. An information retrieval method for checking out, by computer processing, where a retrieval string appears in a database of a plurality of documents stored in a retrievable manner, the method comprising the steps of:

(a) inputting a search string;

(b) inputting similarity;

(c) a step of extracting a partial character string having a length of M characters or more and M being a predetermined integer of 2 or more from the beginning of the search character string and detecting a start position and an end position matching the extracted partial character string in the same document in the database, wherein the partial character string having a length of M characters or more determined by the start position and the end position is referred to as an effective matching character string-;

(d) searching for the valid matching character string if a response indicating that no valid matching character string is detected occurs in step (c), by shifting a character from a start position of a partial character string of the search character string, and by selecting a partial character string of a predetermined integer having a length of at least M characters and having a length of at least M2;

(e) searching for a valid matching character string having a distance of L characters or less from the start position of the partial character string of the search character string and the search start position in the same document, L being a predetermined integer of 1 or more, if a response indicating that a valid matching character string is detected occurs, by shifting only the length of the valid matching character string just detected from the start position of the partial character string of the search character string and the search start position in the same document;

(f) continuing the step of step (e) as long as the valid consistent character string is found;

(g) and calculating a similarity between the search string and the character string from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document based on information present in the valid matching character string at least in the character string from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document.

(h) If a response is obtained through the calculation that the degree of similarity is greater than the degree of similarity input in the step (b), the contents of the valid matching character string contained in the document are displayed.

15. The information retrieval method according to claim 14, characterized in that: the method includes a step of labeling the plurality of documents with a unique number or symbol in advance.

16. The information retrieval method as recited in claim 15, wherein: the above-mentioned inherent numbers or symbols are numbers in order.

17. The information retrieval method according to claim 14, characterized in that: m is 2 and L is 3.

18. The information retrieval method according to claim 14, characterized in that: the calculation of the similarity takes a small value among the proportion of the valid matching character strings in the search character string and the proportion of the valid matching character strings in the character strings between the start position of the first valid matching character string of the document and the end position of the last valid matching character string of the document.

19. The information retrieval method according to claim 14, characterized in that: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and a score is subtracted when it does not belong to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the perfect matching score.

20. The information retrieval method as recited in claim 19, wherein: the above-mentioned addition is divided into a character 1, and the above-mentioned subtraction is divided into a character 1/L.

21. An information retrieval system for detecting, by computer processing, a position where a retrieval character string appears in a document stored in a retrievable manner, the system having:

(a) means for inputting a search string;

(b) a device for searching for a matching start position and end position in the above document, wherein a partial character string having a length of M characters or more to a predetermined integer having M characters or more to 2 or more is taken as a search character string, and a partial character string having a length of M characters or more determined by the start position and the end position is referred to as an effective matching character string;

(c) a means for searching for a valid matching character string by using the means (b) from the beginning of the search character string, if a response for detecting a valid matching character string occurs, by shifting only the length of the valid matching character string just detected from the start position of the partial character string of the search character string and the search start position in the document, and by shifting the start position of the valid matching character string within L characters, L being a predetermined integer of 1 or more, from the start position of the valid matching character string just detected, and if a response for detecting a valid matching character string does not occur, by shifting one character from the start position of the partial character string of the search character string and then taking out a partial character string of M characters or more (M being a predetermined integer of 2 or more) and searching for the valid matching character string;

(d) means for continuing said step (d) as long as said valid matching string is detected;

(e) and a means for calculating the similarity between the search string and the character string from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document based on information present in the valid matching character string at least in the character string from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document.

22. An information retrieval system for detecting, by computer processing, a position where a retrieval character string appears in a document stored in a retrievable manner, the system comprising:

(a) means for inputting a search string;

(b) means for inputting the similarity;

(c) a device for searching for a matching start position and end position in the above document, wherein a partial character string having a length of M characters or more to a predetermined integer of 2 or more is taken as a search character string, and a partial character string having a length of M characters or more determined by the start position and the end position is referred to as an effective matching character string;

(d) a means for searching for a valid matching character string by applying the means (c) from the beginning of the search character string and by shifting only the length of the valid matching character string just detected from the start position of the partial character string of the search character string and the search start position in the document based on the occurrence of a response to detect a valid matching character string, the valid matching character string having a distance of L characters or less from the start position of the valid matching character string just detected and L being a predetermined integer of 1 or more, and if no response to detect a valid matching character string has occurred, the valid matching character string being searched by shifting one character from the start position of the partial character string of the search character string and then taking out a partial character string of M characters or more (M being a predetermined integer of 2 or more);

(e) means for continuing said step (d) as long as said valid matching string is detected;

(f) means for calculating a similarity between a character string at least between a start position of a first valid matching character string of the document and an end position of a last valid matching character string of the document and the search character string, based on information present in the valid matching character string;

(g) and (c) means for displaying the contents of the valid matching character strings included in the document if the calculated similarity is greater than the similarity inputted in the step (b).

23. The information retrieval system as recited in claim 22, wherein: m is 2 and L is 3.

24. The information retrieval system as recited in claim 22, wherein: the calculation of the similarity takes a small value among the proportion of valid matching character strings in the search character string and the proportion of valid matching character strings in the character strings from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document.

25. The information retrieval system as recited in claim 22, wherein: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and a score is subtracted when it does not belong to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the perfect matching score.

26. The information retrieval system as recited in claim 25, wherein: the above-mentioned addition is divided into a character 1, and the above-mentioned subtraction is divided into a character 1/L.

27. An information retrieval system for detecting, by computer processing, a position where a retrieval character string appears in a database of a plurality of documents stored in a retrievable manner, the system comprising:

(a) means for inputting a search string;

(b) means for inputting similarities;

(c) a device for searching for a matching start position and end position in the above document, wherein a partial character string having a length of M characters or more to a predetermined integer having M characters or more to 2 or more is taken from the beginning of the search character string, and a partial character string having a length of M characters or more determined from the start position and the end position is referred to as an effective matching character string;

(d) a means for searching for a valid matching character string by using the means (c) from the beginning of the search character string if a response for detecting a valid matching character string occurs, and by shifting only the length of the valid matching character string just detected from the start position of the partial character string of the search character string and the search start position in the same document, and searching for a valid matching character string whose start position is within L characters of the distance from the valid matching character string just detected-L is a predetermined integer of 1 or more, and if a response for detecting a valid matching character string does not occur, by shifting one character from the start position of the partial character string of the search character string, and then retrieving a partial character string of M characters or more and having a length of M being a predetermined integer of 2 or more;

(e) means for continuing said step (d) as long as said valid matching string is detected;

(f) means for calculating a similarity between a character string at least between a start position of a first valid matching character string of the same document and an end position of a last valid matching character string of the same document and the search character string, based on information present in the valid matching character string, from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document;

(g) and (c) means for displaying the contents of the valid matching character strings included in the document if the similarity calculated as described above is greater than the similarity inputted in the step (b).

28. The information retrieval system as recited in claim 27, wherein: m is 2 and L is 3.

29. The information retrieval system as recited in claim 27, wherein: the calculation of the similarity takes a small value among the proportion of the valid matching character strings in the search character string and the proportion of the valid matching character strings in the character strings between the start position of the first valid matching character string of the document and the end position of the last valid matching character string of the document.

30. The information retrieval system as recited in claim 27, wherein: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and not a score is subtracted when it belongs to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the full matching score.

31. The information retrieval system as recited in claim 30, wherein: the above-mentioned addition is divided into a character 1, and the above-mentioned subtraction is divided into a character 1/L.

32. A method of making an index file with which glyphs of length N characters can be retrieved at high speed in documents stored in a retrievable manner by computer processing, the method comprising the steps of:

(a) sequentially scanning the document and writing the font of any N characters appearing in the document and the information of the appearance position of the font of the N characters in the document into a storage area;

(b) a step of, if a response that all the documents have been scanned has occurred in the step (a), sorting information written in the storage area by the fonts, and adding the position information corresponding to the sorted information to the different fonts;

(c) and a step of creating and outputting a file using the font as a key so as to search the added position information corresponding to the font.

33. The index documentation method of claim 32 wherein: the search in the step (c) is a binary search.

34. The information retrieval method according to claim 1 or claim 5, characterized in that: in the above document, search for M characters in a glyph is performed using an index file created by the method of claim 33 and using position information detected from the index file.

35. A method of making an index file with which a font of N characters in length can be retrieved at high speed in a database of a plurality of documents stored in a retrievable manner by computer processing, the method comprising the steps of:

(a) a step of adding a symbol or a number for identifying each of the plurality of documents individually;

(b) sequentially scanning the database and writing information on the fonts of arbitrary N characters appearing in each document of the database and the positions where the fonts of the N characters appear in the document into a storage area corresponding to the attached document identification symbol or number;

(c) if a response that all the documents in the database have been scanned is generated in step (b), sorting the information written in the storage area by the font, and adding the document identification number or serial number corresponding to the sorted information and the position information in the document to the different fonts;

(d) and a step of creating and outputting a file using the font as a key so as to search the attached document identification symbol or number and the position information corresponding to the font.

36. The index documentation method of claim 35 wherein: the search in the step (d) is a binary search.

37. The information retrieval method according to claim 10 or claim 14, characterized in that: in the above document, search for M characters in a glyph is performed using an index file created by the method according to claim 36, and using position information detected from the index file.

38. The index documentation method of claim 37 wherein: both M and N are 2, and L is 3 or more.

39. A method of indexing a document, using which a glyph of length N characters can be retrieved at high speed in a document stored in a retrievable manner by computer processing, the method comprising the steps of:

(a) sequentially scanning the documents, writing a pre-specified separator appearing in the documents and information on the appearance position of the separator in the documents into a storage area, and simultaneously writing the font of any N characters appearing in the documents continuously and information on the appearance position of the font of the N characters in the documents into the storage area;

(b) a step of, if a response that all the documents have been scanned has occurred in step (a), sorting information written in the storage area in accordance with the font, and adding the position information corresponding to the sorted information to the different fonts;

(c) and a step of creating and outputting a file using the font as a key so as to search the added position information corresponding to the font.

40. The information retrieval method according to claim 1 or claim 5, characterized in that: in the above document, search for M characters in a zigzag form is performed using an index file created by the method according to claim 39, and using position information detected from the index file.

41. The information retrieval method as recited in claim 40, wherein: and a step of searching for the separator in the document and adding position information detected when searching for M characters in a font in the document to a corresponding position.

42. A system for creating an index file, with which a font having a length of N characters can be retrieved at high speed in a document stored in a retrievable manner by computer processing, comprising:

(a) means for sequentially scanning the document and writing information on the position where the N character patterns appear in the document and the font pattern of any N characters appearing in the document consecutively in the document into a storage area;

(b) means for sorting information written in the storage area in accordance with the font when a response that all the documents have been scanned appears in the means (a), and adding the position information corresponding to the sorted information to the different fonts;

(c) and a device for generating and outputting a file by using the font as a key so as to search the added position information corresponding to the font.

43. A system for creating an index file, with which a font having a length of N characters can be retrieved at high speed in a database of a plurality of documents stored in a retrievable manner by computer processing, comprising:

(a) attaching a symbol or number to each of the plurality of documents for individually identifying the document;

(b) means for sequentially scanning the database and writing information on the fonts of arbitrary N characters appearing consecutively in each document of the database and the positions where the fonts of the N characters appear in the document into a storage area corresponding to the attached document identification symbol or number;

(c) means for sorting information written in the storage area in accordance with the font if a response that all documents in the database have been scanned is generated in the means (b), and adding the document identification number or serial number corresponding to the sorted information and position information in the document to the different font;

(d) and a device for generating and outputting a file by using the font as a key so as to search the attached document identification symbol or number and the position information corresponding to the font.

44. An index documentation system according to claim 43 wherein: all of the above N are 2.

45. A system for creating an index file, with which a font having a length of N characters can be retrieved at high speed in a document stored in a retrievable manner by computer processing, comprising:

(a) means for sequentially scanning the document, writing a previously specified delimiter appearing in the document and information on the position where the delimiter appears in the document into a storage area, and writing a font of arbitrary N characters appearing in the document and information on the position where the font of the N characters appears in the document into the storage area;

(b) means for sorting the information written in the storage area in accordance with the font when a response that all the documents have been scanned appears in the means (a), and adding the position information corresponding to the sorted information to the different fonts;

(c) and a device for generating and outputting a file by using the font as a key so as to search the added position information corresponding to the font.

46. A system for creating an index file, with which a font having a length of N characters can be retrieved at high speed in a database of a plurality of documents stored in a retrievable manner by computer processing, comprising:

(a) means for attaching a symbol or number to each of the plurality of documents for individual identification thereof;

(b) means for sequentially scanning the database, writing a previously designated delimiter appearing in each document of the database and information on the position of the delimiter appearing in the document into a corresponding storage area to which the document identification symbol or number is appended, and writing information on the position of the character pattern of any N characters and the position of the character pattern of the N characters appearing in each document of the database into the corresponding storage area to which the document identification symbol or number is appended;

(c) means for sorting information written in the storage area in accordance with the font when a response that all documents in the database have been scanned is generated in the means (b), and adding the document identification symbol or number and position information in the document corresponding to the sorted information in each of the different fonts;

(d) and a device for generating and outputting a file by using the font as a key so as to search the attached document identification symbol or number and the position information corresponding to the font.

47. An information retrieval method for enabling, by computer processing, the detection of a position where a retrieval character string appears in a database of a plurality of documents stored in a retrievable manner, the method comprising the steps of:

(a) inputting a search string;

(b) inputting similarity;

(c) a step of searching for a start position and an end position that match a partial character string having a length of at least M characters and a predetermined integer having M of 2 or more from the beginning of the search character string in the same document in the database, wherein the partial character string having a length of at least M characters and determined by the start position and the end position is referred to as an effective matching character string;

(d) get

The starting position of the ith valid coincident string in the literature is s (D, i)

The end position of the ith valid consistent character string in the literature is e (D, i)

The starting position of the ith valid consistent character string in the character string to be searched is s (C, i)

The end position of the ith effective consistent character string in the character string to be searched is e (C, i)

A step of retrieving the i +1 th valid identical character string satisfying the following two conditions:

e(D，i)+1≤s(D，i+1)≤e(D，i)+L+1

and is

s(C，i+1)＞e(C，i)-(M-1)

In the above formula, L is a predetermined integer of 1 or more,

(e) continuing the step (d) as long as the valid matching character string is detected;

(f) and calculating a similarity between the search string and the character string from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document based on information present in the valid matching character string at least in the character string from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document.

(g) If the similarity obtained by the above calculation is greater than the similarity input in the above step (b), the contents of the above valid matching character strings contained therein are displayed in the above document.

48. The information retrieval method as recited in claim 47, wherein: m is 2 and L is 3 or more.

49. The information retrieval method as recited in claim 47, wherein: the calculation of the similarity takes a small value among the proportion of valid matching character strings in the search character string and the proportion of valid matching character strings in the character strings from the start position of the first valid matching character string of the document to the end position of the last valid matching character string of the document.

50. The information retrieval method as recited in claim 47, wherein: the similarity calculation takes a small value between the proportion of the search string in the valid matching strings and the proportion of the valid matching strings between the start position of the first valid matching string of the document and the end position of the last valid matching string of the document.

51. An information retrieval method for detecting, by computer processing, where a retrieval string appears in a database of a plurality of documents stored in a retrievable manner, the method comprising the steps of:

(a) inputting a search string;

(b) inputting similarity;

(c) a step of extracting a partial character string having a length of M characters or more and M being a predetermined integer of 2 or more from the beginning of the search character string and detecting a start position and an end position matching the partial character string in the same document in the database, wherein the partial character string having a length of M characters or more determined by the start position and the end position is referred to as an effective matching character string …;

(d) get

The starting position of the ith valid coincident string in the literature is s (D, i)

The end position of the ith valid consistent character string in the literature is e (D, i)

The starting position of the ith valid matching character string in the character string to be searched is s (C, i)

The end position of the ith valid matching character string in the character string to be searched is e (C, i)

A step of retrieving the i +1 th valid coincident character string satisfying the following conditions:

s(C，i+1)＞e(C，i)-(M-1)

s(D，i+1)＞e(D，i)

and is

s(D，i+1)-e(D，i)-1+max(e(C，i)-s(C，i+1)

+1.0)≤L

(in the above formula, L is a predetermined integer of 1 or more)

(e) Continuing the step (d) as long as the valid matching character string is detected;

(f) and calculating a similarity between the search string and the character string from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document based on information present in the valid matching character string at least in the character string from the start position of the first valid matching character string of the same document to the end position of the last valid matching character string of the same document.

(g) Displaying the contents of the valid matching character strings contained in the documents if the calculated similarity is greater than the similarity inputted in the step (b).

52. The information retrieval method as recited in claim 51, wherein: m is 2, and L is 3 or more.

53. The information retrieval method as recited in claim 51, wherein: the calculation of the similarity takes a small value among the proportion of valid matching character strings in the search character strings and the proportion of valid matching character strings in the character strings between the start position of the first valid matching character string of the document and the end position of the last valid matching character string of the document.

54. The information retrieval method as recited in claim 51, wherein: for each character in the character string from the start position of the first valid matching character string of the above-mentioned document to the end position of the last valid matching character string of the above-mentioned document, a score is added when it belongs to the valid matching character string, and not a score is subtracted when it belongs to the valid matching character string, and the calculation of the above-mentioned similarity uses a value obtained by dividing the result score by the value of the full matching score.

55. The information retrieval method as recited in claim 51, wherein: the above-mentioned addition is divided into a character 1, and the above-mentioned subtraction is divided into a character 1/L.

56. And subtracting 1/(2L) for the characters which belong to the ith valid consistent character string and the corresponding search character string characters belong to the (i-1) th valid consistent character string.

Images