JP6809119B2 - Document comparison program, document comparison method, and document comparison device - Google Patents

Description

The present invention relates to a document comparison program, a document comparison method, and a document comparison device.

Conventionally, when comparing documents, in order to reduce the amount of calculation, for each document, sentences representing the features and features are extracted, and the extracted features and documents are compared to make the documents similar. I am evaluating the degree.

From the viewpoint of evaluating the similarity, a technique for evaluating the frequency of appearance of one or more search keywords in a document stored in advance in a database, the proximity between search keywords, and the search keywords has been proposed.

A technique for determining a match between user preference information when the inner product of the vector value of the preference information of a specific user and each vector value of the preference information of a plurality of arbitrary users exceeds a predetermined value is known. ing.

Special Table 2009-515249 Japanese Unexamined Patent Publication No. 2001-306606 Japanese Unexamined Patent Publication No. 2012-252484

D. Gusfield: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997 T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. ICLR, 2013 "What is MeCab (Wakame seaweed)", [online], [Search on July 21, 2016], Internet <URL: http: // taku910. github. io / mecab ＞ C. D. Manning, P.M. Raghavan, H. et al. Schutze: Introduction to Information Retrieval, Cambridge University Press, 2008

Although the techniques described above evaluate the degree of similarity, it is difficult to obtain information on the details of similarity between documents, such as the distinction between similarity and theft.

In recent years, it has become possible to obtain a vector representation of words for each document by using technologies such as machine learning and neural networks. However, simply calculating the weights between words appearing in a sentence is a calculation amount. Becomes very huge.

Therefore, in one aspect, the present invention aims to reduce the amount of calculation when calculating the correlation value between documents.

According to one aspect, each of the plurality of documents to be compared is separated into a plurality of elements, and the position where the word order of the other document is changed with respect to one of the plurality of documents is set as the offset position. The inner product of the vector associated with each element by expressing the correlation value of each of the plurality of elements including the weighting between the elements at all the deviation positions of the plurality of documents as a vector. A document comparison program is provided that allows a computer to perform a process calculated by the discrete Fourier transform.

Further, as a means for solving the above problems, a document comparison method and a document comparison device can be used.

The amount of calculation when calculating the correlation value between documents can be reduced.

It is a figure for demonstrating the misalignment. It is a figure which shows the example of the weight table. It is a figure for demonstrating the relationship between a calculation and a calculation time. It is a figure which shows the result example of the correlation calculation. It is a figure which shows the hardware configuration of the document comparison apparatus. It is a figure which shows the functional structure example of a document comparison apparatus. It is a flowchart for demonstrating the vector expression collection process. It is a flowchart for demonstrating the document comparison process. FIG. 5 is a flowchart for explaining the weighted correlation calculation process in the case where step S204 of FIG. 8 is the first calculation method. It is a flowchart for demonstrating the weighted correlation calculation process in the case of the 2nd calculation method in step S204 of FIG.

Hereinafter, embodiments of the present invention will be described with reference to the drawings. First, consider the problem of finding the weighted correlation of two documents. here,
"Correlation" represents the number of matches with the words associated with all misalignments.
The "weight" is represented by the continuous value of a certain range added to a word pair.

There are the following two existing methods for finding the correlation between sentences. The first method is to compare words in order and refer to the weights from the table. The second method is an unweighted FFT (Fast Fourier Transform) -based algorithm, which is known as a method for obtaining correlation at a relatively high speed. Each calculation time is calculated when σ is the number of word types and n is the length of each sentence.
The time required for the first method is represented by O (n ² (logσ) ² ).
The time required for the second method is represented by O (σn ² log n).

Before considering the first method and the second method, the problem of finding the weighted correlation of two documents shall be formulated as follows.
-Document: string of words, W: set of words, W ⁿ : set consisting of the entire document of length (number of words) n-s _i : i-th word of sentence s-st: sentences s and t Connected documents, w ⁿ : A document consisting of n words w

の相関C(s，t)は、2n-1次元ベクトルで、i番目の要素は、

Correlation C (s, t) is a 2n-1 dimensional vector, and the i-th element is

で表される。ただし、

It is represented by. However,

について、

about,

のように文字列を数式のように表わすことで、範囲外の形式的な比較のためにダミーの語を付加することを表現する。このようにすることで、位置ずれを考慮して相関を算出できる。

By expressing a character string like a mathematical formula, it is expressed that a dummy word is added for a formal comparison outside the range. By doing so, the correlation can be calculated in consideration of the positional deviation.

FIG. 1 is a diagram for explaining misalignment. FIG. 1 shows a conceptual diagram in which a dummy word x that does not belong to either the document s or the document t is added before and after the document t in order to consider the misalignment of the i-th element with respect to the document t of the document s. ing.

The sentence s is shifted word by word, and the correlation with one word of the document t at the shifted position is calculated. In the document s, when the word order is changed with respect to the document t, it corresponds to the shift position.

Furthermore, if φ is a function from two words to a continuous value,

の重み付き関数C’(s，t)は、

The weighted function C'(s, t) of

で表される。数６において、各φは-１から+１の間の値を取り、j=1〜nまでを積算することにより、重み付き相関の要素C’_iは、-nから+nの値を取る。

It is represented by. In Equation 6, the φ takes a value between -1 to +1, by integrating up to j = 1 to n, the element C _'i weighted correlation takes a value from -n + n ..

Regarding the existing first method, three sentences s, t and u are written s: This is a dog.
Sentence t: That is a cat.
Sentence u: This is a pen.
And. In this case, a weight table as shown in FIG. 2 is created. FIG. 2 is a diagram showing an example of a weight table.

In FIG. 2, the weight table 3 shows words obtained from sentences s, t, and u in a matrix, and shows the weights of word-to-word correlation. With reference to the weight table 3, if the meanings match, the weight "1" is given, and if they do not match, the weight "0" is given. Also, the similarity of the semantics is given by a numerical value between 0 and 1. For example, the weight for the similarity between the meanings of "cat" and "dog" is given by "0.7", and the weight for the similarity between the meanings of "pen" and "cat" is given by "0.1". Has been done.

In the first method, the unweighted correlation C is
C (s, t) = (0,0,0,2,0,0,0)
C (s, u) = (0,0,0,3,0,0,0)
C (t, u) = (0,0,0,2,0,0,0)
And refer to the weight table 3 for each,
C'(s, t) = (0,0,0,3.5,0,0,0)
C'(s, u) = (0,0,0,3.1,0,0,0)
C'(t, u) = (0,0,0,2.9,0,0,0)
We get such a weighted correlation C'. From this result, it can be determined that the document s and the document t are the closest, then the document s and the document u are the closest, and the document t and the document u are the least similar.

In this first method, a weight table 3 showing weights for each word pair is created in advance, words are compared in order, and weights are acquired by referring to the weight table 3. In particular,

として、σ×σの語の対から重みへの表を予め準備する。

As a result, a table from pairs of words of σ × σ to weights is prepared in advance.

For all misalignments, the corresponding words are compared in order, and the weights corresponding to the word pairs are obtained from the weight table 3.

According to the processing procedure described above, the word comparison is performed O (n ² ) times, and one reference to the weight table 3 is represented by O ((log σ) ² ) time. That is, for all word pairs
It is considered that O (n ² ) × O ((logσ) ² ) = O (n ² (logσ) ² ) time is required. Here, n indicates the number of words, and σ indicates the length of the weight table 3.

Regarding the existing second method, first, the calculation of convolution by FFT will be described.

The circular convolution r of two n-dimensional vectors u and v is

で表される。ただし、-n+1≦i≦０についてはv_i=v_n+iである。

It is represented by. However, for -n + 1 ≤ i ≤ 0, v _i = v _{n + i} .

If R, U, and V are discrete Fourier transforms of r, u, and v, respectively, and o is the product of each element,

で表される。このことから、rは、uとvとからＦＦＴによりO(nlogn)時間で計算可能である。計算ルートと計算時間との関係を図３で説明する。

It is represented by. From this, r can be calculated from u and v by FFT in O (nlogn) time. The relationship between the calculation route and the calculation time will be described with reference to FIG.

FIG. 3 is a diagram for explaining the relationship between the calculation and the calculation time. In FIG. 3, n represents the length of the sentence. In the case of a calculation that obtains r from u and v, that is, a calculation that compares the word u and the word v, it is expressed by the calculation time O (n ² ).

On the other hand, the calculation time of the discrete Fourier transforms U and V of u and v is O (nlogn), and the calculation time of the product R for each element of U and V is O (n). The calculation time of the inverse discrete Fourier transform from R to r is O (nlogn).

Next, the outline of the FFT-based Algorithm will be described. The unweighted function between documents is calculated by the convolution of vectors obtained by digitizing words. By replacing some words a in the set of words W with 1 and others with 0, the correlation considering only the match of a can be expressed by convolution, and it can be calculated in O (nlogn) time. The replacement of a document with a numeric sequence is O (n) hours. Moreover, since a match or a mismatch can be expressed by multiplication, a convolution operation can be applied.

The correlation is calculated by repeating the convolution operation of O (nlogn) time σ times and taking the sum of each element. In particular,

について、φ_aは、aを1、それ以外を0に写す関数である。定義より、1≦i≦2n-1について、相関Ciは、

For, φ _a is a function that copies a to 1 and the others to 0. By definition, for 1 ≤ i ≤ 2n-1, the correlation Ci is

と表される。

It is expressed as.

(U _{a, 1} , u _{a, 2} , ..., u _{a, 2n-1} ) and (va _{, 1} , v _{a, 2} , ..., v _{a, 2n-1} )

である２ｎ−１次元ベクトルとすると、数１１は、

Assuming that the 2n-1 dimensional vector is, the number 11 is

で表される。数１３内の

It is represented by. Within the number 13

は畳み込み演算である。

Is a convolution operation.

In this FFT-based Algorithm, in the first method, the weightless correlation is much faster (O (σn log n) time) than the square time of document length n (O (n ² log σ) ² hours). You can. However, if the evaluation of φ is realized and used using the weight table 3, it is difficult to extend the second method using the weight table 3 because the equation of C'(s, t) cannot be regarded as a convolution. is there. It is difficult to increase the speed by combining existing methods.

In the consideration of the existing first method and the second method as described above, the applicant uses the inner product because the matrix representing the correlation between each element of two or more sentences, that is, the correlation C is sparse. Also focused on the fact that the amount of calculation can be suppressed. That is, we have found that the second method is extended to a weighted function by the inner product of vectors instead of the weight table 3.

Examples described by the inventor will be described below.

β: W → R ^d : Vector representation, R: Set consisting of all real numbers

について、

about,

で表す。定数α、γについて

It is represented by. About constants α and γ

としてもよい。

May be.

By expressing the weight as the inner product of the vectors, the weighted correlation can be performed in O (dnlogn) time by the convolution operation.

Even with the vector representation where d = σ, the calculation can be performed in O (σnlogn) time. One example is a vector in which the element corresponding to a certain word is 1 and the other elements are 0, and the vectors are sparse and all orthogonal.

In a realistic document or language, it is considered to be d << σ. That is, since the distribution of weight values has some bias, φ can be represented by a dimension d smaller than the table size σ. It does not have to be a vector representation in which all the vectors representing errors are orthogonal.

The calculation time when the reference of the weight table 3 of the existing first method is replaced with the inner product of the vectors is O (dn ² ).

Next, the extension of the second method to weighted correlation by using the vector representation of words is shown below. By definition, the weighted correlation is obtained by applying the number 16 to the number 6 for 1 ≤ i ≤ 2n-1.

ベクトル表現に置き換えて、内積についての畳み込み演算を得る。

Replace with a vector representation to get a convolution operation on the dot product.

Then, it transforms into the integration of the vector inner product in the d dimension,

を得る。この数１８に対して、発明者は、積算する順番を入れ替えることで、

To get. For this number 18, the inventor can change the order of integration.

を得る。

To get.

That is, after calculating the inner product of the vectors at all the deviation positions for each dimension, the total value is obtained for the entire d dimension, so that the number 19

が畳み込み演算となる。後述にて、数２０は、配列[Z_k，i]で表される。

Is the convolution operation. Later, the equation 20 is represented by an array [Z _{k, i} ].

When the weight table 3 shown in FIG. 2 is considered as a matrix, the matrix representing the correlation between each element is sparse, and the amount of calculation can be suppressed even if the inner product is used. The calculation of the number 20 for 1 ≦ i ≦ 2n-1 can be performed in O (nlogn) time as in the first method. Therefore, the weighted correlation C'(s, t) can be calculated in d × O (nlogn) time multiplied by the number of dimensions d.

Next, an example of the result of correlation calculation between documents depending on the presence or absence of weight will be illustrated. FIG. 4 is a diagram showing an example of the result of the correlation calculation. In FIG. 4, the vertical axis shows the vector value, and the horizontal axis shows the order (i-th) of the elements in the document. The upper row shows the unweighted correlation, and the lower row shows the weighted correlation. Furthermore, each of the non-theft, the theft, and the theft including paraphrase is shown in the vertical correspondence.

In the case of no theft, there is no significant change in the fluctuation range in any case. In the case of theft by a simple copy, the peak 6a is shown in the unweighted correlation, and the peak 6b also appears in the weighted correlation.

However, for theft, including paraphrasing, the unweighted correlation and the weighted correlation are different. In the unweighted correlation, it is difficult to specify the peak, whereas in the weighted correlation, the peak 6c can be specified.

In this embodiment, as compared with the first method using the weight table 3, the calculation time can be suppressed to O (dnlogn) time, and the calculation of the weighted correlation can be realized.

The document comparison device 100 according to this embodiment has a hardware configuration as shown in FIG. FIG. 5 is a diagram showing a hardware configuration of the document comparison device. In FIG. 5, the document comparison device 100 is an information processing device controlled by a computer, and is a CPU (Central Processing Unit) 11, a main storage device 12, an auxiliary storage device 13, an input device 14, and a display device. It has 15, a communication I / F (interface) 17, and a drive device 18, and is connected to the bus B.

The CPU 11 corresponds to a processor that controls the document comparison device 100 according to a program stored in the main storage device 12. A RAM (Random Access Memory), a ROM (Read Only Memory), or the like is used in the main storage device 12, and is obtained by a program executed by the CPU 11, data required for processing by the CPU 11, and processing by the CPU 11. Store or temporarily store the data, etc.

An HDD (Hard Disk Drive) or the like is used in the auxiliary storage device 13, and data such as a program for executing various processes is stored in the auxiliary storage device 13. Various processes are realized by loading a part of the program stored in the auxiliary storage device 13 into the main storage device 12 and executing the program in the CPU 11.

The input device 14 has a mouse, a keyboard, and the like, and is used by the user to input various information necessary for processing by the document comparison device 100. The display device 15 displays various information required under the control of the CPU 11. The input device 14 and the display device 15 may be a user interface using an integrated touch panel or the like. The communication I / F17 communicates through a network such as wired or wireless. Communication by communication I / F17 is not limited to wireless or wired.
A program that realizes the processing performed by the document comparison device 100 is provided to the document comparison device 100 by a storage medium 19 such as a CD-ROM (Compact Disc Read-Only Memory), for example.

The drive device 18 interfaces the storage medium 19 (for example, a CD-ROM or the like) set in the drive device 18 with the document comparison device 100.

Further, a program for realizing various processes according to the present embodiment described later is stored in the storage medium 19, and the program stored in the storage medium 19 is installed in the document comparison device 100 via the drive device 18. Will be done. The installed program can be executed by the document comparison device 100.

The storage medium 19 for storing the program is not limited to the CD-ROM, and is one or more non-transitory, tangible media having a structure that can be read by a computer. It should be. The computer-readable storage medium may be a DVD (Digital Versatile Disk) disk, a portable recording medium such as a USB memory, or a semiconductor memory such as a flash memory, in addition to the CD-ROM.

FIG. 6 is a diagram showing a functional configuration example of the document comparison device. In FIG. 6, the document comparison device 100 mainly has a vector representation collection unit 40 and a document comparison unit 50. The vector expression collection unit 40 and the correlation acquisition unit 50 are realized by processing performed by the CPU 11 executing the corresponding program.

Further, the storage unit 130 includes a set of a plurality of documents 70, a set of word strings 72 for each document 70, a vector representation DB 74, two or more documents 80 to be compared, and a word sequence 82 for each document 80 to be compared. The weighted correlation result 89 and the like are stored.

The vector expression collection unit 40 is a processing unit that converts a set of documents 70 that have been collected and accumulated in advance into a vector expression in the structural unit of the document and stores it in the vector expression DB 74, and is a decomposition unit 41 and a conversion unit. It has 42 and. The structural unit of the document may be for each part of speech, or for each character or phrase. A building block is an element of a document.

The decomposition unit 41 reads the document 70 from the storage unit 130, divides the read document 70 into structural units by detecting blanks or morphological analysis, and generates a word string 72. The word sequence 72 for each document 70 is stored in the storage unit 130. If the document 70 is in English, the document 70 may be decomposed by blanks. When the document 70 is in Japanese, it may be decomposed by morphological analysis (mecab or the like).

The conversion unit 42 converts the word string 72 into a vector representation. As a vector expression, it may be converted into the appearance frequency, the appearance position, their union, and the like. Conversion to the frequency of appearance may be performed using tfidf, LSI, or the like. In addition, word2vec or the like may be used for conversion to the appearance position. The vector representation is represented by a vector sequence.

The document comparison unit 50 calculates the correlation of the documents 80 to be compared with weights, and outputs the weighted correlation result 89 to the storage unit 130. The document comparison unit 50 further includes a decomposition unit 51, a conversion unit 52, and a weighted correlation calculation unit 53.

The decomposition unit 51 inputs two documents 80 to be compared and divides each document 80 into constituent units to generate an example 72 of two words. The document 80 to be input may be 3 or more. A word string 72 is generated for each document 80 and stored in the storage unit 130. The division into the constituent units may be the same as the decomposition unit 41 in the vector representation collection unit 40.

The conversion unit 52 converts the word sequence 80 obtained by the decomposition unit 51 into the vector sequence 84, respectively, with reference to the vector representation DB 74. The vector sequence 84 for each document 80 to be compared is stored in the storage unit 130.

The weighted correlation calculation unit 53 calculates the correlation of the document 80 by using the vector sequence 84 and using the inner product of two vectors for each constituent unit as a weight. By configuring the weighted correlation calculation unit 53 so as to perform the convolution calculation unit 54, the calculation time can be suppressed. The obtained weighted correlation result 89 is stored in the storage unit 130.

Next, the processing flow will be described. First, the procedure of the vector expression collection process by the vector expression collection unit 40 will be described. FIG. 7 is a flowchart for explaining the vector representation collection process.

In FIG. 7, in the vector expression collecting unit 40, the decomposition unit 41 reads one document 70 from the set of documents 70 (step S101), decomposes the read document 70 into constituent units, and creates a word string 72. .. Taking sentence 70 as an example of "I am a cat", this sentence 70 is represented by the column 72 of the words "I am a cat." The word sequence 72 is stored in the storage unit 130.

When the word string 72 is created, the conversion unit 42 then converts each word in the word string 72 into a vector to generate a vector sequence, which is stored in the vector representation DB 74 (step S103). In the vector expression DB74, the vector expression (1,0,1) is associated with the word "I", the vector expression (0,1,2) is associated with the word "ha", and the word "cat" is associated with the vector expression DB74. Vector representations (1,1,3, vector representations (0,2,4) associated with the word "de", and vector representations (0,3,5) associated with the word "aru" are accumulated. ..

The vector representation collection unit 40 determines whether or not there is an unprocessed document 70 in the set of documents 70 (step S104). When there is an unprocessed sentence 70 (YES in step S104), the vector expression collecting unit 40 returns to step S101 and repeats the same processing as described above. On the other hand, when there is an unprocessed sentence 70 (NO in step S104), the vector expression collecting unit 40 ends the vector expression collecting process.

The structural unit for decomposing the document 70 may be characters. In this case, there is no need to divide by spaces in the case of English text, or to divide in the case of Japanese text. In the case of the above sentence example "I am a cat", it is decomposed into ["I", "I am", "ha", "cat", "de", "a", "ru"]. A vector sequence in which each divided character is represented by a vector is generated and stored in the vector representation DB 74.

Further, the method of acquiring the vector expression in character units is performed in the document comparison unit 50 with reference to the vector expression DB 74. In this case, the vector is divided into character units instead of words, and the vector associated with the character is acquired to create a vector string.

As another example, the structural unit may be a phrase. When a phrase is used as a constituent unit, it is necessary to define the phrase and perform parsing based on it. In the case of the above sentence example "I am a cat", it is decomposed into ["I am a cat", "I am a cat"].

To obtain a vector representation for a phrase, it may be calculated from the vector representation of the words that make up the phrase. That is,
β (“I am”) = (β (“I am”) + β (“ha”)) / 2
Obtained by Set phrases before getting vector expressions, and learn vector expressions by regarding them as words.

Next, the document comparison process by the document comparison unit 50 will be described. FIG. 8 is a flowchart for explaining the document comparison process. In the description of FIG. 8, the document 80 to be compared is referred to as document A and document B, respectively.

In the document comparison unit 50, the division unit 51 reads the document A and the document B to be compared (step S201). Then, the division unit 51 divides the document A and the document B into constituent units to create the word column A and the word column B (step S202).

Next, the conversion unit 52 converts the word string A into the vector string A with reference to the vector representation DB 74, and similarly converts the word string B into the vector string B (step S203).

Then, the weighted correlation calculation unit 53 weights and calculates the correlation between the vector column A and the vector column B (step S204). The weighted calculation result 89 is output to the storage unit 130. The weighted calculation result 89 may be displayed on the display device 15. By displaying the weighted correlation graph in the lower part of FIG. 4, the user can visually know whether or not there is similarity or theft.

Next, the calculation procedure of the weighted correlation will be described. In the calculation of the weighted correlation, there are a first calculation method using the number 18 and a second calculation method using the number 19 that can reduce the amount of calculation. First, in step S204 of FIG. 8, a case where the weighted correlation is calculated by the first calculation method will be described. In the first calculation method, the inner product is convolved, but the weighted correlation calculation unit 53 does not include the convolution calculation unit 54 of FIG.

FIG. 9 is a flowchart for explaining the weighted correlation calculation process in the case where step S204 of FIG. 8 is the first calculation method. In FIG. 9, the weighted correlation calculation unit 53 reads the two vector sequences A and B (step S211), and sets the variable i and the variable k to 1 (step S212). The variable i indicates the out-of-position position, and the variable k indicates the dimension of the vector.

Each element (vector of the constituent unit) of the vector sequence A is

で表される。β(s_i)は、文書Ａのi番目の構成のベクトル表現を示す。また、ベクトル列Ｂの各要素は、

It is represented by. β (s _i ) indicates the vector representation of the i-th configuration of document A. Further, each element of the vector column B is

で表される。β(t_i)は、文書Ｂのi番目の構成のベクトル表現を示す。

It is represented by. β (t _i ) indicates the vector representation of the i-th configuration of document B.

After the variables i and j are initialized, the weighted correlation calculation unit 53 determines whether or not the variable i is 2n-1 or less (step S213).

On the other hand, if the variable i is 2n-1 or less (YES in step S213), the weighted correlation calculation unit 53 initializes to zero the C _'i (step S214). _C'i is a variable that indicates the element of weighted correlation at the shift position i.

Then, the weighted correlation calculation unit 53 determines whether or not the variable j is 1 or more and n or less (step S215). n indicates the length of sentences A and B. When the variable j is 1 or more and n or less (YES in step S215), the weighted correlation calculation unit 53 initializes the variable x _j to zero (step S216). The variable x _j indicates the dot product for all vector dimensions d.

Then, the weighted correlation calculation unit 53 determines whether or not the variable k is 1 or more and the dimension d or less (step S217). When the variable k is 1 or more and the dimension d or less (YES in step S217), the weighted correlation calculation unit 53 obtains the inner product y _k of the vectors of the dimension k (step S218), and sets the inner product y _k to the variable x _j . Add (step S219). Then, the weighted correlation calculation unit 53 returns to step S217 and repeats the same process as described above to add all the inner products of the vectors up to the dimension d.

On the other hand, if the variable k is not less than 1 and not more than dimension d (NO in step S217), the weighted correlation calculating unit 53 adds the value of the variable x _j on the correlation C _'i shift position i (step S220) , Return to step S215 and repeat the same process as described above to obtain a weighted correlation value for the shift position i.

On the other hand, if the variable j is not less than 1 and not more than n (NO in step S215), the weighted correlation calculating unit 53 in association with the shift position i records the value of the correlation C _'i the weighted correlation results 89 ( Step S221). Returning to step S213, the same process as described above is repeated in order to acquire the weighted correlation value at the shift position i including the length of the dummy word column.

Finally, when it is determined that the variable i is not 2n-1 or less (NO in step S213), the weighted correlation for all the deviation positions is obtained, so that the weighted correlation calculation unit 53 performs all the deviation positions. The weighted correlation result 89 indicating the weighted correlation value of is output to the storage unit 130 (step S222), and the weighted correlation calculation process is completed.

FIG. 10 is a flowchart for explaining the weighted correlation calculation process in the case where step S204 of FIG. 8 is the second calculation method. In FIG. 10, the weighted correlation calculation unit 53 reads the two vector sequences A and B (step S231), and sets the variable i and the variable k to 1 (step S232). The variable i indicates the off-position, and the variable k indicates the dimension of the vector.

As described in FIG. 9, each element of the vector sequence A (the vector of the constituent unit) is represented by the equation 21, and each element of the vector sequence B is represented by the equation 22. After the variables i and j are initialized, the weighted correlation calculation unit 53 initializes all _C'i (1 ≦ i ≦ 2n-1) to zero (step S233).

The weighted correlation calculation unit 53 determines whether or not the variable k is 1 or more and the dimension d or less (step S234). When the variable k is 1 or more and the dimension d or less (YES in step S234), the weighted correlation calculation unit 53 performs a convolution operation (step S235). The array [Z _{k, i} ] (Equation 20) is obtained.

The weighted correlation calculation unit 53 determines whether or not the variable i is 1 or more and 2n-1 (step S236). When the variable i is 1 or more and 2n-1 (YES in step S236), the weighted correlation calculating unit 53 adds the correlation C _'i for position i deviation convolution operation result (step S237). Sequence [Z _{k, i]} the value of are stored in the correlation C _'i. Variable i is up to 2n-1, weighted correlation calculating unit 53 adds the value of the correlation C _'i.

If the variable i is 1 or more and not 2n-1 (NO in step S236), the weighted correlation calculating unit 53 may record the correlation C _'i shift position i to the weighted correlation results 89 (step S238), step Returning to S234, the same process as described above is repeated.

On the other hand, when the variable k is 1 or more and not the dimension d or less (NO in step S234), the weighted correlation for all the deviation positions is obtained, so that the weighted correlation calculation unit 53 has the weighted correlation value for all the deviation positions. The weighted correlation result 89 indicating the above is output to the storage unit 130 (step S239), and the weighted correlation calculation process is completed.

In the second calculation method described above, the weighted correlation between the documents 80 can be obtained in the quasi-linear time of the document size.

Similarly, both the first calculation method and the second calculation method obtain the correlation between the documents 80 by expressing the weights by the inner product of the vectors. However, in the first calculation method shown in FIG. Based on the determination of step S213, step S215, and step S217, the iterative process shows a triple structure. Therefore,
(2n-1) × n × d Iterative processing will be performed.

On the other hand, in the second calculation method shown in FIG. 10, by transforming it into a convolution operation, it is performed by a single iterative process in step 233 and a double structure iterative process in steps S234 and S236. Therefore
It can be performed by repeating processing (2n-1) + (2n-1) × d times, and the burden of calculation processing can be further reduced compared to the first calculation method.

Here, the approximate range of the size of the actual data of the document 80 is shown.

About σ
-Double-byte characters: 65536
・ Number of words in a single language: Thousands to tens of thousands
About n ・ News articles: Hundreds ~
・ Academic treatise (number of words): Thousands to tens of thousands
About d ・ Default value of word2vec: 200
This is the number of dimensions when word2vec is taken as an example as a tool for obtaining a distributed representation (low-dimensional vector representation) from document data. The closeness of the vector generally represents the closeness of the meaning. Similarity can be judged accurately by document classification.

Since d << σ in this way, compared to the O (n ² (logσ) ² ) time of the existing first method (unweighted correlation), even the weighted correlation in this embodiment is O (dnlogn). ) Since it is time, the calculation time can be significantly reduced.

Further, in this embodiment, since the weighted correlation can be obtained, as shown in the lower part of FIG. 4, it is possible to detect the theft including paraphrases that are difficult to detect by the unweighted correlation. It is possible to evaluate the similarity between documents with higher accuracy.

In the above-described embodiment, the decomposition unit 51 corresponds to the separation unit, and the weighted correlation calculation unit 53 corresponds to the calculation unit.

The present invention is not limited to the specifically disclosed examples, and major modifications and modifications can be made without departing from the scope of claims.

The following additional notes will be further disclosed with respect to the embodiments including the above embodiments.
(Appendix 1)
Separate multiple documents to be compared into multiple elements
The correlation value of each of the plurality of elements at all the deviation positions of the plurality of documents, including the weighting between the elements, is represented by a vector of the characteristics of the element, so that the vector associated with each element is associated with the vector. A document comparison program that lets a computer perform the processing calculated by the discrete Fourier transform as the inner product.
(Appendix 2)
On the computer
For each dimension of the vector, a convolution operation is performed by the discrete Fourier transform which is the inner product of the vector associated with each element of the plurality of documents, and the calculated value at each deviation position of the dimension is acquired.
The document comparison program according to Appendix 1, which performs a process of summing up the calculated values obtained for each dimension of the vector at each deviation position.
(Appendix 3)
On the computer
The document comparison program according to Appendix 1 or 2, wherein the plurality of documents are separated by any of a part of speech, a character, a phrase, or a word separated by a space as an element.
(Appendix 4)
On the computer
The feature is that each element of each of the plurality of documents is converted into the vector representing the feature by referring to the storage unit that stores the vector representing the feature for each element separated from the plurality of sample documents. The document comparison program according to any one of Appendix 1 to 3.
(Appendix 5)
Separate multiple documents to be compared into multiple elements
The correlation value of each of the plurality of elements at all the deviation positions of the plurality of documents, including the weighting between the elements, is represented by a vector, and the inner product of the vector associated with each element. A document comparison method in which a computer performs a process of calculating by the discrete Fourier transform.
(Appendix 6)
A separator that separates each of the multiple documents to be compared into multiple elements,
The correlation value of each of the plurality of elements at all the deviation positions of the plurality of documents, including the weighting between the elements, is represented by a vector, and the inner product of the vector associated with each element. A document comparison device having a calculation unit calculated by the discrete Fourier transform.

11 CPU
12 Main storage device 13 Auxiliary storage device 14 Input device 15 Display device 17 Communication I / F
18 Drive device 19 Storage medium 40 Vector expression collection unit 41 Division 42 Conversion unit 50 Document comparison unit 51 Division 52 Conversion unit 53 Weighted correlation calculation unit 54 Convolution calculation unit 70, 80 Sentence 72, 82 word sequence 74 Vector representation DB
84 Vector column 89 Weighted correlation result

Claims (5)

Separate multiple documents to be compared into multiple elements
Of the plurality of documents, the position where the word order is changed in the other document is set as the shift position with respect to one document, and the gap between the elements of each of the plurality of elements at all the shift positions of the plurality of documents. A document comparison program that allows a computer to perform a process of calculating a correlation value including weighting by a discrete Fourier transform that is the inner product of the vector associated with each element by expressing the characteristics of the element with a vector. On the computer
For each dimension of the vector, a convolution operation is performed by the discrete Fourier transform which is the inner product of the vector associated with each element of the plurality of documents, and the calculated value at each deviation position of the dimension is acquired.
The document comparison program according to claim 1, wherein a process of summing the calculated values obtained for each dimension of the vector is performed at each deviation position. On the computer
The document comparison program according to claim 1 or 2, wherein the plurality of documents are separated by any of a part of speech, a character, a phrase, or a word separated by a space as an element. Separate multiple documents to be compared into multiple elements
Of the plurality of documents, the position where the word order is changed in the other document is set as the shift position with respect to one document, and the gap between the elements of each of the plurality of elements at all the shift positions of the plurality of documents. A document comparison method in which a computer performs a process of calculating a correlation value including a weight by a discrete Fourier transform which is an inner product of the vector associated with each element by expressing the feature of the element with a vector. A separator that separates each of the multiple documents to be compared into multiple elements,
Of the plurality of documents, the position where the word order is changed in the other document is set as the shift position with respect to one document, and the gap between the elements of each of the plurality of elements at all the shift positions of the plurality of documents. A document comparison device having a calculation unit that calculates a correlation value including weighting by a discrete Fourier transform as an inner product of the vector associated with each element by expressing the characteristics of the element with a vector.

Images