JP4045728B2 - Similar document search method and apparatus, and storage medium storing program for similar document search method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a method for searching a document database for a document including content similar to the content described in a document designated by a user.
[0002]
[Prior art]
In recent years, with the spread of personal computers, the Internet, etc., the number of electronic documents has increased explosively and is expected to increase at an accelerated rate in the future. Under such circumstances, there is an increasing demand for searching for a document including information desired by a user at high speed and efficiently.
[0003]
As a technique for responding to such a request, a similar document search technique in which a user exemplifies a document including contents desired by the user (hereinafter referred to as a seed document) and searches for a document similar to the document has been attracting attention. .
[0004]
As a method for retrieving similar documents, for example, “Japanese Patent Laid-Open No. 11-66086” is disclosed (hereinafter referred to as Prior Art 1).
[0005]
In the conventional technique 1, when a document is registered in the document database, information necessary for full-text search of the document to be registered (referred to as an inverted index in the conventional technique 1. Hereinafter, for full-text search. This is referred to as an index.) When searching for similar documents, the frequency of occurrence of words contained in a registered document (hereinafter referred to as a registered document) by referring to the full-text search index is used as an element. A vector (hereinafter referred to as a feature vector) is created, and this and the feature vector of a document specified as a search condition (hereinafter referred to as a seed document) form a cosine of the angle formed in the vector space. This is a technique for calculating the degree.
[0006]
Hereinafter, the processing procedure of Prior Art 1 will be described with reference to a PAD (Problem Analysis Diagram) diagram of FIG.
[0007]
In the prior art 1, first, in step 200, it is determined whether the process is a document registration process or a similar document search process. If it is determined that the process is a document registration process, a full-text search index creation step 210 is executed. Create an index.
[0008]
If it is determined in step 200 that the search process is a similar document, a seed document feature vector generation step 220 is executed to create a feature vector for the seed document. Then, the similarity calculation step 221 using the full-text search index is executed, and the cosine of the angle formed by the feature vector of the seed document and the feature vector of the registered document in the vector space is calculated as the similarity between documents.
[0009]
The above is the processing procedure of the prior art 1.
[0010]
Hereinafter, an outline of the related art 1 will be described with reference to FIG.
[0011]
In the document registration process of Prior Art 1, first, the full text search index creation process 210 extracts words and appearance positions contained in the registration document 1 and the document 2 to create a full text search index 403. As a result, the full-text search index 403 is recorded as “construction: (documents 1 and 5) (documents 2 and 8)”. Here, “construction: (document 1, 5) (document 2, 8)” indicates that the character string “construct” appears at the fifth character of document 1 and at the eighth character of document 2. Yes.
[0012]
In the similar document search process, the seed document specified by the search condition is extracted, and the seed document feature vector 406 corresponding to the seed document is generated through the seed document feature vector generation process 220.
[0013]
Next, the number of appearances in each registered document is acquired by referring to the full-text search index 403 created in the document registration process for all words included in the seed document feature vector 406.
[0014]
Here, as shown in FIG. 4, the cosine of the two vectors X and Y is obtained by dividing the product-sum value of the corresponding components of the vectors (for example, x (i) and y (i)) by the magnitude of each vector. Pay attention to what you get by doing. That is, instead of calculating the inner product between specific vectors for each set of vectors, after calculating the inner product component (hereinafter referred to as elemental similarity) for each element of the vector, Calculate the sum of similarities. In FIG. 4, the i-th element of the vector X is represented as “x (i)”, and the magnitude of the vector X is represented as “| X |”.
[0015]
That is, in order to calculate the cosine of the seed document feature vector 406 and the feature vector of the registered document in FIG. 3, the number of occurrences in the seed document and each registered document is calculated for all the words in the seed document feature vector 406. The product-sum value can be calculated as the elemental similarity for each word in each registered document, and the sum of the elemental similarities for each word can be calculated for all registered documents.
[0016]
Hereinafter, the similarity calculation method will be specifically described with reference to FIG.
[0017]
When the seed document feature vector is represented as vector X, the feature vector of document 1 (hereinafter referred to as feature vector 1) is represented as vector Y, and the feature vector of document 2 (hereinafter referred to as feature vector 2) is represented as vector Z. The first component of the inner product of the vector, the feature vector 1 and the feature vector 2 can be calculated as “x (1) y (1)” and “x (1) z (1)”, respectively.
[0018]
Here, “x (1)” represents the number of occurrences of word 1 in the seed document, and “y (1)” and “z (1)” represent occurrences of word 1 in document 1 and document 2, respectively. It represents the number of times.
[0019]
That is, the number of appearances 600 of each word in each document can be obtained by counting the number of appearances of the word 1 in the seed document and referring to the full-text search index corresponding to the word 1.
[0020]
Similarly, the similarity of the registered document to the seed document can be calculated by referring to the full text search index corresponding to all the words in the seed document.
[0021]
The above is a specific description of the similarity calculation method in the prior art 1.
[0022]
Finally, the similarity 407 of each registered document is output.
[0023]
The above is the outline of the prior art 1.
[0024]
As described above, according to the prior art 1, by creating a full-text search word index for words contained in a registered document in advance, it is possible to generate a feature vector of the registered document at the time of document search. By calculating the cosine of the seed document feature vector corresponding to the seed document specified as the condition as the similarity, it is possible to search for documents having similar contents from the document database.
[0025]
However, since the prior art 1 uses the full-text search index for all words extracted from the seed document and uses it for similarity calculation, a large amount of processing is required when the number of words included in the seed document is large. Time is needed.
[0026]
For example, even if it is possible to refer to the full-text search index for one type of word in the seed document in 0.5 seconds, if 100 types of words are extracted from the seed document, processing time of 50 seconds may be required. become.
[0027]
On the other hand, if the word of the seed document feature vector is simply thinned out in order to reduce the processing time, the number of types of the word is reduced, and even a word having an important meaning in the seed document may be excluded. There is a risk that the search accuracy is extremely lowered.
[0028]
[Problems to be solved by the invention]
In order to solve such problems, the present invention aims to solve the following problems.
[0029]
That is, an object of the present invention is to create a feature vector of all registered documents when searching for similar documents without creating a feature vector of registered documents at the time of document registration in a document database, and calculate similarity using the latest word information In a similar document search method for performing
By using a minimum number of words that can ensure search accuracy, a high-speed similar document search method is realized.
[0030]
[Means for Solving the Problems]
The PAD diagram shown in FIG. 7 shows the processing procedure of the similar document search shown in the present invention for solving the above problem.
[0031]
The similar document search method according to the present invention includes a process type determination process 200 for determining whether a registration process or a research process, a full-text search index creation process 210 as a document registration process, and a seed document feature as a similar document search process. In the similar document search method including the vector generation process 220 and the similarity calculation process 221 using the full-text search index, the search is performed between the seed document feature vector generation process 220 and the similarity calculation process 221 using the full-text search index. And a word extraction process 701.
[0032]
That is, in the similar document search method according to the present invention, as the full-text search index creation processing 2100 at the time of document registration in the document database, (Step 1) a registered document reading step for reading a registration target document, (Step 2) reading the registered document Full-text search information file creation and registration step that extracts full-text search information from the text of the registration target document read in step and stores it in the full-text search information file, and seed document feature vector generation in similar document search processing As processing 220, (step 3) a seed document acquisition step for acquiring a seed document specified by the search condition, and (step 4) a word contained in the seed document by analyzing the seed document read in the seed document reading step. Extraction step of seed document analysis word extracting step (Step 5) Extraction in the seed document analysis step The number-of-appearance counts step in the seed document for counting the number of appearances of the generated word, and the search word extraction processing 701 (step 6) based on the number of appearances of each word counted in the above-mentioned seed document occurrence count counting step, A word importance calculating step for calculating the importance of the word; (step 7) selecting words in descending order of the weight of each word calculated in (step 6) above; When the similarity by element exceeds a predetermined threshold, a search word determination step for extracting the word as a search word and a similarity calculation process 221 using the full-text search index are (step 8) In the seed document feature vector generation process 220, similarity calculation is performed by executing the following (Step 9) to (Step 10) using the search word extracted from the seed document. (Step 9) A search word appearance number acquisition step for acquiring the number of appearances of the search word in each registered document by referring to the full text search information created in the full text search information file creation registration step. Step 10) Regarding the search word selected in the search word selection step
Using the number of appearances in the seed document acquired in the seed document occurrence count counting step and the number of search word appearances in each registered document acquired in the word appearance count acquisition step, the elemental similarity between the seed document and the registered document is calculated. And an element-by-element similarity calculation step for adding to the overall similarity of each registered document, and (step 11) a search result output step for outputting the similarity calculated at the element-by-element similarity calculation step.
[0033]
The principle of the present invention using the similar document search method will be described with reference to FIGS.
[0034]
In the similar document search method of the present invention, (Step 1) and (Step 2) are executed when a document is registered in the document database.
[0035]
Hereinafter, an outline of a processing procedure for registering a document will be described with reference to FIG.
[0036]
First, a document to be registered is read in (Step 1). In the example shown in FIG. 8, as documents to be registered, document 1 “provides equipment necessary for LAN construction and operation / maintenance.” And document 2 “partners with an SI vendor that handles information system construction and maintenance.” Is read as a registration target document.
[0037]
Next, in (Step 2), full-text search information is extracted from the text of the registration target document read in (Step 1) and stored in the full-text search information file.
[0038]
In the example shown in FIG. 8, (document 1, 1) is extracted as the full text search information corresponding to “L” included in the document 1 and stored in the full text search information file 803. Note that L (documents 1 and 1) indicates that the character “L” appears at the character position 1 of “document 1”.
[0039]
As the full-text search information used here, the word index method may be used as shown in the prior art 1 as long as the number of occurrences of an arbitrary word or character string in each registered document can be acquired. However, the n-gram index method disclosed in “JP 08-194718” may be used.
[0040]
The above is the outline of the processing procedure for document registration according to the present invention.
[0041]
Next, in the similar document search method shown in the present invention, (Step 3) to (Step 11) are executed when searching for a document.
[0042]
Hereinafter, an outline of a processing procedure for searching a document will be described with reference to FIG.
[0043]
First, the seed document 901 “Developing a solution with a LAN system construction know-how as a weapon” designated as a search condition in (Step 3) is read.
[0044]
In (Step 4), the seed document is analyzed, and words included in the seed document are extracted. The seed document analysis process used here may be a method of referring to a word dictionary and extracting words included in the word dictionary as disclosed in the prior art 1, or disclosed in “Japanese Patent Laid-Open No. 10-148721”. The word extraction method using statistical information in the document database may be used, the n-gram contained in the seed document may be mechanically extracted, or other word extraction techniques May be used.
[0045]
In the example shown in FIG. 9, a word string 903 (LAN, construction, know-how, weapon, solution, deployment,...) Is extracted as a result of this type of document analysis processing.
[0046]
Next, in (Step 5), the number of appearances in the seed document of the word extracted in (Step 4) is counted, and a pair 904 ([LAN, 4] [construction, 3] [ Knowhow, 2] [weapon, 1] [solution, 2] [deployment, 1].
[0047]
Here, [LAN, 3] indicates that the word “LAN” appears three times.
[0048]
Next, in (Step 6), importance is calculated for the pair 904 of words and appearances extracted in (Step 5), and a pair of words and importance is output. As a method of calculating the importance, for example, the number of appearances in the seed document may be used, or the ratio of the number of appearance documents of the word to the number of documents registered in the database (hereinafter referred to as the appearance ratio) is used. Also good. In the example shown in FIG. 9, the number of appearances in the seed document 901 is calculated as the importance of the word, and the word importance column 905 “[LAN, 4] [construction, 3] [solution, 2]. Here, [LAN, 4] indicates that the word “LAN” is included in the seed document as the importance “4”.
[0049]
Then, in (Step 7), elemental similarity to the seed document itself is calculated in descending order of importance of each word calculated in (Step 8), and the elemental similarity exceeds a predetermined threshold. In this case, the word is extracted as a search word. As a result, the search word [LAN, 4] [construction, 3] is extracted.
[0050]
Next, in (Step 8) to (Step 10), the number of appearances of each word in the seed document obtained in (Step 7) and the full-text search information file 803 created in (Step 2) are referred to. Thus, the similarity of each registered document to the seed document is calculated.
[0051]
In (step 11), the similarity calculation result 906 is output.
[0052]
The above is the outline of the processing procedure for the document search of the present invention.
[0053]
Hereinafter, the search word extraction processing procedure executed in the above-described (Step 7) will be described with reference to FIG.
[0054]
First, in (Step 7), the word importance sequence 905 output in (Step 6) is read, and words are selected in descending order of importance. In FIG. 10, [LAN, 4] is first extracted from the word importance column 905 “[LAN, 4], [construction, 3], [solution, 2]...”.
[0055]
Then, using the number of occurrences “4” in the seed document of the search word “LAN”, the similarity of each element of the search word for the similarity of the seed document to the seed document is calculated. That is, it is assumed that the same document as the seed document exists as a registered document (hereinafter referred to as a virtual registered document), and the similarity of the search word between the seed document feature vector and the feature vector of the virtual registered document by element The degree is calculated and the sum is calculated.
[0056]
In FIG. 10, the product of the number of appearances “4” in the seed document of the search word “LAN” and the number of appearances “4” in the virtual registration document is calculated, and the similarity by element “16” is obtained.
[0057]
As a result, the elemental similarity to the seed document itself by the search word “LAN” exceeds a predetermined threshold value (5 in the example shown in the figure), and is stored in the work area 170 as a search word. To do.
[0058]
Next, [construction, 3] having the next highest importance is selected after [LAN, 4], and the similarity of each element of the search word is calculated as the similarity of the seed document to the seed document. As a result, the element-by-element similarity is 9, which exceeds the predetermined threshold value 5, and is stored in the work area 170 as a search word.
[0059]
Then, [Solution, 2] having the next highest importance is selected after [Construction, 3], and the similarity of each element of the search word of the similarity of the seed document to the seed document is calculated. As a result, the similarity for each element is 4, which does not exceed the predetermined threshold value, and thus is terminated without being extracted as a search word.
[0060]
The above is the description of the search word extraction processing procedure.
[0061]
As described above, when registering a document in the document database, instead of creating a registered feature vector for the registered document, a full-text search index is created. Compared to the case where all the words are used for the search because the search words are extracted in order of the importance in the seed document and the extracted words are used as the search words until the similarity to the seed document itself converges. Thus, the similarity between the seed document and the registered document can be calculated at high speed without drastically reducing the search accuracy.
[0062]
DETAILED DESCRIPTION OF THE INVENTION
A first embodiment of the present invention will be described below with reference to FIG.
[0063]
A first example of a similar document search system to which the present invention is applied is a display 100, a keyboard 101, a central processing unit (CPU) 102, a magnetic disk device 103, a floppy disk drive (FDD) 104, a main memory 105, and connecting them. The bus 106 is configured.
[0064]
The magnetic disk device 103 is one of secondary storage devices and stores a full text search information file 180.
[0065]
Information stored in the floppy disk 107 is read into the main memory 105 or the magnetic disk device 103 via the FDD 104.
[0066]
The main memory 105 includes a system control program 110, a registration control program 111, a search control program 112, a registered document reading program 120, a full text search information file creation registration program 121, a search condition analysis program 130, a search word extraction program 131, A similarity calculation program 132 and a search result output program 133 are stored, and a work area 170 is secured.
[0067]
The search condition analysis program 130 includes a seed document acquisition program 140, a word extraction program 142, and a seed document occurrence count program 143.
[0068]
The search word extraction program 131 includes a word importance calculation program 150 and a search word extraction determination program 151.
[0069]
The similarity calculation program 132 includes a search word appearance count acquisition program 161 and an elemental similarity calculation program 162.
[0070]
The registration control program 111 and the search control program 112 are activated by the system control program 110 in response to an instruction from the keyboard 101 by the user, and control and search of the registered document reading program 120 and the full text search information file creation registration program 121, respectively. The condition analysis program 130, the search word extraction program 131, the similarity calculation program 132, and the search result output program 133 are controlled.
[0071]
In this embodiment, the registration control program 111 and the search control program 112 are activated by a command input from the keyboard 101. However, the registration control program 111 and the search control program 112 are activated by a command or event input via another input device. It does not matter if it is a thing.
[0072]
These programs are stored in a storage medium such as the magnetic disk device 103, floppy disk 107, MO, CD-ROM, DVD (not shown in FIG. 1), and read into the main memory 105 via the drive device. It can also be executed by the CPU 102.
[0073]
Hereinafter, a processing procedure of the similar document search system in the present embodiment will be described.
[0074]
First, the processing procedure of the system control program 110 will be described with reference to the PAD diagram of FIG.
[0075]
The system control program 110 first analyzes a command input from the keyboard 101 in step 1100.
[0076]
If it is analyzed in step 1101 that the result is a registration execution command, the registration control program 111 is activated in step 1102 to register the document.
[0077]
If it is determined in step 1101 that the command is a search execution command, the search control program 112 is activated in step 703 to search for similar documents.
[0078]
The processing procedure of the system control program 110 has been described above.
[0079]
Next, the processing procedure of the registration control program 111 activated by the system control program 110 in step 1102 shown in FIG. 11 will be described using the PAD diagram of FIG.
[0080]
In the registration control program 111, first, the registered document reading program 120 is started in step 1200, a document designated as a registration target (hereinafter referred to as a registration target document) is read and stored in the work area 170.
[0081]
Next, in step 1201, the full-text search information file creation / registration program 121 is started, full-text search information corresponding to the registered document stored in the work area 170 is created, and stored in the full-text search information file 180. .
[0082]
The processing procedure of the registration control program 111 has been described above.
[0083]
Next, the processing procedure of the search control program 112 activated by the system control program 110 in step 1103 shown in FIG. 11 will be described using the PAD diagram of FIG.
[0084]
In step 1300, the search control program 112 first starts the search condition analysis program 130 and extracts words from the seed document.
[0085]
Next, in step 1301, the search word extraction program 131 is started, the importance of the word extracted from the seed document in step 1300 is calculated, and a word having high importance is used as a search word based on a predetermined condition. Extract.
[0086]
In step 1302, the similarity calculation program 132 is activated, and the similarity of each registered document with respect to the seed document is calculated using the appearance information of the search word extracted from the seed document in step 1301.
[0087]
In step 1303, the search result output program 133 is activated, and the similarity calculation result calculated in step 1302 is output as a search result.
[0088]
Here, the output destination of the search result may be displayed on the display 100 or may be stored on the work area 170 or the magnetic disk 103. Further, when the similarity calculation result is output to the display 100, it may be output in descending order of similarity, or may be output in ascending or descending order of management numbers assigned to the documents.
[0089]
The processing procedure of the search control program 112 has been described above.
[0090]
Next, the processing procedure of the search condition analysis program 130 activated by the search control program 112 in step 1300 shown in FIG. 13 will be described using the PAD diagram of FIG.
[0091]
In step 1400, the search condition analysis program 130 first activates the seed document acquisition program 140, extracts the seed document specified by the search condition, and stores it in the work area 170.
[0092]
In step 1402, the word extraction program 142 is activated to extract words from the seed document stored in the work area 170.
[0093]
In step 1403, the seed document occurrence count program 143 is activated, and the number of appearances in the seed document is counted for the words extracted in step 1402 and stored in the work area 170.
[0094]
The processing procedure of the search condition analysis program 130 has been described above.
[0095]
Next, the processing procedure of the search word extraction program 131 activated by the search control program 112 in step 1301 shown in FIG. 13 will be described using the PAD diagram of FIG.
[0096]
First, in step 1500, the search word extraction program 131 starts up the word importance calculation program 151, calculates the importance of words stored in the work area 170 based on a predetermined calculation formula, and stores it in the work area 170. .
[0097]
Next, steps 1502 to 1505 are repeatedly executed for all the words stored in the work area 170 in step 1500 (step 1501).
[0098]
First, in step 1502, words stored in the work area 170 are acquired in descending order of importance.
[0099]
Next, in step 1503, the search word extraction determination program 151 is activated to calculate the elemental similarity of the seed document.
[0100]
In step 1504, it is determined whether the elemental similarity of the seed document exceeds a predetermined threshold value. If it exceeds, step 1505 is entered. If not, the iterative process is terminated.
[0101]
In step 1505, the word is stored in the work area 170 as a search word.
[0102]
The processing procedure of the search word extraction program 131 has been described above.
[0103]
In addition, the calculation method of the similarity of each word in step 1502 described above may be calculated using the number of appearances of each word in the seed document, as shown in the related art 1.
As will be described later, statistical information such as the number of appearing documents in the document database of the word may be used,
Furthermore, appearance position information in the document can be taken into consideration.
[0104]
Next, the processing procedure of the similarity calculation program 132 activated by the search control program 112 in step 1302 shown in FIG. 13 will be described using the PAD diagram of FIG.
[0105]
The similarity calculation program 132 repeats steps 1602 to 1603 for all search words stored in the work area 170 (step 1601).
[0106]
In step 1602, the search word appearance count acquisition program 161 is started, the full text search information file 180 corresponding to the search word is referred to, and the appearance count in each registered document is acquired and stored in the work area 170. To do.
[0107]
Next, in step 1603, the element-by-element similarity calculation program 162 is started, and the seed document is calculated by a predetermined calculation formula using the number of appearances of the search word stored in the work area 170 in the seed document and the number of appearances in the registered document. The similarity by element of the registered document with respect to is calculated and added to the similarity of the entire registered document.
[0108]
The processing procedure of the similarity calculation program 132 has been described above.
[0109]
The above is the first embodiment of the present invention.
[0110]
In this embodiment, a word is extracted from the seed document by the search condition analysis program 130, but an n-gram may be extracted instead of the word. In this case, the unit processed by the search word extraction program 131 is also an n-gram.
[0111]
In step 1504 of the search word extraction program 131, it is determined whether or not the elemental similarity of the seed document calculated in step 1503 exceeds a predetermined threshold.
It may be determined whether the sum of similarities exceeds a predetermined threshold instead of elemental similarity,
Furthermore, it may be determined whether the calculation ratio of the similarity with respect to the sum of the similarity by element in all words extracted from the seed document exceeds a predetermined threshold.
[0112]
In this embodiment, the number of occurrences of a word is directly used to calculate the similarity of each registered document with respect to the seed document. However, this may be normalized based on the length of the seed document or the document of the registered document. It will be clear.
[0113]
As described above, according to the first embodiment of the present invention, the number of search words used for similarity calculation is reduced with reference to the value of similarity by element with respect to the seed document. The processing can be terminated with a minimum necessary search for the similarity calculation result for.
[0114]
As a result, the number of search words can be reduced without extremely reducing the search accuracy, and a high-speed similar document search can be realized.
[0115]
In this embodiment, the registration target document or the seed document is a document, but it is obvious that it may be a sentence or a character string.
[0116]
Further, in the search word extraction program 131 in the first embodiment of the present invention described above, the search word is reduced using the similarity value by element of the seed document as a guideline. A number of search words may be extracted. As a method for setting the number of search words in this case, the number of search words may be determined using a test pattern prepared in advance so that the search is completed within a predetermined time.
[0117]
Next, a second embodiment of the present invention will be described with reference to FIG.
[0118]
The second embodiment of the similar document search system to which the present invention is applied uses statistical information of registered documents stored in a document database when calculating the importance of words extracted from seed documents. .
[0119]
According to this method, in the word importance calculation by the word importance calculation program 150 in the first embodiment, it is possible to use not only the appearance information in the seed document but also the appearance information in the entire document database, It is possible to adjust the importance of words that frequently appear in the document database, and the word importance can be calculated with higher accuracy than in the first embodiment.
[0120]
This embodiment has almost the same configuration as the first embodiment (FIG. 1), but the configuration of the word importance calculation program 150 is different, and a statistical information reference program 1700 is added as shown in FIG.
[0121]
Hereinafter, the processing procedure of the word importance degree calculation program 150a different from the first embodiment will be described with reference to FIG.
[0122]
First, in step 1800, the word importance calculation program 150a activates the statistical information reference program 1700 and refers to the full-text search information file 180, whereby the number of appearance documents in the document database of each word extracted from the seed document is determined. Obtained as statistical information of the word.
[0123]
Note that the number of appearance documents of the word is obtained from the full-text search information file 180, as shown in the full-text search information file 803 shown in FIG. This can be realized by counting the number of different document numbers of the word using the stored position.
[0124]
In step 1801, the importance level of each word extracted from the seed document is calculated using the number of occurrences of the word in the seed document and statistical information in the document database, and stored in the work area 170.
[0125]
The above is the processing procedure of the word importance calculation program 150a.
[0126]
As the word importance calculation formula in this embodiment, for example, a TF / IDF (Text Frequency, Inverted Documents Frequency) method may be used.
[0127]
The above is the second embodiment of the present invention.
[0128]
As described above, by using the similar document search system according to the second embodiment of the present invention, it is possible to calculate the word importance in consideration of words that frequently appear in the document database (hereinafter referred to as frequent words). It becomes like this. In other words, by setting the word importance of frequent words low and the word importance of rare words high, it is possible to preferentially select words that represent the characteristics of the seed document, and high-precision similar document search can be performed. Can be realized.
[0129]
Next, a third embodiment of the present invention will be described with reference to FIG.
[0130]
The third embodiment of the similar document search system to which the present invention is applied is similar to the second embodiment in that when the importance of the word extracted from the seed document is calculated, the registered documents stored in the document database are stored. The statistical information is used, but the statistical information file 1900 is used for obtaining the statistical information.
[0131]
According to this method, it is possible to obtain statistical information to be referred to at the time of calculating word importance in the second embodiment at high speed.
[0132]
This embodiment has almost the same configuration as the second embodiment (FIG. 17), but the configuration of the registration control program 111 is different, and a statistical information file creation / registration program 1900 is added as shown in FIG. In addition, a statistical information file 1910 is stored in the magnetic disk device 103. In step 1800 of the word importance calculation program 150a, instead of referring to the full-text search information file 180 when obtaining statistical information in the document database of each word extracted from the seed document, the statistical information shown in FIG. The file 1910 is referred to.
[0133]
Hereinafter, a processing procedure of the registration control program 111a different from the second embodiment will be described with reference to FIG.
[0134]
In the registration control program 111a, first, the registered document reading program 120 is started in step 1200, and the document designated as the registration target is read and stored in the work area 170.
[0135]
Next, in step 1201, the full-text search information file creation / registration program 121 is started, full-text search information corresponding to the registered document stored in the work area 170 is created, and stored in the full-text search information file 180. .
[0136]
Next, in step 2000, the statistical information file creation / registration program 1900 is activated to create statistical information corresponding to the registered document stored in the work area 170 and store it in the statistical information file 1910.
[0137]
The processing procedure of the registration control program 111 has been described above.
[0138]
FIG. 21 shows an example of the statistical information file 1910 created by the statistical information file creation / registration program 1900.
[0139]
In the statistical information file 1910 shown in this figure, a management number 2100, a word 2101 and the number of appearing documents 2102 are stored.
[0140]
In the example shown in the drawing, the word “LA” is stored in the area of the management number “0”, and the number of appearance documents of the word is stored as “1”.
[0141]
In the example shown in FIG. 21, the statistical information file 1900 is stored in a table format. However, any format may be used as long as the word and the number of appearing documents can be acquired. For example, it may be stored in a trie format, or may be stored in the top area of the full text search information file 180.
[0142]
The above is the third embodiment of the present invention.
[0143]
As described above, according to the third embodiment of the present invention, the statistical information of each word extracted from the seed document is obtained by referring to the statistical information file created in advance during the document registration process. It is no longer necessary to count the number of different appearance document numbers by referring to the search information, and statistical information can be acquired at high speed. This makes it possible to realize a similar document search that is faster than in the second embodiment.
[0144]
Next, a fourth embodiment of the present invention will be described with reference to FIG.
[0145]
In a fourth embodiment of the similar document search system to which the present invention is applied, the statistical information of each word extracted from the seed document is approximated and used.
[0146]
According to this method, the capacity of the statistical information stored in the statistical information file 1910 in the third embodiment can be reduced without extremely reducing the accuracy of the statistical information.
[0147]
This embodiment has almost the same configuration as that of the third embodiment (FIG. 19), but the configuration of the statistical information reference program 1700 is different and an approximate statistical information calculation program 2200 is added.
[0148]
Hereinafter, the processing procedure of the statistical information reference program 1700b different from the third embodiment will be described with reference to FIG.
[0149]
The statistical information reference program 1700b repeatedly executes Steps 2301 to 2304 for all words extracted from the seed document (Step 2300).
[0150]
In step 2301, the statistical information file 1910 is referenced to check whether statistical information corresponding to the word is stored.
[0151]
If the word is stored in the statistical information file 1910, step 2303 is executed, and if it is not stored, step 2304 is executed (step 2302).
[0152]
In step 2303, the statistical information file 1910 is referred to, and the statistical information of the word is acquired.
[0153]
In step 2304, the approximate statistical information calculation program 2200 is activated to calculate approximate statistical information of the word.
[0154]
The above is the processing procedure of the statistical information reference program 1700b.
[0155]
Next, the processing procedure of the approximate statistical information calculation program 2200 will be specifically described with reference to FIG.
[0156]
In the example shown in this figure, first, in step 2301, the statistical information file 1910 is referred to for the word 2400 “LAN” for which statistical information is to be acquired.
[0157]
Here, since “LAN” is not stored in the statistical information file 1910, step 2304 is executed.
[0158]
In step 2304, statistical information of “LA” and “AN”, which are constituent elements of the word 2400 “LAN”, is acquired, and a smaller value of these appearing document numbers is set as the statistical information of “LAN”.
[0159]
In the example shown in the figure, the number of appearing documents “807” stored in the statistical information 2401 of “LA” is compared with the number of appearing documents “1512” stored in the statistical information 2402 of “AN”. As a result, the number of appearance documents “807” of “LA” having a small value is stored as statistical information 2403 of “LAN” (2410).
[0160]
This utilizes the property that if the number of documents “LA” and “AN” in the word “LAN” are different, the number of documents in “LAN” cannot be greater than each component. is there. That is, as the number of appearing documents of the word “LAN”, the number of appearing documents of the “LAN” itself should be used, but the appearing documents of “LA” or “AN” which are the constituent elements of the word “LAN”. It refers to the appearance document number that approximates a small value.
[0161]
The specific processing procedure of the approximate statistical information calculation program 2200 has been described above.
[0162]
The above is the fourth embodiment of the present invention.
[0163]
As described above, by using the similar document search system in the fourth embodiment of the present invention, it is not necessary to store the number of appearance documents of all words in the statistical information file. , You will be able to reduce the capacity of the statistics file.
[0164]
As described above, in the similar document search system in the first to fourth embodiments of the present invention, the similarity of the seed document is calculated, and the number of search words is adjusted based on this. Thus, a similar document search can be realized at high speed while ensuring the search accuracy.
[0165]
Next, a fifth embodiment of the present invention will be described with reference to FIG.
[0166]
The fifth embodiment of the similar document search system to which the present invention is applied outputs a search result within a predetermined search time.
[0167]
According to this method, since the user can acquire the search result within a predetermined search time, it is possible to determine without stress whether the seed document specified by the search condition matches the search purpose.
[0168]
This embodiment has almost the same configuration as that of the first embodiment (FIG. 1), but the configuration of the similarity calculation program 132 is different and a search processing time measurement program 2500 is added.
[0169]
Hereinafter, the processing procedure of the similarity calculation program 132b different from the first embodiment will be described with reference to the PAD diagram of FIG.
[0170]
In step 2600, the similarity calculation program 132b activates the search processing time measurement program 2500 and starts measuring the search processing time.
[0171]
Next, if the search processing time is less than or equal to a predetermined value (hereinafter referred to as search limit time) for all the search words stored in the work area 170, steps 1602, 1603 and 2602 are repeatedly executed ( Step 2601).
[0172]
In step 1602, the search word appearance count acquisition program 161 is started, the full text search information file 180 corresponding to the search word is referred to, and the appearance count in each registered document is acquired and stored in the work area 170. To do.
[0173]
Next, in step 1603, the element-by-element similarity calculation program 162 is started, and the seed document is calculated by a predetermined calculation formula using the number of appearances of the search word stored in the work area 170 in the seed document and the number of appearances in the registered document. The similarity by element of the registered document with respect to is calculated and added to the similarity of the entire registered document.
[0174]
In step 2602, the search processing time measurement program 2500 is activated, the elapsed time of the search processing time is measured, and the search processing time is calculated.
[0175]
The above is the processing procedure of the similarity calculation program 132b.
[0176]
The above is the fifth embodiment of the present invention.
[0177]
Note that the search time limit in step 2601 of the present embodiment may be specified as a search condition when executing a search, or may be set in advance as a system setting value.
[0178]
In this embodiment, the search time limit is set. However, depending on the set value, only a small number of search words may be used. Therefore, the minimum number of search words for maintaining search accuracy is considered. May be set. In this case, even if the search processing time exceeds the search limit time, the similar search is repeated up to the specified minimum number of search words.
[0179]
Furthermore, in this embodiment, the time required for the similarity calculation processing is measured using the search processing time measurement program 2500, but the search processing itself may be measured. In this case, instead of starting the search time measurement at step 2600 shown in FIG. 26, the search processing time measurement program 2500 is started before the search condition analysis program 130 is started by the search control program 112. Measurement of the processing time may be started.
[0180]
As described above, in the similar document search system according to the fifth embodiment of the present invention, the number of search words is adjusted based on the time required for the search, so that the search result can be acquired in a predetermined processing time. become.
[0181]
As a result, the user can predict the search end time.
[0182]
The similar document search system that ends the search based on the similarity of the seed document described in the first to fourth embodiments and the search ends as described in the search time described in the fifth embodiment. It is also possible to use a similar document search system by switching between search execution or system definition.
[0183]
Next, a sixth embodiment of the present invention will be described with reference to FIG.
[0184]
In the sixth embodiment of the similar document search system to which the present invention is applied, the search time is estimated from the search word used for the search from the word extracted from the seed document. We ask for confirmation.
[0185]
According to this method, when a long time is required for the search in the search word extraction condition in the similar document search system described in the first to fourth embodiments, the search can be canceled in advance. The user will not be inadvertently waiting.
[0186]
This embodiment has almost the same configuration as the first embodiment (FIG. 1), but the configuration of the search word extraction program 131 is different, and a search time estimation confirmation program 2700 is added as shown in FIG.
[0187]
Hereinafter, the processing procedure of the search word extraction program 131b different from the first embodiment will be described with reference to the PAD diagram of FIG.
[0188]
In the search word extraction program 131, first, in step 1500, the word importance calculation program 151 is activated, calculates the importance of words stored in the work area 170 based on a predetermined calculation formula, and stores it in the work area 170. .
[0189]
Next, steps 1502 to 1505 are repeatedly executed for all the words stored in the work area 170 in step 1500 (step 1501).
[0190]
First, in step 1502, words stored in the work area 170 are acquired in descending order of importance.
[0191]
Next, in step 1503, the search word extraction determination program 151 is activated to calculate the elemental similarity of the seed document.
[0192]
In step 1504, it is determined whether the elemental similarity of the seed document exceeds a predetermined threshold value. If it exceeds, step 1505 is entered. If not, the iterative process is terminated.
[0193]
In step 1505, the word is stored in the work area 170 as a search word.
[0194]
Next, when the search time is estimated from the search word stored in the work area 170 in step 2800, and the estimated search time (hereinafter referred to as the estimated search time) exceeds a predetermined value (designated search time). Displays a message confirming the continuation of the search and receives confirmation from the user. As this confirmation message, for example, as shown in FIG. 6, a message 2900 having a continuation button 2901 and a cancel button 2901 may be displayed.
[0195]
The above is the processing procedure of the search word extraction program 131b.
[0196]
The specified search time in step 2800 may be specified as a search condition, specified in advance as a system definition, or automatically set from the results of several test patterns. It may be a thing.
[0197]
In addition, as a method for estimating the search time in the above step 2800, it may be estimated from the number of appearance documents of the search word, or estimated from the size of the full-text search information file 180 corresponding to the search word. It is good. Alternatively, an average time required for one search word may be measured using several test patterns, and the search time may be estimated using the average time.
[0198]
As described above, in the similar document search system shown in the present embodiment, the search time is estimated from the extracted search word, and if the estimated search time exceeds the time specified in advance, the search word is extracted. Since the conditions can be adjusted, the user will not be inadvertently waited.
[0199]
【The invention's effect】
As described above, in the present invention, the number of search words is set based on the similarity of the seed document, so the number of search words used for calculating the similarity can be reduced. Thereby, a high-speed similar document search that can ensure the search accuracy can be realized.
[Brief description of the drawings]
FIG. 1 is a diagram showing an overall configuration of a similar document search system in a first embodiment of the present invention.
FIG. 2 is a PAD for explaining a processing procedure of prior art 1;
FIG. 3 is a diagram for explaining an overview of prior art 1;
FIG. 4 is a diagram for explaining the concept of the similarity calculation method of the prior art 1;
FIG. 5 is a diagram for explaining the concept of a similarity calculation method of Conventional Technique 1;
FIG. 6 is an example of a confirmation message by a search time estimation confirmation program 2700 in the sixth embodiment of the present invention.
FIG. 7 is a PAD explaining the processing procedure of the present invention.
FIG. 8 is a diagram illustrating an overview of registration processing according to the present invention.
FIG. 9 is a diagram illustrating an outline of search processing according to the present invention.
FIG. 10 is a diagram illustrating an outline of a search word extraction process according to the present invention.
FIG. 11 is a diagram illustrating a processing procedure of the system control program 110 in the first embodiment of the present invention.
FIG. 12 is a diagram illustrating a processing procedure of a registration control program 111 in the first embodiment of the present invention.
FIG. 13 is a PAD for explaining the processing procedure of the search control program 112 in the first embodiment of the present invention.
FIG. 14 is a PAD explaining the processing procedure of the search condition analysis program 130 in the first embodiment of the present invention.
FIG. 15 is a PAD explaining the processing procedure of the search word extraction program 131 in the first embodiment of the present invention.
FIG. 16 is a PAD explaining the processing procedure of the similarity calculation program 132 in the first embodiment of the present invention.
FIG. 17 is a diagram showing a configuration of a word importance calculation program 150a in the second embodiment of the present invention.
FIG. 18 is a PAD diagram for explaining the processing procedure of the word importance calculation program 150a in the third embodiment of the present invention.
FIG. 19 is a block diagram of a registration control program 111a in the third embodiment of the present invention.
FIG. 20 is a PAD showing a processing procedure of a registration control program 111a in the third embodiment of the present invention.
FIG. 21 shows an example of a statistical information file 1910 in the third embodiment of the present invention.
FIG. 22 is a diagram showing a configuration of a statistical information reference program 1700b according to the fourth embodiment of the present invention.
FIG. 23 is a PAD diagram for explaining the processing procedure of a statistical information reference program 1700b according to the fourth embodiment of the present invention.
FIG. 24 is a diagram for explaining a method of calculating approximate statistical information in the fourth embodiment of the present invention.
FIG. 25 is a diagram showing a configuration of a similarity calculation program 132b in the fifth embodiment of the present invention.
FIG. 26 is a PAD explaining the processing procedure of the similarity calculation program 132b in the fifth embodiment of the present invention.
FIG. 27 is a diagram showing a configuration of a search word extraction program 131b in a sixth embodiment of the present invention.
FIG. 28 is a PAD illustrating the processing procedure of the search word extraction program 131b in the sixth embodiment of the present invention.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 100 ... Display, 101 ... Keyboard, 102 ... Central processing unit (CPU), 103 ... Magnetic disk apparatus, 104 ... Floppy disk drive (FDD), 105 ... Main memory, 106 ... Bus, 107 ... Floppy disk, 110 ... System Control program 111 ... Registration control program 112 ... Search control program 120 ... Registered document reading program 121 ... Full text search information file creation / registration program 130 ... Search condition analysis program 131 ... Search word extraction program 132 ... Similarity calculation program, 133 ... Search result output program, 140 ... Seed document acquisition program, 142 ... Word extraction program, 143 ... Seed document occurrence count counting program, 150 ... Word importance calculation program, 151 ... Search word extraction determination Professional Ram, 161 ... search word occurrence count acquisition program, 162 ... elemental similarity calculation program, 170 ... work area, 180 ... full-text search information file.

Claims (7)

A similar document retrieval method in the similar document retrieval apparatus for given species document from the registration documents such as text or character string which is registered in the document database to find documents similar,
The similar document search device includes:
A full-text search information creation step of creating a full-text search index for a document to be registered and storing it as full-text search information;
A string extraction step of the specified species documents predetermined character string and the character string is extracted and number of occurrences appearing in the seed document,
The severity of the character string extracted on the basis of the number of occurrences in the seed document of the string, the selecting the character string in the descending order of importance of the character string as a processing target string, continuation determination step similarity A similarity calculation repetition step that repeats the calculation step;
When the importance of the processing target character string is smaller than a predetermined threshold, the continuation determination step of ending the repetition processing of the similarity calculation repetition step;
With reference to the full-text search information, the processing to calculate the number of occurrences in the registration document the subject string, appearance of the appearance frequency in the registration document of the processing target string in the seed document based on the number of times, and the similarity calculation step of calculating the similarity is added to the total similarity of each registered document in the processed character string of each registered document for the seed document,
Similar document search method characterized by executing and a search result output step of outputting the total similarity to the seed document of each registered document calculated by the similarity calculation step. The similar document search method according to claim 1,
The continuation determining step ends the repetition process of the similarity calculation repetition step when the increase rate of the total similarity of each registered document is smaller than a predetermined threshold . The similar document search method according to claim 1 or 2,
The continuation determining step ends the repetitive processing of the similarity calculation repetitive step when the elapsed time from the start of similar document retrieval exceeds a predetermined time . In a similar document search apparatus for searching for a document whose content is similar to a specified seed document from a registered document such as a sentence or a character string registered in a document database,
A full-text search information creation means for creating a full-text search index for a document to be registered and storing the full-text search information;
And character string extraction means from specified species document is a predetermined character string and the character string to extract the number of occurrences appearing in the seed document,
The severity of the character string extracted on the basis of the number of occurrences in the seed document of the string, to select the character string in the descending order of importance of the character string as a processing target string, and processing continuation determination means Similarity calculation repetition means for repeating the processing of the similarity calculation means;
The continuation determination means for ending the repetition processing of the similarity calculation repetition means when the importance of the processing target character string is smaller than a predetermined threshold;
With reference to the full-text search information, it calculates the number of occurrences in the registration document of the processed character string, and the number of occurrences of in the registration document of the processed character string, in the seed document based on the number of occurrences, and the similarity calculation means for calculating the similarity in the processing object character string of each registered document for the species document is added to the total similarity of each registered document,
A search result output means for outputting a total similarity to the seed document of each registered document calculated by the similarity calculation means,
A similar document search device characterized by comprising: The similar document search device according to claim 4 ,
The similar document search apparatus , wherein the continuation determination unit ends the repetition process of the similarity calculation repetition unit when the increase rate of the total similarity of each registered document is smaller than a predetermined threshold . The similar document search device according to claim 4 or 5 ,
The similar document search device, wherein the continuation determination step ends the repetition process of the similarity calculation repetition step when an elapsed time from the start of the similar document search exceeds a predetermined time . Storage medium storing a program for implementing the steps of the similar document search method in a computer according to any one of claims 1-3.

Images