JP2015090528A - Device and method for determining continuous excerpts - Google Patents

Abstract

PROBLEM TO BE SOLVED: To detect that a plurality of documents are continuously excerpted.SOLUTION: The present invention comprises: cutting a character string segment out of one sentence of an input document; determining a start point of the character string segment; making a digest, in which a character string corresponding to a character string segment for each predetermined number of characters from the start point has been converted into a hash function, slide by a predetermined number of characters, and storing a document ID and a digest group of the digest in a digest DB; reading out the digest from the digest DB; and determining that a plurality of documents are continuously excerpted, when excerpting, in a character string segment separated by a predetermined window size w of the digest, a document having a different digest.

Description

  The present invention relates to a continuous citation determination apparatus and method, and in particular, a continuous citation determination for determining that an electronic document (for example, a blog on the Web) quotes other documents without interruption. The present invention relates to an apparatus and a method.

  Citation analysis has been used as a technique for determining citations from other documents.

  In Patent Document 1, a document is divided into segments that can be cited, a digest is generated for each segment, a concatenated character string is created, and similarly obtained from a document stored in the original document DB. By comparing with the character string, the quotation from the original source is determined.

  In Patent Document 2, a method called a sliding window is used to detect an abnormality of a network packet. This is not to segment the data sequence, but to detect abnormalities from function values for data in a moving (sliding) window with a fixed data length as a window. By applying this to a document, a character string in the document is regarded as a data sequence, and an abnormal value for each window can be found by moving a window of a certain size from the top of the document.

  In Patent Document 3, the citation determination is performed based on the similarity between two documents.

JP 2010-182238 A JP 2009-152712 A JP 2009-205694 A

  Conventional problems will be described with reference to FIGS.

  Consider a case in which citation determination is performed on a document composed of a plurality of document fragments as shown in FIG. As shown in FIG. 2, one fragment is about 50 characters in Japanese, and the fragment is not divided depending on the sentence but is divided and connected at random positions. In addition, the original kana may be converted to kanji. For example, as shown in FIG. 2, in the original (quoting source), it is “Looking back”, but in the example in the figure, the single character “Looking” is quoted as “Looking” as “Looking back”. Yes. In such a document, if a part of the sentence is focused, the meaning will pass, but the whole will not make sense, but it will be hit by a keyword search.

By using the method of Patent Document 1 above, it works effectively for documents that can be clearly segmented,
(1) Segmentation cannot be performed on a document that cannot clearly specify sentence breaks, such as those targeted by the present invention;
(2) When it is quoted in a relatively short character string unit, it is difficult to determine that it has been quoted;
There is a problem.

  Here, by introducing the sliding window of Patent Document 2, it is possible to create a digest in an arbitrary section in the document, and it is possible to make a citation determination even for a document where the sentence break is not clear. However, the following problems remain.

  (1) The criteria for selecting an appropriate sliding window starting point is unclear.

  (2) It cannot be determined that a plurality of documents are cited continuously.

  (3) The determination cannot be made when a minute correction is made in the document.

  (4) If the sliding window method is used, the number of sections in which the digest is created increases compared to the case where the document is segmented. Therefore, if the digest is created as it is, the size of the DB storing the digest will explode. To do.

  (5) It is not possible to determine a document that cites a plurality of documents seamlessly.

  In addition, since the method of Patent Document 3 does not assume citation of a plurality of documents, it cannot perform citation determination of a document composed of a plurality of document fragments.

  The present invention has been made in view of the above points, and an object thereof is to provide a continuous citation determination apparatus and method capable of detecting that a plurality of documents are continuously cited.

According to one aspect, a continuous citation determination apparatus for determining continuous citations of a plurality of documents,
A character string section is cut out from one sentence of the input document, the starting point of the character string section is determined, and a digest obtained by converting a character string for the character string section for each fixed number of characters from the starting point by a hash function is obtained for a predetermined number of characters. Digest calculation means for sliding and storing the digest document ID and digest group in the digest DB;
When the digest is read from the digest DB and a document having different digests is cited in a character string section separated by a predetermined window size w of the digest, it is determined that a plurality of documents are cited continuously. A citation determination means,
A continuous citation determination device is provided.

  According to one aspect, it is possible to detect that a plurality of documents are cited continuously, so if a citation is valid, citations and other sentences usually appear alternately, so By detecting that it is continuous, it is possible to reduce the risk of false detection of legitimate citations as spam.

It is an example of the target document of quotation determination. It is an example of a fragment of the target document. It is a figure which shows the fundamental view of this invention. It is an example of digest creation in one embodiment of the present invention. It is a block diagram of the continuous quotation determination apparatus in one embodiment of this invention. It is a flowchart of the whole continuous quotation determination apparatus in one embodiment of this invention. It is an example of digest DB in one embodiment of this invention. It is a flowchart of the process of the digest calculation part in one embodiment of this invention. It is the algorithm of the digest calculation of the single document in one embodiment of this invention. It is a flowchart (detail of S230) of the digest calculation of the single document in one embodiment of this invention. It is a flowchart of the quotation determination part in one embodiment of this invention. It is an example of determination that a plurality of documents are cited continuously in an embodiment of the present invention. It is an example of the collation table in one embodiment of this invention. It is an example of digest DB for continuous quotation determination when using morpheme division | segmentation in one embodiment of this invention. It is an example of a collation table (used in continuous citation) in the case of morpheme separation in one embodiment of the present invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  First, terms used in this specification will be described.

  -Digest: When a certain character string is given, the character string is converted into a short number of bytes (or number of bits) by a hash function.

  • Digest size: The above short byte count.

  -Matching digest: A digest is generated for each of many character string sections included in one document, but it is included in a digest group generated from one document and appears in the digest group of another document. The digest that comes.

  -Number of matching digests: Number of sets of matching digests in the two digest groups.

  The outline | summary of this invention is shown.

  FIG. 3 shows the basic idea of the present invention.

  Assume that a document in which a part of the documents A, B, and C of the citation source is extracted from the documents of the citation sources A, B, and C is created.

  In the existing method, a digest set is created by segmenting in sentence units, compared, and if they match, it is determined that they are the same sentence. However, when the cited document does not form a sentence, segmentation by the technique of Patent Document 1 cannot be performed.

  On the other hand, in the present invention, when a sliding window is used instead of a citation analysis for a pair of documents, a character string in which one document has the same digest as other documents is used. The ratio of the number of sections is used. Further, the citation is determined based on the ratio of the total number of character string sections that match other documents.

  In the present invention, a document is divided into more detailed character string sections, a starting point is set using character units and morpheme breaks, and a digest for a character string section for each predetermined number of characters is created from each starting point. FIG. 4 shows an example in which a character string section is cut out from one sentence and a digest is generated. Here, the starting point between character strings is shifted in units of one character, and the number of characters is 20. The digest is the upper 32 bits of the MD5 hash value (Non-Patent Document 1: The MD5 Message-Digest Algorithm. Http://tools.ietf.org/html/rfc1321) when the character string is expressed in UTF-8. This is an example using a hexadecimal representation from 0 to F (for example, “c595”).

  The digest created in this way is stored in the digest DB as a forward and reverse lookup table.

  In the citation analysis, the digest and the document ID corresponding to the digest are read from the digest DB, divided into positions that are shifted by the length of a predetermined window size, and a digest that is common to multiple documents is detected, and the multiple documents are detected. Is determined to be cited continuously.

  This will be specifically described below.

  FIG. 5 shows the configuration of the continuous citation determination apparatus in one embodiment of the present invention.

  The continuous citation determination apparatus 100 shown in the figure includes a digest calculation unit 110, a citation determination unit 120, a digest size calculation unit 130, a digest size selection table 140, and a digest DB 150.

  FIG. 6 is a flowchart of the overall processing of the continuous citation determination apparatus according to the embodiment of the present invention.

  Step 100) The digest size calculation unit 130 calculates the digest size using the maximum number of documents assumed, the number of matches (k) for citation determination, and the maximum value of the false detection probability as inputs. If the digest size is increased, it usually becomes enormous, but if it is decreased, erroneous detection is likely to occur. Therefore, it is necessary to obtain a digest size that minimizes the erroneous detection while suppressing the digest size. The digest size calculation unit 130 determines the number of documents (the maximum number of documents assumed), the number of matches for citation determination (k), and the maximum false detection probability (allowable false detection probability (for example, 0.01%)). Is obtained by referring to a digest size selection table 140 described later. Detailed processing will be described later.

  Step 200) The digest calculation unit 110 reads a document from the document DB 101, and calculates the character string length of the document input from the operator, the character string length of the section to be digested, and the i + 1th starting point in the document. According to the number of characters, the character string for the i-th character in the document d, the digest function for calculating the digest of the character string x, and the digest size obtained from the digest size calculation unit 130, the digest for each character string section is obtained for each document. calculate. Detailed processing will be described with reference to FIG.

  Step 300) The digest calculation unit 110 stores the calculated digest in the digest DB 150.

  The digest DB 150 includes a forward lookup table 151 and a reverse lookup table 152. FIG. 7 shows an example of the digest DB 150. FIG. 11A shows a forward lookup table 151, and FIG.

  The forward lookup table 151 stores the creation date and the digest group using the document ID as a key. The reverse lookup table 152 stores a corresponding document ID group using the digest as a key. In addition to the document ID, the appearance order of the character string sections in the document can also be stored. In the example of FIG. 7, the digest size is 16 bits, and the bit string is expressed in hexadecimal. Further, in the reverse lookup table 152, the document IDs are expressed in pairs in the order of appearance.

  Step 400) The citation determination unit 120 reads a set of documents including a character string section having the same digest from the digest DB 150.

  Step 500) The citation determination unit 120 uses the window size w input from the operator and the difference (allowable error) α between the start positions of the character string sections, and a plurality of documents in the read document set are continuous. Determine that it is quoted. Detailed processing will be described with reference to FIGS.

  Step 600) The quotation determination unit 120 outputs the document ID whose determination result is “true” (with quotation).

  Each of the above processes will be described in detail.

Process of digest size calculation unit 130:
Here, calculation of the digest size of the digest size calculation unit 130 in step 100 will be described.

  In carrying out the present invention, the digest DB 150 may become huge in size. This is because the size of the digest DB 150 is affected by the number of digests created per document, so using a sliding window requires only the number of character string sections used. is there.

  If the existing method divides a document into sentence units, if the average number of characters in a sentence is 50 characters, the digest size per document is assumed if the digest size is g bytes and the average document length is w bytes. Was gw / 50 bytes. For example, even if the digest size is 5 bytes, the total digest size per document falls within 1/10 of the document size.

  However, since a sliding window is used in the present invention, the total size of digests becomes enormous as the number of character string sections increases. However, if the digest size is reduced, the same digest is accidentally given to different character string sections, and detection errors increase.

  Therefore, when a certain number or more of the digest sets given to different documents match, it is determined probabilistically “not accidental”.

  In the present invention, the size of the digest DB 150 is minimized by simultaneously considering the digest size, the concept of the starting point of the section, and the threshold value.

As a starting point of view,
(1) Start each character (for example, FIG. 4);
(2) Starting from morpheme separation;
(3) Starting from a certain set of morphemes;
(4) Start with sentence breaks;
Etc. are considered. However, since citation is often performed ignoring the sentence structure, (3) and (4) are not realistic. Therefore, (1) and (2) are examined.

<Definition>
・ The digest size is g bytes.

  -The average number of characters in a document is L bytes.

  • Let s be the average number of sections per document.

  At this time, the total number of digest bytes required per document is gs, and the goal is to reduce this value.

  If the digest size is reduced, a plurality of character strings have the same digest, and an citation determination error occurs. If this probability can be lowered, the digest size can be reduced to the limit.

Since the document d _h contains s intervals on average, if the digest set of a document is expressed as {h ₁ , h ₂ ,..., H _n } (for simplicity), an arbitrary digest is represented by this document. The possibility of being included in the digest set can be written as p = s / 2 ^g . That is, p is obtained by giving a constant s (an average of sections included in the number of documents in the document DB 101) and a digest size g (bytes).

Among the s digest included in a document, the probability that one arbitrary appearing simultaneously in the document with another, a sp = s ^{2/2 g,} the probability of simultaneously occurring in any of the k different document Can be written as follows (assuming k is sufficiently smaller than s):

この値が十分小さくなるように文書DB１０１に格納されている文書数（想定される最大の文書数）に応じて、ｐとｋを選ぶことで、偶然を排除する。ｐ、ｋは、ダイジェストサイズ計算部１３０によってｇとｋを選択し、ｇと文書ＤＢ101内の文書中に含まれる区間の数の平均ｓにより、p=s/2^gによって求められる。上記の式(1)で求められた値がダイジェストサイズ選択テーブル１４０に格納される。

By selecting p and k according to the number of documents stored in the document DB 101 (the maximum number of documents assumed) so that this value becomes sufficiently small, chances are eliminated. p and k are obtained by p = s / 2 ^g by selecting g and k by the digest size calculation unit 130, and g and the average s of the number of sections included in the document in the document DB 101. The value obtained by the above equation (1) is stored in the digest size selection table 140.

<When the morpheme break is the starting point of the section>
If the morpheme break is the starting point of the section, assuming that the average character string length per morpheme is 3 characters, one character is 3 bytes in UTF-8.

である。例えば、文書の平均長が10キロバイトとすると、s=1111だが、簡単のため、

It is. For example, if the average document length is 10 kilobytes, s = 1111, but for simplicity,

とする。

And

For example, if g = 24 (bits),
p = 1000/2 ²⁴ = 5.96 × 10 ^-5
However, at this time, the probability that one or more digests match is 5.96 × 10 ⁻² . This indicates that if the number of documents is about 20, an average of one or more false detections occurs.

  The false detection probability can be lowered from the direction of increasing the number of matching digests and the direction of increasing the digest size.

Table 1 shows an example of the digest size selection table 140 that stores the false detection probability when the number of digests k and the digest size g are increased. The example in Table 1 assumes 1000 segments per document. However, it is limited to k where the misdetection probability is about 10 ⁻¹³ for g.

ダイジェストサイズを求める際には、ダイジェスト選択テーブル１４０に対し、文書数の逆数に誤検出確率を乗じたものを基準とし、その数値よりもダイジェストサイズ選択テーブル１４０の値が小さくなるようなｋとｇの組み合わせを選択する。以下に詳述するが、例えば、文書数が100個、誤検出確率を１％（0.01=1/100）とすると、
1/100+1/100=1/10000=0.0001=10^-4
を基準としてこれを下回るようなｋとｇの組み合わせを選択する。k=2であればg=24ビット、k=3であればg=20ビットが選択される。

When obtaining the digest size, the digest selection table 140 is obtained by multiplying the reciprocal of the number of documents by the false detection probability, and k and g such that the value of the digest size selection table 140 is smaller than the numerical value. Select a combination. As will be described in detail below, for example, if the number of documents is 100 and the probability of false detection is 1% (0.01 = 1/100),
1/100 + 1/100 = 1/10000 = 0.0001 = 10 ^-4
A combination of k and g that is less than this is selected. If k = 2, g = 24 bits are selected, and if k = 3, g = 20 bits are selected.

<Specific value settings>
In implementation, the row k of the digest size selection table 140 of Table 1 is scanned horizontally based on the matching number k and the maximum value of the false detection probability, and when the value falls below the maximum value of the false detection probability, The value of the row of the number of bits of the column g is output as the digest size ds. For example, assuming that the number of documents is 1 billion = 10 ⁹ and the total false detection probability is less than 10 ⁻⁴ (0.01%), the threshold is 10 ⁻¹³ and falls below this [g = 20bit, k = 6], [g = 24bit, k = 4], [g = 28bit, k = 3], or [g = 32bit, k = 2] may be used.

Further, assuming that the cited document is limited to a certain period in the past, a smaller value can be set. For example, if the number of target documents is 1 million = 10 ⁶ and the total false detection probability is less than 10 ^-4 (0.01%), 10 ^-10 is set as a threshold, [g = 20bit, k = 5], Using either [g = 24bit, k = 4], [g = 28bit, k = 2], or [g = 32bit, k = 2], the value of the row of g less than the false detection probability is set as the digest size ds. do it.

The above calculation does not consider the appearance position of the character string section in the document. However, if the character string position is taken into account, chances can be further eliminated. If the average of the character string intervals for one document is 1,000 = 10 ³ , the false detection probability is reduced by 10 ^−6, so the values in Table 1 may be multiplied by 10 ⁻⁶ .

For example, assuming that the number of documents is 1 billion = 10 ⁹ and the total false detection probability is less than 10 ⁻⁴ (0.01%) (0.01% is an acceptable false detection probability), the threshold is 10 ^{− 13} is replaced with 10 ^-7 , [g = 16bit, k = 6], [g = 20bit, k = 4], [g = 24bit, k = 3], [g = 28bit, k = 2], [ Any of g = 32bit, k = 2] may be used.

Process of digest calculation unit 110:
Next, the processing of the digest calculation unit 110 in step 200 of FIG. 6 will be described.

  FIG. 8 is a flowchart of the process of the digest calculation unit in one embodiment of the present invention.

  When one document is read from the document DB 101 (step 220), the digest calculation unit 110 performs digest calculation for the one document (step 230) and stores it in the digest DB 150 (step 240). By repeating this, the digest is calculated for all the documents in the document DB 101.

  When the document is read out in step 220, a triplet of the document ID, the document creation date and time, and the document (more precisely, the content string of the document) is obtained. The document ID is a symbol that can identify the document. For example, a URI (Uniform Resource Identifier) format such as a URL (Uniform Resource Locator) is used.

  In FIG. 8, the digest is calculated and stored for all the documents at once. However, it is not necessary to process the document once processed and stored in the digest DB 150. Therefore, after the digest is calculated for all the documents, the processing of steps 220 to 240 may be performed at the timing when a new document is stored in the document DB 101.

  FIG. 9 shows an algorithm for digest calculation of a single document in step 230, and FIG. 10 shows a flowchart. The processing shown in FIGS. 9 and 10 shows an example in which a character string section is cut out from one sentence of a read document and a digest is generated. Here, the starting point of the character string section is shifted by one character unit as shown in FIG. 4, and the number of characters is 20 characters. That is, in FIG. 9, w = 20, and next (d, i) = i + 1 for any i-th document d, i. Here, an example of shifting in units of one character is shown, but the present invention is not limited to one unit of characters. However, the finer the particle size, the more precisely it can be determined. In addition, the character units shifted by the digests between the documents to be compared are the same, and it is necessary to align the starting points by using a delimiter based on the morphological analysis result. By aligning the starting points using the morphological analysis results, the amount of data stored in the digest DB 150 can be compressed.

  The digest uses the hexadecimal representation of the upper 16 bits of the MD5 hash value (see Non-Patent Document 1) when the character string is expressed in UTF-8. Also, by using the character string section cut out from one sentence immediately after the morpheme segmentation obtained by the morphological analysis, it becomes difficult for character deviation to occur, and comparison can be made with the same granularity.

  The digest calculation unit 110 obtains the digest size ds from the digest size calculation unit 130, and calculates the digest function (digest (x, ds)) using the digest size ds of the character string x (step 231). The digest function is a one-way function that results in completely different results even if one bit is different.

  The character string length of the document d is (length (d)), the character string length of the section to be digested is (w), the number of characters up to the next section (next (d, i)), the i-th character in the document d A character string (partial character string) corresponding to w characters is set to (distr) as a digest by hash (substr [(d, i, w), ds]) (step 232).

  The initial value of the index value (idx) is set to 0 (step 233), and the digest set (digest) is set to an empty set (step 234).

  The digest calculation unit 110 obtains a character string (substr [(d, i, w), ds]) from the i-th character in the document d based on the digest function (digest (x, ds)) and the input parameters. ) Is obtained (step 235), and the hash value is added to the digest set (digest ← digest∪ {hash}) (step 236). If i = i + 1 (step 237) and there is next (d, i), the process proceeds to step 235, and if not, the digest set (digest) is output to the digest DB 150 (step 239).

  The digest DB 150 includes a forward lookup table 151 and a reverse lookup table 152 as shown in FIG. The digest calculation unit 110 extracts the document ID, creation date and time, and digest group of the read document for each element of the digest set, and stores them in the forward lookup table 151. Also, the document ID group corresponding to the digest is stored in the reverse lookup table 152 using the digest as a key. At this time, the order of appearance of the character string sections in the document can also be stored. In the example of the reverse lookup table 152 of FIG. 7, “http://example.com/00003,1” exists after the document ID “http://example.com/00002,2” corresponding to the digest “0abc”. This indicates that the data are stored in chronological order.

  Also, in the citation determination process, when morpheme breaks are used, information about the number of characters from the beginning of the document is added to the forward lookup table 151 ′.

● Processing of citation determination unit 120:
Next, the citation determination process in step 400 of FIG. 6 will be described.

  FIG. 11 is a flowchart of the processing of the citation determination processing unit in one embodiment of the present invention.

  The quotation determination unit 120 acquires a predetermined window size (w) and an allowable error (α) from the operator. In addition, the spam set S whose citation determination is “true” is initialized (φ) in a memory (not shown) (step 410), and the document i acquired from the forward lookup table 151 of the digest DB 150 is stored. Based on the document ID, the digest set corresponding to the document ID is read from the reverse lookup table 152 (step 430), it is determined whether a plurality of documents are cited continuously (step 440), and the determination result is “ If true (step 460, Yes), the document i is added to the spam set S (step 460). At this time, digest size information to be added to the spam set S is acquired from the forward lookup table 151 and added. When the processing for all the documents in the digest DB 150 is completed (step 420, No), the spam set S is output as a determination result (step 470).

  The processing of the citation determination unit 120 in step 440 will be described.

  The citation determination unit 120 quotes a plurality of documents without breaks in the document targeted by the present invention. Therefore, if it is determined that a plurality of documents are cited without a break, it is possible to determine the citation more accurately.

  Assuming that the input window size is w, if a digest common to a plurality of documents is detected at positions shifted by exactly the length of w, it can be determined that a plurality of documents are cited continuously. . In the example of FIG. 12, when w is the window size and α is the difference (allowable error) of the start position of the allowable character string section, if there are different digests separated by w or w + α, multiple It is determined that the document is cited continuously. Here, as the allowable error α, the average value or the maximum length of the number of characters in the morphological analysis result is used. By using the allowable error α, it is possible to reduce the probability of missing a plurality of documents cited continuously.

  In FIG. 12, it is assumed that each digest is generated by shifting one character at a time or by morpheme separation. In the example shown in the figure, the digest c located at a position separated by the window size w that matches the digest b that cites the last matching “document 1” cites “document 2”. Judged as being cited continuously. The section between digest b that matches first and digest c that matches next is substantially the same as window w.

  In the collation determination unit 120, when all of the following (1) to (3) are satisfied in the collation table 121 including the in-document position and the match candidate shown in FIG. Determined to be quoted (without).

(1) Consecutive digest matches with a document:
It is determined that the digests are continuous because the positions in the matching candidate document are continuous.

(2) Consecutive digest match with another document:
The determination is made based on the fact that the second matching candidate positions in the document are continuous.

(3) The inconsistent section between (1) and (2) is the window size + allowable error (α):
Judgment is made based on the fact that the inconsistent section of the document in the document is separated by the window size + α.

  In the case of the collation table of FIG. 13, when the window size is 10, it is determined that the documents “0002” and “0003” are cited continuously.

  In the above determination, the case where the character string section is shifted one character at a time has been described. The case where the character string section is shifted by morpheme division will be described below.

  When citation determination is performed using morpheme breaks, when the digest calculation unit 110 generates the digest DB 150, the number of characters from the beginning of the document based on the morpheme analysis result is added to the forward lookup table 151 in FIG. The number of characters from which the start position of the character string section that is the basis of each digest is written from the top of the document is described. An example is shown in FIG. In the example of the digest DB 150 in FIG. 14, the digest “c595” of the document ID http://example.com/00001 is the top (0), “d03e” is the third character from the top, and “ea79” is from the top. Indicates the seventh character.

  Further, FIG. 15 shows an example of a collation table when morpheme separation is used. In the collation table 121 ′, information on the number of characters from the beginning of the document is added to the collation table 121 of FIG.

  In the case of citation determination in morpheme separation, the digest set corresponding to the document ID is read from the reverse lookup table 152 ′ based on the document ID of the document i acquired from the forward lookup table 151 ′ of the digest DB 150 ′, and the collation table With reference to the number of characters from the document head 121 ′ and matching candidates, it is determined that the mismatching section that continues between the document and another document is mismatched by the window size + α as the number of characters.

  It is possible to construct the operation of the constituent elements of the continuous citation determination device shown in FIG. 5 as a program and install it on a computer used as the continuous citation determination device, or to distribute it via a network. .

  The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.

100 Continuous citation judgment device 101 Document DB
110 Digest Calculation Unit 120 Citation Determination Unit 121, 121 ′ Collation Table 130 Digest Size Calculation Unit 140 Digest Size Selection Table 150, 150 ′ Digest DB
151, 151 ′ forward lookup table 152, 152 ′ reverse lookup table

Claims (8)

A continuous citation determination device for determining continuous citation of a plurality of documents,
A character string section is cut out from one sentence of the input document, the starting point of the character string section is determined, and a digest obtained by converting a character string for the character string section for each fixed number of characters from the starting point by a hash function is obtained for a predetermined number of characters. Digest calculation means for sliding and storing the digest document ID and digest group in the digest DB;
When the digest is read from the digest DB and a document having different digests is cited in a character string section separated by a predetermined window size w of the digest, it is determined that a plurality of documents are cited continuously. A citation determination means,
A continuous citation determination device characterized by comprising: The citation determination means includes
When documents with different digests are cited in a character string section separated by the window size w plus a tolerance α of the start position of a predetermined character string section, a plurality of documents are cited continuously. 2. The continuous citation determination apparatus according to claim 1, further comprising means for determining that there is a thing. The citation determination means includes
It further has a collation table that stores document IDs that are candidates for matches with positions in the document,
Based on the position in the document when the digest is shifted by one character unit, refer to the collation table,
Consecutive digest matches with a document:
Only the length between the last matched digest and the next matched digest plus the window size plus tolerance (α) does not match:
Consistent digest match with another document:
3. The continuous citation determination apparatus according to claim 2, further comprising means for determining that a plurality of documents are continuously cited when all of the above are satisfied. The digest DB includes the number of characters from the beginning of the digest document,
The citation determination means includes
It further has a collation table that stores the document ID that is a candidate for matching with the position in the document, the number of characters from the beginning of the document in the digest,
Based on the document position when the digest is shifted by morpheme separation, refer to the collation table,
A means for determining that a plurality of documents are cited consecutively when a non-matching section continuous with a certain document and another document is non-matching by a size obtained by adding a predetermined allowable error to the window size as the number of characters; The continuous quotation determination apparatus according to claim 2. A continuous citation determination method for determining continuous citation of a plurality of documents,
In an apparatus having digest calculation means, digest DB, and citation determination means,
The digest calculation means cuts out a character string section from one sentence of the input document, determines the starting point of the character string section, and converts the character string for the character string section for each fixed number of characters from the starting point by a hash function. Digest calculation step of sliding the digest by a predetermined number of characters and storing the digest document ID and digest group in the digest DB;
When the citation determination means reads the digest from the digest DB and cites documents with different digests in a character string section separated by a predetermined window size w of the digest, a plurality of documents are continuously cited. A citation determination step for determining that the
A continuous citation determination method characterized by: In the citation determination step,
When documents with different digests are cited in a character string section separated by the window size w plus an allowable error (α) of the start position of a predetermined character string section, a plurality of documents are cited continuously. The continuous citation determination method according to claim 5, wherein the continuous citation determination method is determined to be. In an apparatus further comprising a first collation table storing document IDs that are candidates for matching with positions in the document,
In the citation determination step,
Based on the position of the digest in the document, refer to the first collation table,
Consecutive digest matches with a document:
Only the length between the last matched digest and the next matched digest, which is the window size (w) plus the tolerance (α), does not match:
Consistent digest match with another document:
The continuous citation determination method according to claim 6, wherein if all of the above are satisfied, it is determined that a plurality of documents are continuously cited. In the apparatus further comprising a second collation table that stores the document ID that is a candidate for matching with the position in the document, and the number of characters from the beginning of the digest document,
The digest DB includes the number of characters from the beginning of the digest document,
In the citation determination step,
Based on the document position when the digest is shifted by morpheme separation, refer to the second collation table,
If a non-matching section that is continuous with a certain document and another document is non-matching by the window size (w) plus the tolerance (α) as the number of characters, a plurality of documents are cited continuously. The continuous citation determination method according to claim 6 for determination.

Images