This paper describes a joint software entry by King Fahd University of Petroleum & Minerals and the University of Sheffield for the text-alignment task at PAN-2014. We employ the three steps of seeding, extension and filtering for text alignment. For seeding we use character n-grams with a variant of the RabinKarp Algorithm for multiple pattern search. We then use an elaborate merging mechanism with several cases to combine the individually found seeds. A short filtering step is then used to remove extraneous passages. This approach scored plagdet scores of 0.65954 and 0.73416 on test corpora 2 and 3 during the final test run.
Text Reuse Detection has been a part of plagiarism detection at the PAN Competition
since inception as text alignment [
Several approaches have been employed by participants for text alignment
including character n-grams, word n-grams and their variants, along with various similarity
metrics. Three distinct stages in participants’ approaches have been identified in PAN
Overview paper for 2013 [
For our current year’s (2014) entry, our submitted software also consists of these
three stages of seeding, extension/merging and filtering. In the seeding stage we use
character n-grams after post-processing and apply a variant of the Rabin-Karp
Algorithm [
As outlined in the first section our approach consists of 3 phases: seeding, extension and filtering along with some preprocessing. An overview of the resulting software appears in the block diagram as shown in Figure 1. The language of the software was java.
to source files ........... n p a m h s a h i t l u M
of char n-grams with (key, value) pairs as (char n-gram, position pair)
Initially the ‘pairs’ file is sorted according to the source file by file number. Since one
source document may be linked to several suspicious documents, a single hashing of
source document is repeatedly used for finding matches in corresponding suspicious
documents. Furthermore, during hashing, all punctuation, whitespace and non-printable
characters are removed. This is done as two perfectly reused strings (one in the source
document and other in the suspicious one) could go undetected because of an unequal
amount of spaces, punctuation and/or other characters.
Seeding is defined as “Given a suspicious document and a source document, matches
(so-called “seeds”) between the two documents are identified using some seed
heuristic.... By coming up with as many reasonable seeds as possible, the subsequent step of
extending them into aligned passages becomes a lot easier”. [
For seeding, or identifying exact matches of character n-grams between two
documents, we use Rabin-Karp Algorithm [
Once the multihashmap for a particular source document is created, we make a run of each suspicious file to find the matching character n-grams. The output is a list of pairs of 3-tuples: one from the source file and the other from the suspicious file. source-document01999 (2013 Test Corpus 2) Mutiple Valued Hash Map What are the symptoms of arrhythmias? The effects on the body are often the same, however, whether the heartbeat is too fast, too slow, or too irregular. Some symptoms of arrhythmias include, but are not limited to: weakness The symptoms of arrhythmias may resemble other conditions.
KEY char n-gram symptomsof arrhythmia theeffects onthebodya
VALUE (start, end, size) (x1, y1, size1), (x2, y2, size2), (x3, y3, size3).
.......
For example after the algorithm is run on a source file with the corresponding suspicious file, the output would be a list of the form:
List of 3-tuple pairs = f(x1; y1; s1) ! (a1; b1; s′1); (x2; y2; s2) ! (a2; b2; s′2); : : :g In the list above, the entry (x1; y1; s1) ! (a1; b1; s′1) means that the text in the source file from position x1 to y1 of size s1 is aligned with the text in the suspicious file from location a1 to b1 of size s′1. It may be noted that y1 > x1 and b1 > a1, furthermore s1 y1 x1, s′1 b1 a1. 2.3
Extension Once the list of matching pairs is generated between a pair of source and suspicious documents, the next step is the extension or merging of these matches into contiguous, aligned passages. This is done by combining seeds or matches that satisfy certain criteria both in the source and suspicious documents into larger matches. We identify four distinct categories of matches as follows based on their vicinity towards each other.
Consider two matching pairs (x1; y1; s1) ! (a1; b1; s′1), (x2; y2; s2) ! (a2; b2; s′2) where (x1; y1; s1) indicates text from position x1 to position y1 of size s1 in the source document, and (a1; b1; s′1) indicates the corresponding text from position a1 to b1 of size s′1 in the suspicious document. In order to merge these pairs in each of the source and suspicious documents, we identify four categories of matches as follows: 1. Containment: Containment is the relationship between two matches within the same document when the text-positions of one match are fully contained within the text-positions of the other. More formally, the match (x2; y2; s2) is contained within (x1; y1; s1) if x2 x1, y2 y1 and the size s1 s2. 2. Overlap: Two matches (x1; y1; s1) and (x2; y2; s2) overlap if some, but not all textpositions of the first one are contained within the text-positions of second match. More formally, the match (x1; y1; s1) overlaps (x2; y2; s2) if y2 y1 x2 x1 i.e., x2 lies between x1 and y1, y1 lies between x2 and y2. 3. Near-Disjoint: Two matches are near-disjoint, if they are close enough to be combined into a single chunk of text, i.e. separated by a small number of characters, but have no overlapping text-positions. More formally if (x1; y1; s1) and (x2; y2; s2) are two matches such that 0 x2 y1 gap, where the parameter gap depends on the particular features of the training corpus, then the matches may be categorized as near-disjoint. 4. Far-Disjoint: Two matches (x1; y1; s1) and (x2; y2; s2) are far-disjoint if they are separated by such a large number of characters that they cannot be adequately merged into a single chunk of text. In this case x2 y1 > gap.
Containment: x2 >= x1, y2 <= y1
Overlap: y2 >= y1 >= x2 >= x1 x1 x1
Near-disjoint: x2 - y1 <= gap x2 y2
y1 gap y1 x2 y2 x1 x1 x2 y1
gap Far-disjoint: x2 - y1 > gap Strategy for Merging The overall strategy for merging is based on the idea that two matching pairs that have either one of the containment, overlap or near-disjoint relationship can be merged towards forming a larger 3-tuple. 3-tuples that are far-disjoint cannot be merged. Furthermore, if two mapping pairs of 3-tuples have a different relationship in the source and suspicious documents then these tuples may be combined according to their respective categories. However, in a particular case of 3-tuples, i.e., when the 3-tuples have a near-disjoint relationship in one document and overlap or containment relationship in the other document, then no merging may be carried out. This is because it is a likely case of term-repetition, a situation in which a term is repeated within one of the documents, but it may mistakenly map to a large portion of text in the other document.
Figure 3 shows the four categories, while Table 1 gives a case-by-case listing of the merging strategies that we used for merging. 2.4
Filtering After seeding and merging, the next step is filtering. For PAN-2014 training corpus, it was observed that short passages, typically less than 200 characters resulted in a lot of false positives. Hence all passages which were less than 200 characters in the source document aligned with passages less than 100 characters in the suspicious document were removed. The final output was then written to the XML files.
Setup The first step before testing was to select the values of the parameters n and gap for character-n-grams and the gap size. Since this was a first time participation for us, one of the goals of our approach was to ensure at least a 90% precision while getting a high value of recall. After testing through a range of values, n = 20, gap = 200 was found to be the most suitable since, this set of values ensured at least 90% precision on all training corpora, while giving the highest values for the overall plagdet score and recall. 3.2
Training Corpora
We tested our approach on three corpora [
These results imply that our approach based on hashing and merging heuristics gives very good plagdet scores for no plagiarism and no obfuscation cases, mid-range scores for random and translation obfuscations, and marginal scores for summary obfuscation. 2014 Training Corpus 2013 Test Corpus 1 2013 Test Corpus 2 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0
Overall No Plagiarism
No Random Translation Summary
Obfuscation Obfuscation Obfuscation Obfuscation For the final testing, the final software was uploaded on 30/April/2014 and test runs on all three test corpora were done on 16/May/2014. No errors were found during the runs, and hence exactly a single run was done on each of the test corpora. Results of runs on test corpora 2 and 3 have been published and are listed in Table 2, while results of test corpus 1 runs were made available to the participants only (as it was the early bird corpus). It can be observed from Table 2 that the overall plagdet scores are inline with those obtained for the training corpora earlier.
Currently, performance results of the software according to various obfuscation types are not available on the test corpora. However, it is expected that these results will be in agreement with the training corpora results too. In this work, we used hashing and merging heuristics on character n-grams for text reuse detection. Our approach scored a mid-range performance on PAN-2014 test corpora. From the training corpora, it was obvious that while the approach scored very well in no plagiarism and no obfuscation types, there was room for improvement for translation and random obfuscations. Furthermore, a completely new approach may need to be devised for the marginal summary obfuscation scores.
Several directions of future work arise from here. For the current approach, a better detection with improved recall can be achieved if a more fine-grained merging mechanism is adopted with further sub-cases. Likewise, an improved granularity would also help in improvising detection score, by confining matches to only the necessary number.
On a different level, we can devise new approaches by using a variety of
mechanisms such as character skip grams [