How can I keep track of original character positions in a string across transformations?

Question

I'm working on an anti-plagiarism project for my CS class. This involves detecting plagiarism in computer science courses (programming assignments), through a technique described "Winnowing: Local Algorithms for Document Fingerprinting."

Basically, I'm taking a group of programming assignments. Lets say one of the assignments looks like this:

public class MyClass
{
    public static void main(String[] args)
    {
        // declare a variable called someVar
        int someVar = 0;
    }
}

This needs to get run through a front-end, lexical analysis portion to strip out features of the code we don't want. In this instance I want to rename all Identifier names to the constant "V" and strip all comments from the code.

To do this, we will use ANTLR and existing grammars for various languages to generate the appropriate lexers.

The end result is this:

public class V
{
    public static void V(String[] V)
    {
        int V = 0;
    }
}

We then strip all whitespace to get:

publicclassV{publicstaticvoidV(String[]V){intV=0;}}

This string is then broken down into k-grams of a preset size. For example say k = 5 (in reality it would be larger):

publi ublic blicc liccl iccla ... =0;}}

Here is the problem:

Each k-gram is hashed with a rolling hash function and is supposed to be recorded with their original character position in the source text. A k-gram hash and character position together form a fingerprint.

How can I keep track of a k-grams original position in the source text across all the front-end stripping of identifiers, comments and white-space?

This is essential for the final phase of the program where you highlight matches in pairs of documents in the original source text. In order to highlight the matches of k-gram hashes I need to know where that k-gram started and ended in the original source.

Answer 1

The ANTLR lexers keep track of token positions in the source stream.

• Move comments and whitespace to the hidden channel
• Set the Text property of identifier tokens to "V"
• Run your rolling hash against a CommonTokenStream, looking at the Text property of each token.

With the tokens intact from start to end, you'll have the mapping preserved as well.

Answer 2

Hey, why are using this step:

This string is then broken down into k-grams of a preset size. For example say k = 5 (in reality it would be larger): publi ublic blicc liccl iccla ... =0;}}

I mean why is this required for Plagiarism Detection?