JPH1153381A - Device and method for retrieving similar document - Google Patents

Abstract

PROBLEM TO BE SOLVED: To retrieve the similar documents in consideration of their frequency of occurrence and also to simultaneously retrieve plural similar retrieving and retrieved object documents with high accuracy and high efficiency by calculating the similarity between both document data based on a word frequency table and a document norm table. SOLUTION: A main processing part 11a takes a word frequency table out of a retrieving object/word frequency table store buffer 11j and a retrieved object/word frequency table store buffer 11k respectively and transfers its processing to a word correspondence table production part 11d. When a word correspondence table is produced at the part 11d and stored in a word correspondence table store buffer 11m, the part 11a transfers its processing to a similarity calculation part 11e. The part 11e refers to the word correspondence table and a document norm table to calculate the similarity between the retrieving and retrieved object documents for each paragraph of word frequency tables of both retrieving and retrieved object documents. Then the similarity is calculated between both documents by calculating the average similarity value of paragraphs, etc., and this calculation result is outputted to an external storage.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an electronic document data search apparatus, and more particularly to a similar document search apparatus and a similar document search method for searching document data similar to certain document data.

[0002]

2. Description of the Related Art In recent years, a large amount of electronic document data has been distributed, and a system for automatically retrieving a document similar to a designated document from a document database for the purpose of automatic classification and the like has been put into practical use. Is coming. In these systems, when searching for a similar document of a specified document (this is referred to as a search target document), a search is made between this search target document and another document (this is referred to as a search target document). Calculate similarity that reflects the number of common word types,
The one with the larger value is output as a search result.

For example, as shown in FIG. 27, several words i1, i2,..., In are specified in advance as primary search conditions, and m pieces of document data b1, b2, .., Bm, the presence or absence of individual primary search condition words i1, i2,. After creating the word presence / absence table for each document as described above, the primary search condition words i1, i2,.
n, a number of words existing in the search target document are designated as secondary search conditions, and a document containing more words is determined by referring to the above-mentioned word presence / absence table. Output as result.

[0004]

However, in such a conventional similar document search system, similar search is performed only based on the presence / absence of a word serving as a search condition in the search target document. Therefore, the weight of the search condition word in the search target document is not taken into account, and a long document containing more types of words is always easily selected as a similar document candidate. It has been pointed out that there is. Further, in the above-described conventional method, every time a search for a similar document is performed, a word that exists in the search target document and that well represents the characteristics of the document is correctly specified as a secondary search condition. Words must always be excluded from secondary search conditions, and when selecting secondary search conditions, for example, an operator needs to refer to the search target document to find a key word, which requires artificial labor. There was also a problem.

The present invention has been made to solve such a problem, and an object of the present invention is to provide a similar document search device and a similar document search method which have high search accuracy and can perform high-speed processing.

[0006]

According to another aspect of the present invention, there is provided a similar document search apparatus comprising: a storage unit for storing a plurality of document data; and a document stored in the storage unit. For each data, a word frequency table creating means for finding a frequency of appearance for each preset search condition word to create a word frequency table, and for each document data stored in the storage means, the word frequency table creating means Document norm table creating means for calculating a norm of a one-dimensional vector having an appearance frequency for each search condition word in the created word frequency table as an element to create a document norm table, and document data stored in the storage means Means for designating the document data to be searched and searched for from among the document data; and the similarity between the document data designated by the designating means, the word frequency table and the document norm. And having a similarity calculation means for calculating, based on the.

According to the present invention, a similar document search can be performed in consideration of the frequency of occurrence of search condition words in document data.
Further, it becomes possible to perform a similar document search for a plurality of search target documents and a plurality of search target documents simultaneously with high efficiency and high accuracy.

According to the first aspect of the invention, a word frequency table and a document norm table are calculated and stored in advance for each document data stored in the storage means, and the search target and the search target document data are designated. Then, the similarity calculating means obtains the similarity between the document data from the word frequency table and the document norm table of the corresponding document data, so that a plurality of documents to be searched and a plurality of documents to be searched are successively obtained. Is performed, that is, after calculating the similarity between one search target document and each search target document, the similarity search between the next one search target document and each search target document is performed. Even when the similarity calculation is performed, high-speed processing can be performed because the creation of the word frequency table and the norm calculation for each document to be searched need to be performed only once.

Further, according to a second aspect of the present invention, there is provided a similar document search apparatus, wherein a storage means for storing a plurality of document data, and a predetermined search condition word for each of the document data stored in the storage means. A word frequency table creating means for creating a word frequency table by obtaining an appearance frequency; and for each document condition stored in the storage means, for each search condition word in the word frequency table created by the word frequency table creating means. A document norm table creating means for calculating a norm of a one-dimensional vector having an appearance frequency as an element to create a document norm table; and a search target and a search target document data from the document data stored in the storage means. The designation means to designate, and the registration position relationship of common words between the respective word frequency tables created by the word frequency table creation means for each document data designated by the designation means are shown. Word correspondence table creation means for creating a word correspondence table, and similarity calculation for calculating the similarity between the respective document data designated by the designation means based on the word frequency table, the document norm table and the word correspondence table. Means. According to the present invention, in calculating the similarity between the respective document data, the commonality between the word frequency table of the search target document and the word frequency table of the search target document, which is necessary for calculating the inner product of the vector data of each word frequency table Since the appearance frequency information of a word can be uniquely obtained by referring to the word correspondence table, it is possible to further speed up the processing. Further, in order to achieve the above object, a similar document search method according to the present invention provides, for each of the individual document data stored in a document database,
A step of creating a word frequency table by obtaining the appearance frequency of each preset search condition word; and for each document data stored in the document database, for each search condition word in the created word frequency table. Calculating a norm of a one-dimensional vector having an appearance frequency as an element to create a document norm table; and specifying document data to be searched and searched for from document data stored in the document database. , The similarity between the specified document data,
A step of calculating based on the word frequency table and the document norm table. The operation and effect of the present invention are equivalent to those of the first embodiment.

Further, according to the similar document search method of the present invention, the appearance frequency of each preset search condition word is determined for each document data stored in the document database. Creating a word frequency table, and calculating, for each document data stored in the document database, the norm of a one-dimensional vector having an appearance frequency for each search condition word in the created word frequency table as an element Creating a document norm table, specifying a search target and a search target document data from the document data stored in the document database, and generating a document norm table for each of the specified document data. Creating a word correspondence table indicating the registered positional relationship of common words between the respective word frequency tables, and calculating the similarity between the designated document data by using the word frequency table and the sentence. Is intended and characterized by a step of calculating, based on the norm table and word alignment table, the action of the present invention, the effect is the same equivalent of the invention of claim 2.

[0011]

Embodiments of the present invention will be described below in detail with reference to the drawings.

FIG. 1 is a diagram showing a hardware configuration of a similar document search apparatus according to an embodiment of the present invention.

As shown in FIG. 1, the similar document search device includes an input device 1, a display device 2, a control device 3, a memory 4,
It comprises an external storage device 5 and a communication device 6, and each device is connected to each other via a bus.

The input device 1 is composed of a keyboard, a mouse, a tablet, a touch panel or the like, and inputs a character string and inputs various data and commands to the apparatus.
The display device 2 includes a CRT or a liquid crystal display and a display controller, and displays search results and instructions from the system to the user. The control device 3 is configured by a CPU, and performs processes such as control of each device and transfer of data between the devices.

The memory 4 comprises a RAM or the like. As shown in FIGS. 2 and 3, the control device 3 stores a program for storing programs for executing various controls and processes, and stores data necessary for the processes. It consists of a buffer for storing.

The program section includes, as shown in FIG. 2, a main processing section 11a for controlling the entire processing, and a main processing section 11a for controlling the whole processing, as shown in FIG. As a called subroutine,
It comprises an initialization section 11b, a norm calculation section 11c, a word correspondence table creation section 11d, a similarity calculation section 11e, an output editing section 11f, a document list display section 11g, a document selection section 11h, and a document content display section 11i.

As shown in FIG. 2, the buffer unit includes an input document data storage buffer 10b, a word ID-word table storage buffer 10c, and a work area for the word extraction unit 10a.
It comprises a word frequency table storage buffer 10d and a word extraction table storage buffer 10e. As the work areas of the main processing unit 11a, as shown in FIG. 3, a search target / word frequency table storage buffer 11j, a search target / word frequency table storage buffer 11k, a document norm table storage buffer 111, a word correspondence table storage There is a buffer 11m, a similarity calculation result storage buffer 11n, and an output editing result storage buffer 11o.

The input document data storage buffer 10b stores document data as shown in FIG. In FIG. 4, A, B, and C are individual sections of one document. In the word ID-word table storage buffer 10c, as shown in FIG.
A word ID-word table data in a format indicating the correspondence between the word and the word is stored. In the word frequency table storage buffer 10d, FIG.
Alternatively, a word frequency table in a format as shown in FIG. 7 is stored. The search target / word frequency table storage buffer 11j stores a word frequency table of a search target document in a format as shown in FIG. The search target / word frequency table storage buffer 11k stores a word frequency table of the search target document in a format as shown in FIG. The document norm table storage buffer 111 stores a document norm table in a format as shown in FIG. The word correspondence table storage buffer 11m stores a word correspondence table in a format as shown in FIG. The similarity calculation result storage buffer 11n stores similarity calculation results in a format as shown in FIG. Output editing result buffer 11o
Stores an output editing result of a similarity calculation result in a format as shown in FIG.

In the buffer section, other areas 10f and 11p for working variables are secured. In the areas 10f and 11p for these work variables, variables used in the processing described later include the total number dat of the search target / word frequency table, the total number dbt of the search target / word frequency table, and the total number of documents dt. In addition, da is secured as the ID of the search target / word frequency table currently being referred to, and db is secured as the ID of the search target / word frequency table.

The external storage device 5 comprises a hard disk, a flash memory or a magneto-optical disk and a controller, and stores document data, a word frequency table, a word extraction table, and the like. FIG. 12 shows the storage format of the document data and the word frequency table stored in the external storage device 5, and FIG. 13 shows the storage format of the word extraction table. As shown in FIG. 12, each document data includes a header section storing attribute data such as a document title, a file creation date and time, and a creator, and a text data section which is character code data constituting the document. And these are stored in order of ID. The word extraction table is referred to when extracting a word when creating a word frequency table from text data. This word extraction table is arbitrarily set by, for example, an operator.

The word ID-word table shown in FIG.
It is created based on the word extraction table of FIG.
An actual word corresponding to the word ID is described. This word ID-word table is used for conversion between word IDs and words.

The word frequency table shown in FIG. 6 is created from individual document data by a word extraction process. The word frequency table includes a word ID for each section which is a component of the document.
-The appearance frequency of the word corresponding to the word ID described in the word table (the word described in the word extraction table) is described. Note that the contents of the word frequency table shown in FIG. 6 are examples in which the document data shown in FIG. 4 is subjected to word extraction processing. In this word frequency table, word appearance frequency information is described for each of the nodes A to Z of the document data.

In the document norm table shown in FIG. 8, the magnitude (norm) of a vector for each clause (A to Z) for each word frequency table is described.

The word correspondence table shown in FIG. 9 is a table temporarily created when the similarity calculation process is performed. In this word correspondence table, the word ID described in the word frequency table of the search target document shown in FIG. 6 and the same word ID in the word frequency table of the search target document shown in FIG.
And information for associating with. Specifically, in the case of a word ID that is commonly present in the search target document and the search target document, the offset position of the word ID on the word frequency table of the search target document is described as the association information. . In the case of a word ID that does not exist in the search target document, a value indicating this (for example, (-1)) is described. This word correspondence table is used for the purpose of calculating the inner product by the minimum necessary calculation when calculating the similarity between document data.

The similarity calculation result shown in FIG. 10 is a table created by the similarity calculation process, and describes each similarity of each search target document with respect to one search target document.
Here, when all the search target documents are divided into r blocks, r (2 in the example of FIG. 10) similarity calculation results corresponding to one search target document are created. That is,
In FIG. 14A, as search target documents, a1 to an
, And n documents bl to bn are given as search target documents. Assuming that n = 10 and the number of divisions r = 2, the number of documents in one block is 5. In this example, as shown in FIG. 14C, as the similarity calculation results, o11 (similarity corresponding to bl to b5) and o12 (similarity corresponding to bn-4 to bn) are obtained for the search target document a1. 2
One is obtained.

The communication device 6 is a device for exchanging data with the outside via a communication line, and includes, for example, a LAN line and a LAN controller.

The operation of this embodiment will be described below.

As shown in FIG. 12, the external storage device 5
It is assumed that n document data having document IDs 0 to n and a word frequency table corresponding to each document data are stored.

In the description of the operation, first, the overall processing operation of the present apparatus will be described, and then details of each important processing will be described.

The program processing in the present apparatus includes two processes, a word extraction process and a main process. The word extraction process is a process for creating a word frequency table from document data. The main process is a process of searching for a similar document using the word frequency table created in the word extraction process. Therefore, the word extraction processing is performed before the main processing.

FIG. 15 is a flowchart showing the overall procedure of the word extraction process.

The word extracting unit 10a clears the buffers in the buffer units 10b to 10f immediately after the activation. Also,
The word extraction unit 10a stores the word extraction table (FIG. 13) stored in the external storage device 5 in a word extraction table storage buffer 10d.
Then, the word ID-word table (FIG. 5) is stored in the word ID-word table storage buffer 10c (step S1).
At this time, the word extracting unit 10a creates a word ID-word table with reference to the word extraction table (FIG. 13), and
-Store in the word table storage buffer 10c.

Next, the word extracting section 10a is connected to the external storage device 5
Is read out, word frequency tables (FIGS. 6 and 7) corresponding to the document data are created, and stored in the external storage device 5 (step S2). When the creation and storage of the word frequency tables for all the document data have been completed, the word extraction processing ends (step S3).

Next, the operation of the main processing will be described with reference to FIG.

When the main processing unit 11a is started, the initialization unit 11b first clears each of the buffer units 11j to 11p, and sets the number of word frequency tables of the documents to be searched and the documents to be searched as variables. Then, various initialization processes necessary for similar document search are performed (step S4).

Thereafter, the norm calculation unit 11c is started. The norm calculation unit 11c calculates the word I for each section of the search target document and the search target document stored in each word frequency table.
The norm (= vector size) of a one-dimensional vector having the word appearance frequency as an element for each D is calculated, a document norm table is created on the document norm table storage buffer 111, and output to the external storage device 5 (step). S5).

When the document norm table is created, the main processing section 11a reads the word frequency table (FIG. 6) of the number of documents to be searched specified in the initialization processing S4 from the external storage device 5, and retrieves the words to be searched. The data is stored in the frequency table storage buffer 11j (step S6). Next, the main processing unit 11a reads the word frequency table (FIG. 7) of the designated number of documents to be searched from the external storage device 5 and stores it in the search object / word frequency table storage buffer 11k (step S7). .

Thereafter, the main processing unit 11a searches for
One word frequency table is extracted from each of the word frequency table storage buffer 11j and the search target / word frequency table storage buffer 11k, and the process is passed to the word correspondence table creating unit 11d. The word correspondence table creation unit 11d creates a word correspondence table (FIG. 9),
When this is stored in the word correspondence table storage buffer 11m (step S8), the main processing unit 11a passes the processing to the similarity calculation unit 11e. The similarity calculating unit 11e calculates the similarity between each of the word frequency tables of the search target document and the search target document with reference to the word correspondence table and the document norm table. Then, the similarity between the documents is calculated by, for example, averaging the similarity for each node, and the similarity calculation result is output to the external storage device 5 (step S9).

Then, with respect to the word frequency tables of all the documents to be searched (for the specified number) stored in the search target / word frequency table storage buffer 11j, all of the word storage tables (designated numbers) stored in the search target / word frequency table storage buffer 11k are stored. Steps S8 and S9 are repeated until the similarity calculation with the word frequency table of the searched document (several minutes) is completed (step S1).
0).

Thereafter, the word frequency tables of the next specified number of documents to be searched are read from the external storage device 5, and the word frequency tables for the documents to be searched are stored in these word frequency tables.
Is rewritten, and the search target / word frequency table storage buffer 11
As for the word frequency tables of all (specified number of) search target documents stored in j, the search target / word frequency table storage buffer 11k stores all (specified number of) search target documents in the same manner as described above. Steps S7 to S10 are repeated until the calculation of the similarity with the word frequency table is completed (step S1).
1).

Thereafter, the word frequency tables of the next specified number of search target documents are read from the external storage device 5, and the search target / word frequency table storage buffer 11j is rewritten with these word frequency tables to similarly calculate the similarity. Is performed (step S12).

Next, the processing from steps S6 to S12 will be specifically described with reference to FIG.

First, the range surrounded by the thick line frame in FIG. 14A, that is, the word frequency tables a1 to a1 of a plurality of search target documents.
a5 and the word frequency tables b1 to b5 of a plurality of documents to be searched are collectively written in the memory, and the word frequency table a1 of the first document to be searched and the word frequency tables b1 to b of each document to be searched.
5 and outputs a similarity calculation result o11 as shown in FIG. Subsequently, as shown in FIG. 14B, the similarity calculation is performed for each of the word frequency table a2 of the next search target document and the word frequency tables b1 to b5 of the search target document, and the similarity calculation result o21 is obtained. Is output. Similarly, the similarity calculation is performed between the word frequency tables a3, a4, a5 of the search target document and the word frequency tables b1 to b5 of the search target document, and the similarity calculation results o31, o41, o51 are output.

Next, as shown in FIG. 14C, the reserved area of the word frequency table of the search target documents b1 to b5 on the memory is released, and the search target documents bn-4 to bn are stored there. Write the word frequency table of Then, in the same manner as described above, the similarity between the word frequency tables a1 to a5 of the search target document and the word frequency tables bn-4 to bn of the search target document is calculated, and the similarity calculation result o12 is output.

Thereafter, as shown in FIG. 14D, the reserved area of the word frequency table of the search target documents a1 to a5 in the memory is released, and the next specified number of search target documents are stored there. The word frequency tables an-4 to an are written, the reserved area of the word frequency table of the search target documents bn-4 to bn on the memory is released, and the word frequency tables b1 to b5 of the search target documents are re-stored there. Is written, and the similarities between the word frequency tables an-4 to an of the search target document and the word frequency tables b1 to b5 of the search target document are calculated in the same manner as described above. The reserved areas of the word frequency tables b1 to b5 are released, and the word frequency table bn of the search target document is stored therein.
-4 to bn are written, and the similarity is calculated in the same manner.

As described above, the similarities between the word frequency tables of all the documents to be searched existing in the external storage device 5 and the word frequency tables of all the documents to be searched are calculated. Is stored in the main processing unit 11a
Transfers control to the output editing unit 11f.

The output editing unit 11f sequentially reads the similarity calculation results of the individual search target documents and all the search target documents stored in the external storage device 5, and, for example, ranks a higher similarity higher rank. Are stored in the external storage device 5 as output editing results as shown in FIG. 11 (step S13).

When the output and editing results corresponding to all the search target documents are stored in the external storage device 5, the main processing section 11a displays a document list screen as shown in FIG. 18 via the document list display section 11g. The document is output to the device 2 (step S14), and the document selection unit 11h is subsequently activated (step S15). The document list screen is provided with input items for the user to input the ID of the search target document. By inputting the search target document ID (for example, a1) to the input item through the document selection unit 11h, A list of search target document IDs that are the search results and their similarities are displayed.

By selecting a check box corresponding to the search target document ID with a pointing device such as a mouse, the document content display section 11i is activated and, as shown in FIG. The degree and the contents of the document are displayed (step S16).

The display processing of these similar search results is shown in FIG.
Alternatively, the process ends by selecting a close box at the upper left of the screen shown in FIG. 19 with a pointing device or the like (step S17).

Next, a word extraction process in step S2, an initialization process in step S4, a norm calculation process in step S5, a word correspondence table creation process in step S8, and a step S9
The similarity calculation process and the output editing process in step S13 will be specifically described.

First, the word extraction process in step S2 will be described. FIG. 20 is a detailed flowchart showing the word extraction processing in step S2.

When the environment such as the number of documents is set in the initialization processing step S1 in a state where the document data is stored in the external storage device 5, the word extracting unit 10a starts. The word extracting unit 10a stores the specified input document data in the input document data storage buffer 10b (Step S21). Next, the word extracting unit 10a refers to the word extraction table, extracts words included in the word extraction table from the input document data, and stores the words in the work area (step S22).

Next, the word extracting section 10a refers to the word ID-word table, and if the extracted word is not already registered in the word ID-word table, shifts the control to step S25. To step S24 (step S23). In step S24, a process of adding a word that has not been registered in the word ID-word table is performed. Further, a new word ID is issued for the corresponding word (step S24). The word stored in step S22 is replaced with a word ID based on the word ID-word table (step S25).

Next, the word extraction unit 10a recounts the words stored in the work area, checks the appearance frequency of the word (the same word as the word included in the word extraction table) for each section of the document data, and as a result, Is written into the word frequency table storage buffer 11m (step S26). When the calculation of the word appearance frequency and the writing of the calculation result have been completed for all the sections of the document data, the process proceeds to the next step 28 (step S27). Finally, the word extraction unit 10a outputs the contents written in the word frequency table storage buffer 11m to the external storage device 5 as a word frequency table (Step S28).

Next, the initialization processing in step S4 will be described. FIG. 21 is a flowchart showing details of the initialization processing.

When the word frequency table is stored in the external storage device 5, the main processing unit 11a transfers control to the initialization unit 11b. The initialization unit 11b stores an area 11p for a work variable.
When storing the word frequency tables in the word frequency table storage buffers 11j and 11k of the search target document and the search target document as work variables, the number of documents read at one time: sep, and the search target / word frequency table Total number: dat, total number of search target / word frequency tables: dbt, total number of word frequency tables: dt, ID of search target / word frequency table to be calculated: da, target search / word frequency table to be calculated ID: db is prepared. In addition, initial values are assigned to these variables. In the present embodiment, the number of documents to be read sep is 5, and other variables are 0.
Is substituted (step S41).

Thereafter, the initialization unit 11b stores the external storage device 5
The number of word frequency tables of the search target document is checked, and the value is substituted for the total number dat of the search target / word frequency table (step S42). Further, the initialization unit 11b checks the number of word frequency tables of the search target document in the external storage device 5 and substitutes it into the total number dbt of the search target / word frequency tables (step S4).
3). Finally, the initialization unit 11b calculates the total number dat of the search target / word frequency table and the total number db of the search target / word frequency table.
t is substituted for the total number dt of the word frequency table (step S
44).

Next, the norm calculation processing in step S5 will be described. FIG. 22 is a flowchart showing details of the norm calculation processing.

The norm means that a one-dimensional matrix is represented by A = [a1,
a2, ..., an],

(Equation 1) Is the value represented by In the present embodiment, since one document data is divided into a plurality of sections, p norms equal to the number of sections are calculated for each document ID in the document norm table.

The norm calculation processing is performed as follows. When the processing of the initialization unit 11b is completed, the main processing unit 11
The control is returned to a, and the main processing unit 11a transfers the control to the norm calculation unit 11c. The norm calculation unit 11c stores, in the area 11p for the working variable, as the working variable, the clause being referred to: p, the total number of clauses: pt, the word ID being referenced: q, the total number of words: qt, Document: d, frequency of appearance of the word being referred to: f, work: w, norm: norm. Further, the initial value 0 is substituted into these variables (step S5).
01).

Next, the norm calculation unit 11c reads out the document norm from the external storage device 5 and stores it in the document norm table storage buffer 111 (step S502). Subsequently, the norm calculation unit 11c stores the d-th word frequency table stored in the external storage device 5 in the search target / word frequency table storage buffer 1.
1j (step S503). Further, the norm calculation unit 11c stores a search target / word frequency table storage buffer 11j.
Read the total number of clauses and the total number of words from
Substitute t and qt (step S504).

Subsequently, the norm calculation unit 11c checks the word appearance frequency for each of the designated clause: p and the word ID: q, and substitutes the word appearance frequency for f (step S505). Also,
To find the norm of the specified clause: p, the value obtained by squaring the word appearance frequency f of the specified word ID: q is used as the work variable w.
(Step S506). Further, the value of q is incremented by 1 to advance the word ID (step S5).
07). Steps S505 to S507 are repeated until all the words of the designated section are referred to (step S505).
508).

Next, the norm calculator 11c calculates the norm of the node p. The norm of the node p is obtained by norm ← W ^1/2 , and the obtained norm of the node p is stored in a corresponding portion of the document norm table storage buffer 111 (step S509). Subsequently, to calculate the norm of the next section, the word q and the norm work area w are cleared (step S51).
0). When the norm calculation for all the nodes is completed, the control is moved to step S512 (step S511). In step S512, the value of d is set to 1 in order to advance the next document $ D.
Go forward. When the above-described norm calculation is completed for all the documents, the control proceeds to step S514 (step S513), and finally, the document norm table storage buffer 111
Is output to the external storage device 5 as a document norm table (step S514).

Next, the word correspondence table creation processing in step S8 will be described. FIG. 23 is a flowchart showing details of the word correspondence table creation processing.

When the document norm table is stored in the external storage device 5, the main processing section 11a transfers control to the word correspondence table creating section 11d. The word correspondence table creating unit 11d receives the values of the ID of the search target / word frequency table: da and the ID of the search target / word frequency table: db specified in step S4. This value is the document ID of the word frequency table that is referred to when creating the word correspondence table (step S801).

Next, as shown in FIG. 9, the word correspondence table creator 11d stores, in the word correspondence table storage buffer 11m, the same number of word correspondences as the number of words used in the word frequency table of the search target document. A table is created, and the position information fields of the word IDs in the search target document are all filled with initial values ((-1) in the example) (step S802).

Subsequently, the word correspondence table creator 11d stores the search target document I from the search target / word frequency table storage buffer 11j.
Reference is made to the word frequency table of D = da and the word frequency table of the search target document ID = db from the search target / word frequency table storage buffer 11k. Here, the words used in the search target / word frequency table are matched with the words used in the search target / word frequency table, and the words in the search target / word frequency table are included in the search target / word frequency table. If it is found, the position information of the word in the search target / word frequency table is written into the word correspondence table of the word correspondence table storage buffer 11m, and the word in the search target / word frequency table becomes the search target / word frequency table. If not included, an arbitrary value (in the example, (-1)) indicating "no reference destination" is written in the word correspondence table (step S80).
3).

If there is no longer any of the number of words in the search target / word frequency table or the number of words in the search target / word frequency table, the word correspondence table creating unit 11d advances the control to step S805. Otherwise, control is returned to step S803 to repeat step S803 (step S8
04). When the number of words in the search target / word frequency table is larger than the number of words in the search target / word frequency table, the word correspondence table creating unit 11d transfers control to step S806, and otherwise transfers control to step S9 ( Step S805).

When the number of words in the search target / word frequency table is larger than the number of words in the search target / word frequency table, the word correspondence table creating unit 11d leaves a blank in the word correspondence table of the word correspondence table storage buffer 11m. Step S803
An arbitrary value indicating "no reference destination" is written in the same manner as (1) (step S806).

Next, the similarity calculation processing in step S9 will be described. FIG. 24 and FIG. 25 are flowcharts showing details of the similarity calculation processing.

The document similarity s is a similarity: s, the similarity sp of each section, the number of sections i, the search target of each section, a vector having the word appearance frequency as an element, and the search target of each section When a vector having a word appearance frequency as an element is fbp,

(Equation 2) It is represented by

When the word correspondence table is stored in the word correspondence table storage buffer 11m, the main processing unit 11a transfers control to the similarity calculation unit 11e. The similarity calculating unit 11e stores, as working variables, in the area for working variables 11p, the section being referred to: p, the total number of sections: pt, the word ID being referred to: q, the total number of words: qt, and the search target. Word appearance frequency of document: fa, word appearance frequency of search target document: fb, work: w, norm work of search target document: norma, norm work of search target document: normb, document similarity: s And an inner product: innprd [pt] and a similarity per node: sp [pt] as an array of size pt, and assign initial values to these variables (step S901).

Next, the similarity calculating section 11e proceeds to step S4
The document ID of the search target / word frequency table specified in the above: d
a, The value of the document ID: db of the search target / word frequency table is received. This document ID is the same as the document ID received in step S8 (step S902).

Subsequently, the similarity calculating section 11e determines in step S
Referring to the word correspondence table created in the word correspondence table storage buffer 11m in step 8, the position information in the search target / word frequency table in the section p and the word q is read. If the position information is “no reference destination (−1)”, control is performed in step S904.
Otherwise, control is passed to step S905 (step S903).

If the reference destination is “no reference destination” in step S 903, the similarity calculation unit 11 e sets the node p, the word q
In step S904, 0 is substituted for a variable fa for storing the word appearance frequency of the search target document. In step S903, when the reference destination includes any value other than “no reference destination”, the similarity calculation unit 11e determines the word appearance frequency fa of the search target document in the node p and the word q.
Then, the word appearance frequency of the search target document is substituted for the search target document, and the word appearance frequency of the search target document is substituted for the word appearance frequency fb of the search target document (step S905).

When the word appearance frequency fa of the search target document and the word appearance frequency fb of the search target document are set, the similarity calculator 11e calculates the inner product of each node. The inner product of nodes innprd [p] is expressed by innprd [p] ← innprd [p] + fa × fb (step S906).

If the similarity calculation unit 11e calculates the inner product of all the clauses of the word frequency table, the process proceeds to step S908.
If the calculation is in progress, control is transferred to step S903 (step S907). Further, the similarity calculation unit 11e proceeds to step S909 if the calculation has been completed for all the words in the word frequency table, and proceeds to step S9 if the calculation is in progress.
The control is shifted to 03 (step S908).

The above is the calculation of the numerator of the similarity for each node. Next, calculation regarding the denominator is performed.

First, the similarity calculating section 11e determines in step S5
With reference to the document norm table calculated in step (909),
Document ID = da, norm in section p is set to variable norma
And the norm in the document ID = db and the section p is set to the variable nor
mb (step 910).

Next, the similarity calculating section 11e obtains the similarity sp [p] of the node p. The similarity sp [p] of the node p is calculated from spnprd [p] calculated in step S906 and norma and normb in step S910, as follows: sp [p] ← inprd [p] / (norma × no)
rmb) (step S911).

Subsequently, the similarity calculating unit 11e checks the node p. If the similarities of all the nodes have not been obtained, the control returns to step S901. If the similarities of all the nodes have been obtained, the control returns to step S901. The control proceeds to step S913 (step S912).

Here, the similarity of the document is obtained. Here, assuming that the total number of sections is pt, the section is p, and the similarity of the section p is sp [p], the document similarity s is

(Equation 3) (Step S913).

Finally, the similarity calculating section 11e determines in step S
The document similarity s obtained in 913 is output as a similarity calculation result to the external storage device 5 together with the document ID of the search target (step S914).

Next, the output editing process in step S13 will be described. FIG. 26 is a flowchart showing details of the output editing process.

The output editing unit 11f outputs a plurality of divided similarity calculation results stored in the external storage device 5 as one output editing result. Here, the role of the output editing unit 11f will be described.

In this method, as shown in FIG.
The similarity calculation results of the search target document a1 and the search target documents b1 to bn are two files o11 and o12. For this reason, a process for integrating the plurality of divided similarity calculation results into one output editing result is required.

First, when all the similarity calculation results are stored in the external storage device 5, the main processing section 11a transfers control to the output editing section 11f. The output editing unit 11f reads the divided similarity calculation result from the external storage device 5 and writes it into the similarity calculation result storage buffer 11n (step S13).
1).

Next, the output editing unit 11f determines the division number assigned to each similarity calculation result (when the similarity calculation result is divided into two files, the division number of the first similarity calculation result is 1,
The division number of the next similarity calculation result is 2. ) Check r. When the total number of divisions is dr, the division number r <
During dr, the control returns to step S131, and otherwise, the control proceeds to S133 (step S132). FIG.
In the example, the similarity calculation result is read in the order of o11 → o12.

When all of the divided similarity calculation results are stored in the similarity calculation result storage buffer 11n, the output editing unit 1
1f performs sorting using the document similarity as a key (step S1).
33), the output editing result (FIG. 11) is written to the output editing result storage buffer 11o, and then output to the external output device 5 (step S134).

In this embodiment, the similarity calculation result corresponding to the similarity calculation result o11 in FIG.
# 1 ”, the similarity calculation result corresponding to o12 is represented by“ a ”in FIG.
1 # 2 ", an output editing result as shown in FIG. 11 is obtained. That is, the pieces of information are rearranged in descending order of similarity.

Further, the output editing unit 11f deletes the similarity calculation result read in steps S131 and S132 from the external output device 5 (step S135). Finally, check whether all the similarity calculation results have been output edited. If the output editing process is in progress, the control returns to step S131, otherwise the control proceeds to S14 (step S136).

As described above, the similar document search apparatus of the present embodiment can perform a similar document search with higher reliability than the conventional one in consideration of the frequency of occurrence of a specific word (word in the word extraction table) in the document data. At the same time, a similar document search for a plurality of search target documents and a plurality of search target documents can be performed with high efficiency and high accuracy.

In addition, a word frequency table and a document norm table are created in advance for each document data stored in the external storage device 5, and the word frequency of each document is specified when each of the documents to be searched and searched is specified. When the similarity between document data is calculated by referring to the table and the document norm table, the similarity between a plurality of search target documents and a plurality of search target documents is continuously calculated, that is, one search target After calculating the similarity between a document and each document to be searched and then calculating the similarity between the following one document to be searched and each document to be searched, it is necessary to create a word frequency table and calculate the norm. There is no need to perform the processing repeatedly, and high-speed processing can be performed.

Further, in this embodiment, in calculating the similarity between the search target document and the search target document, the word frequency table of the search target document and the search target document required for the inner product of the vector data of each word frequency table are calculated. Since the appearance frequency information about the common word with the word frequency table of the target document can be uniquely obtained by referring to the word correspondence table, it is possible to further speed up the processing.

Further, in this embodiment, as described with reference to FIG. 14, each word frequency table of the search target document and the search target document is called from the external storage device 5 into the memory in units of a plurality of groups. , Calculate the similarity between the document to be searched and the document to be searched in as many combinations as possible, and successively call the word frequency tables of the documents to be searched and the document to be searched in the next group into the memory (rewrite T) Similarly, by performing the similarity calculation, the number of accesses to the external storage device 5 can be reduced.

For example, if the number of word frequency tables in the document to be searched is m, the number of word frequency tables in the document to be searched is n, the number of divisions is v, and the clause is 1, this method reads the word frequency table. Sometimes nv + m times, when writing the similarity calculation result, vm
Times, and vm times when reading the similarity calculation result during output editing and m times when writing the output editing result, for a total of 2 m
(V + 1) + nv accesses occur. This can be represented as O (m + n) as a calculation order.

As a comparative example, as shown in FIG. 17, a method of calculating the similarity by calling the word frequency table of the search target document and the word frequency table of the search target document one by one in the memory will be considered. In this case, the number of accesses to the external storage device 5 is nm times when reading the word frequency table and m times when writing the similarity calculation result, that is, a total of m (n + 1) times.
This is O (mn) as the calculation order, and it can be said that the number of accesses to the external storage device 5 of this method is extremely small.

When this is expressed by specific values, when the number of word frequency tables of the document to be searched is 100, the number of word frequency tables of the document to be searched is 100, and the number of divisions is 2, 8
In the method of the comparative example, file access occurs 10,100 times.

Furthermore, in the present embodiment, the word frequency table is structured to include a plurality of sections, so that the similarity can be obtained for each section such as a document title outline and a body, and more accurate. High similarity search results can be obtained.

[0101]

As described above, according to the first and third aspects of the present invention, it is possible to perform a similar document search in consideration of the frequency of occurrence of a search condition word in document data. A similar document search for a target document and a plurality of search target documents can be performed with high efficiency and high accuracy.

According to the first and third aspects of the present invention, a word frequency table and a document norm table are created in advance for each document data stored in the storage means, and the document data to be searched and to be searched are By specifying the similarity between the document data from the word frequency table and the document norm table of each applicable document data at the specified location, the similarity for multiple search target documents and multiple search target documents in succession Even when performing a document search, there is no need to duplicately create the word frequency table and calculate the norm, and high-speed processing can be performed.

Further, according to the second and fourth aspects of the present invention, in calculating the similarity between document data, the word frequency table of the document to be searched, which is necessary for calculating the inner product of the vector data of each word frequency table Since the appearance frequency information about the common word between the search target document and the word frequency table of the search target document can be uniquely obtained by referring to the word correspondence table, the processing speed can be further increased.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a hardware configuration of a similar document search device according to an embodiment of the present invention.

FIG. 2 is a diagram showing a configuration of a memory in FIG. 1;

FIG. 3 is a diagram showing a configuration of a program unit and a buffer unit in the memory of FIG. 2;

FIG. 4 is a diagram showing a structure of document data.

FIG. 5 is a diagram showing a structure of a word ID-word table.

FIG. 6 is a diagram showing a word frequency table of a search target document.

FIG. 7 is a diagram showing a word frequency table of a document to be searched;

FIG. 8 shows a document norm table.

FIG. 9 is a diagram showing a word correspondence table.

FIG. 10 is a diagram showing a similarity calculation result;

FIG. 11 is a diagram showing an output editing result of a similarity calculation result;

FIG. 12 is a diagram showing a storage format of document data and a word frequency table in an external storage device.

FIG. 13 shows a word extraction table.

FIG. 14 is a diagram for specifically explaining the processing from steps S6 to S12 of the main processing shown in FIG. 16;

FIG. 15 is a flowchart showing the overall procedure of word extraction processing;

FIG. 16 is a flowchart showing the overall procedure of a main process.

FIG. 17 is a view showing a comparative example with respect to the processing from steps S6 to S12 of the main processing shown in FIG. 16;

FIG. 18 is a view showing a document list screen as a similar document search result.

FIG. 19 is a diagram showing a document screen as a similar document search result.

FIG. 20 is a flowchart showing details of a word extraction process;

FIG. 21 is a flowchart showing details of initialization processing;

FIG. 22 is a flowchart showing details of a norm calculation process;

FIG. 23 is a flowchart showing details of a word correspondence table creation process;

FIG. 24 is a flowchart showing details of a similarity calculation process;

FIG. 25 is a flowchart showing details of a similarity calculation process subsequent to FIG. 24;

FIG. 26 is a flowchart showing details of output editing processing;

FIG. 27 is a view for explaining a conventional similar document search method.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Input device 2 ... Display device 3 ... Control device 4 ... Memory 5 ... External storage device 10a ... Word extraction part 10b ... Input document data storage buffer 10c ... Word ID-word table storage buffer 10d ... Word frequency table storage buffer 10e... Word extraction table storage 11a... Main processing unit 11b... Initialization unit 11c... Norm calculation unit 11d. Output editing unit 11g Document list display unit 11h Document selection unit 11i Document content display unit 11j Search target / word frequency table storage buffer 11k Reference target / word frequency table storage buffer 11l Document Norm table storage buffer 11m... Word correspondence table storage buffer 11n... Similarity calculation result storage buffer 11o... Output editing result storage buffer

 ──────────────────────────────────────────────────続 き Continuing from the front page (72) Inventor Naohide Kubota 1381-1, Shinmachi, Omachi, Tokyo Toshiba Computer Engineering Co., Ltd. (72) Yukio Nakamoto 1381-1, Shinmachi, Ome, Tokyo Toshiba Computer Data Engineering Co., Ltd. (72) Inventor Takuya Nishina 1381 Shinmachi, Ome-shi, Tokyo Toshiba Computer Engineering Co., Ltd.

Claims (4)

[Claims] 1. A storage unit for storing a plurality of document data, and a word frequency for generating a word frequency table by obtaining an appearance frequency for each preset search condition word for each document data stored in the storage unit A table creation unit, and for each document data stored in the storage unit, calculate a norm of a one-dimensional vector having an appearance frequency for each search condition word in the word frequency table created by the word frequency table creation unit as an element Document norm table creating means for creating a document norm table, and specifying means for specifying each document data of a search target and a search target from the document data stored in the storage means, A similarity calculating means for calculating a similarity between the respective document data based on the word frequency table and the document norm table. 2. A storage unit for storing a plurality of document data, and a word frequency for creating a word frequency table by obtaining an appearance frequency for each preset search condition word for each document data stored in the storage unit A table creation unit, and for each document data stored in the storage unit, calculate a norm of a one-dimensional vector having an appearance frequency for each search condition word in the word frequency table created by the word frequency table creation unit as an element Document norm table creating means for creating a document norm table, and specifying means for specifying each document data of a search target and a search target from the document data stored in the storage means, Word correspondence table creating means for creating a word correspondence table indicating the registered positional relationship of common words between the respective word frequency tables created by the word frequency table creating means for each document data A similar document search device comprising: a similarity calculating unit that calculates a similarity between respective document data specified by the specifying unit based on the word frequency table, the document norm table, and the word correspondence table. . 3. A step of obtaining a frequency of appearance for each preset search condition word for each individual document data stored in the document database to create a word frequency table, and an individual document stored in the document database. A step of calculating a norm of a one-dimensional vector having an appearance frequency for each search condition word in the created word frequency table as an element for each data to create a document norm table; and a document stored in the document database. A step of designating each document data of a search target and a search target from data; and a step of calculating a similarity between the designated document data based on the word frequency table and the document norm table. A similar document search method characterized in that: 4. A step of generating a word frequency table by obtaining an appearance frequency for each preset search condition word for each document data stored in the document database, and each document stored in the document database. A step of calculating a norm of a one-dimensional vector having an appearance frequency for each search condition word in the created word frequency table as an element for each data to create a document norm table; and a document stored in the document database. A step of designating each of the document data to be searched and the object to be searched from the data; And calculating the similarity between the specified document data based on the word frequency table, the document norm table, and the word correspondence table. Similar document retrieval method according to claim.