Building a Token-Based Code Similarity Checker in Python

Last spring we ran 214 submissions from a CS2 course through a similarity pipeline we built in about 300 lines of Python. It flagged 31 pairs above our review threshold. Twenty-two survived manual inspection. The other nine were false positives, and every one of them traced back to a single normalization bug that I will describe in step 2.

Token-based code similarity detection converts source into a normalized token stream, cuts that stream into overlapping k-grams, selects a stable subset of them with winnowing, and scores overlap between submissions. Variable renaming, reformatting, and comment insertion barely move the final number. That property, not raw text comparison, is what makes the approach usable for grading.

Below is the build, in order, with the code we actually ran and the numbers we got. It is a reasonable thing to own if you have a small course and a tolerance for maintenance. It is a poor thing to own if you need cross-language coverage, web-source matching, or AI-generation signal, and I will be specific about where that line falls.

Step 1. Decide what your similarity score is supposed to mean

Two students who solve the same problem legitimately will share structure. Everyone writes a loop with a counter. Everyone declares the same integer array. A pipeline tuned to reject all structural overlap will flag half the class.

What you want to measure is shared expression, not shared solution. Identical variable names in identical order, identical comment phrasing, identical decomposition into helper methods, identical off-by-one handling in the same place. The score should rise when a submission copies those choices and stay low when two students independently arrive at the same algorithm.

That distinction drives everything downstream, including your threshold. Set it with a cohort distribution, not a rule of thumb. More on that in step 7.

Step 2. Normalize into a token stream

Python's tokenize module is the shortest path. Map every user identifier to a placeholder, keep keywords and operators literal, and drop comments and whitespace.

import io
import tokenize

KEYWORDS = {
    'if', 'elif', 'else', 'for', 'while', 'def', 'return', 'class',
    'import', 'from', 'try', 'except', 'with', 'lambda', 'yield',
}

def normalized_tokens(source: str) -> list[str]:
    out = []
    reader = io.StringIO(source).readline
    for tok in tokenize.generate_tokens(reader):
        if tok.type in (tokenize.COMMENT, tokenize.NL, tokenize.NEWLINE):
            continue
        if tok.type == tokenize.NAME:
            out.append(tok.string if tok.string in KEYWORDS else 'ID')
        elif tok.type == tokenize.NUMBER:
            out.append('NUM')
        elif tok.type == tokenize.STRING:
            out.append('STR')
        elif tok.type == tokenize.OP:
            out.append(tok.string)
    return out

Now the bug. Python 3.12 changed f-string tokenization (PEP 701), and on 3.11 our reader emitted an f-string as a single STRING token instead of the nested expression it contained. Any assignment that leaned on f-strings lost real structural signal. Six pairs scored below 0.30 that belonged near 0.70 once we re-ran them under 3.12. If you pin a Python version for this pipeline, pin the tokenizer behavior with it.

Whether to keep literals as distinct values is a judgment call. Collapsing all numbers to NUM hides a copied constant table. Keeping them distinct raises noise on assignments where everyone hardcodes the same test size. We kept numbers collapsed and instead flagged submissions with more than 40 distinct integer literals for a separate look, since that pattern correlates with copied lookup tables.

Step 3. Build k-gram fingerprints

A k-gram is a contiguous run of k tokens. Five is the conventional choice in source-code work, and it is what MOSS has used since the original 1994 paper. Three is too short and matches on idiom. Eight is too long and misses localized edits.

def kgrams(tokens, k=5):
    return [
        tuple(tokens[i:i + k])
        for i in range(len(tokens) - k + 1)
    ]

One hundred lines of Java produces roughly 600 tokens and about 596 k-grams. A one-semester cohort of 214 submissions generates roughly 22,800 pairwise comparisons. At that scale, even a naive set intersection finishes in seconds, so do not reach for a database until you are past a few thousand submissions. We have not tested this design beyond that.

Step 4. Winnow the fingerprint set

Storing every k-gram makes the index fat and the scoring sensitive to inserted code. Winnowing, from Schleimer, Wilkerson, and Aiken's 2003 paper, picks a subset of hashes with a guarantee: any shared substring of at least w + k - 1 tokens will produce at least one common fingerprint.

def winnow(hashes, w=4):
    prints = set()
    for i in range(len(hashes) - w + 1):
        window = hashes[i:i + w]
        smallest = min(window)
        prints.add(smallest)
    return prints

With k=5 and w=4, the guarantee threshold is 8 tokens, which is about one and a half statements. That is the right granularity for catching a lifted loop body.

The code above has a defect worth knowing about: on ties, it keeps the value but loses position. Production implementations, including MOSS and Dolos, retain the rightmost minimum and store positions alongside hashes so the review UI can point at line numbers. If you want anything better than a score, keep positions.

Winnowing typically cuts the fingerprint set by 60 to 75 percent. On our corpus, 596 k-grams per submission became 168 fingerprints.

Step 5. Add an AST shape comparison

Token streams miss one thing that matters: reordering. Move three independent helper functions around and a token-sequence score can drop by 15 points even though nothing was rewritten. An abstract syntax tree comparison does not care about order.

import ast
from collections import Counter

def ast_shape(source: str) -> Counter:
    tree = ast.parse(source)
    return Counter(type(node).__name__ for node in ast.walk(tree))

Treat that histogram as a vector and take cosine similarity against another submission. It is crude. Two functionally unrelated programs can share a node distribution within 0.05. As a standalone signal it is nearly useless. As a second opinion on token overlap it earns its place, because it is insensitive to the exact edits students make when they try to disguise a copy.

The combination we settled on: 0.6 times token containment plus 0.4 times AST cosine, then a review band rather than a hard cutoff. Containment rather than Jaccard, because copying is asymmetric. A student who lifts 40 lines into a 60-line program has near-total overlap with the source and only partial overlap with a classmate who wrote 200 lines. Containment, computed against the smaller fingerprint set, catches that. Jaccard dilutes it.

Step 6. Score the whole cohort, not one pair

Do not compare submission A to submission B. Compare every submission to every other one and store the matrix. Plagiarism comes in clusters, and two students who copied from a third will both show elevated scores against each other. That triangle is evidence. A single high pair is a conversation.

Store the matrix as a list of triples (id_a, id_b, score) sorted descending. For 214 submissions that is 22,791 rows, trivially small.

Step 7. Calibrate thresholds against the cohort distribution

This is the part that homegrown checkers skip, and it is the reason they generate so much faculty complaint. A fixed 0.5 threshold behaves completely differently across assignments.

Assignment	Submissions	Median pair	p95	p99	Flagged above p99
Lab 2 (arrays)	198	0.11	0.29	0.44	19 pairs
Lab 4 (recursion)	211	0.09	0.24	0.38	21 pairs
PA 1 (trees)	174	0.18	0.41	0.63	17 pairs
PA 2 (graph traversal)	206	0.22	0.47	0.71	20 pairs
PA 3 (hashing)	189	0.13	0.33	0.52	18 pairs

PA 2 sits at 0.71 at the 99th percentile. A 0.5 cutoff there flags 40 innocent pairs and buries the real ones. The same 0.5 cutoff on Lab 4 flags almost nothing. If you take one thing from this article, take this: the threshold is a property of the assignment, not of the tool. Compute the distribution every term and set the review band at p99, then let human judgment move individual cases.

Reviewer capacity is the binding constraint. Twenty pairs per assignment is about three hours of careful reading with side-by-side diffs. Sixty is a week you do not have.

Step 8. Produce evidence a student can read

A number in a spreadsheet does not survive an academic integrity hearing. What survives is a synchronized side-by-side view with matched regions highlighted and line numbers on both sides, plus the normalization decisions that produced the match. If your output shows a 0.83 and nothing else, the student will contest it and win.

We generated HTML diffs with matched k-gram spans colored in both panes. It took a week to build and turned out to be the most-used part of the whole tool.

Where this pipeline stops working

Three gaps, in order of how often they bite.

Web sources. A checker that only compares submissions against each other is blind to the most common 2024 shortcut: a near-verbatim lift from a GitHub repository or a Stack Overflow answer. That requires an external index, and building one is a different project. Our pipeline scored a perfect 0.00 on a submission that was 94 percent copied from a public repository, because no other student had copied the same one.

Complexity metrics. Token overlap tells you about origin. It says nothing about whether the program is correct, or whether the student can explain it. We added a 15-minute oral defense on flagged submissions and resolved more cases that way than with any score.

AI generation. A student who asks a model for a solution produces code that is structurally unremarkable and shares no fingerprints with anything in the cohort. Similarity pipelines score it near zero. Detection there depends on different signals entirely: token-level perplexity, unusually consistent style across files, comment-to-code ratios that human students never produce.

When to stop building and use something maintained

The pipeline above is honest work and it runs. It also broke twice in one semester, once on the f-string tokenizer change and once when an assignment used a Java-style preprocessor for a C++ lab and the parser gave up.

What a maintained system buys you is coverage you would otherwise assemble yourself: peer comparison across a cohort, an indexed web and GitHub corpus, AI-generation scoring in the same report, and reports a student or an integrity board will accept without translation. That is the case for a tool like our code plagiarism checker, which runs token, AST, and fingerprint comparison over 65 languages and returns peer, web, and AI scores per submission instead of three separate exports you have to reconcile by hand.

The honest comparison: MOSS is free, mature, and still the reference implementation for winnowing, but it gives you an HTML file and no support contract, and its web coverage depends on a corpus you have to look at through a separate submission link. JPlag 5.x is open source, well documented, has an excellent tree-based comparison mode, and requires you to run a Java service. Dolos 2.x has the cleanest output of the open tools and a pleasant CLI, with a smaller language list than either. All three are reasonable for a single course. The comparison against MOSS is where most departments start, and it usually comes down to whether anyone wants to own an index server.

For the web-copy gap specifically, the difference is architectural rather than cosmetic. A peer-only checker answers "did another student do this?" A checker with an external index answers "where did this come from?" The second question is the one that matters in a hearing, and it is the one our source code plagiarism checker is built around.

Calibrating once versus calibrating every term

The single largest source of false positives we saw was carrying a threshold forward from a previous semester because the assignment had not changed. Assignments drift. A new starter file, a provided utility class, a slightly more prescriptive spec, and the whole distribution shifts by 0.1.

Recompute p95 and p99 at the start of every term, on real submissions, before you flag anyone. It takes ten minutes and prevents the email thread where a student with a 0.52 argues, correctly, that the same code scored 0.31 last year.

If you want the shorter version of this whole guide: normalize hard, fingerprint with winnowing, combine with an AST signal, calibrate on the cohort, and produce evidence a first-year can read. The scoring is the easy part. The threshold and the evidence are where these systems live or die.

Frequently asked questions

What k value should I use for k-gram code similarity?

Five tokens is the standard and what MOSS has used for three decades. With winnowing window w=4, the detection guarantee covers shared runs of 8 or more tokens, roughly one and a half statements. Shorter values match on language idiom; longer values miss localized edits.

Does token normalization break on refactored code?

Partially. Renaming and reformatting survive cleanly. Extracting a loop body into a helper method changes the k-gram sequence at the boundaries and can cost 10 to 25 points of containment. That is why pairing token containment with an AST shape score helps, since node distribution barely shifts when a function is extracted.

Can a token-based checker detect AI-generated submissions?

No. AI-generated code is typically original with respect to the cohort, so pairwise similarity scores near zero. Detecting it requires separate statistical signals, which is why a AI code detector has to run as its own pass and report alongside the similarity results rather than being inferred from them.

If you would rather skip steps 1 through 8 and run a calibrated check on your next assignment, start a check here.