CN104392002B - A kind of the approximate of extensive collections of web pages repeats lookup method - Google Patents

Abstract

The invention relates to a method for approximate duplicate search of a large-scale webpage collection, which uses point signatures of documents to filter web page content noise, and combines partitioning and inverted index pruning to complete approximate duplicate search, making approximate duplicate search efficient and only calculating points The Jaccard similarity of signatures keeps the complexity of the method low.

Description

A Approximate Duplicate Finding Method for Large-Scale Web Collections

technical field

The invention relates to an information retrieval technology, in particular to a method for searching for approximate repetition of core content in a large-scale webpage collection.

Background technique

With the rapid development of the Internet, the scale of data stored on the Internet continues to expand. In order to quickly obtain the desired data, search engines have become the main means. Although search engines remove duplicate web pages in the returned search results, near-duplicate web pages continue to appear in the corpus. To obtain more accurate and valuable results, it is necessary to find and remove these near-duplicate web pages. However, traditional approximate duplicate search methods have many deficiencies. For example, the shingling method based on shingles or n-gram subsets is too complex to calculate Jaccard overlap. Overhead, locality-sensitive hashing methods map multiple signatures to a single hash value adding additional overhead for signature extraction and hashing.

Contents of the invention

The technical solution of the present invention is to overcome the deficiencies of the prior art and provide a method for approximate duplicate search of a large-scale webpage collection, using document point signatures to filter web page content noise, and combining partitioning and inverted index pruning to complete approximate duplicate search , so that the approximate duplicate search efficiency is high, and only the Jaccard similarity of point signatures is calculated so that the complexity of the method is very low.

The technical solution of the present invention: an approximate duplicate search method for a large-scale webpage collection, the process is shown in Figure 1:

In step 0, start to execute the present invention, and turn to step 1 for execution;

In step 1, input document vector with weighted point signature, partition k with boundary [p _k ,p _k+1 ) and inverted list (the inverted list is empty at this time), turn to step 2 to execute; [p _k , p _k+1 ) is the range of document length, which is a half-open and half-closed interval, p _k is the lower boundary of the interval, and p _k+1 is the upper boundary of the interval;

In step 2, the pair set for storing the result is initialized to be empty, and then turn to step 3 for execution;

In step 3, it is judged whether there is an uncalculated document vector d _i in the document length random sorting sequence, and if so, turn to step 4 for execution, otherwise turn to step 22 for execution;

In step 4, the interval lower boundary p _k of the partition k sets the length of the document vector d _i , and turns to step 5 for execution;

In step 5, arrange all point signatures of d _i in partition k in ascending order of frequency, put the point signature with the smallest point signature frequency first, and turn to step 6 to execute;

In step 6, set the first auxiliary boundary delta ₁ to 0, set the detected document vector set to empty, and turn to step 7 for execution;

In step 7, it is judged whether there is a point signature s _ij that has not been calculated in the point signature of d _i , where j is the position of the point signature in d _i , if it exists, then go to step 8, otherwise go to step 20;

In step 8, the document vectors related to s _ij in partition k are put into the inverted list list _kj , and arranged in descending order according to the document length, and then turn to step 9 for execution;

In step 9, set the second auxiliary boundary delta ₂ to 0, and turn to step 10 for execution;

In step 10, it is judged whether there is a document vector d _i ' in descending order of document length in the list _kj , if it exists, then go to step 11, otherwise, go to step 18;

In step 11, delta ₂ is set to be the difference between the lengths of document vectors d _i and d _i' , and turn to step 12 for execution;

In step 12, it is judged whether the document vector d _i and d _i' are equal or the document vector d _i' has been detected, if satisfied, then go to step 10, otherwise go to step 13;

In step 13, it is judged that delta ₂ is less than 0 and delta ₁ -delta ₂ is greater than 1-t times the length of d _i' , if satisfied, then go to step 10, otherwise go to step 14;

In step 14, it is judged that delta ₂ is greater than or equal to 0 and delta ₁ + delta ₂ is greater than 1-t times of the length of d _i , if satisfied, then turn to step 18 for execution, otherwise turn to step 15 for execution;

In step 15, it is judged that the Jaccard similarity between the document vectors d _i and d _i' is greater than or equal to t, if satisfied, then turn to step 16 for execution, otherwise turn to step 10 for execution;

In step 16, add <d _i , d _i' > to the result pair set, and turn to step 17 for execution; <d _i , d _i' > is a document pair composed of document vector d _i and d _i ', document vector d _i When the Jaccard similarity with d _i' is greater than or equal to the threshold, it matches, and joins the pair set in the form of <d _i , d _i' >, otherwise it does not join the pair set.

In step 17, add d _i' to the detected document vector set, and turn to step 10 for execution;

In step 18, the value of delta ₁ increases the frequency of point signature s _ij in the document vector d _i , and turns to step 19 for execution;

In step 19, it is judged that delta ₁ is greater than 1-t times of the maximum length of the undetected document vector in partition k, if satisfied, then turn to step 20 to execute, otherwise turn to step 7 to execute;

In step 20, it is judged that the difference between the upper bound of the partition and the length of the document vector d _i is less than or equal to 1-t times the upper bound of the partition, if it is satisfied, then go to step 21, otherwise go to step 3; t is the criticality of Jaccard similarity Value ratio, the value depends on the actual situation, generally between 0.5 and 1;

In step 21, set the interval upper boundary p _k+1 as the interval lower boundary p _k , iterate to the next partition, and turn to step 6 for execution;

In step 22, return the result pair set, and turn to step 23 for execution;

In step 23, the whole program ends.

The advantage of the present invention compared with prior art is:

(1) Existing near-duplicate web page detection methods mainly include shingling algorithm, fingerprint mode, and locality-sensitive hashing. The shingling algorithm calculates Jaccard overlap based on shingles or n-grams, and its complexity is too high. On this basis, the improvement of introducing "super shingles" can only slightly reduce the accuracy of the result; the fingerprint mode extracts representative words or entire Sentence hashes concatenate bitstrings to generate fingerprint features for judging document similarity, however bitstring selection incurs significant overhead; locality-sensitive hashing concatenates from each data object to a single hash, via a separate hash function , with the additional overhead of signature extraction and multiple hashes.

(2) The present invention uses a short chain formed by disabling antecedents and adjacent content items as a document signature, and the signature extraction speed is fast and the overhead is small; when calculating the Jaccard similarity, the calculation range is reduced in combination with the set partition, and the calculation is obviously not similar The similarity between the document vectors, the introduction of inverted index pruning removes the redundant calculation process and speeds up the calculation process. The method of the invention can achieve the goals of accuracy, speed and low computational complexity.

Description of drawings

Fig. 1 is the realization flow chart of the method of the present invention;

Fig. 2 is an execution diagram of the midpoint signature approximate duplicate search method in the present invention.

detailed description

Before elaborating the present invention, the relevant concepts are firstly explained and illustrated.

Point (p): Words that often appear in documents are called stop words in natural language texts, such as is, the, do, have, etc.

Common vocabulary: words in the document that are not dots.

Dot distance (d): the number of words in the document between the common word and the dot selected before it or between the common word and the common word before it, dots are not included in this count, such as "a rally to kick", the word " Both a" and "to" appear frequently in documents, and both can be used as points. The point distance between "rally" and "a" is 1, and the point distance between "kick" and "a" is 2. The distance between "kick" and "rally" is 1 (since "to" is not counted as a point), and the distance between "kick" and "to" is 1.

Chain length (c): The number of common words in the specified document that satisfy the dot distance relative to a certain point, for example, "a rallyto kick", the chain length is 2 when the dot distance is 1 relative to point "a".

Point signature (s): It is used to find a continuous list of common words with a chain length of c. The distance between common words in the linked list is the dot distance d, and the distance between the first common word in the linked list and the dot is d, the representation form is p(d,c), that is, point signature = point (point distance: chain length), such as "a rally to kick", select "a" as point, point distance d is 1, and chain length c is 2, point signature s="a"(1,2) is {"a":"rally":"kick"}.

Point signature frequency: the number of times the point signature appears in the document, for example, "a rally to kick off aweeklong campaign", the number of times the point signature s="a"(1,2) appears is 2, that is, the frequency is 2.

Point signature weight: the point signature frequency.

Document length (|d|): the sum of the frequency of all point signatures in the document, for example, "a rally to kick off aweeklong campaign", point signature s ₁ = "a" (1,2) occurs twice, point signature s ₂ = "to"(1,2) appears for 1 times, and the document length is 2+1=3.

Document vector (d): The document is expressed as a sequence of point signatures with frequencies, that is, document vector = {point signature 1: point signature 1 frequency, point signature 2: point signature 2 frequency, ...}, for example d="a rally to kick off a weeklongcampaign", the document vector is expressed as d={s ₁ :2, s ₂ :1}, where s ₁ = "a"(1,2), s ₂ = "to"(1,2), Document length |d|=3.

Partition k: the range of document length, which is a half-closed and half-open interval. The lower bound of the interval is fixed, and the upper bound is not fixed. [p _k ,p _k+1 ) is the range of document length, which is a half-open and half-closed interval, p _k is the lower boundary of the interval, and p _k+1 is the upper boundary of the interval.

Inverted list (list): A list of document vectors with the same point signature, that is, inverted list = {document vector 1, document vector 2, ...}, each document vector in the list has the frequency of the point signature, for example, s ₁ ="a"(1,2), s ₂ ="to"(1,2), s ₃ ="the"(2,1), d ₁ ="a rally to kick off a weeklong campaign", d ₁ ＝{s ₁ :2, s ₂ :1}, d ₂ ="a biological argument for the cougar phenomenon", d ₂ ＝{s ₁ :1, s ₃ :1}, d ₃ ="the past can be corrected ", d ₃ ={s ₃ :1}, list ₁ : {d ₁ :2,d ₂ :1} (point signature s ₁ = "a" (1,2) corresponding inverted list), list ₂ : {d ₁ :1} (point signature s ₂ = "to" (1,2) corresponding inverted list), list ₃ : {d ₂ :1, d ₃ :1} (point signature s ₃ = "the" (2,1) corresponds to the inverted list).

Jaccard similarity sim: the sum of the smaller values of the corresponding point signature frequencies in the two document vectors divided by the larger value of the corresponding point signature frequencies in the two document vectors, sim(d ₁ ,d ₂ )=(1 +0+0)/(2+1+1)=0.25.

Threshold (t): The critical value ratio of Jaccard similarity, the value depends on the actual situation, generally between 0.5 and 1.

Auxiliary boundary (delta): A variable used to temporarily record values.

Pair set {<d _i ,d _i' >}: document pair set, when the Jaccard similarity of two document vectors d _i and d _i' is greater than or equal to the threshold, the two document vectors are matched with "<document vector 1, document vector 2>", that is, "<d _i ,d _i' >", the form will be added to the pair set, otherwise it will not match and will not be added to the pair set.

The present invention will be described in detail below in conjunction with the above.

Figure 2 shows the execution diagram of the approximate deduplication of the web page set. The web document vectors calculated in Figure 2 are d ₁ ={s ₁ :5, s ₂ :4, s ₃ :4}, d ₂ ={s ₁ :8,s ₂ :4} and d ₃ ={s ₁ :4,s ₂ :5,s ₃ :5}, the lengths of document vectors d ₁ , d ₂ and d ₃ are 13, 12 and 14 respectively, and the threshold t is set to 0.8. The execution process is described as follows:

(1) Input document vectors d ₁ , d ₂ and d ₃ with weighted point signatures, and input partitions and inverted lists whose boundaries are [p _k ,p _k+1 );

(2) The pair set is set to be empty, the document vectors are randomly arranged according to the length, and d ₁ is randomly selected to compare with other document vectors;

(3) Set the lower boundary of the partition to the length 13 of the document vector d ₁ , and the frequencies of the point signatures s ₁ , s ₂ and s ₃ are 17, 13, and 9 respectively, and sort the point signatures in ascending order according to the frequency, and choose to calculate The point signature with the smallest point signature frequency is the document list under s ₃ , the auxiliary boundary delta ₁ is set to 0, and the detected document vector set is set to empty;

(4) The document vectors under each point signature are arranged in descending order according to the length of the document. Firstly, traverse the document vector set of point signature s ₃ and put it into the inverted list, detect the document vector d ₃ , and the auxiliary boundary delta ₂ = the length of d ₁ - length of d ₃ = -1<0, document vector d ₁ is not equal to d ₃ and d ₃ is not detected, delta ₁ -delta ₂ (=1) is less than (1-0.8)*14 (=2.8), delta ₁ +delta ₂ (=-1) is less than (1-0.8)*13(=2.6), so calculate the Jaccard similarity sim(d ₁ ,d ₃ of document vector d ₁ and document vector d ₃ in point signature s ₃ )=(4+4+4)/(5+5+5)=0.8≥t, add <d ₁ ,d ₃ > to the pair set;

(5) Detect document vector d ₁ in the inverted list of point signature s ₃ , document vector d ₁ is equal to d ₁ , not calculated, delta ₁ increases the frequency of point signature s ₃ of document vector d ₁ , delta ₁ = 4, And end this traversal, traverse the document vector set of the second point signature s ₁ , set delta ₁ to 0, put the document vector set of s ₁ into the list, detect document vector d ₂ , auxiliary boundary delta ₂ = d ₁ The length of -d ₂ = 1>0, the document vector d ₁ is not equal to d ₂ and d ₂ has not been detected, delta ₁ -delta ₂ (=-1) is less than (1-0.8)*12 (=2.4) , delta ₁ +delta ₂ (=1) is less than (1-0.8)*13 (=2.6), so calculate the Jaccard similarity between the document vector d ₁ and the document vector in the point signature s ₃ , sim(d1,d2)= (5+4)/(8+4+4)=0.5625<t, <d ₁ , d ₃ >does not join the pair set;

(6) Continue traversing the inverted list, the document vector d ₁ and d ₁ in the list are equal, the document vector d ₃ has been detected, delta ₁ increases the frequency of the point signature s ₁ of the document vector d ₁ , delta ₁ = 5, end this time Traverse, traverse the document set s ₂ signed by the third point, set delta ₁ to 0, document vector d ₁ and d ₁ in the list are equal, document vector d ₃ and d ₂ have been detected, end this traversal, and return the pair set{ <d ₁ ,d ₃ >}, end the program.

The above embodiments are provided only for the purpose of describing the present invention, not to limit the scope of the present invention. The scope of the invention is defined by the appended claims. Various equivalent replacements and modifications made without departing from the spirit and principle of the present invention shall fall within the scope of the present invention.

Claims (1)

1. A method for approximately repeated search of a large-scale webpage collection, characterized in that the steps of realization are as follows: Step 1, input document vector with weighted point signature, partition k with boundary [p _k ,p _k+1 ) and inverted list, turn to step 2 for execution; [p _k ,p _k+1 ) is document length The range of is a semi-open and semi-closed interval, p _k is the lower boundary of the interval, and p _k+1 is the upper boundary of the interval; In step 2, the pair set storing the result is initialized to be empty, and then turn to step 3 for execution; in step 3, judge whether there is an uncalculated document vector d _i in the document length random sorting sequence, and if it exists, turn to step 4 for execution, otherwise turn to step 22 execution; In step 4, the interval lower boundary p _k of the partition k sets the length of the document vector d _i , and turns to step 5 for execution; In step 5, arrange all point signatures of document vector d _i in partition k in ascending order of frequency, put the point signature with the smallest point signature frequency first, and turn to step 6 to execute; In step 6, the first auxiliary boundary delta ₁ is set to 0, and the detected document vector set is set to empty, and the execution turns to step 7; In step 7, judge whether the point signature of document vector d _i has point signature s _ij that has not been calculated, where j is the position of point signature in document vector d _i , if it exists, go to step 8, otherwise go to step 20 execution; In step 8, the document vectors related to point signature s _ij in partition k are put into the inverted list list _kj , and arranged in descending order according to the document length, and then turn to step 9 for execution; In step 9, set the second auxiliary boundary delta ₂ to 0, and turn to step 10 for execution; In step 10, it is judged whether there is a document vector d _i' arranged in descending order of document length in the inverted list list _kj , if it exists, then go to step 11, otherwise, go to step 18; In step 11, set the second auxiliary boundary delta ₂ as the difference between the lengths of document vectors d _i and d _i' , and turn to step 12 for execution; In step 12, it is judged whether the document vector d _i and d _i' are equal or the document vector d _i' has been detected, if satisfied, then go to step 10, otherwise go to step 13; In step 13, it is judged that delta ₂ is less than 0 and delta ₁ -delta ₂ is greater than 1-t times the length of d _i' , if satisfied, then go to step 10, otherwise go to step 14; In step 14, it is judged that the second auxiliary boundary delta ₂ is greater than or equal to 0 and delta ₁ + delta ₂ is greater than 1-t times the length of d _i , if satisfied, then go to step 18, otherwise go to step 15; In step 15, it is judged that the Jaccard similarity between the document vectors d _i and d _i' is greater than or equal to t, if satisfied, then turn to step 16 for execution, otherwise turn to step 10 for execution; In step 16, add <d _i , d _i' > to the result pair set, and turn to step 17 for execution; <d _i , d _i' > is a document pair composed of document vectors d _i and d _i' , document vector d _i When the Jaccard similarity with d _i' is greater than or equal to the threshold, it matches, and joins the pair set in the form of <d _i , d _i' >, otherwise it does not join the pair set; In step 17, add d _i' to the detected document vector set, and turn to step 10 for execution; In step 18, the value of delta ₁ increases the frequency of point signature s _ij in the document vector d _i , and turns to step 19 for execution; In step 19, it is judged that delta ₁ is greater than 1-t times of the maximum length of the undetected document vector in partition k, if satisfied, then turn to step 20 to execute, otherwise turn to step 7 to execute; In step 20, it is judged that the difference between the upper bound of the partition and the length of the document vector d _i is less than or equal to 1-t times the upper bound of the partition, if it is satisfied, then go to step 21, otherwise go to step 3; t is the criticality of Jaccard similarity Value ratio, the value depends on the actual situation, and the value range is 0.5-1; In step 21, set the interval upper boundary p _k+1 as the interval lower boundary p _k , iterate to the next partition, and turn to step 6 for execution; In step 22, return the result pair set, and turn to step 23 for execution; In step 23, the whole program ends.