JP5389715B2 - Document number prediction apparatus, method and program for compound words - Google Patents

Description

  The present invention relates to an apparatus, method, and program for predicting the number of documents for a compound word, and more particularly to predicting the number of documents when the number of documents including the compound word is unknown for a compound word query input by a user. The present invention relates to a document number prediction apparatus, method, and program for a compound word focusing on a bias of a document including a compound word with respect to a part of a document group in order to improve a calculation amount of a document search and a response speed of a search result.

  In recent years, search services have become widespread on the Internet, and it has become possible to search for documents efficiently using queries to documents that users want. Here, in order to realize this search, an index relating to the document is created, and the document is provided as a search result from the index corresponding to the query input by the user.

  A transposed index is generally used as an index for a document group (see, for example, Non-Patent Document 1). The transposed index is a list of documents including words with respect to a certain word. This will be described with reference to the example of the inverted index in FIG. The figure shows a transposed index related to the “sun”. The first square in the transposed index indicates information regarding a document including “sun”. Here, information regarding “Doc1” is included as a document. The information related to Doc1 is composed of several pieces of information. In the figure, the following three pieces of information are included as information of “Doc1”.

1. Document ID
2. 2. Number of occurrences of word ("sun") Appearance position of word ("sun") Since this transposed index is created in advance, information on the number of documents including the word is also held. In FIG. 9, there are 15 documents including “sun”.

  As described above, a transposed index for a word is created for a word extracted from a document group to be searched, but a query input from a user may be a word for which a transposed index is not prepared. For a query for which an inverted index is not prepared, it is necessary to obtain a corresponding document from a group of words constituting the query and an inverted index of related words.

  Here, a case where the query is a compound word (a word composed of a plurality of words) will be taken up, and a method for obtaining a list of documents when a transposed index for the compound word is not prepared will be described. The case of “solar energy” as a compound word query will be described. When transposed indexes of “sun” and “energy” are prepared as shown in FIG. 9, it is necessary to obtain a document including “solar energy” from these transposed indexes. First, paying attention to the document “Doc1” including “sun”, the document including “energy” is searched. Here, it can be seen from the transposition index of “energy” that “Doc1” contains “energy”.

  Next, the location where the appearance position of “energy” continues after the appearance position of “Sun” in “Doc1” is searched. From FIG. 9, since the appearance position of “sun” is “1” and the appearance position of “energy” is “2”, it is detected that “Doc 1” includes “solar energy”. A similar process is performed for all documents present in the transposed index of “sun” to create a list of documents that contain “solar energy”.

Justin Zobel, Alistair Moffat and Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing.ACM Transactions on Database Systems (TODS), Volume 23, Issue 4 (December 1998), Pages: 453-490.

  However, in the above-described conventional technology, when a query is input from a user, it is necessary to detect a document including a compound word from a plurality of inverted indexes constituting the compound word, and calculation is performed when sequentially processing from the entire inverted index. There is a problem that the amount is large and the response time becomes long.

  In addition, when a transposed index for a compound word is created in advance from a target document group to shorten the response time, there is a problem that the number of prepared transposed indexes becomes enormous and the cost increases.

  On the other hand, when predicting the number of documents that make up the compound word of the entire document group based on the number of documents that make up the compound word, it depends on the existence status of some documents that make up the compound word. There is a problem that the predicted values differ greatly. The existence status of the document group here indicates the ratio of the number of documents in which the target compound word is included in the document to the number of documents that are not included.

  The present invention has been made in view of the above points. In the case where the number of documents can be predicted at a low cost, and the number of documents is predicted based on the number of documents including compound words detected from some document groups. Another object of the present invention is to provide a document number prediction apparatus, method, and program for a compound word that can be predicted with higher accuracy than the number of predicted documents by a general means.

  FIG. 1 is a principle configuration diagram of the present invention.

The present invention (Claim 1) is a document number prediction apparatus for compound words in document search,
For each word name, a transposed index storage means 60 that stores a transposed index including a document ID including the word, the number of appearances of the word, and the appearance position of the word;
Word splitting means 10 for splitting a compound word into a single word when the query inputted by the user is a compound word;
A transposed index obtaining unit 21 that extracts a transposed index for each divided word by referring to the transposed index storage unit 60 based on the divided word;
Document number calculation means 22 for calculating the number of documents including a compound word extracted from the extracted transposed index for a preset number of documents;
Prediction for calculating a predicted value of the number of documents including a compound word for all documents using a document number prediction rule based on the number of documents including the detected compound word and the number of documents including each word acquired by the transposed index acquisition unit 21 Value calculating means 100.

The present invention (Claim 2) provides the document number prediction rule of Claim 1,
When detecting a document containing compound words, if the ratio of the number of documents searched for the transposed index of each word is larger than the ratio of the number of documents of a single word, the number of predicted documents is corrected to be smaller using the ratio of the number of single documents. Including rules to do.

Further, the present invention (Claim 3) is the document number prediction rule of Claim 1,
When detecting documents containing compound words, if the ratio of the number of documents searched for the transposed index of each word is smaller than the ratio of the number of documents of a single word, the number of predicted documents is greatly corrected using the ratio of the number of single documents. Including rules to do.

  FIG. 2 is a diagram for explaining the principle of the present invention.

The present invention (Claim 4) is a method for predicting the number of documents for a compound word in document search,
For each word name, a transposed index storage unit that stores a transposed index including a document ID including the word, the number of occurrences of the word, and the appearance position of the word;
An apparatus having rule storage means storing document number prediction rules,
A word dividing step (step 1) for dividing the compound word into a single word when the query inputted by the user is a compound word;
A transposed index acquisition step (step 2) for referring to the transposed index storage means based on the divided words and extracting a transposed index for each divided word;
A document number calculation step (step 3) for calculating the number of documents including a compound word extracted from the extracted transposed index for a preset number of documents;
Based on the number of documents including the detected compound word and the number of documents including each word acquired in the transposed index acquisition step (step 2), the predicted value of the number of documents including the compound word for all documents is calculated using the document number prediction rule. A predicted value calculation step (step 4) to be calculated is performed.

Further, according to the present invention (Claim 5), in the predicted value calculation step of Claim 4,
When detecting a document containing compound words, if the ratio of the number of documents searched for the transposed index of each word is larger than the ratio of the number of documents of a single word, the number of predicted documents is corrected to be smaller using the ratio of the number of single documents. Use the document number prediction rule.

Further, the present invention (Claim 6) is a predicted value calculating step according to Claim 4,
When detecting documents containing compound words, if the ratio of the number of documents searched for the transposed index of each word is smaller than the ratio of the number of documents of a single word, the number of predicted documents is greatly corrected using the ratio of the number of single documents. Use the document number prediction rule.

  The present invention (Claim 7) is a document number prediction program for causing a computer to function as each means constituting the document number prediction apparatus according to any one of Claims 1 to 3.

  As described above, according to the present invention, in the calculation of the number of documents for the conventional compound word, the calculation amount is smaller than the calculation of the number of documents including the compound word by sequentially scanning the transposed index of the words constituting the compound word. Predict the number of documents. Further, when the number of documents is predicted based on the number of documents including a compound word detected from a part of the document group, it can be predicted with higher accuracy than the number of documents predicted by a general means.

It is a principle block diagram of this invention. It is a figure for demonstrating the principle of this invention. It is a block diagram of the document number prediction apparatus in one embodiment of this invention. It is a flowchart of operation | movement of the document number prediction apparatus in one embodiment of this invention. It is the detection condition of the document which has "solar energy" of one Example of this invention. It is calculation example 1 of the number of documents with respect to compound word "solar energy" of one Example of this invention. It is the calculation example 2 of the number of documents with respect to the compound word "solar energy" of one Example of this invention. It is the calculation example 3 of the number of documents with respect to the compound word "solar energy" of one Example of this invention. It is an example of an inverted index.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  FIG. 3 shows the configuration of the document number prediction apparatus according to the embodiment of the present invention.

  The document number prediction apparatus shown in the figure includes a query input unit 10, a document number prediction unit 20, a prediction formula 1 calculation unit 30, a prediction formula 2 calculation unit 40, a prediction formula 3 calculation unit 50, a transposed index storage unit 60, a prediction rule. The storage unit 70 is configured. Among these, the transposed index storage unit 60 and the prediction rule storage unit 70 are storage media such as a hard disk and a memory.

  When the input query is a compound word, the query input unit 10 divides the compound word into a single word.

  The document number prediction unit 20 searches the transposed index 60 based on the words divided by the query input unit 10, extracts the transposed index including the document ID, the number of appearances, and the appearance position corresponding to each word. Generate a transpose list for. The number of documents including compound words is detected from the transposed index.

  The prediction formula 1 calculation unit 30, the prediction formula calculation unit 40, and the prediction formula 3 calculation unit 50 determine the number of documents including the detected compound word and each of the compound words based on the prediction rule corresponding to the preset condition. The number of documents is predicted based on the number of documents including words.

  The transposed index storage unit 60 stores a transposed index for each word name. Here, the transposed index includes the document ID of the document including the word, the number of appearances of the word, and the appearance position of the word.

  The prediction rule storage unit 70 stores rules for document number prediction used in the prediction formula 1 calculation unit 30, the prediction formula calculation unit 40, and the prediction formula 3 calculation unit 50.

  The operation in the above configuration will be described.

  FIG. 4 is a flowchart of the operation of the document number prediction apparatus according to the embodiment of the present invention.

  Step 101) The ratio of the inverted index to be processed is set in advance in the memory (not shown) of the document number prediction apparatus.

  Step 102) The query input unit 10 morphologically analyzes the input compound word and divides it into a single word.

  Step 103) The document number prediction unit 20 reads the transposed index for each divided word from the transposed index storage unit 60.

  Step 104) The document number prediction unit 20 counts the document number df for each word by the transposed index read in Step 103, selects the word with the smallest number of documents in the document number, and sets it as the word a here. Conversely, a word with a small number of documents is designated as word b. Also, the number of documents for word a is df1, and the number of documents for word b is df2.

  Step 105) The number of documents to be searched is determined based on the ratio stored in the memory (not shown) in Step 101 with respect to the transposed index of the word a selected in Step 104. The number of documents determined here is N.

  Step 106) From the transposed list of word a selected in step 104, the N compound words of the query input based on the appearance position of the word from the beginning of the transposed index of word a determined in step 105 are included. Search the number of documents. Assume that the number of documents including the compound word detected at this time is D, the number of indexes searched for word a is s1, and the number of indexes searched for word b is s2.

  Step 107) When s1 / s2 is larger than “1.0”, the document number predicting unit 20 proceeds to Step 108, and otherwise proceeds to Step 109.

  Step 108) The prediction formula 1 calculation unit 30 acquires the following prediction formula 1 from the prediction rule storage unit 70 based on the condition (s1 / s2> 1.0), and predicts and outputs the number of compound word documents. .

Prediction formula 1 = D / (s2 / (df1-s1 + s2))
Step 109) s1 / s2 is compared with df1 / df2, and if s1 / s2 <df1 / df2, the process proceeds to Step 110, and if s1 / s2 ≧ df1 / df2, the process proceeds to Step 111.

  Step 110) The prediction formula 2 calculation unit 40 obtains the following prediction formula 2 from the prediction rule storage unit 70 based on the conditions (s1 / s2> 1.0 and s1 / s2 <df1 / df2), and the compound word Predict and output the number of documents.

Prediction formula 2 = D / (a1 / df1) × (1.0 − ((s1 / s2) / (df1 / df2)))
Step 111) The prediction formula 3 calculation unit 50 acquires the following prediction formula 3 from the prediction rule storage unit 70 based on the conditions (s1 / s2> 1.0 and 1 / s2 ≧ df1 / df2), and combines Predict and output the number of word documents.

    Prediction formula 3 = D / (s1 / df1)

  The specific operation of the document number prediction apparatus described in the above embodiment will be described below with reference to the flowchart of FIG.

  In the following embodiment, it is assumed that the transposed index storage unit 60 stores transposed index information related to “sun” and “energy” as word names.

  When the compound word “solar energy” is input as a query to the query input unit 10, “solar energy” is morphologically analyzed and divided into two words “solar” and “energy”. Next, “sun” and “energy” are transferred to the document number prediction unit 20 (step 101).

  When the document number prediction unit 20 acquires the words “sun” and “energy”, the document number prediction unit 20 reads the transposition index information regarding the two words “sun” and “energy” from the transposition index storage unit 60 (step 102). Here, an example of the read transposed index information is shown in FIG. In the figure, the document ID, the number of appearances, and the appearance position for each document are stored as a transposition index for the document containing the words “sun” and “energy” in the document.

  Next, the document number prediction unit 20 searches for a document including the word “solar energy” for each document ID with respect to the transposed indexes of “solar” and “energy” (step 103). First, in order to search for a compound word of “solar energy” for the document with document ID “Doc1”, the appearance position of the word “sun” from the transposed index of “sun” To extract. Here, “1” is extracted from FIG. Next, the minimum appearance position that is larger than “1” and is extracted from the transposed index of “energy” is extracted. Here, “2” is extracted. Since the appearance position “1” of “sun” and the appearance position “2” of “energy” are continuous, it is detected that “solar energy” appears in the document (document ID “Doc1”). Since “solar energy” is detected in the document ID “Doc1”, the same processing is performed on the next document.

  FIG. 5 shows a detection state of a document group including “solar energy” in the present embodiment. In FIG. 5, one rectangle represents a transposition index of a document, and “○” indicates that the document includes “solar energy” in the document (step 104).

  In the present embodiment, four items are searched from the top of the transposed index of “Sun” having a small number of documents. In this embodiment, if the number of documents (df1) of “sun” is 10, as in the example of FIG. 6, the first four documents of the transposed index are searched. At this time, it is assumed that one of four documents (D = 1) is found (a document with a circle in FIG. 6).

  In this example, the number of documents s1 searched for “sun” is “4” and the number of documents s2 searched for “energy” is “2” (steps 105 and 106). The ratio of the number of documents searched for two transposed indexes. Since (4/2) is 1.0 or more (step 107), the prediction formula 1 calculation unit 30 predicts the number of documents by the following prediction formula (step 108).

Number of predicted documents = D / (s2 / (df1-s1 + s2))
= 1 / (2 / (10-4 + 2))
= 4
The above is the number of documents for “solar energy”.

  Next, a case where the number of documents related to the compound word “solar energy” is predicted as in the example of FIG. 7 will be described. In the example shown in the figure, the number of documents of “sun” is “10”, the number of documents of “energy” is “11” (step 103), and the inverted index of “sun” is small (step 104). It is assumed that the first two documents are searched (steps 105 and 106), and one document including “solar energy” (D = 1) is found.

  In the example of FIG. 7, the document number s1 searched for “sun” is “2”, the document number s2 searched for “energy” is “7”, and the ratio of documents searched for two transposed indexes is 2/7. Since it is less than 1.0 (step 107) and the DF ratio (10/11) of the two words is larger than the ratio (2/7) of the documents searched for the two transposed indexes (step 109), the prediction The number of documents is predicted by the following prediction formula in the formula 2 calculation unit 40 (step 110).

Number of predicted documents = D / (s1 / df1) × (1.0 − ((s1 / s2) / (df1 / df2)))
= 1 / (2/10) x (1.0-((2/7) / (10/11)))
= 1 / (1/5) x (1.0-0.3143)
= 1 / (1/5) x 0.6857
= 3.4285
The above is the number of documents for “solar energy”.

  Next, a case where the number of documents related to the compound word “solar energy” is predicted as in the example of FIG. 8 will be described. In the example in the figure, the number of documents for “Sun” is “6”, the number of documents for “Energy” is “16”, and the first two documents are searched for the inverted index of “Sun” with a small number of documents. It is assumed that one document including “solar energy” is found (steps 103 to 104).

  In this example, the document number s1 searched for “sun” is “2” and the document number s2 searched for “energy” is “3” (step 105). The ratio of documents searched for two transposed indexes (2 / 3) is less than 1.0 (step 107), and the DF ratio (6/16) of the two words is smaller than the ratio (2/3) of the documents searched for the two transposed indexes (step 109). ), The prediction formula 3 calculation unit 50 predicts the number of documents by the following prediction formula (step 111).

Expected number of documents = D / (s1 / df1)
= 1 / (2/6)
= 3
The above is the prediction DF of “solar energy”.

  The operations of the components of the document number predicting apparatus shown in FIG. 3 can be constructed as a program and installed in a computer used as the document number predicting apparatus, or can be distributed via a network. It is.

  In addition, the constructed program can be stored in a portable storage medium such as a hard disk, a flexible disk, or a CD-ROM, and can be installed or distributed in a computer.

  The present invention is not limited to the above-described embodiments and examples, and various modifications and applications are possible within the scope of the claims.

DESCRIPTION OF SYMBOLS 10 Word division means, Query input part 20 Document number prediction part 21 Inverted index acquisition means 22 Document number calculation means 30 Prediction formula 1 calculation part 40 Prediction expression 2 calculation part 50 Prediction expression 3 calculation part 60 Inverted index storage means, Inverted index storage Unit 70 prediction rule storage unit 100 predicted value calculation means

Claims (7)

A device for predicting the number of documents for a compound word in document search,
For each word name, a transposed index storage unit that stores a transposed index including a document ID including the word, the number of occurrences of the word, and the appearance position of the word;
A word dividing means for dividing a compound word into a single word when a query inputted by a user is a compound word;
A transposed index obtaining unit that extracts a transposed index for each of the divided words by referring to the transposed index storage unit based on the divided words;
Document number calculation means for calculating the number of documents including compound words extracted from the extracted transposed index for the number of documents set in advance;
Prediction for calculating a predicted value of the number of documents including compound words for all documents using a document number prediction rule based on the number of documents including detected compound words and the number of documents including each word acquired by the transposed index acquisition unit A value calculating means;
An apparatus for predicting the number of documents. The document number prediction rule is:
When detecting a document containing compound words, if the ratio of the number of documents searched for the transposed index of each word is larger than the ratio of the number of documents of a single word, the number of predicted documents is corrected to be smaller using the ratio of the number of single documents. The document number prediction apparatus according to claim 1, further comprising: The document number prediction rule is:
When detecting documents containing compound words, if the ratio of the number of documents searched for the transposed index of each word is smaller than the ratio of the number of documents of a single word, the number of predicted documents is greatly corrected using the ratio of the number of single documents. The document number prediction apparatus according to claim 1, further comprising: A method for predicting the number of documents for a compound word in a document search,
For each word name, a transposed index storage unit that stores a transposed index including a document ID including the word, the number of occurrences of the word, and the appearance position of the word;
An apparatus having rule storage means storing document number prediction rules,
A word splitting step that splits a compound word into a single word when the query entered by the user is a compound word;
A transposed index acquisition step of extracting a transposed index for each divided word with reference to the transposed index storage means based on the divided word;
A document number calculating step for calculating the number of documents including a compound word extracted from the extracted transposed index for a preset number of documents;
Prediction for calculating a predicted value of the number of documents including compound words for all documents using a document number prediction rule based on the number of documents including detected compound words and the number of documents including each word acquired in the transposed index acquisition step A value calculation step;
Document number prediction method characterized by performing In the predicted value calculation step,
When detecting a document containing compound words, if the ratio of the number of documents searched for the transposed index of each word is larger than the ratio of the number of documents of a single word, the number of predicted documents is corrected to be smaller using the ratio of the number of single documents. The document number prediction method according to claim 4, wherein the document number prediction rule is used. In the predicted value calculation step,
When detecting documents containing compound words, if the ratio of the number of documents searched for the transposed index of each word is smaller than the ratio of the number of documents of a single word, the number of predicted documents is greatly corrected using the ratio of the number of single documents. The document number prediction method according to claim 4, wherein the document number prediction rule is used.   A document number prediction program for causing a computer to function as each means constituting the document number prediction apparatus according to any one of claims 1 to 3.

Images