This report explains our Arabic plagiarism detection system which we used to submit our run to AraPlagDetect competition at FIRE 2015. The system was constructed through four main stages. First is pre-processing which includes tokenisation and stop words removing. Second is retrieving a list of candidate documents for each suspicious document using K-gram fingerprinting and Jaccard coefficient. Suspicious documents are then compared indepth with the associated candidate documents. This stage entails the computation of the similarity between constructed N-grams with K-overlapping where N and K were experimentally assigned to 8 and 3, respectively. The similarity between N-Gram pairs were computed based on word correlations. Each word was compared with words in candidate N-Gram and correlated by 1 if they are matched. Correlation values were averaged then compared to a threshold. The last step is post-processing whereby consecutive N-Grams were joined to form united plagiarised segments. Our performance measures on the training corpus were encouraging (recall=0.829, precision=0.843, granularity=1.11). The recall measure on the test collection was unfortunately less (recall= 0.530) but precision and granularity remained consistent with the train set (precision= 0.831, granularity= 1.18). This drop in recall may be due to the fact that our candidate retrieval stage retrieves only documents which share copied fragments but there exist plagiarised documents which have no exact-copied cases. Although this system can detect some means of obfuscation such as restructuring or rewording of few phrases, it might not work with handmade paraphrases. Our future work is to advance the candidate retrieval stage and contain semantic-based metrics in the detection stage.
Methods for Arabic plagiarism detection can easily track verbatim plagiarism; however, finding excessive plagiarism cases on a high-scale dataset is challenging. Many current techniques rely on exactly matched substrings or some kinds of textual fingerprinting. This paper aims to detect cases of rephrasing and rewording the content in Arabic texts. In this regard, matching fragments of text can be approximated by correlating the words from two candidate texts. In this paper, the problem considered is stated as follows. Given a suspicious document dataset Dq and a large source collection D wherein a small subset Dx is similar to a suspicious document dq, the task is to find all suspicious parts sq from each dq:dqϵDq that are similar to parts sx from dx:dxϵDx which is known as external plagiarism detection [1]. This work used on word correlations from N-grams with k-overlapping approach similar to our previous work in PAN’10 [2]. The languages of both suspicious and candidate documents are written in Arabic.
features for each dqϵDq and dϵD. Second, find a list of most promising documents Dx where DxϲD based on K-gram fingerprinting and Jaccard similarity coefficient. Third, perform
comparison between N-grams using word correlation approach.
Arabic Suspicious Documents dq
Preprocessing d′ ,d′ q
d′ ′ ,d′ ′ q
Jaccard List of Jaccards
For each dq Ǝ Dx : dx ϵ D
Phase I Phase II
plagiarism detection. The operational framework is shown in Figure 1. The process starts with a set of source collection D and suspicious/query documents Dq. Then new representatives namely d′ and d′ q are generated for cleansed and tokenised dq and d documents respectively. Then, d′ and d′ q are used for K-gram fingerprinting and computing the similarity between the shingles. The list of most similar documents for each dqϵDq is called candidate set Dx whereby DxϲD. After generating Dx, detailed analysis stage is performed to obtain similar N-grams (sq, sx) where sq∈dq, sx∈dx. The similarity score is gained by implementing a word-based correlation approach between words in both N-grams as will be seen shortly. Finally, the system performs post-processing in order to merge similar N-grams into passages (pq, px) such that pq∈dq, px∈dx. Subsequent sections detail each stage.
Near duplicate detection methods can be used to bring similar sources and discard dissimilar ones. We use K-gram fingerprinting and Jaccard coefficient approach [3]. The k- gram referred to a sequence of consecutive words of size k. The value for k is typically 3 or 4. Intuitively, two documents A and B are similar if they share enough k-grams. By performing union and intersection operations between the k-grams, we can find the
J(A,B)=|K-grams_A ∩K-grams_B| / | K-grams_A ∪ K-grams_B| (1) Therefore for each suspicious document dq, documents of Jaccard coefficient above a threshold value are taken to form the set of candidate documents Dx. We set the threshold of Jaccard ≥ 0.1 because we found that this value derives about 1 to 20 candidate documents for each dq. It was found that when we compare documents of Jaccard similarity less than 0.1, either none or about 1-2 plagiarised statements are detected. Also by using this method, we find that some suspicious documents do not have any candidates. That means that they might contain very obfuscated plagiarism or do not contain plagiarism at all. More interesting, using this approach assumes that the number of candidates for each suspicious document is dynamic and may be small. That saves the computation time in contrast to having a fixed number of candidates for each suspicious document.
(dq , dx) pairs At this stage, a detailed analysis between each suspicious document dq and its candidate document dx∈Dx is performed. At first, dq and dx are segmented into N-grams with K-overlapping Sq and Sx respectively. N and K were experimentally assigned to 8 and 3 because these values were found the best to achieve optimum precision and recall on the training set. An example of this segmentation is shown in Figure 2. 6يمورلا 5نيدلا 4للاج 3جارسلا 2انرمأ 1حضفت 01روصلا 11ةديصق 10دهشم 9ةركاذلا 8فقوأ 7لواحأ
01رطملا 01مدلا 01ثادحلأا 6 يمورلا 5نيدلا 4للاج 3جارسلا 2انرمأ 1حضفت
8فقوأ 7لواحأ 11ةديصق 10دهشم 9ةركاذلا 8فقوأ 7لواحأ 6يمورلا
01ثادحالأ 01روصلا 01رطملا 01مدلا 01ثادحالأ 01روصلا 11ةديصق
Fq,k = S1=“ S2=“ 1 0 ” and ” Next, to compute the similarity between two N-grams (sq, sx), a word to N-gram correlation factor for each word wq in sq and the N-gram sx is computed as in [4]:
μq,x= 1−∏ wk ∈Sx(1 – Fq,k) where wk are words in sx and Fq,k is proposed as follows: if wk and wq are identical otherwise (3) (2) are almost identical except for one word and with some restructuring. The similarity between (sq, sx) is expressed using the equation
Sim(sq, sx) = ( μ1,x+ μ2,x+ . . . + μq,x+. . . + μn,x) / n (4) where n is the total number of words in sq. Thus, we can calculate the degree of similarity between the S1 and S2 as shown in Figure 3 taking into account that stop words were removed. This indicates that N-grams are very similar. Thus to judge two sentences as equal (i.e. plagiarised), the minimum similarity score should be above a threshold value as stated in equation (5). The value of α was set to 0.85 in the experimental works. According to this, the pair shown in Figure 3 is considered similar (i.e. plagiarised) because the minimum similarity is greater than α.
EQ(sq, sx) = 1 0 if MIN(Sim(sq, sx), Sim(sx, sq)) ≥ α otherwise (5) Finally, the output of this algorithm is a list of pairs (sq, sx): sq∈dq, sx∈dx, dx∈D marked as similar/plagiarised. Because of using Ngrams as comparison scheme, post-processing is required to merge subsequent sentences marked as plagiarised into passages. Also, we consider small distances under the predicate less than or equal to 300 characters to merge subsequent plagiarised N-grams and their corresponding source N-Grams into passages pairs (pq, px) : pq∈dq, px∈dx, dx∈Dx.
3.1 Instrumentation
cores, we worked on C#.NET 2010 which has introduced the concept of parallel computing1. 3.2
Below is a list of some parameters and settings that we have configured in our code.
For pre-processing, stop words removal were used. For generating k-grams, the k was set to 3 (i.e. word 3grams). For computing Jaccard similarity and finding candidates, a threshold value of Jaccard=0.1 was set to filter out noncandidate documents. For plagiarism detection, the equations (2)-(5) were employed, and the threshold in (5) was set to α= 0.85 which was found to be the most suitable based on our experimental trials.
The run time of the training set was 12 hours (using parallel computing on 16 cores). The same time (12 hours) was consumed for the test set using parallel computing on 16 cores. 4 Evaluation and Conclusion Our results from the training and test datasets are shown in Table 1. The results from training set showed that we detected about 83% of the plagiarism cases and about 85% of the detections were correct. These results are highly encouraging and good for Arabic plagiarism systems. The experimental works on the test set shows high precision where 83% of detected cases were correct but moderate recall equals to about 53%. The decrement in recall between the training and test sets might be due to these reasons: (i) unlike in the training set, the candidate retrieval stage was not sufficient to retrieve all relevant documents to the plagiarism cases in the test set, (ii) we used high threshold in the detailed analysis stage (α= 0.85) but in previous works it was set between 0.75-0.65. Our future work is to improve it for more detection efficiency and less time complexity. We will consider using semantic measures for simulated and hand-made plagiarism cases.
α 0.85
Recall