Information retrieval method, device, program, and recording medium

【0001】

[Technical field to which the invention belongs]

The present invention relates to an information retrieval method and an apparatus for indexing a set of documents to be searched and searching for a document that matches the search conditions entered by the user.

【0002】

[Conventional technology]

The information retrieval device is a device that searches for documents that match the search question given by the user from the document set and presents them to the user. Therefore, many of today's information retrieval devices do not simply list documents containing search terms, but calculate the goodness of fit for each document's search question, and only the documents with high goodness of fit are in descending order of goodness of fit. Present to. This is called a ranking search.

【0003】

The concept of index term weights is used to calculate the goodness of fit (Non-Patent Documents 3 and 4). Here, the index term is a word that characterizes the content of the document, but in today's full-text search device, basically all the words in the document are regarded as the index term. In Asian languages such as Japanese, word delimiters are not clear, so it is common to use morphemes or letter N grams as index terms. The index term weight is a numerical value that indicates how important the index term is in expressing the content of the document, and is generally the index term w._iDocument D_jWeight in d_{i, j}Is the local weight l_{i, j}, Global weight g_i, Document normalizing coefficient n_jFrom these three indexes, it is characterized as Eq. (1) (Non-Patent Document 3).

【0004】

[Number 1]<img file="JP2004192546A_D0001.tif" /> 【0005】

For example, in the TF / IDF method, which is known as the most basic weighting method, the local weight l_{i, j}The index term frequency (TF: term frequency), which is the number of occurrences of the index term in the document, is the global weight g._iThe reciprocal of the percentage of documents in which the index term appears (IDF: inverse document frequency) is used as. Also, the document normalizing coefficient n_jThe simplest method is to use the document size (sum of index term frequencies). That is, the index term weight d by the TF / IDF method_{i, j}Is as shown in equation (2).

【0006】

[Number 2]<img file="JP2004192546A_D0002.tif" /> 【0007】

Also, using methods other than the TF / IDF method, l_{i, j}From the index term frequency, g_iIs from the document frequency, n_jIs often obtained from the document size.

【0008】

An information retrieval device for a large number of documents stores index terms and information on their appearance positions in a kind of database called an index in advance in order to perform a search process at high speed. This is called an index search method (Non-Patent Document 3, Non-Patent Document 4). Inverted index is a typical implementation method of index search (Non-Patent Document 3 and Non-Patent Document 4). An inverted index is a database that lists index terms in lexical order and uses them as keys to refer to a list of index term occurrence positions (Fig. 5). In the inverted index method, not only the document number but also the position in the document is stored as the position information, so that the appearance position of the search word composed of a sequence of a plurality of index words can be found without referring to the document itself. You can ask. In addition, the inverted index is ranked because the basic parameters necessary for calculating the degree of suitability, such as the number of occurrences of the search term in each document, the number of documents in which the search term appears, and the total number of occurrences of the search term, are also obtained at the same time. It can be said that this is an index search method suitable for searching.

【0009】

[Non-Patent Document 1]

Michael Persin, Justin Zobel, Ron Sacks-Davis: "Filtered Document Retrieval with Frequency-Sorted Indexes", Journal of the American Society of Information Science, Vol.47, No.10, pp. 749-764, 1996. Reference 2]

Satoshi Hayami, Hiroshi Takeno, Tomoya Nagase, Noriyuki Fujimoto, Kenichi Hagiwara "Proposal and Evaluation of Scalable WWW Parallel Full-Text Search System Construction Method", IPSJ Database Study Group Research Report, Vol.123, No.7, pp .45-52, 2001.

[Non-Patent Document 3]

Kenji Kita, Kazuhiko Tsuda, Masami Shishibori "Information Search Algorithm", Kyoritsu Shuppan, 2002.

[Non-Patent Document 4]

Takenobu Tokunaga "Information Search and Language Processing", University of Tokyo Press, 1999.

【0010】

[Problems to be Solved by the Invention]

In the case of an information retrieval device that employs an inverted index, most of the processing time for ranking search is occupied by the process of reading the occurrence position list from the inverted index into main memory and the process of calculating the goodness of fit of the document that is the search result. Be done. Therefore, the ranking search requires a time that is roughly proportional to the total number of occurrences of the search terms included in the search question.

【0011】

In general, the number of occurrences of a phrase increases in proportion to the amount of text in the document set to be searched. Therefore, in a large-scale information retrieval system such as a WWW search engine, the search process may take a very long time with a conventional inverted index. In order to deal with this problem, a parallel search method may be used in which a document set is divided, each subdocument set is searched in parallel by a plurality of computer systems, and the search results are merged (non-patented). Reference 2). However, since a lot of hardware is required, the cost required to install and maintain the system is high.

【0012】

An object of the present invention is to provide an information retrieval method, an apparatus, a program, and a recording medium capable of performing ranking retrieval for a large-scale document set at high speed and at low cost.

【0013】

[Means for solving problems]

The information retrieval apparatus of the present invention includes an index creation means, an inverted index, a high-frequency word extraction means, a high-frequency word inverted index, a suitability calculation means, and a search processing means.

【0014】

The inverted index stores a list of pairs of index terms and occurrence positions by index creation means. The high-frequency word inverted index stores a list of index words whose index word frequency is equal to or higher than a predetermined threshold and a set of their occurrence positions by the high-frequency word extraction means. The search processing means receives the search term from the user, and when the search term is composed of only one index term, inputs a list of the occurrence positions of the index term from the high-frequency word transposition index, and the search term is In the case of a sequence of multiple index terms, a list of occurrence positions of each index term is input from the high-frequency word transposition index, and a list of positions where all index terms appear adjacent to each other is obtained to obtain a high-frequency word. If the list of occurrence positions obtained from the translocation index refers to T or more documents (T is an integer of 1 or more) required to display the search results, the list of appearance positions is used as the conformity calculation means. If you receive a list of conformance documents and the top T-th conformance document has a greater conformity than the maximum possible conformance of a low-frequency document that is not stored in the high-frequency word transposition index, then they Is output, and if a list of occurrence positions that refer to T or more documents cannot be obtained from the high-frequency word transposition index, or if there is a possibility that the T documents with the highest degree of conformity have not been searched correctly. , Obtain a list of occurrence positions of search terms using a transposed index, output it to the conformity calculation means, input a list of conformance documents from the conformity calculation means, and rank the conformity documents in descending order of conformity. Output T pieces.

【0015】

In the information retrieval device of the present invention, in addition to the normal transposed index, a high-frequency word transposed index that stores only the occurrence position list having a high index term frequency is prepared in advance, so that the search question is composed of only one search term. If this is the case, only a relatively small high-frequency word transposition index is used to search for a highly suitable document, and if the search question is composed of a plurality of search words, the conventional search method is used.

【0016】

BEST MODE FOR CARRYING OUT THE INVENTION

Next, an embodiment of the present invention will be described with reference to the drawings.

【0017】

Referring to FIG. 1, the information retrieval apparatus according to the embodiment of the present invention includes an index creation unit 1, an inverted index 2, a high frequency word extraction unit 3, a high frequency word inverted index 4, a search reception unit 5, and a conformity calculation unit 6. It is composed of a search processing unit 7, a document set database 8, and a document size database 9.

【0018】

The index creation unit 1 inputs a document to be searched from the document set database 8, extracts index terms that characterize the document, and stores the index terms and a list of their occurrence positions in the transposed index 2.

【0019】

As shown in FIG. 2, the high-frequency word extraction unit 3 sequentially reads a pair of index terms and occurrence positions from the transposed index 2 (step 11), and corresponds to a document in which the index term frequency exceeds a predetermined threshold. Extract the occurrence position (step 12), and if the number of such documents is T or more (T is an integer of 1 or more) displayed as the top of the search results, the extracted index term and appearance Store the list of positions in the high frequency word translocation index 4 (step 13).

【0020】

The search reception unit 5 receives the search question from the user, passes it to the search processing unit 7, receives the conforming document list from the search processing unit 7, and inputs the document information corresponding to the document number in the conforming document list from the document set database 8. Read it out and present it to the user.

【0021】

As shown in FIG. 3, the conformity calculation unit 6 receives a list of appearance positions of search terms from the search processing unit 7 (step 21), receives a document size from the document size database 9 (step 22), and searches in each document. From the frequency of words and the document size, the degree of conformity is calculated for each document according to a calculation formula such as the TF / IDF method (step 23), and the conformity document list is output to the search processing unit 7 (step 24). When the search question has only one search term (not AND search or OR search, just one word search), the document frequency (the number of documents in which the search term appears) can be regarded as a constant, so it is used in the calculation of suitability. It does not have to be. That is, in this case, "how well the search question matches the document" is the same as "how strongly the index terms contained in the document characterize the document", and a document such as the TF / IDF method. Calculate the degree of conformity with the formula that calculates the weight of the index term inside. For example, when searching with the search term "mobile phone" and calculating the goodness of fit by the TF / IDF method, the goodness of fit of a document and "mobile phone" = f._{i, j} log (N / F_i) / Σ_if_{i, j}Where f_{i, j}Is the number of "mobile phones" that appear in the document, N is the total number of documents, F_iIs the number of documents in which "mobile phones" appear, Σ_if_{i, j}Is the sum of the index term frequencies in the document. By calculating and comparing this goodness of fit for all documents that contain the word "mobile phone" more than a certain number of times, it is possible to determine which document fits well (whether it is strongly related to the topic "mobile phone"). Understand. Σ_if_{i, j}Is the sum of the index term frequencies of all index terms in a document j, so it is the size of the document j. This can be calculated from the inverted index 2, but this is inefficient because it requires reading and summarizing the entire index, so prepare it separately as in document size database 9.

【0022】

In the case of the word "search" in FIG. 5, the appearance position list is (2,100), (2,121), (2,207), (3,24), (19,31). In other words, it can be seen that the word "search" appears 5 times in total, 3 times for the document with document number 2, 1 time for the document with document number 3, and 1 time for the document with document number 19. ..

【0023】

As described above, while obtaining the index term frequency for each document from the occurrence position list in this way (log (N / F)_i) Is regarded as a constant) and the goodness of fit of each document is calculated.

【0024】

As shown in FIG. 4, the search processing unit 7 first receives a search word passed from the user via the search reception unit 5, and uses the high-frequency word inverted index 4 to obtain a list of occurrence positions of the search word. (Step 31). That is, when the search term is composed of only one index term, the occurrence position list of the index term is input from the high-frequency word transposition index 4, and when the search term is a sequence of a plurality of index terms, the search term is a sequence of a plurality of index terms. , Input the list of occurrence positions of each index term from the high-frequency word transposition index 4, and find the list of positions where all index terms appear adjacent to each other. Next, if the occurrence position list obtained from the high-frequency word inverted index 4 refers to T or more documents required for displaying the search results, the appearance position list is sent to the goodness-of-fit calculation unit 6. Pass and receive a list of conforming documents (steps 32,36,37). Then, if the T-th document with the highest goodness of fit has a goodness of fit larger than the maximum goodness of fit that the low-frequency document that is not stored in the high-frequency word transposition index 4 can take, the T-th document with the highest goodness of fit is Now that they are searched correctly, print them out (steps 38, 39). For example, when the TF / IDF method is used to calculate the goodness of fit, the T-th document D in descending order of goodness of fit._TIndex term frequency is F_T, Document size is S_TThen F_T/ S_TIs (F-1) / S_minIf it is larger, documents with index term frequency (F-1) or less stored in inverted index 2 are guaranteed not to be in the top T of goodness of fit. Where S_minIs the smallest document size in the document set. If the high-frequency word inverted index 4 does not provide a list of occurrence positions that refer to T or more documents, or if there is a possibility that the T documents with the highest goodness of fit have not been searched correctly, it is normal. Perform ranking search processing using inverted index 2. That is, the inverted index 2 is used to obtain the appearance position list of the search term (step 33), the output is output to the goodness-of-fit calculation unit 6 (step 34), and the goodness-of-fit document list is input from the goodness-of-fit calculation unit 6 (step). 35), output the top T maximum in descending order of goodness of fit (step 39).

【0025】

When a search question using one or more search terms is given, or when the ranking search based on the goodness of fit is not performed, the conventional search process using a normal inverted index may be performed. The method of the present invention can be additionally introduced into an existing information retrieval apparatus.

【0026】

When indexing a Japanese document, there are a method using a morpheme as an index term, a method using N grams, a method combining both, and the like, and the method of the present invention can be applied in any case.

【0027】

Although a fixed threshold value F is used in the method of the present invention, a different threshold value can be set for each index term. In that case, the maximum value of the index term thresholds included in the search term phrase is set to F._maxIf so, F_T/ S_TIs (F_max-1) / S_minIf it is larger, it can be determined that the search was possible only with the high-frequency word inverted index.

【0028】

The method of the present invention is applicable not only to the TF / IDF method but also to many goodness-of-fit calculation methods that use the index term frequency and the document size as the main parameters of the goodness-of-fit calculation. Further, when the calculation of the goodness of fit does not need to be strict, when T or more documents are searched by the high frequency word inverted index, the upper T documents may be used as the search result.

【0029】

Instead of creating a high-frequency word inverted index separately, by arranging the occurrence position list stored in the translocation index in descending order of index term frequency, the first part of the occurrence position list is regarded as a high-frequency word inverted index, and the present invention The same search process can be performed (Non-Patent Document 1). However, in an inverted index having such a configuration, the speed of a normal search process that does not use the method of the present invention is slowed down.

【0030】

As a method similar to the present invention, it is also conceivable to perform a ranking search for all index terms in advance and save the top T items in the conforming document list (Non-Patent Document 2). However, unlike the method of the present invention, that method cannot search for a phrase that is a sequence of a plurality of index terms. The method of the present invention can also be used in combination with such a method.

【0031】

In addition to the program realized by the dedicated hardware, the present invention records a program for realizing the function on a computer-readable recording medium, and the program recorded on the recording medium is stored in the computer system. It may be read and executed. The computer-readable recording medium refers to a recording medium such as a floppy disk, a magneto-optical disk, a CD-ROM, or a storage device such as a hard disk device built in a computer system. Furthermore, the computer-readable recording medium is one that dynamically holds the program for a short period of time (transmission medium or transmission wave), such as when the program is transmitted via the Internet, and is a server in that case. It also includes those that hold programs for a certain period of time, such as volatile memory inside a computer system.

【0032】

[Effect of the invention]

As described above, according to the present invention, when searching for a single search term, a high-fitness document is searched using only the high-frequency word index. Therefore, as compared with the conventional search method, a database is used. The amount of data read from the main memory and the CPU processing time required to calculate the goodness of fit can be significantly reduced, and the search processing can be speeded up. For example, in a WWW search engine, about 70% of search questions are composed of only a single search term, so it is expected that the speed-up effect of the present invention will be great.

[Simple explanation of drawings]

FIG. 1 is a block diagram showing a configuration of an information retrieval device according to an embodiment of the present invention.

FIG. 2 is a flow chart showing processing of a high-frequency word extraction unit of the information retrieval device of FIG.

FIG. 3 is a flow chart showing processing of the goodness-of-fit calculation unit of the information retrieval device of FIG.

FIG. 4 is a flow chart showing processing of a search processing unit of the information retrieval device of FIG.

FIG. 5 is a diagram showing a general structure of an inverted index.

[Explanation of symbols]

1 Index creation unit 2 Inverted index 3 High-frequency word extraction unit 4 High-frequency word inverted index 5 Search reception unit 6 Conformity calculation unit 7 Search processing unit 8 Document database 9 Document size database 11 ~ 14,21 ~ 24,31 ~ 39 Steps