JPH11143902A - Similar document search method using n-gram - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a similar document retrieval system which can retrieve even for such languages as the Japanese have many character types at a high speed and with high accuracy. SOLUTION: This system is provided with a step where the appearance frequency of a feature character string existing in a text 103 contained in a text data base is stored as an appearance frequency file 104, a step where the feature character string is extracted from the text that is designated by a user and a step where the appearance frequency of the feature character string is counted in the text designated by the user. Then, a similarity is calculated to the text designated by the user by using the appearance frequency stored in the file 104 and in the text designated by the user. Thus, the similar documents are retrieved by using the calculated similarity.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a method for searching a document database for a document similar to a document specified by a user.

[0002]

2. Description of the Related Art In recent years, with the spread of personal computers, the Internet, and the like, the number of digitized documents has exploded, and is expected to increase at an accelerating rate in the future. In such a situation, there is an increasing demand for a user to quickly and efficiently search for a document containing desired information.

There is a full-text search as a technique to meet such a demand. In the full-text search, a document to be searched is registered as a text in a computer system and made into a database, and a document including a search character string (hereinafter, referred to as a search term) specified by a user is searched from the database. As described above, in the full-text search, since a search is performed for the character string itself in a document, a keyword is previously assigned, and unlike a conventional search system in which this keyword is used as a clue, detection omission does not occur in principle. There is a feature.

However, in order to accurately search for a document containing information desired by the user, it is necessary to input a complicated search condition expression that accurately represents the user's search intention.

[0005] In order to solve this complexity, similar document search technology, in which a user designates a document having a desired content (hereinafter referred to as a seed document) and searches for a document similar to the document, has attracted attention. I have.

As a similar document search method, for example,
Japanese Patent Application Laid-Open No. 8-335222 discloses a technique for extracting words included in a seed document by morphological analysis or the like and searching for a similar document using the extracted words (hereinafter referred to as Conventional Technique 1). .

[0007] Japanese Patent Application Laid-Open No. Hei 6-110948 discloses
Is a string of n consecutive characters from the seed document (hereinafter ng
A technique for extracting a similar document using the extracted ram (hereinafter referred to as ram) (hereinafter referred to as prior art 2) is disclosed.

The outline of the above two prior arts will be described.

In the prior art 1, a word included in a seed document is extracted by morphological analysis, and a document containing this word is searched for as a similar document. For example, when a document “This device can be used for observation of groundwater veins” is used as a seed document, the word dictionary is referred to by morphological analysis, and “device” “underground”
The words "water vein", "observation", and "usable" are extracted.
As a result, a document "predict the occurrence of an earthquake by observing groundwater veins" can be retrieved as a similar document. However, in the prior art 1, since the word dictionary is used for extracting words, the following two problems occur.

First, words not included in the word dictionary are:
There is a problem that a document including this word cannot be searched because it is not extracted as a search word from the seed document. Therefore, the information desired by the user is expressed in a new word,
If this is not included in the word dictionary, it will not be possible to search for documents containing the desired information.

[0011] Next, even if a word representing information desired by the user is included in the word dictionary, search omission may occur depending on how the word is extracted. For example, the word “device”, “underground”, “water vein”, “observation”, “usable” is extracted from the seed document “this device can also be used for observation of groundwater veins”. However, since the word "groundwater" is not extracted, there is a problem that the document "The ground subsidence area has been expanded by the large pumping of groundwater" cannot be searched as a similar document.

The above is the problem of the prior art 1.

In order to solve this problem, the above-mentioned prior art 2 has been proposed. This is a similar document search method using an n-gram.

Hereinafter, a database in which a document 1 “Electrocardiogram at the time of a seizure by a newly developed electrocardiograph”, a document 2 “New software development work”, and a document 3 “Software supporting software development” are registered. And n-gram
A specific processing method of the prior art 2 will be described by taking as an example a case where the value of n is set to 2 and the user designates the document 2 as a seed document.
The problem is described.

First, 2-grams are extracted from documents 1 to 3 in the database.

[0016]

[Table 1]

Table 1 shows a 2-gram extracted by removing duplicates from 2-grams appearing in document 1 (hereinafter referred to as a duplicate-eliminated 2-gram).
). Next, a weight is calculated for each of these 2-grams. This weight is obtained by dividing the appearance frequency of each 2-gram by the total appearance frequency including the duplication of the 2-gram appearing in the document. Weight is 2-
The gram represents the appearance rate of the document in the document, and the larger the value of 2-gram, the more frequently the gram appears in the document. The same processing is performed on document 2 and document 3,
Find the weight for each. Tables 2 and 3 show the processing results.

[0018]

[Table 2]

[0019]

[Table 3]

Thereafter, the commonality between the documents in the database is removed. Here, first, a commonality weight is calculated for a 2-gram from which duplicates have been eliminated among 2-grams existing in the database. This commonality weight is calculated by dividing the sum of the weights of each 2-gram for all documents in the database by the total number of documents. The commonality weight indicates the appearance ratio of each 2-gram in the entire database, and means that a 2-gram with a larger value appears more commonly in any document in the database.

[0021]

[Table 4]

Table 4 shows the commonality weights among Document 1, Document 2, and Document 3.

For example, the commonality weight of the 2-gram “new opening” is (0.063 + 0.0 + 0.0) /3=0.021. Where 2-gram
Since “Shinkai” does not appear in the document 2 and the document 3, the weight is “0.0”, respectively. The commonality weight of 2-gram `` development '' is (0.063 + 0.077 + 0.067) /3=0.06
9

As described above, the commonality weight is n-gr
It is the average value of am weight.

By subtracting this commonality weight from the weight of each n-gram, the commonality between documents in the database is removed (this value is called a normalized weight in the prior art 2). The normalized weight represents the appearance bias of each n-gram in the database.
This means that gram appears more eccentric to a specific document.

If a certain n-gram appears in all documents at the same ratio, the weight and the commonality weight have the same value, so that the normalized weight is "0". That is,
For n-grams that appear at the same rate in any document, the weights will approach “0” without limit.

Table 5, Table 6 and Table 7 show Document 1, Document 2
And the normalized weight of Document 3.

[0028]

[Table 5]

[0029]

[Table 6]

[0030]

[Table 7]

Using the normalized weights obtained as described above, the similarity between the document designated by the user as the seed document and all the documents in the database is expressed as similarity. Assuming that the document number is i, the similarity S (i) of document i
Is determined by the following equation (1).

[0032]

(Equation 1)

Here, U (j) is the j-th n-gram in the seed document.
R (j) is the normalized weight of the document in the database.
The normalized weight of the j-th n-gram is shown. N represents the total number of documents in the database. When the similarity of all documents in the database is calculated using this equation, the following is obtained.

S (1) = 0.018 S (2) = 1.0 S (3) = 0.119 Finally, the documents are output in descending order of the obtained similarity. In this example, document 2, document 3, and document 1 are output in this order.

The above is the specific processing content of the prior art 2. As described above, in the second prior art, since a document similar to a seed document can be searched without using morphological analysis based on a word dictionary, two problems in the first prior art can be solved.

However, the prior art 2 has the following 2
There are two problems.

First, the first problem is that since the number of n-grams extracted from a seed document becomes enormous, a long time is required for retrieval. For example, if all 2-grams are extracted from a seed document consisting of 1,000 characters, 999 2
-gram will be extracted. Therefore, in the method of prior art 2 in which all extracted 2-grams are used for similarity search,
Even if one 2-gram search takes 0.1 seconds, 999 2
In the case of -gram, it takes 99.9 seconds, that is, about 1 minute and 40 seconds.

The second problem is that a similar document is searched using all n-grams, so that the search result contains noise.

Hereinafter, this problem will be specifically described with reference to an example in which a document 4 "distribution work of a new soft serve ticket" is added to the database in which documents 1 to 3 are registered.

In this example, it is assumed that document 2 is designated by the user as a seed document.

First, a result of extracting a 2-gram from the document 4 and obtaining a weight is shown in Table 8.

[0042]

[Table 8]

Using the weight of the document 4 and the weights of the documents 1 to 3 shown in Tables 1 to 3, a commonality weight is calculated.

[0044]

[Table 9]

Table 9 shows the commonality weight between documents 1 to 4. For example, the commonality weight of 2-gram “development” is (0.063 + 0.077 + 0.067 + 0.000) /4=0.052. Next, a normalized weight is obtained by subtracting the commonality between documents in the database by subtracting the commonality weight from the deduplication 2-gram weight of each document.

[0046]

[Table 10]

[0047]

[Table 11]

[0048]

[Table 12]

[0049]

[Table 13]

Tables 10 to 13 show documents 1 to 4
This shows the normalized weight of 2-gram. Using these, the similarity of each document to document 2 which is a seed document is calculated using equation (1). S (1) = 0.036 S (2) = 1.0 S (3) = 0.179 S (4) = 0.190.

Here, the document 3 is determined to be similar to the document 2 irrelevant document 4 though the document 3 is a document relating to software like the document 2. This is because “soft” and “soft” extracted from “software” in document 2 are also extracted from “soft cream” in document 4. Since an n-gram is not a character string in a unit semantically like a word, even the same n-gram does not always represent the same meaning in a document. Therefore, there is a problem that a completely unrelated document like this example is found as a document having a high similarity.

[0052]

SUMMARY OF THE INVENTION In order to solve the problems of the prior art, the present invention aims to solve the following problems.

(1) To provide a similar document search method with high search accuracy.

(2) A method is provided that enables similar documents to be searched at high speed even for languages with many types of characters such as Japanese.

[0055]

In order to solve the above-mentioned problems, a document retrieval method according to the present invention retrieves a document similar to a seed document in the following steps.

That is, in the document search method according to the present invention, as the document registration processing, (step 1) a document reading step for reading the registration target document, and (step 2) a character string of the registration target document read in the document reading step. The same character type character string extraction step of dividing at a character type boundary such as kanji or katakana and extracting as a character string composed of the same character type (hereinafter referred to as the same character type character string);
(Step 3) For the same character type character string extracted in the same character type character string extraction step, the character type is determined, and if it is a kanji character, a character string of a predetermined length may be an independent word ( Hereinafter, it will be referred to as a characteristic character string).
A character string of the same character type is extracted as a characteristic character string if it is a katakana or English character, and a character string for registration is not extracted as a characteristic character string if it is any other character type (step 4). An appearance frequency counting step of counting the appearance frequency in the registration target document with respect to the feature character string extracted in the registration feature character string extraction step; (step 5) the occurrence frequency counted in the appearance frequency counting step corresponds to the occurrence frequency The method includes a step of creating and registering an appearance frequency file to be stored in a file. As a search process for a document similar to a seed document, (step 6) a seed document reading step of reading a seed document, and (step 7) reading in the seed document reading step. The same character type sentence that divides the character string of a type document at character type boundaries and extracts it as the same character type character string String extraction step, (Step 8) The same character type character string extracted in the same character type character string extraction step is determined for the character type, and if it is a kanji character, a character string of a predetermined length is used as a characteristic character string. A character string of the same character type itself is extracted as a characteristic character string if it is a katakana or English character, and a character string for retrieval is not extracted as a characteristic character string if it is any other character type. (Step 9) An appearance frequency counting step of counting the appearance frequency in the seed document with respect to the characteristic character string extracted in the search characteristic character string extraction step; (step 1
0) an appearance frequency acquisition step of reading the appearance frequency file for all the characteristic character strings extracted in the appearance frequency counting step and acquiring an appearance frequency in each document in the database; (step 11) an appearance frequency acquisition For the characteristic character string extracted in the step, a predetermined calculation is performed using the appearance frequency in the seed document counted in the appearance frequency counting step and the appearance frequency in each document in the database acquired in the appearance frequency acquisition step. A similarity calculating step of calculating a similarity between the seed document and each document in the database based on the equation; (step 12) a search result displaying a list of documents in descending order of the similarity calculated in the similarity calculating step It has a display step.

The principle of the present invention using the above document search method will be described below.

When registering a document, (step 1) to
(Step 5) is executed. First, a document to be registered is read in (Step 1). Next, in (Step 2), the character string in the registration target document read in (Step 1) is divided at character type boundaries such as kanji and katakana to extract a character string having the same character type. For example, from the document “Document 4“ Distribution work of new soft serve ticket ””, “new”, “new”, “soft serve”, “ticket”
Six identical character type character strings “no” and “distribution work” are extracted.

Next, in (Step 3), for the same character type character string extracted in (Step 2), the character type is determined, and if it is a kanji character, a character string of a predetermined length is used as a characteristic character string. If the characters are katakana or English characters, the same character type character string itself is extracted as a characteristic character string, and if it is any other character type, no character character string is extracted. For example, if it is determined in advance that a 2-gram is to be extracted from a kanji character string, the above (step 2)
From the same character type string in
“Distribution”, “cloth”, and “work” are extracted as characteristic character strings.

Next, in (Step 4), the appearance frequency of the characteristic character string extracted in (Step 3) in the registration target document is counted. For example, in the document "Document 4" Distribution work of a new soft serve ticket ", information is obtained that the characteristic character string" soft serve "appears once and" work "appears once.

Next, in (Step 5), the appearance frequency of the characteristic character string counted in (Step 4) is stored in the corresponding appearance frequency file. FIG. 2 shows an example of the appearance frequency file. The appearance frequency files shown in this figure are shown in Table 1,
This is an example in a case where documents 1 to 4 shown in Tables 2, 3 and 8 are registered.

At the time of retrieval, a similar document retrieval step consisting of (Step 6) to (Step 12) is executed.

First, in step (6), document 2 is read as a seed document.

Next, in (Step 7), the character string of the seed document (document 2) read in (Step 6) is divided at the character type boundary to extract the same character type character string.

Next, in (Step 8), a characteristic character string is extracted from the same character type character string extracted in (Step 7) in the same manner as in the registration (Step 3).
FIG. 3 shows an outline of the characteristic character string extraction processing in the case where document 2 is designated as a seed document (step 8). In this figure,
If the same character type character string is a Chinese character, 2-gram is extracted. When all 2-grams were extracted from document 2, thirteen types of 2-grams were extracted.
In this method, the number of characteristic character strings of “software”, “development”, “seizure”, and “work” can be reduced to four types. As described above, in the present invention, the types of characteristic character strings to be extracted can be significantly deleted as compared with the above-described related art 2 that extracts all n-grams.

Next, in (Step 9), the appearance frequency of the characteristic character string extracted in (Step 8) in the seed document is counted. Then, in (Step 10),
With respect to the characteristic character string extracted in (Step 8), the appearance frequency in each document in the database is obtained by referring to the appearance frequency file described above. Then, in (Step 11), for the characteristic character string extracted in (Step 8), the appearance frequency in the seed document counted in (Step 9) and (Step 10), and the appearance frequency in each document in the database Is calculated based on. The equation (1) shown in the related art 2 may be used as the equation for calculating the similarity.
When the similarity when the document 2 is specified as the seed document is calculated using the equation (1), the following is obtained.

S (1) = 0.077 S (2) = 1.0 S (3) = 0.263 S (4) = 0.148 As a result, in step 12, when the documents are displayed in descending order of similarity, document 2, document 3, document 4 and document 1 are displayed in this order. This similarity calculation result (S (1) = 0.077, S (2)
= 1.0, S (3) = 0.263, S (4) = 0.148) are the similarity calculation results (S (1) = 0.036, S (2) = 1.0, S (3) =
0.179, S (4) = 0.190), the similarity is calculated correctly in the order similar to the document 2.

As described above, according to the similar document search method of the present invention, even if a similar document search is performed on a document such as Japanese without breaking words, the word dictionary as in the prior art 1 is used. Since the character string is mechanically extracted from the seed document without any error, it is possible to perform a search without omission for any word as in the related art 2. Also, instead of simply extracting an n-gram from a document as in conventional technology 2, it is possible to perform a search using a character string with a meaning by extracting a characteristic character string according to a character type. Therefore, a highly accurate similar document search can be realized. Furthermore, since the types of character strings to be extracted are significantly reduced as compared with the related art 2 that extracts all n-grams, similar documents can be searched at high speed.

[0069]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A first embodiment of the present invention will be described below with reference to FIG.

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 1
05, a floppy disk drive (FDD) 106, a main memory 109, and a bus 108 connecting these.

The magnetic disk device 105 is one of the secondary storage devices, and includes a text 103 and an appearance frequency file 104.
Is stored. The information stored in the floppy disk 107 via the FDD 106 is read into the main memory 109 or the magnetic disk device 105.

The main memory 109 has a system control program 110, a document registration control program 111, a shared library 112, a text registration program 113, an appearance frequency file creation registration program 114, a search control program 118, a search condition analysis program 119, and the like. The work area 130 is secured while the document search program 120 and the similarity sort program 126 are stored.

The shared library 112 includes the same character type character string extraction program 115 and the characteristic character string extraction program 1
16. Kanji character string corresponding feature character string extraction program 127
And character string extraction program for katakana character strings 1
28.

Appearance frequency file creation registration program 11
No. 4 is constituted by an appearance frequency file creation program 117, and has a configuration of calling the same character type character string extraction program 115 and the characteristic character string extraction program 116 as described later.

The similar document search program 120 includes a seed document reading program 121, a character string extraction program 115 of the same character type, an appearance frequency counting program 123, an appearance frequency file reading program 124, and a similarity calculation program 125, and will be described later. The configuration is such that the characteristic character string extraction program 116 is called.

The document registration control program 111 and the search control program 118 correspond to the keyboard 10 by the user.
1 is started by the system control program 110 in response to an instruction from
3 and the control of the appearance frequency file creation registration program 114, the search condition expression analysis program 119, the similar document search program 120, and the similarity degree sort program 12
6 is performed.

Hereinafter, the processing procedure of the similar document search system according to the present embodiment will be described.

First, regarding the processing procedure of the system control program 110, the PAD (Problem Ana) shown in FIG.
This will be described with reference to a lysis diagram.

First, in step 400, the system control program 110 analyzes a command input from the keyboard 101.

If it is determined in step 401 that the result is a command to execute registration, the document registration control program 111 is activated in step 402 to register a document.

If it is determined in step 403 that the command is a search execution command, the search control program 118 is activated in step 404 to search for a similar document.

The processing procedure of the system control program 110 has been described above.

Next, the processing procedure of the document registration control program 111 started by the system control program 110 in step 402 shown in FIG.
This will be described with reference to the drawings.

The document registration control program 111 first activates the text registration program 113 in step 500, and the floppy disk 107 inserted in the FDD 106.
Text data of the document to be registered from work area 1
Then, the data is read into the magnetic disk device 105 as text 103. The text data is not limited to being input using the floppy disk 107, but may be configured to be input from another device using a communication line, a CD-ROM device (not shown in FIG. 1), or the like. It is possible.

Next, in step 501, the appearance frequency file creation / registration program 114 is started, the text 103 stored in the magnetic disk device 105 is read, and the appearance frequency file 104 for each document therein is created. It is stored in the device 105.

The above is the processing procedure of the document registration control program 111.

Next, the processing procedure of the appearance frequency file creation registration program 114 started by the document registration control program 111 in step 501 shown in FIG.
This will be described with reference to the PAD diagram of FIG.

Appearance frequency file creation registration program 11
In step 4, the same character type character string extraction program 115 is started in step 600, the text 103 is read into the work area 130, and the character string is extracted by dividing the character string at the character type boundary.
30.

Next, in step 601, the characteristic character string extraction program 116 is started, and the work area 130
, A characteristic character string is extracted from the same character type character string stored in.

Then, in step 602, the appearance frequency file creation program 117 is started, the appearance frequency is counted by referring to the characteristic character string stored in the work area 130, and the appearance frequency file 104 is used as the magnetic disk drive. 105.

The above is the processing procedure of the appearance frequency file creation registration program 114.

Next, the processing procedure of the characteristic character string extraction program 116 started by the appearance frequency file creation / registration program 114 in step 601 shown in FIG. 6 will be described with reference to the PAD diagram of FIG.

The characteristic character string extraction program 116 checks the number of identical character type character strings extracted by the identical character type character string extraction program 115, and repeatedly executes Step 701 and subsequent steps for all the identical character type character strings (Step 700).

In step 701, the work area 130
Judge the character type of the same character type string stored in
If the character type is Kanji, execute step 702,
In the case of katakana, step 703 is executed.

In step 702, a kanji character string corresponding characteristic character string extraction program 127 to be described later is started to extract a characteristic character string from the kanji character string.

In step 703, a katakana character string corresponding characteristic character string extraction program 128 similarly described later is started to extract a characteristic character string from the katakana character string.

The above is the characteristic character string extraction program 116
This is the processing procedure.

Next, the processing procedure of the kanji character string corresponding characteristic character string extraction program 127 started by the characteristic character string extraction program 116 in step 702 shown in FIG. 7 will be described with reference to the PAD diagram of FIG.

In the kanji character string corresponding characteristic character string extraction program 127, in step 800, the same character type character string extraction program 115 extracts the work area 1
The kanji character string stored in 30 is acquired. Then, in step 801, while shifting one character at a time from the beginning of the kanji character string acquired in step 800,
An n-gram (the value of n is predetermined) is extracted as a characteristic character string.

The above is the processing procedure of the kanji character string corresponding characteristic character string extraction program 127.

Next, the processing procedure of the katakana character string corresponding characteristic character string extraction program 128 started by the characteristic character string extraction program 116 in step 703 shown in FIG. 7 will be described with reference to the PAD diagram of FIG.

In the katakana character string corresponding characteristic character string extraction program 128, in step 900, katakana character strings extracted by the same character type character string extraction program 115 and stored in the work area 130 are obtained.

At step 901, the katakana character string itself obtained at step 900 is extracted as a characteristic character string.

The above is the processing procedure of the katakana character string corresponding characteristic character string extraction program 128.

Hereinafter, the processing procedure of the characteristic character string extraction program 116 shown in FIG. 7 will be described using a specific example.

First, the characteristic character string extraction program 1 shown in FIG.
The processing procedure of the kanji character string corresponding characteristic character string extraction program 127 in step 16 702 and the katakana character string corresponding characteristic character string extraction program 128 in step 703 will be described with reference to the examples of FIGS. Kanji character string compatible feature character string extraction program 127
And katakana character string correspondence characteristic character string extraction program 128
Is activated by the characteristic character string extraction program 116. At this time, the same character type character string extraction program 115
The same character type character strings extracted by the above are transferred to the kanji character string corresponding characteristic character string extraction program 127 and the katakana character string corresponding characteristic character string extraction program 128.
Passed through.

FIG. 10 shows the result of extracting the same character type character string from the text 103 including the document 1, the document 2, the document 3, and the document 4 by the same character type character string extraction program 115. For example, five identical character type character strings “new”, “new”, “software”, “no”, and “development work” are extracted from document 2 “new software development work”.

The characteristic character string extraction program 116 activates the kanji character string corresponding characteristic character string extraction program 127 or the katakana character string corresponding characteristic character string extraction program 128 in accordance with the extracted character type of the same character type character string.

The characteristic character string extraction program 127 corresponding to the kanji character string stores all 2-grams while shifting one character at a time from the beginning of the kanji character string stored in the work area 130.
Is extracted as a characteristic character string. FIG. 11 shows the result of extracting a characteristic character string from the kanji character string extracted in the example of FIG. 10 by the kanji character string corresponding characteristic character string extraction program 127. For example, “development”, “seizure”, and “work” are extracted from “new”, “shin”, “software”, “no”, and “development work” extracted from the document 2 in the same character type character string 1000.

The katakana character string corresponding characteristic character string extraction program 128 extracts a katakana character string itself stored in the work area 130 as a characteristic character string. FIG. 12 shows the katakana character string extracted in the example of FIG.
This is a result of extracting a characteristic character string by a katakana character string-compatible characteristic character string extraction program. For example, “software” is extracted from “new”, “shin”, “software”, “no”, and “development work” extracted from the document 2 in the character string 1000 of the same character type.

The above is the processing procedure of the Kanji character string corresponding characteristic character string extraction program 127 in step 702 of the characteristic character string extraction program 116 in the first embodiment, and the katakana character string corresponding characteristic character string extraction program 128 in step 703. It is.

In this example, as the processing of the kanji character string corresponding characteristic character string extraction program 127, 2-gr
am has been described as being extracted as a feature string,
It will be apparent that the feature character string extraction process can be performed in the same manner for 1-gram or 3-gram or more, or for a combination thereof.

Next, the processing procedure of similar document search by the search control program 118 started by the system control program 110 in step 404 shown in FIG. 4 will be described with reference to the PAD diagram of FIG.

The search control program 118 starts the search condition expression analysis program 119 at step 1300, analyzes the search condition expression input from the keyboard 101, and extracts the seed document number designated as a parameter of the search condition expression. I do.

Next, the similar document search program 120 is activated in step 1301, and the similarity of each document in the text 103 stored in the magnetic disk device 105 is compared with the seed document number extracted in step 1300. calculate.

Then, in step 1302, the similarity sort program 126 is started, and
The similarities of the documents calculated in step 01 are sorted in descending order.

Finally, in step 1303, the similarities sorted in step 1302 are output together with the respective document numbers.

The above is the processing procedure of the document search by the search control program 118.

Next, the processing procedure of the similar document search program 120 started by the search control program 118 in step 1301 shown in FIG.
This will be described with reference to FIG. Similar document search program 12
In step 1400, the seed document reading program 121 is started in step 1400, and the seed document of the document number extracted from the search condition formula by the search condition formula analysis program 119 is read into the work area 130. Here, the seed document not only reads the document stored in the text 103, but also reads the floppy disk 107 and the CD-ROM device (FIG. 1).
It is also possible to adopt a configuration in which data is input from another device using a communication line or the like.
It is also possible to adopt a configuration for inputting from a search result by a full-text search system or the like, or to select a seed document from the output of the similarity sort program 126.

Next, in step 1401, the same character type character string extraction program 115 is started, and the text of the seed document read in the seed document reading step 1400 is divided at character type boundaries to obtain the same character type character string.
It is stored in the work area 130.

Then, in step 1402, the characteristic character string extraction program 116 is started, and a characteristic character string is extracted from the same character type character string acquired in the same character type character string extraction step 1401.

FIG. 15 shows a specific example of this processing. The processing procedure of the characteristic character string extraction program 116 is as described above.

In this example, five identical character type character strings 1500 of “new”, “new”, “software”, “no”, and “development work” are extracted from document 2 “new software development work” which is a seed document. Will be. A characteristic character string is extracted according to the character type of the extracted character string 1500 of the same character type. As a result, four characteristic character strings 1 of “software”, “development”, “seizure” and “work” are obtained from the document 2.
501 is extracted.

Next, in step 1403 of FIG. 14, the appearance frequency counting program 123 is started, and the appearance frequency of the characteristic character string extracted in the characteristic character string extraction step 1402 in the seed document is counted.

FIG. 16 shows this specific example. This figure shows a feature character string 150 extracted from the seed document illustrated in FIG.
The result of counting the appearance frequency of 1 is shown. That is,
"(Software, 1), (Development, 1), (Seizure,
1), (work, 1) ". Here, for example, (development, 1) indicates that the characteristic character string "development" appears "1" times.

Next, in step 1404 of FIG. 14, the appearance frequency file reading program 124 is started, and the frequency of appearance of the characteristic character string extracted in the characteristic character string extraction step 1402 in each document in the text 103 is calculated as the frequency of appearance. Read from file 104.

FIG. 17 shows this specific example. here,
FIG. 16 shows a result obtained from the read appearance frequency file, the appearance frequency of the characteristic character string 1501 extracted in the example of FIG. 15 in each document in the text 103. FIG.

In this example, the appearance frequency of the four characteristic character strings 1501 “software”, “development”, “seizure” and “work” extracted from the seed document is stored in the appearance frequency file 104.
Get from. As a result, as the appearance frequency 1700, for example, in the case of document 3, “(software, 1), (development, 1),
(Seizure, 0), (work, 0) "can be obtained.

Finally, in step 1405 of FIG. 14, the similarity calculation program 125 is started, and the appearance frequency of the characteristic character string counted in the appearance frequency counting step 1403 in the seed document and the appearance frequency file reading step 1404 are read. The degree of similarity with each document in the text 103 is calculated from the frequency of occurrence of the characteristic character string read in step 103 in each document in the text 103.

FIG. 18 shows this specific example. here,
The appearance frequency 1600 in the seed document counted in the example of FIG.
And the similarity S of each document using the appearance frequency 1700 of each document in the text 103 acquired in the example of FIG.
The results of calculating (1) to S (4) are shown. That is, the following result is obtained.

S (1) = 0.077 S (2) = 1.0 S (3) = 0.263 S (4) = 0.148 In the present embodiment, the similarity is calculated by the equation (1) disclosed in the prior art 2. ) Is used, but other methods may be used.

The above is the processing procedure of the similar document search program 118.

The above is the first embodiment of the present invention.

In the present embodiment, the characteristic character string extraction program 116 is configured to include the kanji character character string extraction program 127 and the katakana character string correspondence characteristic character string extraction program 128. It may be configured to include a corresponding characteristic character string extraction program, or a kanji character string corresponding characteristic character string extraction program 127
Alternatively, the configuration may not include the katakana character string corresponding feature character string extraction program 128.

In the present embodiment, the characteristic character string is extracted from the character string of the same character type. However, by extracting a partial character string extending between the specific character type as a boundary and the preceding and following character string, the characteristic character string is extracted. For example, a character string such as "F1" or "Vitamin C" can be used for the search, and a more accurate similar document search can be realized.

Further, in this embodiment, the appearance frequency file 104 is created in the table format shown in FIG. 2. However, in this method, as the size of the database increases, the type of the characteristic character string is changed. Because of the increase, the processing of the appearance frequency file reading step 1404 requires a long time. This problem can be solved by adding a search index to the characteristic character string. This makes it possible to realize a high-speed similar document search even for a large-scale database. As a search index for this characteristic character string, see Japanese Patent Application Laid-Open No. 8-32911.
No. 2 publication ”or the like, a word index method can be used.

Next, a second embodiment of the present invention will be described with reference to FIG.
9 will be described.

The second example of the similar document search system to which the present invention is applied uses a full-text search index without omission for obtaining the frequency of occurrence of a characteristic character string extracted from a seed document in each document in a database. It is. This eliminates the need to have an appearance frequency file when the similar document search system is implemented in combination with a full-text search system.

That is, according to the present method, the full-text search index can be used for searching for the characteristic character string of the appearance frequency file 104 in the first embodiment, and a high-speed similar document can be used for a large-scale database. A search can be realized. Furthermore, since the appearance frequency file 104 is substituted by the full-text search index, the required magnetic disk capacity can be reduced as compared with the first embodiment.

This embodiment has substantially the same configuration as the first embodiment (FIG. 1), but differs in the appearance frequency file reading program 124 constituting the similar document search program 120. Instead of this program, a characteristic character string search program 1900 is used as shown in FIG.

Hereinafter, of the processing procedures in this embodiment,
Similar document search program 120 different from the first embodiment
The processing procedure a will be described with reference to FIG.

Here, the only difference from the similar document search program 120 (FIG. 14) in the first embodiment is the appearance frequency acquisition step 2004. The processing procedure of the other processing steps is as described in the first embodiment.

In the appearance frequency acquisition step 2004, the characteristic character string search program 1900 is started, and the characteristic character string extracted in the characteristic character string extraction step 1402 is searched by the full-text search system 1901.
The appearance frequency of each document in 3 is acquired.

Appearance frequency acquisition step 2004 of this embodiment
For the feature character string search program 1900 used in, any method may be applied as long as there is no search omission and the full text search method can acquire the appearance frequency in each document. For example, “JP-A-64-35627”
(Hereinafter referred to as prior art 3).
It is also possible to use the gram index method.

In the n-gram index method according to the prior art 3, when a document is registered, an n-gram and an appearance position of the n-gram in the text are extracted from text data of the document to be registered in the database, and are used for full-text search. Index 19
03 is stored in the magnetic disk drive 1902.
N-gr that appears in the specified search term during search
am, the corresponding index is read from the magnetic disk drive 1902, and n in the index is read.
By comparing the appearance positions of -grams and determining whether the positional relationship of the n-gram extracted from the search term is equal to the positional relationship of the n-gram in the index, the document in which the specified search term appears is determined. Search fast.

By using this method, a characteristic character string is input to the full-text search system 1901 as a search term, and the occurrence document of the search term and its position information are obtained.
The appearance frequency of the characteristic character string in each document can be obtained.

Hereinafter, a method of calculating the appearance frequency using the prior art 3 will be specifically described with reference to FIG. In the figure, the value of n of the n-gram is 2.

First, a text 2101 to be registered in the database at the time of document registration is read by the index creation unit 2102, and an n-gram index 2100 is created. The n-gram index 2100 includes all the 2-grams that appear in the text 2101 and their 2-grams in the text 2101.
The 2-gram appearance position is stored.

[0149] In the text 2101 shown in this figure, the 2-gram "cardiogram" appears in the fifth character, the fifteenth character, ... of the text 2101 (document number "1"), so the n-gram index 2100 Contains the 2-gram “cardiogram” and the corresponding appearance positions ｛(1,5), (1,1
5),... Are stored.

At the time of a search, first, a search term is input to the n-gram extraction unit 2103, and all n-grams appearing in the search term and the appearance positions of the n-gram in the search term are extracted. Next, the extracted n-gram and its corresponding
The appearance position of the n-gram in the search term is input to the index search unit 2104.

In the index search unit 2104, the index corresponding to the n-gram extracted from the search term is n-gram.
The index is read from the index 2100, and the index having the same document number and the same positional relation as that in the search term is extracted from these indexes and output as a search result.

In the case of the present figure in which “electrocardiogram” is input as a search term, first, the n-gram extraction unit 2103
(N-gram “electrocardiogram”, n-gram position “1”) and (n-gram “electrogram”, n-gram position “2”) are extracted. Where ng
The ram position "1" is the head of the search term, and the n-gram position "2"
Indicates the next character position.

Next, the index corresponding to the n-gram “cardiogram” and the “electrogram” is read from the n-gram index 2100 in the index search unit 2104. The appearance positions in these indexes are n-gram position "1" and n-gram position
Consecutive items such as gram position “2”, that is, adjacent items are extracted and output as a search result.

In this figure, since the appearance position “15” of the n-gram “ECG” is adjacent to the appearance position “16” of the n-gram “ECG”, the n-gram “ECG” exists as a character string. This indicates that the search term “ECG” appears in the document 1. However, since the appearance position “5” of the n-gram “ECG” and the appearance position “16” of the n-gram “ECG” are not adjacent to each other, the search term “ECG” may not appear at this position. I understand.

In the present method, when a characteristic character string is input as a search term, the appearance frequency of the characteristic character string can be obtained by counting the number of appearance positions output from the index search unit 2104 as a search result. Become.

As described above, according to the present embodiment,
A full-text search index can be used instead of the index for character string search and the frequency file of the frequency file, so similar documents can be searched at high speed even for large-scale databases without adding extra files. It becomes possible.

Next, a third embodiment of the present invention will be described with reference to FIG.
2 will be described.

The third example of the similar document search system to which the present invention is applied calculates the importance of a characteristic character string extracted from a seed document, and restricts the characteristic character strings whose importance satisfies a predetermined value to a database. In this case, the frequency of appearance in each document is obtained, and the similarity is calculated based on the frequency.

That is, the present method reduces the number of characteristic character strings used for similarity calculation by reducing the number of characteristic character strings whose appearance frequency is to be acquired in the appearance frequency file reading step 1404 in the first embodiment. In addition, a high-speed similar document search can be realized even for a seed document having a large number of characters.

This embodiment has substantially the same configuration as the first embodiment (FIG. 1), but differs from the similar document search program 120, and has a characteristic character string selection program 2200 as shown in FIG.

Hereinafter, of the processing procedures in this embodiment,
Similar document search program 120 different from the first embodiment
The processing procedure of b will be described with reference to the PAD diagram of FIG.

Here, the only difference from the processing procedure of the similar document search program 120 (FIG. 14) in the first embodiment is a characteristic character string selection step 2300. The processing procedure of the other processing steps is as described in the first embodiment.

In the characteristic character string selection step 2300, the characteristic character string selection program 2200 is started, and the characteristic character string extraction step 1402 (characteristic character string extraction program 11
The importance of the characteristic character string extracted in 6) is calculated, and a character string satisfying a predetermined value is selected as a characteristic character string for similarity search.

Hereinafter, the processing procedure of the characteristic character string selection program 2200 started in the characteristic character string selection step 2300 will be described with reference to the PAD diagram of FIG.

The characteristic character string selection program 2200 first obtains the characteristic character string extracted in the characteristic character string extraction step 1402 in step 2400 and stores it in the work area 130.

Next, in step 2401, the number of documents in which each characteristic character string appears is obtained from the appearance frequency file 104.

Then, in step 2402, the importance of the characteristic character string is calculated using a predetermined importance calculation formula.

As a result, the characteristic character string whose importance level satisfies a predetermined value is limited, and this is extracted as a characteristic character string for calculating similarity (step 2403). For this importance, the commonality weight of prior art 2 may be used. In this embodiment, the following equation (2) is used for calculating the importance.

[0169]

(Equation 2)

Here, n is the number of documents in the database, Num
Doc indicates the number of appearing documents in the database of the characteristic character string. This value is the smallest when the characteristic character string appears in all the documents in the database, and becomes large when the characteristic character string appears unevenly in a specific document.

Further, as the threshold value used as a reference when extracting a characteristic character string, an upper limit importance level and a lower limit importance level may be determined in advance, or the upper k priority levels (k is 1
The above-mentioned predetermined integer) may be used.

The processing procedure of the characteristic character string selection step 2200 will be described below with reference to a specific example shown in FIG. In this figure, it is assumed that the characteristic character string 1501 extracted in the example of FIG. 15 is targeted and a characteristic character string having an importance of 3.0 or more is selected.

First, in step 1404 (FIG. 23), the number of documents in which each characteristic character string appears is obtained from the appearance frequency file 104 read into the work area 130. In this example,
As the number of appearing documents 2500 of the characteristic character string 1501 of the document 2, [software, 2], [development, 3], [seizure,
2] and [Work, 2] are obtained. Here, [software, 2] indicates that the characteristic character string “software” appears in “2” documents in the database.

Next, the number of appearance documents of each characteristic character string is 2500.
, The importance character string having an importance of 3.0 or more is extracted. As a result, one characteristic character string 2502 “software” is selected as a characteristic character string for similarity calculation.

As described above, since the number of characteristic character strings can be reduced from four to one, the time required for similarity calculation can be greatly reduced.

In this embodiment, the appearance frequency file 1
04, the number of appearing documents of each characteristic character string is acquired. However, when registering a document, the number of characteristic characters in each document is counted, and the number of appearing documents of each characteristic character string is obtained. By storing as a document number file, it is possible to select a characteristic character string even faster.

Also, in this embodiment, the appearance frequency file 1
04, the number of appearing documents of each characteristic character string is acquired and the importance is calculated. However, when the document is registered, the importance of the characteristic character string in each document is calculated and stored as an importance file. By doing so, it is possible to select a characteristic character string even faster.

Further, in the present embodiment, the number of documents in the database of the characteristic character string is used to calculate the importance. For example, the character type and character string length of the characteristic character string, the frequency of appearance in the seed document, or It can also be calculated by any one of the information such as the appearance position or a combination thereof.

As described above, according to the present invention, a character string is mechanically extracted from a seed document even when a similar document search is performed on a document such as Japanese without wording. Thus, it is possible to perform a search without omission for any word. Further, by extracting a characteristic character string according to a character type, a search can be performed using a character string with a significant meaning, so that a highly accurate similar document search can be realized. Furthermore, since the types of character strings to be extracted are greatly reduced, similar documents can be searched at high speed.

Further, when used in combination with a full-text search system, a high-speed similar document search can be realized even for a large-scale document database.

[0181]

According to the present invention, even when a similar document search is performed without using a word dictionary, the search can be performed using a character string having a significant meaning. Can be realized. Also, a substring (n-gra) with the optimal length according to the character type of the character string to be extracted
Since m) is extracted, similar documents can be searched at high speed.

[Brief description of the drawings]

FIG. 1 is a diagram showing an entire configuration of a first embodiment of a similar document search system according to the present invention.

FIG. 2 is a diagram illustrating a configuration example of an appearance frequency file.

FIG. 3 is a PAD diagram showing a flow of a characteristic character string extraction process.

FIG. 4 is a PAD showing a processing procedure of a system control program according to the first embodiment of the present invention.

FIG. 5 is a PAD showing a processing procedure of a document registration control program according to the first embodiment of the present invention.

FIG. 6 is a PAD diagram showing a processing procedure of an appearance frequency file creation program in the first embodiment of the present invention.

FIG. 7 is a PAD showing a processing procedure of a characteristic character string extraction program in the first embodiment of the present invention.

FIG. 8 is a PAD showing a processing procedure of a kanji character string corresponding characteristic character string extraction program in the first embodiment of the present invention.

FIG. 9 is a PAD showing a processing procedure of a katakana character string corresponding feature character string extraction program in the first embodiment of the present invention.
FIG.

FIG. 10 is a diagram showing a processing example of a program for extracting the same character type character string in the first embodiment of the present invention.

FIG. 11 is a diagram illustrating a processing example of a kanji character string corresponding feature character string extraction program according to the first embodiment of the present invention.

FIG. 12 is a diagram illustrating a processing example of a katakana character string corresponding feature character string extraction program in the first embodiment of the present invention.

FIG. 13 is a PAD showing a processing procedure of a search control program according to the first embodiment of the present invention.

FIG. 14 is a PAD diagram showing a processing procedure of a similar document search program in the first embodiment of the present invention.

FIG. 15 is a diagram illustrating a processing example of a characteristic character string extraction program in the first embodiment of the present invention.

FIG. 16 is a diagram showing a processing example of an appearance frequency counting program in the first embodiment of the present invention.

FIG. 17 is a diagram illustrating a processing example of an appearance frequency acquisition file reading program according to the first embodiment of this invention.

FIG. 18 is a diagram illustrating a processing example of a similarity calculation program in the first embodiment of the present invention.

FIG. 19 is a diagram showing a program configuration of a search processing system according to the second embodiment of the present invention.

FIG. 20 is a PAD diagram showing a processing procedure of a similar document search program according to the second embodiment of the present invention.

FIG. 21 is a diagram illustrating an example of an n-gram index according to the second embodiment of the present invention.

FIG. 22 is a diagram showing a program configuration of a search processing system according to a third embodiment of the present invention.

FIG. 23 is a PAD showing a processing procedure of a similar document search program according to the third embodiment of the present invention.

FIG. 24 is a PAD showing a processing procedure of a characteristic character string selection program according to the third embodiment of the present invention.

FIG. 25 is a diagram showing an example of selecting a characteristic character string in the third embodiment of the present invention.

[Explanation of symbols]

Reference Signs List 100 display, 101 keyboard, 102 central processing unit (CPU), 103 text, 104 appearance frequency file, 105 magnetic disk device, 106 floppy disk drive (FDD), 107 floppy disk, 108 Bus 109: main memory 110: system control program 111: document registration control program 112: shared library 113: text registration program 114: appearance frequency file creation registration program 115: identical character type character string extraction program 116 ... Characteristic character string extraction program for registration, 117 ... Frequency frequency file creation program, 118 ... Search control program, 119 ... Search condition expression analysis program, 120 ... Similar document search program, 121 ... Seed document reading program Ram, 123: appearance frequency counting program, 124: appearance frequency reading program, 125: similarity calculation program, 126: similarity sorting program, 127: kanji character string corresponding characteristic character string extraction program, 128 ... katakana character string corresponding characteristic character Column extraction program, 130 ... Work area

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Natsuko Sugaya 890 Kashimada, Saiwai-ku, Kawasaki-shi, Kanagawa Prefecture Inside the Information & Communication Development Division, Hitachi, Ltd. Hitachi, Ltd. Software Development Division

Claims (10)

[Claims] 1. A similar document search method for searching a text database storing character information as code data for a document similar to a document specified by a user, comprising the steps of: A character string extracting step of extracting a character string with a boundary of a predetermined character type from a boundary, and a search for extracting one or more partial character strings from the predetermined one or more character string types according to the type of the character string A similar document search method, comprising: extracting a partial character string for use; and calculating a similarity of a text in the text database with respect to the designated text using a predetermined similarity calculation formula. 2. The character string extracting step in the similar document search method according to claim 1, wherein, as the character string to be extracted from the designated text, a character string of the same character type is extracted at a boundary between all character types. A similar document search method having a character type character string extraction step. 3. A partial character string having a predetermined character string length according to all character types is extracted as a partial character string for search in the search partial character string extracting step in the similar document search method according to claim 2. A similar document search method characterized by having a character type search partial character string extraction step. 4. A method according to claim 1, wherein said step of extracting a partial character string for retrieval comprises extracting a character string having a predetermined length as a partial character string for retrieval. Extracting the character string itself extracted in the character string extraction step as a partial character string for search, calculating the appearance frequency ratio of the character string extracted in the character string extraction step and the specified character string of the partial character string, Extracting a partial character string that satisfies a predetermined value as a search partial character string; a character string created in advance from the character string extracted in the character string extraction step and not extracted as a search partial character string is unnecessary. Extracting a character string not included in the exclusion character string dictionary described as a word as a search partial character string; and extracting the character string in the character string extraction step. A step of not extracting a partial character string as a search partial character string from the character string obtained, or a step of extracting a partial character string for search by combining them. A similar document search method characterized by: 5. A predetermined length for extracting a character string having a predetermined length as a search partial character string in the search partial character string extraction step in the similar document search method according to claim 1, 2 or 3. A character string extracting step, a longest character string extracting step of extracting the character string itself extracted in the character string extracting step as a partial character string for search, a character string extracted in the character string extracting step, and designation of the partial character string A high appearance frequency ratio character string extracting step of calculating an appearance frequency ratio in the text and extracting a partial character string satisfying a predetermined value as a search partial character string; the above-mentioned predetermined long character string extracting step, the longest character string extracting step, and a high appearance From the partial character strings extracted in at least one of the frequency ratio character string extracting steps,
A step of deleting a character string included in an exclusion character string dictionary in which a character string not extracted as a search partial character string is described as an unnecessary word, and a character string extracted in the character string extraction step A step of not extracting a partial character string as a partial character string for search from, or a partial character string extraction step of extracting a partial character string for search by combining them. Similar document search method. 6. The similar document search method according to claim 1, wherein the importance of the search partial character string extracted in the search partial character string extraction step is calculated in advance. A similar document search method comprising a search partial character string selection step of extracting a search partial character string that satisfies a predetermined value, calculated using an expression. 7. The method according to claim 5, wherein the step of selecting a partial character string for search includes: a character type, a character string length, and the like of the partial character string for search extracted in the partial character string extraction step for search. An importance calculation step of calculating any one of information such as the number of appearance documents in the text database, the appearance frequency in the designated text, and the appearance position in the text, or a combination thereof to calculate the importance of the partial character string for search A similar document search method characterized by having: 8. A similar document search method according to claim 6, further comprising an appearance document number file creation step of saving the number of occurrence documents in the text database of the partial character string for search at the time of registration as an appearance document number file. A similarity document search method characterized in that the importance calculation step at the time of reading includes an appearance document number file reading step of reading the number of occurrence documents of the search partial character string from the occurrence document number file. 9. A similar document search method according to claim 6, wherein at the time of registration, the importance of the search partial character string is calculated using a predetermined calculation formula, and this is stored as an importance file. A similarity file search step having an importance file creation step; and an importance file reading step for reading the importance of the search partial character string from the importance file in the importance calculation step at the time of search. Method. 10. A similar document search method according to claim 1, further comprising an appearance frequency file creation step of saving an appearance frequency of each partial character string for search in each text in the text database as an appearance frequency file at the time of registration. A similar document search method, characterized in that the similarity calculation step at the time of retrieval includes an appearance frequency file reading step of reading appearance frequency information from the appearance frequency file.