JP2000207404A - Document search method and apparatus, and recording medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] A document search method and apparatus capable of effectively reducing the number of N-grams used for searching for a similar document similar to an arbitrary document and performing high-speed similar document search processing, and a document search method therefor. Provided is a recording medium on which a program for executing a search method is recorded. SOLUTION: A word included in a search target document is extracted (S2 to S6), and an N-gram of the word is generated (S7).
To S9), a transposed vector table indicating the relationship between the search target document and the included N-gram is prepared (S10, S11). A word included in an arbitrary search key document is extracted, and an N-gram of the word is generated. A similar document similar to the search key document is searched based on the transposed vector table and the N-gram in the search key document.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a method and an apparatus for retrieving a similar document similar to an arbitrary document from a plurality of retrieval target documents, and a recording medium on which a program for executing the retrieval method is recorded.

[0002]

2. Description of the Related Art The amount of electronic documents created by a word processor or the like is increasing, and a search target document for searching for a similar document similar to a question document specified by a user. Is also enormous, and it is difficult to speed up the process of searching for similar documents. As a method of searching for a similar document to such a question document from a search target document, the following three methods, a method disclosed in JP-A-2-2458 (hereinafter referred to as Conventional Example 1), and a method described in A method disclosed in Japanese Patent Application Laid-Open No. 110948 (hereinafter referred to as Conventional Example 2) and a method disclosed in Japanese Patent Application Laid-Open No. Hei 9-153051 (hereinafter referred to as Conventional Example 3) are known.

[0003] In Conventional Example 1, keywords are extracted from a question document and a search target document, the extracted keywords are compared to determine similarity, and a document having a high similarity is output as a similar document. In the first conventional example, a word that cannot be searched is generated depending on a keyword extraction method. Also, search omission occurs. For example, if the keywords “development work” are extracted in the search target document 1 and “development” is extracted in the search target document 2 and the keyword “development” is extracted in the question document, the search target document 1 is searched. Will not be.

In Conventional Example 2, an N-gram reference sequence is generated for a plurality of search target documents, each N-gram is weighted, commonality among the plurality of reference sequences is removed, and a query document is generated. N
-N-gram of the query document and N-gram of the reference sequence of the search target document are weighted to each of the decomposed N-grams.
The gram is compared with the gram, a score representing the similarity between the question document and the search target document is obtained, and a similar document is searched according to the score. In the second conventional example, the commonality of the search target documents is obtained and used for determining the similarity. Therefore, when a change such as addition or deletion occurs in the search target document, the commonality must be obtained again. However, it is not possible to flexibly respond to changes in the search target document. Further, when the set of search target documents changes, their commonality also changes, so that even for the same question document, the score indicating the similarity changes, and the similarity evaluation judgment may be reversed. . In addition, if the search target documents are biased, removing their commonality removes information that is effective in identifying the field, and it is not possible to determine the correct similarity. Further, all N-grams included in the document
Since the similarity is determined for the Japanese language, it takes an enormous amount of time to calculate the similarity for Japanese characters. In the case of Japanese, there are 1024 kinds of JIS first-level kanji alone, and for example, the number of kinds of 2-gram reaches 1048576 kinds of the square. If you add katakana and hiragana to this, you get 2
The number of types of grams is enormous, and it takes a long time to calculate the similarity.

In prior art 3, a predetermined partial character string and its appearance frequency are obtained from a search target document, the importance of the partial character string is obtained based on the appearance frequency, and a predetermined partial character string and its occurrence frequency are obtained from a question document. A similarity is determined based on the frequency of occurrence and the importance, and a similar document is searched according to the similarity. In the third conventional example, since all partial character strings are extracted at once, it takes a long time to calculate the importance. Even if the importance is calculated based on the frequency of appearance, for example, in consideration of a number or the like, the frequency of appearance may not be considered to be directly related to the importance, and an accurate search cannot be performed.

The present invention has been made in view of such circumstances, and can effectively reduce the number of N-grams used for retrieval.
It is an object of the present invention to provide a document search method and apparatus capable of performing similar document search processing at high speed, and a recording medium on which a program for executing the search method is recorded.

[0007]

According to a first aspect of the present invention, there is provided a document search method for searching for a similar document similar to an arbitrary document from a plurality of documents by extracting words included in the plurality of documents. And N of the extracted word
-Generating a gram, extracting a word included in the arbitrary document, and N-gram of the extracted word.
Generating the N-gram generated for the arbitrary document and the N-gram generated for the plurality of documents.
And searching for a similar document based on the comparison result.

[0008] The document search method according to claim 2 is based on claim 1.
Is characterized in that when extracting a word, the word is extracted using the face information, and unnecessary words are removed from the extracted words.

According to a third aspect of the present invention, there is provided a document search method.
Or in 2, the unnecessary N out of the generated N-grams
-It is characterized in that gram is removed.

According to a fourth aspect of the present invention, there is provided a document search method according to the first aspect.
Calculating a similarity between the arbitrary document and each of the plurality of documents based on the N-gram generated for the arbitrary document and the N-gram generated for the plurality of documents; A similar document is searched in response thereto, a similar document candidate is selected, and the similarity is calculated for the selected similar document candidate.

According to a fifth aspect of the present invention, there is provided a document search method according to the first aspect.
In the above, the existence information of the N-gram generated for the plurality of documents is stored in the storage unit in the form of a vector, and each row of the vector is divided into blocks using a plurality of elements as units, and unnecessary blocks are removed. The method is characterized in that the vector is compressed.

According to a sixth aspect of the present invention, there is provided a document search method.
Wherein the existence information of N-grams generated for the plurality of documents is stored in the form of a vector separately in a plurality of storage units having different reading speeds.

According to a seventh aspect of the present invention, in the document search apparatus for searching a plurality of documents for a similar document similar to an arbitrary document, a first word extracting unit for extracting a word included in the plurality of documents. First N-gram generating means for generating an N-gram of the extracted word, second word extracting means for extracting a word contained in the arbitrary document, and second N-gram generating an N-gram of the extracted word -Gram generation means, and similar document search means for comparing the N-gram generated for the arbitrary document with the N-gram generated for the plurality of documents, and searching for a similar document based on the comparison result. It is characterized by the following.

[0014] The document retrieval apparatus according to claim 8 is the claim 7.
, Wherein the first word extracting means and the second word extracting means have means for extracting a word using document face information, and means for removing unnecessary words from the extracted words. I do.

According to a ninth aspect of the present invention, there is provided a document search apparatus according to the seventh aspect.
Or 8, the first N-gram generating means and the second
The N-gram generation means is characterized by having means for removing unnecessary N-grams from the generated N-grams.

According to a tenth aspect of the present invention, there is provided a document search apparatus according to the seventh aspect.
In the similar document search means, based on the N-gram generated for the arbitrary document and the N-gram generated for the plurality of documents, means for selecting a similar document candidate from the plurality of documents, It is characterized by comprising means for calculating the degree of similarity between the arbitrary document and each of the selected similar document candidates, and means for searching for a similar document according to the degree of similarity.

[0017] The document retrieval apparatus according to claim 11 is the same as claim 7.
, Further comprising storage means for storing the presence information of the N-gram generated for the plurality of documents in the form of a vector, dividing each row of the vector into a plurality of elements as units, and removing unnecessary blocks. The vector is compressed and stored in the storage unit.

According to a twelfth aspect of the present invention, there is provided a document search apparatus according to the seventh aspect.
A first storage unit that stores a part of the N-gram existence information generated for the plurality of documents; and a second storage unit that stores a remaining part of the N-gram existence information generated for the plurality of documents. The storage device further includes a second storage device having a different reading speed from the first storage device.

A recording medium according to claim 13 is a computer-readable recording medium storing a program for retrieving a similar document similar to an arbitrary document from the plurality of documents. Program code means for causing the computer to extract words included in the program, program code means for causing the computer to generate N-grams of the extracted words, and extract words included in the arbitrary document Program code means for causing the computer to do the above, program code means for causing the computer to generate an N-gram of the extracted word, N-gram generated for the arbitrary document and generated for the plurality of documents. N-
and program code means for causing the computer to compare the gram with the gram and search for a similar document based on the comparison result.

A recording medium according to claim 14, wherein the program code means for causing the computer to extract a word is a program code for causing the computer to extract a word using face information. Means and program code means for causing the computer to remove unnecessary words from the extracted words.

According to a fifteenth aspect of the present invention, in the recording medium according to the thirteenth or fourteenth aspect, the program code means for causing the computer to generate an N-gram of the extracted word is:
It is characterized by including program code means for causing the computer to remove unnecessary N-grams from the generated N-grams.

According to a sixteenth aspect of the present invention, in the storage medium according to the thirteenth aspect, the program code means for causing the computer to search for a similar document includes the N-gram generated for the arbitrary document and the plurality of documents. Program code means for causing the computer to select a similar document candidate from the plurality of documents based on the generated N-gram, and a similarity between the arbitrary document and the selected similar document candidate. It is characterized by including program code means for causing the computer to calculate and program code means for causing the computer to search for a similar document according to the degree of similarity.

The recording medium according to claim 17 is the recording medium according to claim 13, wherein the computer is configured to cause the computer to store the existence information of the N-gram generated for the plurality of documents in the form of a vector in the storage unit. And a program code unit for causing the computer to divide each row of the vector into blocks in units of a plurality of elements, remove unnecessary blocks, and compress the vector.

In the recording medium according to the present invention, the N-gram existence information generated for the plurality of documents is stored in a form of a vector separately in a plurality of storage units having different reading speeds. The program further comprises program code means for causing the computer to execute the following.

According to the first aspect of the present invention, a word is extracted from a document to be searched, an N-gram of the word is generated, and a word is extracted from a question document, and the N-gram of the word is extracted. Generate Then, N in the search target document
The gram and the N-gram in the question document are compared to determine the similarity between the search target document and the question document, and a similar document is searched according to the similarity.

As described above, after the word extraction, N-
Since gram generation is performed, the time required for N-gram generation can be reduced as compared with the method of generating all N-grams. Further, since words (particles and the like) that are not important in the search processing are removed by word extraction, the number of N-grams that need to be considered at the time of search can be reduced, and the document search processing can be speeded up.

According to the second aspect of the present invention, a word is extracted from character information. Therefore, word extraction can be performed in a very short time. After removing unnecessary words from the extracted words, N-gram generation is performed. Therefore, the number of N-grams for obtaining the similarity can be reduced, and the search processing can be speeded up.

According to the third aspect of the present invention, unnecessary N-grams in the generated N-grams are removed by referring to, for example, an N-gram dictionary. Therefore, the similarity N
-The number of gram can be significantly reduced, and the search process can be speeded up.

According to the fourth aspect of the present invention, similar document candidates are selected by simple arithmetic processing, and the similarity is obtained only for the selected similar document candidates. Therefore, as compared with the method of calculating the similarity for all the search target documents registered in the transposed vector table, the similarity can be calculated by a smaller number of calculation processes, and the search process can be speeded up.

According to the fifth aspect of the present invention, each row of the vector indicating the information of the N-gram in the search target document is divided into a plurality of elements, and blocks having no meaning in the search processing are excluded. Compress the vector. Therefore, the number of times of reading the vector can be reduced, and the search time can be reduced.

In the sixth invention according to claims 6, 12 and 18, frequently used vectors are stored in a high speed readable main memory. Therefore, the search processing can be speeded up.

[0032]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be specifically described below with reference to the drawings showing the embodiments.

FIG. 1 is a conceptual diagram showing a system configuration for implementing the document search method of the present invention. A document registration device 1 that registers a search target document in an index and a similar document search device 2 that searches the index for a similar document to a search key document (question document) specified or input by a user so that a similar document search can be performed. Provided.

FIG. 2 is a functional block diagram of the document registration device 1. The document registration device 1 includes a document selection device 11 for selecting a search target document from a document database and a keyword extraction device for extracting a word (keyword) from the selected document.
12 and N-gr which generates N-gram (N character chain) of words
An am generator 13 and an index generator 14 for generating an index (transposed vector table) are provided.

FIG. 3 is a functional block diagram of the keyword extracting device 12. The keyword extraction device 12 includes a character analysis device 121 that extracts words by character analysis, and an unnecessary character removal device that removes characters that become noise in similar document search.
122, an unnecessary character string removing device 123 that removes unnecessary character strings by referring to the unnecessary word dictionary, a synonym expanding device 124 that adds synonyms by referring to the synonym dictionary, and an appearance frequency of the extracted words. And a frequency totaling device 125 for totalizing.

FIG. 4 is a functional block diagram of the N-gram generation device 13. The N-gram generation device 13 includes an N-gram decomposition device 131 that decomposes a character string (word) into N-grams,
N-gram extracting registered N-gram by referring to dictionary
It has a gram dictionary reference device 132 and an unnecessary N-gram removal device 133 for removing unnecessary N-grams.

FIG. 5 is a functional block diagram of the index generation device 14. The index generation device 14 includes a document feature vector generation device 141 that generates a document feature vector according to the generated N-gram, and a transposed vector table that generates a transposed vector obtained by transposing the document feature vector and registers the transposed vector in a transposed vector table. Registration device 142.

Next, the document registration process will be described. FIG. 6 is a flowchart showing the processing procedure. A document (a character string having some meaning such as a keyword, an input sentence, a whole sentence, or a part thereof) is selected from the document database by the document selecting device 11 and sent to the keyword extracting device 12 (S1).

From the input document, a character surface analysis device 12
In step 1, a character string in which two or more characters having the same character type (hiragana, katakana, kanji, kanji, alphabet, symbol, etc.) are extracted as a word is extracted (S2). Characters (kanji numerals, Arabic numerals, etc.) that cause an erroneous search in similar document search are removed from the character string by the unnecessary character removal device 122 (S3). Examples of unnecessary characters to be removed include Chinese numerals (1, 2, 3),
There are unit symbols (yen) and dates (year, month, day). The unnecessary character string removing device 123 determines whether or not the character string is unnecessary and removes the unnecessary character string (S4). Determines whether a character string is registered in the unnecessary word dictionary. If registered, removes the character string as an unnecessary character string. And leave it. Examples of unnecessary character strings to be removed include an amount (100 million yen) and a date (November 1995). Further, the synonym expansion device 124 searches the synonym dictionary and adds registered synonyms to the extracted words (S5). The frequency counting device 125 counts the appearance frequencies of the character strings (words) extracted as described above, and arranges the extracted character strings in order of appearance frequency to create a character string table (S6). The created character string table is sent to the N-gram generation device 13.

The N-gram decomposing device 131 decomposes the character strings included in the character string table into N-grams (S7). N-gram
The dictionary reference unit 132 selects N-grams from the decomposed N-grams.
-Extract what is registered in the gram dictionary (S8).
The unnecessary N-gram removing device 13 is executed by the following processing.
At 3, the N-grams determined to be unnecessary are removed (S
9). N-grams extracted in S8 are arranged in order of appearance frequency,
An N-gram list is created, and the importance of the N-grams included in the N-gram list is calculated based on the appearance frequency and the like. N-gr for which the calculated importance is lower than the predetermined value
am is determined to be unnecessary N-gram and is deleted from the N-gram list. The N-gram generated in this way is sent to the index generation device 14. Since the number of N-grams is reduced in this way, the search speed of similar documents can be improved.

The document feature vector generation device 141 sets the bit corresponding to the registration number of the generated N-gram to "1" to generate a document feature vector (S10). In FIG.
4 shows an example of a document feature vector. In the example shown in FIG.
It indicates whether or not each of the types of search target documents 1 to 4 includes four types of N-gram 1 to N-gram 4. For example, in document 2, N-gram 2 and N-gram
4 and not including N-gram1 and N-gram3.

The transposed vector table registration unit 142 transposes the document feature vector to generate a transposed vector, and registers the transposed vector in the transposed vector table (S11). FIG.
FIG. 7 shows a transposed vector table corresponding to the document feature vector in FIG. For example, it indicates that N-gram2 is included in document 2 and document 4. In the present invention, a bit “1” is assigned only when an N-gram is included, and a bit “0” is assigned otherwise, so that a transposed vector table can be created very easily.

Then, it is determined whether or not an instruction to end the registration has been made (S12). If the instruction has been made (S12: YES), the registration processing is ended. If not, (S12: NO) S1.
And the registration process for another search target document is repeated.

Next, the creation of an efficient transposed vector table will be described. FIG. 9 is a functional block diagram of the transposed vector table registration device 142. Transposed vector table registration device 142
Is a transposed vector table generator that generates a transposed vector table
1421, a block decomposer 1422 that blocks the elements of each row of the transposed vector table, and a vector compressor 1423 that compresses the transposed vector table.

With respect to the transposed vector table generated by the transposed vector table generating device 1421, the elements of each row are divided for each length L by the block decomposition device 1422. The vector compression device 1423 does not hold a block including only the “0” element in the block divided into the length L, and stores at least one “1”.
Holds the block containing the element with the location information. In order to reconstruct the transposed vector table even with the compression as described above, the block including the “1” element is restored based on the position information, and all the parts where the block does not exist are replaced by the “0” element. Reconstruction is possible by filling. By compressing the transposed vector table in this manner, effective use of computer resources, reduction in the number of accesses to the transposed vector table can be realized, and search speed can be improved.

FIG. 10 is a functional block diagram of the similar document search device 2. The similar document search device 2 includes a search key document input device 21 for inputting a search key document (question document), a keyword extraction device 22 for extracting a keyword (word) from the input search key document, and an N-gram of the word. N-
It includes a gram generation device 23, an index reference device 24 for extracting a transposed vector corresponding to the generated N-gram, and a similar document determination device 25 for determining a similar document to the search key document.

The structure of the keyword extracting device 22 is the same as the structure of the keyword extracting device 12 described above.
The configuration of the gram generation device 23 is the same as that of the N-gram generation device 13 described above.
The configuration is the same as

FIG. 11 is a functional block diagram of the index reference device 24. The index reference device 24 includes a transposed vector table look-ahead device 241 that reads a frequently used transposed vector table from main storage, and a transposed vector table read device 242 that reads a transposed vector table from an index file.
And

FIG. 12 is a functional block diagram of the similar document determination device 25. The similar document determination device 25 selects a similar document candidate based on the transposed vector.
1, a similarity calculation device 252 for calculating similarity for similar document candidates, a search result sorting device 253 for sorting search results in order of similarity, and a search result output device 254 for outputting search results sorted in order of similarity And

Next, the similar document search processing will be described. FIG. 13 is a flowchart showing the processing procedure. In the search key document input device 21, a document (keyword,
An input sentence, a character string having some meaning such as the whole sentence or a part thereof is input and sent to the keyword extracting device 22 (S21).

The operation of the keyword extracting device 22 is the same as the operation of the keyword extracting device 12 described above. That is, from the input document, a character string in which two or more characters of the same character type are consecutive is extracted as a word (S22), unnecessary characters are removed from the character string (S23), and a character string is referred to the unnecessary word dictionary. Unnecessary / necessary columns are determined to remove unnecessary character strings (S24), a synonym dictionary is searched, and synonyms are added to the extracted words (S25), and the appearance frequency of the extracted character strings (words) is determined. A character string table is created by totaling (S26), and the created character string table is sent to the N-gram generation device 23.

The operation of the N-gram generator 23 is the same as the operation of the N-gram generator 13 described above. That is, the character strings (words) included in the character string table are decomposed into N-grams (S27), and those registered in the N-gram dictionary are extracted from the decomposed N-grams (S28), which is unnecessary. The N-gram determined as is removed (S29), and the remaining N-gram is sent to the index reference device 24.

When reading the transposed vector table, it is first determined whether or not the transposed vector table has been written to the main memory (S30). If the data has been written to the main memory (S30: YES), the transposed vector table is read out therefrom by the transposed vector table look-ahead device 241 (S31). If not written in the main memory (S30: NO), the transposed vector table reading device 242 reads the transposed vector table from the index file (S32). The read transposed vector table is sent to the similar document determination device 25. Since the transposed vector table that is frequently required is written in the main storage that can be accessed at high speed, the search processing can be speeded up.

The similar document candidate selecting device 251 selects similar document candidates as follows (S33). The transposed vector corresponding to the N-gram extracted from the search key document is
Extract from the input transposed vector table. Add the transposed vectors taken out. Then, a search target document for which the addition result (the number of overlapping words) is 1 or more is set as a similar document candidate. The similarity calculation device 252 calculates the similarity of the document which is a similar document candidate according to a predetermined calculation formula described later (S34). Then, the search result sorting device 253
The search results are sorted in order of similarity, and the search results sorted in order of similarity are output from the search result output device 254 (S35).

Here, a specific example of the similarity calculation will be described. The search target document and the transposed vector table are as shown in FIG. Also, the search key document includes N-gr
It is assumed that am1 and N-gram3 are included. First, the transposed vectors corresponding to these N-gram1 and N-gram3 are extracted from FIG. 8, and they are added for each of documents 1 to 4. Specifically, the added value is calculated in Document 1:
2, document 2: 0, document 3: 2, document 4: 1. Document 1, document 3, and document 4 whose addition value is 1 or more are set as similar document candidates. Document 2 is not considered as a similar document candidate because the added value is 0. Next, these similar document candidates (document 1,
The similarity D is calculated for each of the documents 3 and 4) according to the following equation (1). D = γ / (α · β) ^1/2 where α: N-gr of the search target document (document 1, document 3, document 4)
total number of am β: total number of N-grams of the search key document (question document) γ: addition value of the corresponding transposed vectors (in the above example, document 1: 2, document 3: 2, document 4: 1)

The equation for calculating the similarity D shown in the above equation (1) is merely an example, and it goes without saying that the similarity D may be obtained according to another equation.

In the present invention, instead of calculating the similarity for all the search target documents registered in the transposed vector table, similar document candidates are selected first,
Since the similarity is calculated only for those similar document candidates, the similarity can be obtained with a small number of calculations, and the search processing can be speeded up.

FIG. 14 is a block diagram showing the configuration of an embodiment of the recording medium of the present invention. The program exemplified here includes S1 to S12 and S21 to S35 shown in FIGS. 6 and 13 and is recorded on a recording medium described below.

In FIG. 14, a recording medium 31 that is connected online to the computer 30 is, for example, a WWW (World Wide Web) server computer that is installed separately from a place where the computer 30 is installed. Is recorded. The computer 30 executes a document registration process and a similar document search process by controlling the computer 30 by the program 31a read from the recording medium 31.

The recording medium 32 provided inside the computer 30 uses, for example, a hard disk drive or a ROM installed therein, and the recording medium 32 stores the program 32a as described above. By controlling the computer 30 by the program 32a read from the recording medium 32, the computer 30 executes a document registration process and a similar document search process.

The recording medium 33 used by being loaded into the disk drive 30a provided in the computer 30 is a transportable medium such as a magneto-optical disk, a CD-ROM or a flexible disk. The program 33a is recorded as follows. The computer 30 executes the document registration process and the similar document search process by controlling the computer 30 by the program 33a read from the recording medium 33.

[0062]

As described above, according to the present invention, words included in a search target document and a question document are extracted as feature amounts, an N-gram is generated from the extracted words, and the N-gram in the search target document is extracted. -Gram and N-gram in question document
Is compared to obtain a similar document, and a similar document is searched. Therefore, an N-gram required for the search processing can be obtained in a short time, and the search processing can be speeded up.

[Brief description of the drawings]

FIG. 1 is a conceptual diagram showing a system configuration for implementing a document search method of the present invention.

FIG. 2 is a functional block diagram of the document registration device.

FIG. 3 is a functional block diagram of the keyword extracting device.

FIG. 4 is a functional block diagram of the N-gram generation device.

FIG. 5 is a functional block diagram of the index generation device.

FIG. 6 is a flowchart illustrating a procedure of a document registration process.

FIG. 7 is a diagram illustrating an example of a document feature vector.

FIG. 8 is a diagram showing a transposed vector table corresponding to FIG. 7;

FIG. 9 is a functional block diagram of a transposed vector table registration device.

FIG. 10 is a functional block diagram of a similar document search device.

FIG. 11 is a functional block diagram of an index reference device.

FIG. 12 is a functional block diagram of the similar document determination device.

FIG. 13 is a flowchart illustrating a procedure of a similar document search process.

FIG. 14 is a block diagram illustrating a configuration of a recording medium according to an embodiment of the present invention.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Document registration device 2 Similar document search device 12, 22 Keyword extraction device 13, 23 N-gram generation device 14 Index generation device 24 Index reference device 25 Similar document determination device 30 Computer 31, 32, 33 Recording medium 121 Character analysis device 122 Unnecessary character removing device 123 Unnecessary character string removing device 131 N-gram decomposition device 132 N-gram dictionary reference device 133 Unnecessary N-gram removing device 141 Document feature vector generating device 142 Transposed vector table registration device 241 Transposed vector table look-ahead device 242 Transposed Vector table reading device 251 Similar document candidate selection device 252 Similarity calculation device 1421 Transposed vector table generation device 1422 Block decomposition device 1423 Vector compression device

Claims (18)

[Claims] 1. A document retrieval method for retrieving a similar document similar to an arbitrary document from a plurality of documents, a step of extracting words included in the plurality of documents, and generating an N-gram of the extracted words. Extracting a word included in the arbitrary document;
Generating an N-gram for the arbitrary document and an N-gram generated for the plurality of documents.
Comparing the gram with the gram and searching for a similar document based on the comparison result. 2. The document search method according to claim 1, wherein when extracting the word, the word is extracted using the face information, and unnecessary words are removed from the extracted words. 3. Unnecessary N-gr from the generated N-grams
3. The document search method according to claim 1, wherein am is removed. 4. An N-gr generated for the arbitrary document
The similarity between the arbitrary document and each of the plurality of documents is calculated based on am and the N-gram generated for the plurality of documents, and a similar document is searched for according to the similarity. 2. The document search method according to claim 1, wherein a document candidate is selected, and the similarity is calculated for the selected similar document candidate. 5. The N-gr generated for the plurality of documents
2. The document according to claim 1, wherein the presence information of am is stored in a storage unit in the form of a vector, and each row of the vector is divided into blocks in units of a plurality of elements, and unnecessary blocks are removed to compress the vector. retrieval method. 6. The N-gr generated for the plurality of documents
2. The document search method according to claim 1, wherein the presence information of am is separately stored in a plurality of storage units having different read speeds in a vector format. 7. A document search device for searching a plurality of documents for a similar document similar to an arbitrary document, a first word extracting means for extracting words included in the plurality of documents, and N- first N-gram generating means for generating a gram, second word extracting means for extracting a word included in the arbitrary document, and second N-gram for generating an N-gram of the extracted word
-Gram generating means and N generated for the arbitrary document
And a similar document search means for comparing the N-gram generated for the plurality of documents with the N-gram and searching for a similar document based on the comparison result. 8. The first word extracting means and the second word extracting means have means for extracting a word using document face information, and means for removing an unnecessary word from the extracted words. Item 7. The document search device according to Item 7. 9. The first N-gram generation means and the second N-gram generation means.
The gram generation means selects unnecessary N-grams from the generated N-grams.
9. The document search device according to claim 7, further comprising means for removing a gram. 10. The similar document search means selects a similar document candidate from the plurality of documents based on the N-gram generated for the arbitrary document and the N-gram generated for the plurality of documents. 8. The document search apparatus according to claim 7, further comprising: means for calculating a similarity between the arbitrary document and each of the selected similar document candidates; and means for searching for a similar document according to the similarity. 11. An N-file generated for the plurality of documents.
storage means for storing presence information of the gram in the form of a vector, wherein each row of the vector is divided into blocks in units of a plurality of elements, unnecessary blocks are removed and the vector is compressed, and the storage means is provided. 8. The document search device according to claim 7, wherein the document search device is stored. 12. An N-file generated for the plurality of documents.
a first storage unit that stores a part of the existence information of the gram, and a second storage unit that stores the remaining part of the existence information of the N-gram generated for the plurality of documents, the second storage unit having a different reading speed from the first storage unit. The document search device according to claim 7, further comprising a storage unit. 13. A computer-readable recording medium that stores a program for searching a plurality of documents for a similar document similar to an arbitrary document, and extracts words included in the plurality of documents. Program code means for causing the computer to do the above, program code means causing the computer to generate an N-gram of the extracted word, and a program causing the computer to extract a word contained in the arbitrary document Code means, program code means for causing the computer to generate an N-gram of the extracted word, and comparing the N-gram generated for the arbitrary document with the N-gram generated for the plurality of documents. A program that causes the computer to search for a similar document based on the comparison result. Recording medium and having a code means. 14. The program code means for causing the computer to extract a word includes program code means for causing the computer to extract a word using face information, and an unnecessary word from the extracted words. 14. A recording medium according to claim 13, further comprising program code means for causing the computer to remove the program. 15. A program code means for causing the computer to generate an N-gram of an extracted word, wherein the program code causes the computer to remove an unnecessary N-gram from the generated N-gram. The recording medium according to claim 13 or 14, comprising means. 16. The program code means, which causes the computer to search for a similar document, based on the N-gram generated for the arbitrary document and the N-gram generated for the plurality of documents. Program code means for causing the computer to select a similar document candidate from among the documents, and program code means for causing the computer to calculate the degree of similarity between the arbitrary document and each of the selected similar document candidates. 14. Program code means for causing the computer to search for a similar document according to the degree of similarity.
The recording medium according to the above. 17. An N-file generated for the plurality of documents.
program code means for causing the computer to store the presence information of the gram in the storage means in the form of a vector; and dividing each row of the vector into a plurality of elements as a unit, removing unnecessary blocks to remove the vector. 14. The recording medium according to claim 13, further comprising program code means for causing said computer to perform compression. 18. An N-file generated for the plurality of documents.
14. The recording medium according to claim 13, further comprising program code means for causing the computer to store the gram presence information in a plurality of storage means having different read speeds in a vector format.