Related work Text copy detection originated from program code similarity detection in the 1970's. Natural language text copy detection technique appeared in the 1990s, and has produced three detection approaches [2]: 1) Grammar-based method. This method focuses on the grammatical structure of documents, and uses a string-based matching approach to measure similarity between the documents. Huang[3] proposed a similar web pages detection method based on the LCS(Largest Common Subsequence) algorithm by finding the largest common string between two pages to calculate the similarity of the two pages. Winnowing algorithm [4] uses overlapping k-gram method to get hashes of the documents, and it uses moving window to select the minimum hash value from each window to obtain the fingerprints of the document, and then it calculates the rate of the matching fingerprint to get the similarity between the two documents. Hashbreaking[5], DCT[6] are also the grammar-based methods,
Plagiarism detection, also known as text copy detection, is designed to determine
whether a document is copied from other documents in whole or in part without any
reference indicated. Besides copying text without any change, changing the order of
the original text and replacing synonym are also regarded as plagiarism [
Locating is an important step of text copy detection technology. It is required to
give the position of the plagiarized content in the document in addition to calculating
the document similarity. By-word comparison is a common locating method.
Sediyono et al proposed LCCW (Longest Commonly Consecutive Word) algorithm
[
The Cluster-based plagiarism detection method we propose is the grammar-based method. This method is divided into three steps: pre-selecting, locating and postprocessing. We use the pre-selecting step to find out the documents which may be copied, so as to shorten the locating time and improve the detecting efficiency. And we use clustering method to locate plagiarism fragments, which can reduce the impact of obfuscation to some extent. In the last step, we deal with some errors which are found in locating step. 3
We participated in the PAN-10 external plagiarism detection competition. The main objective of the external plagiarism detection is: given a collection of suspicious documents and source documents, to identify all possible copy fragments from the suspicious documents and their locations in the suspicious documents and the corresponding source documents.
We merged PAN-09 training set and test set into a big set to debug our algorithm. This big set contains 14,429 source documents (training set 7214, and test set 7215), 14428 suspicious documents (training set 7214, and test set 7214). For each suspicious document, there is an xml document which notes all copy fragments in the suspicious document and their locations in the suspicious document and source documents.
Based on language, plagiarism fragments can be divided into monolingual
(translation=false) and cross-lingual (translation=true). Based on the degree of
obfuscation[
The plagiarism detection method we propose uses Winnowing’s fingerprint extraction algorithm. The method consists of three steps: The first step is pre-selecting. For each suspicious document, the task is to find out a small list of candidate documents in which the plagiarized content may exist from the source document set quickly. The second step is locating, which compares the suspicious document with each candidate document to get the copy fragments out of the suspicious document. The last step is post-processing, which discards some fragments without plagiarism from the end result. 4.1
Supposed it takes an average of 100ms to process a pair of documents, and then the total computation time will be more than 200 days. Even if parallelizing the tasks with multi-core processors, the time needed is still unacceptable to the competition.
We found out that the most important step is locating. When we analyzed the algorithm, the locating step cost the most time. So we use the pre-selecting method to reduce the number of candidate documents, thereby the time of locating is shortened. Using the pre-selecting method we can save 90% of the running time.
C.Basile[
However, during the testing, we found that there was possibility of false collision when using Winnowing method to obtain fingerprint. For example, the values of two fingerprints are 1024 and 2024, if they are divided by 1000, their remainders are both 24, but in fact the two fingerprints are not the same. We found that the larger the file is, the greater the probability of collision and the higher the similarity will be. So using this method affects the efficiency and accuracy of locating.
To improve the accuracy of pre-selecting, we use successive same fingerprint thresholds to get candidate documents. We define two parameters, valid interval and successive same fingerprint. There are two fingerprint vectors D1 and D2 representing two different documents, if the number of different fingerprint among a given pairs of the fingerprint is not greater than a given number, we consider the pairs of the fingerprint are the same. And this given number is a valid interval. The pair of the same fingerprint is called a successive same fingerprint if it meets the condition of valid interval. By comparing each source document with the suspicious document, the source document will be regarded as candidate document of the suspicious document if the value of the successive same fingerprint is greater than a given threshold.
By setting the successive same fingerprint threshold to pre-select, the results are as follows: we can find 99.9% of the documents which contain none obfuscation (obfuscation=none) fragments, 89.3% of the documents which contain only low obfuscation (obfuscation=low), and there are not a source document is selected which contains only high obfuscation fragments. 4.2
Locating is done between a suspicious document and a source document. In this step, we compare the suspicious document with each source document in the candidate document set, and then get a plagiarism fragment list of the suspicious document. The steps of locating are as follows:
1) Preprocessing. The purpose of this step is to remove all symbols which do not affect document semantic information, such as punctuation, whitespace, etc., converting all letters to lower case. And then we record the position of each word before and after preprocessing.
2) Sampling. The overlapping word-5-grams approach is used to obtain the initial fingerprint of the document. Referring to Winnowing’s fingerprint sampling algorithm, we use 6 fingerprints as a window, and select the minimum fingerprint as a sample fingerprint of the window. We move the window by a fingerprint until the end of the initial fingerprint, the fingerprint that is repeatedly selected in the same position will be discarded. Finally the sample fingerprint vector of the document can be obtained. The beginning and the end position of the original text before preprocessing can be recorded by each fingerprint of the vector. Then the inverted index of the document can also be generated. The position of the original text is computed by the following formula:
SPi EPi1 1；EPi Pcur w k 2
Where SPi , EPi are the beginning and the end position of the original text which is represented by the i-th fingerprint, Pcur is the beginning position of the current window, w is the size of the sample window, and k is the length of the original text.
3) Clustering and merging. Take the source-document10383.txt and
suspiciousdocument07957.txt as example. The sample fingerprint vectors of the two documents
have been obtained in previous steps. By comparing the two fingerprint vectors, a list
of matches between the suspicious document and the source document can be
obtained. We represent the pair of vectors in a bi-dimensional plane [
Approximate successive fingerprint section seqA seqB ... ...
...
...
No-match fingerprint Match fingerprint
Given line ai , class ai conditions are fitted: xi y j (x j yi ) y xi is the beginning position of line ai in the fingerprint vector of the suspicious document, yi is the beginning position of line ai in the fingerprint vector of the source document, li is the length of the line ai . There is a class ai , and line ai belongs to class ai . The idea of the clustering is that, given a passage with ai as axis and width is 2 y , if line a j falls within this passage, and the distance between ai and a j along the passage’s direction is less than x , then we merge a j into class ai . Clustering formula is as follows:
and ai ai , j i ， if the following two (xi yi li ) (x j y j l j ) 1.4 (li l j ) x then a j ai .
By clustering, we can merge these small lines in the shadow square in figure 1 into a long line. The beginning and the end positions of the long line are the lower left and upper right of the shadow square. 4.3
The locating step uses the distance between approximate successive fingerprint sections to decide whether needs to merge or not. If using the same clustering parameter to merge those copy texts, which have different lengths and different obfuscated degrees, may cause merging errors.
For the second merging error, we use the similarity to decide whether discard copy texts. After merging, we compute the similarity of all copy texts, and discard those copy texts whose similarities are less than the threshold. This approach will discard some high-obfuscated copy texts, because the similarity of these copy texts is relatively low. Through repeated experiments, copy texts whose similarities are less than 0.05 have mostly merging error, so we discard them.
From the analysis of the third merging error, we can find that there are two reasons causing the merging error. One is that we merge some sparse points into a fragment that in fact is not plagiarism. Another is that some fragments in the source document are indeed similar to the same fragment in the suspicious document. In the real competition, we do not know the right answer, so for this situation, we rank the product of the copy text’s length and the respective similarity, and then select the copy text whose product is the largest, and discard other copy texts. Through testing in the training dataset, this approach can get a good result. 5
We tested our method in two datasets. One is the union of training and test corpus in PAN-09, including 14429 source documents and 14428 suspicious documents. The other is only test corpus for PAN-09, which is composed of 7215 source documents and 7214 suspicious document.
Our experiments ran on 8 entries HPC (High Performance Computing). Each entry has a Dual-route Intel Xeon 4 cores 5500 series processor and 4G memory. In each experiment, we started 24 threads, 3 threads of each entry. The total running time was 25 hours in the union corpus, and 7 hours in the test corpus.
There are 15925 suspicious documents and 11148 source documents in the PAN10 corpus, and the source documents contain 665 non-English documents. We used google translation api to translate about two thirds of the non-English documents into English. We used the cluster-based plagiarism detection method mentioned above to run this corpus in the same experimental environment, and the overall score is 0.7087, and the rank is: 2. 6
The method we proposed is cluster-based plagiarism detection method, which has been used in South China University of Technology to check plagiarism in network engineering related courses. And we also used it to detect external plagiarism in PAN10 competition. The method uses Winnowing's fingerprint extraction algorithm, consists of three steps: The first step is pre-selecting. For each suspicious document, the task is to find out a small list of candidate documents in which the plagiarized content may exist from the source documents set quickly. The second step is locating, which compares the suspicious document with each document in the candidate documents to get the copy fragments out of the suspicious document. The last step is post-processing, which discards some fragments without plagiarism from the end result References