In this paper a new approach is shown for a very fast monolingual external plagiarism detection system based on an altered n-gram concept (contextual n-gram), a new high precision contextual Information Retrieval engine, and a new pruning strategy (Referential Monotony) for plagiarism detection and its limits. The assessment results can be compared with the carried out by the winner team at PAN'09, but achieved with remarkable speed (35 min) and low hardware requirements (single laptop).
The system shown in this paper, bases the plagiarism analysis on n-grams comparison [2], but by using an special treatment to build them.
The “contextual n-gram” denomination is referred to the feature of these n-grams to describe the essential context with a very short group of word stems.
Because making n-grams by simple tokens extraction, gets analyzers very vulnerable to obfuscation, six steps are carried out when modeling documents by n-grams in order to improve the essential context definition, with gets highly useful n-grams to locate possible plagiarism, obfuscated or not: 1. Lowercase folding when tokenization (a very common practice). 2. Empty words (stopwords) filtering. This step gets n-grams much more context definitory. Stopwords are also easy to delete/change for obfuscation purposes. 3. One character tokens filtering. As they are very used in enumerations and having high frequency, they get few contextual meaningful. 4. Stem reduction (stemming) [3] contributes to get better recall for detecting plagiarisms when words are changed by derivative ones.
representative for the all possible tokens permutations set. This step reduces effectivity of words order changes due to sentence rewriting or translation [4], improving recall. 6. n – 1 tokens overlapping (on its natural order) to extract consecutive contextual n-grams, gets better detection on former obfuscation types.
May be thought that all these steps to help improving recall, may also get false Contextual trigrames positive increasing, but it is Index documents frequency study experimentally demonstrated 100,00% that steps 2 and 3 gets enough x 80,00% compensation due to the final iend 60,00% discriminative capacity got by sm 40,00% contextual n-gram. ra
Studying PAN'09 corpuses, -3g 20,00% it was probated that a high % 0,00% percentage of this n-gram type [01][02][03][04][05][06][07][08][09][10[]>10] behaves like a fingerprint for the passage/document they documents frequency belong, specially if n-grams are Figure 1: PAN'09 Development corpus 3th grade or higher. (figure 1). Contextual trigrams index
This discriminative capacity is strengthened by the neighbor contextual n-grams, being an excellent base to develop specific IRS to detect and locate plagiarisms.
By analyzing the PAN'09 development corpus, it was found that the probability for to repeat a contextual trigram from a new non plagiarized document in a concrete existing document from corpus, was of 0,0026%. However, if it's a plagiarized one, the probability to point to the correct source document is 94,37% (using only three document references max. for every trigram). Contextual bigrams gets 0,052% to be repeated in a concrete document, and 77,00% or 77,76% for pointing to correct document when existing plagiarism (using 5 or 9 references max respectively).
Contextual n-gram groups are excellent for high precision calculation of the most similar passage/document by contextual similarity.
The only inconvenience is the necessary index size, several times bigger than the own text corpus. However, an approximation to VSM, but only based on df1 proportional weighting, and a limited document references amount, is enough to get a very high precision IRS with lower memory consumption (index stores df and 2~3 max. source references if using trigrams or 5~9 if bigrams).
As plagiarizers used to take several plagiarism fonts, having an available IRS as proposed in this paper, to reduce and strength the search space [5], a change of strategy is preferable instead of returning a fix number of candidate fonts: After splitting the suspicious document, identifying only one candidate as possible source (for every split) and using the RM pruning strategy.
When analyzing, it is highly probable that a big number of suspicious fragments should have a possible source document associated. Analyzing anything would need a lot of time and/or computational resources, getting many false positives. To avoid this annoyance, a new pruning strategy is used, named Referential Monotony, consisting in rejecting (as casual matching) all suspicious fragments appearing alone, without repeating reference at least certain times (monotony threshold). RM gets a fast filtering of so enough wide suspicious sections as to point that there is a continuous high correspondence with the right source document, getting also a fast gross detection for its limits.
In the figure 2, the detection process and search space reduction by RM is shown: dark gray emphasized splits give direct detection (5 consecutive splits pointing to reference doc #91) due to pass RM threshold (4 in this example). Light gray splits are included for fishing possible words out of direct detection borders.
73 -1 6 49 11 -1 31 91 91 91 91 91 6 92 5 7 98 91 57 -1 -1 -1 61
The system presented excellent results by using only this strategy with a split length of 25 contextual n-grams and 4 times for RM threshold. The annoyance for this strategy is that plagiarized fragments shorter than 4 splits are not detected (75 contextual n-grams, or about 150 words).
To detect short length (but almost verbatim) plagiarisms, RM threshold is reduced for a zone when any split gets high similarity value.
As many plagiarizers use to employ same fonts to take several fragments, after getting sources knowledge by RM from greater zones, feedback for a second pass may be arranged for fishing the smaller, as show in figure 2 left zone. 1 Frequency of a term based in the number do documents containing it.
Our preliminary version for this idea (a necessary filtering is not yet implemented) only gets similar overall results (+/- 0,5%), but with a better precision/recall balance.
Although RM prune is the main reason, this goal was improved by several strategies: • • • • • •
Using an unbalanced binary tree to sort n-grams and building partial inverted index, later mixed as ordered vectors for final inverted index. IRS uses binary search on former vector to locate n-grams matching with source documents. This gets similar efficiency order that a balanced tree but using less memory. • Avoid repeating source-documents n-grams conversion by saving n-gram versions (while indexing), and caching last 50 analyzed.
Hardware and software used for development and PAN2010 competition: Acer Aspire laptop 5920G (Intel T5750 2.0 GHz processor, 4GB RAM), upgraded to 7200 rpm 2,5” HD.
Ubuntu GNU-Linux 10.04 64 bits edition using EXT4 file-systems.
GNU – C language. Netbeans 6.8 as IDE and Valgrind were used.
External analysis process is arranged by these main steps: 1. Language documents classification (to discard non English sources). 2. Building monolingual inverted index, saving on disk and memory loading. 3. Splitting suspicious documents by fix amount of contextual n-grams. 4. Using the new IRS to get only one source document for every split. 5. Determination of plagiarism existence by Referential Monotony. 6. Finding plagiarism border n-grams separately for suspicious zone by double search from start and end of detected gross zone over the IRS. 7. Using suspicious detected zone to search the best matching window into source document, getting better recall and precision than in suspicious section. Then a post-refinement is done for suspicious fragment limits. 8. Saving analysis results in XML files.
9. Evaluate results over training XML gold standard (if available).
Thanks to its speed, more than 150 trials were carried out on PAN'09 training corpus while system development (started last year), with contextual n-grams grade 2 and 3. The best PAN performance is got by contextual trigrams, however time and resources are better by bigrams. Ten folds2 analysis confirmed behavior regularity.
PAN-PC-09 was only used to confirm former tweaks and prospects, on a 8GB RAM PC. For the competition, we used once again the same 4GB RAM laptop.
Table 1 shows results got in several corpuses and hardware used summary.
As when writing this paper, no information is available for costs, Less is better at any bar hardware and times got by other 4000 PAN2010 teams, figure 3 shows this for best ranked teams in PAN'09, compared 3000 tboigrtahmiss s(yBs)t.emThbisy ctorimgrpaamrastiv(eT) woasr 2000 (eaHmsnwtai.n.lH.ry)eswqi.suCitiromesemtsent* estimated [6] by the available ( €) information from [7], [8] and [9]. 1000
No cross-lingual performance is 0 expected. As experimental version gets T 1º B 2º 3º lower plagdet score than monolingual, we used the last one (where non English Fig.3: PAN'09 comparative Analysis source documents are excluded). time – Hardware reqs. – Costs Overall performance got at PAN2010: 0.5851 (non official external: 0.6666 ).
Timing: Indexing (1.6 GB) 20 min 06 sec + Analysis (3.2 GB) 55 min 44 sec
Good results, with remarkable high speed and low resources. Waiting improvements: • Feedback filtering (+ recall and overall). • Multilingual version refinement (+ recall and overall). • Concurrent and/or parallel programing for multi-core machines (+ speed). • Using SSD (Solid State Disk) HD (+ speed).
Including a confidence attribute in detections would help to users and enforces hybrid analyzers development without present penalty.
Contextual n-grams could improve other NLP disciplines as clustering, classifying, reply oriented search, etc. RM prune should be also usefull in other fields.
Authors thanks to PAN-PC corpuses development team (excellent resources) and the rest of PAN organization and competitors for their motivative work and papers. 2 Similar size subsets got by dividing the suspicious corpus. 2.