Nowadays, plagiarism detection becomes as one of major problems in the text mining eld. New coming technologies have made plagiarisation easy and more feasible. Therefore, it is vital to develop automatic system to detect plagiarisation in di erent contents. In this paper, we propose a trie to compare source and suspicious text documents. We use PersianPlagDet text documents as a case study. Both character-based and knowledgebased techniques for detection purposes have improved our method. Besides, our fast algorithm for insertion and retrieval has made possible to compare long documents with high speed.
Plagiarism means trying to pass o somebody else's words
as your own [
There have been many approaches proposed based on
lexical and semantic methods. On the one hand, the
plagiarisation problem could be reduced to the problem of nding
exact matched phrases, and, on the other hand, it could be
as hard as nding restated phrases. Due to what a problem
asked, di erent knowledge-based or character-based
techniques could be applied. One of the lexical database for
knowledge-based approach is the wordnet database. In this
database di erent words are grouped together based on their
cognitive synonyms[
Plagiarized documents can be in any languages which need
di erent policies to be detected due to di erent semantics
and grammars. In this paper, we have proposed a novel
approach for the PAN FIRE Shared Task of Persian plagiarism
detection in the international contest PersianPlagDet 2016.
We have used a hybrid method considering both
characterbased and knowledge-based approaches. A Persian wordnet
database, Farsnet, is considered as our knowledge database
[
There are many studies to nd solutions for the
problems of plagiarism detection and document matching. In
the Nineties, studies on copy detection mechanisms of
digitalized documents have led to computerized detecting
plagiarism [
The plagiarism detection problem is also studied in di
erent languages. For Persian language plagiarism detection,
In [
Our fast trie-based approach is proposed for the problem of the persian language plagiarisation detection. We describe the problem data and data preprocessing applied to documents in section 2. Then, in section 3, the novel approach for plagiarism detection is described, and, in section 4, algorithm evaluation measurement is described, and our approach is evaluated. Finally, the results are concluded in section 5.
The data is a set of suspicious and source text documents
released by PersianPlagDet competition [
Before applying plagiarism detection method, the source and suspicious text documents should be prepared. We explain the processes needed before plagiarism detection step by step:
We tokenize text documents into words. Tokenization is the
procedure of splitting a text into words, phrases, or other
meaningful parts, namely tokens [
First, we normalize text documents. Normalization is the task of transforming text characters into a unique and normal form of a language. For example, we convert all Arabic \yaa" and \Kaaf" to Persian \ye" and \Kaaf" for preprocessing Persian text documents, and we unify all numbers with di erent Persian and English unicodes. Punctuations are also removed from text documents.
Stop words are also removed from text data. Stop words are words which are moved out from text data in processing steps because they do not contain signi cant information. First, a group of stop words has been selected which an expert has proposed. Then, frequent words are also chosen and removed with considering a frequency threshold value.
The next step is to specify words stems. There are many kinds of words in ections and derivations. The su ces \haa", \aan", \yaan", \aat", \ien" and somtimes \gaan" could make a single word plural. We remove these su ces from nouns. Also, Arabic broken plurals are the most challenging kinds of noun pluralization which cannot be distinguished by removing some su ces. An expert has provided the words stems by the help of Dehkhoda and Moein dictionaries which could help us to convert Arabic broken plural nouns to singular ones.
After de ning words part-of-speech, we search through the Farsnet to nd the nouns cognitive synonyms, synsets. We nd synsets because words may have be used instead of their synonyms in di erent positions. For example, \computers" may be used as \estimators" or \data processors". Like the words o sets, the synsets o sets are stored. Notice that the synset o sets are equal to the original words o sets.
To solve plagiarism problem, o sets speci cation of word tokens and also collecting noun words synsets and words stems are basic satellite data to be used in our proposed tree model, trie, which is explained in the next section. 3.
After source and suspicious documents have been preprocessed, we use a method to nd similar fragments and their exact o sets in both suspicious and source les. Before source and suspicious documents being compared, documents are saved to and retrieved from a trie data structure. In the next subsections, there would be a brief survey of trie trees and an explanation of our new proposed trie. 3.1
A tokenized document is a set of words which can be stored in a dictionary. A trie data structure can be used to insert and nd words in a dictionary in O(n), n represents a single word length. The word \trie" is actually comes from the \retrieval" which is its usage. In the trie tree, the pre x tree, each node is a word or a pre x. All pre x characters of a word are inserted as a node, and the last letter is agged as the word end in trie. Trie trees could have < key; value > data structure. Words with similar pre xes may have similar subpaths. As an example brought in Figure 1, the word \xy" value is \2". Besides, \xy" and \xyzb" words have similar subpath. The node values are de ned based on the problem. In the following, we describe the proposed trie and di erent key values.
In this paper, we use trie data structure to insert and retrieve documents words due to trie properties i.e. fast insertion and searching and its high adjustment to our problem example, for a potential copied phrase P = fw1; w2; :::; w5g in source and suspicious documents, if the synonym of w2 were used instead of w2, both w2 and its synonym are added to the trie.
Furthermore, if w2 were deliberately added or deleted from the suspicious document, our plagiarism detector system could detect the plagiarized section P correctly. This feature is achieved because of the nature of the linked lists which we could trace the front and rear of words with. According to di erent POS in sentence, the words can be weighted di erently for being added to removed intelligently. 4.
We use macro-averaged precision and recall, granularity
measurements, and the plagdet score described in [
∑ jSRj s2SR jRSj solving i.e. de ning the o sets of plagiarized strings. Our method for plagiarism detection is divided into two di erent processes:
After preprocessing both source and suspicious documents, all the words with their exact positions in the source document are inserted into trie, and the suspicious words are added into an ordered list based on their position in the document. According to the trie de nition, each trie node is a part of preprocessed words. In the proposed trie, each word has a \word positions" list which includes the word occurance positions in the documents. Notice that the words may have occurred in di erent positions in the document, but they are only inserted once in the trie, and their occurance positions are added in the words positions lists. Also, the words positions lists are only considered for the nodes which represent the last character of words. The more repeated words include in the suspicious document, the faster the trie can be constructed.
Due to enhancing searching speed, It is better to save the longer document in the trie, however we always save the source doument in the trie for simplicity.
To report plagiarized sections, it is important to nd similar words based on their sequential occurrences in the source and suspicious documents. The contiguity of words in suspicious documents could simply be kept based on the applied data structure i.e. ordered list. For the source documents, the words positions lists added in the trie will help us to nd the order of words in the source plagiarized sections.
After constructing documents data structure, the longest plagiarized fragments should be found in both source and suspicious documents. Thus, we iterate over the suspicious document words one by one and nd the corresponding words in source trie. It is obvious that nding words in trie contribute to obtaining the word positions in the source document. Also, the detected plagiarized positions of the suspicious document are added to the corresponding word \suspicious positions" list in the trie.
When a similar word is found in both documents the information of the word front and rear words in source document in also kept in the trie:
consider Wp = fwp1 ; wp2 ; :::; wpn g is the list of suspicious words in ordered list and Ws = fws1 ; ws2 ; :::; wsm g is the ordered list of source words inserted in the trie. Where n is the number of words in the suspicious document and m is the number of distinct words in the source one. If wp1 = ws1 and wp2 = ws2 , then \ws2 ", \ws2 position in the source" and \wp2 position in the suspicious" are added as the ws1 front node \value", \words position list" and \suspicious position list". Moreover, ws1 is added as the rst of a sentence into the \sentence list". The process is also correct for rear nodes.
Traversing the suspicious document thoroughly leads to generating a set of linked lists helping to nd the plagiarized fragments. The \sentence list" includes the rst of plagiarized sections. By looking at the rst of sentences in the sentence list and nding them in the trie, all the plagiarized fragments could be found.
Adding both the exact word and its synonyms (with the help of Farsnet) to the trie would cause to nd the potential similar sections which are plagiarized by restatement. For (1) (2) (3)
tions and RS
SR = fsjs 2 S ^ 9r 2 R : r detects sg;
RS = frjr 2 R ^ r detects sg:
Plagdet score is an overall score which considers the other
mentioned measurements. The Plagdet score overall score
is as follows [
F log2(1 + gran(S; R)) In which S and R are detections and true cases of a plagiarism and F is F M easure, the weighted harmonic mean of precision and recall which can be de ned as bellow; F = (1 + 2):
precision:recall ( 2:precision) + recall If is not prede ned, we consider = 1.
Table 1 shows the evaluation of our approach on the test
data released by PersianPlagDet 2016 competition which is
based on TIRA and the PAN evaluation setup [
The advents of digitalization and technology have simplied the act of plagiarizing. Thus, it is crucial to develop an automatic systems to detect plagiarisation in di erent contents.
We rst prepared the text data released by international PersianPlagDet 2016 contest. We made the data ready by preprocessing, tokenization and Morphological analysis (e.g. POS tagging) before documents comparison. In this paper, we have proposed a novel trie-based approach to save and retrieve source and suspicious preparation documents for solving the plagiarism detection problem. Fast inserting and retrieval long sentences were our reasons to exploit trie trees structures for the detection problem. Both nding noun words and their synsets with saving them to our extended trie have helped us to improve our text comparison especially in the case of restatement phrase matching.
To evaluate our algorithm, we used macro-averaged precision and recall, granularity measurements, and the plagdet score which were proposed by the PersianPlagDet competition. High precision, recall and acceptable granularity made the overall plagdet score for our algorithm admissible. Besides, thanks to the help of our proposed trie, large documents can be compared for the purpose of plagiarism detection.
In the next study, we will work on the contiguity of text plagriasied phrase for better granularity results. Besides, we will consider other part-of-speech synsets like verb synsets to improve our algorithm performance.