Comment puis-je suivre les positions de caractères d'origine dans une chaîne à travers les transformations?

Question

Je travaille sur un projet anti-plagiat pour ma classe CS. Cela implique de détecter le plagiat dans les cours d'informatique (missions de programmation), grâce à une technique décrite "Winnowing: Local Algorithms for Document Fingerprinting."

Fondamentalement, je prends un groupe d'affectations de programmation. Disons que l'une des missions ressemble à ceci:

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

Cela doit se lancer à travers une extrémité avant, une partie d'analyse lexicale à bande sur les caractéristiques du code que nous ne voulons pas. Dans ce cas, je veux renommer tous Noms d'identificateur à la constante "V" et dépouiller tous les commentaires du code.

Pour ce faire, nous allons utiliser ANTLR et les grammaires existantes pour différentes langues pour générer les lexers appropriés.

Le résultat final est la suivante:

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

Nous bande alors tous les espaces pour obtenir:

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

Cette chaîne est alors décomposée en k-grammes d'une taille prédéfinie. Par exemple dire k = 5 (en réalité, il serait plus):

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

Voici le problème:

Chaque k-gramme est hachée avec une fonction de hachage de roulement et est censé être enregistré avec leur position de caractère d'origine dans le texte source. Un hachage k-gram et une position de caractère forment ensemble une empreinte digitale.

Comment puis-je garder une trace de la position d'origine d'un k-grams dans le texte source sur l'ensemble de l'effacement des identifiants, des commentaires et des espaces blancs?

Ceci est essentiel pour la phase finale du programme où vous mettez en surbrillance des correspondances dans des paires de documents dans le texte source d'origine. Afin de mettre en évidence les correspondances de hachages k-gram, j'ai besoin de savoir où ce k-gram a commencé et s'est terminé dans la source originale.

Answer 1

Les lexers ANTLR assurent le suivi des positions de jetons dans le flux source.

• Déplacer les commentaires et les espaces sur le canal caché
• Définissez la propriété Text de jetons d'identification à « V »
• Exécutez votre hachage de roulement contre un CommonTokenStream, regardant la propriété Text de chaque jeton.

Avec les jetons intacts du début à la fin, le mappage sera également conservé.

Answer 2

Hey, pourquoi utilisent cette étape:

Cette chaîne est ensuite décomposé en k-grammes d'une taille prédéfinie. Par exemple disons k = 5 (en réalité ce serait plus grand): publi ublic blicc liccl iccla ...= 0;}}

Je veux dire pourquoi cela est-il requis pour la détection du plagiat?