Brian St. Marie • Harvard ALM Thesis

Cite Unseen

A plagiarism detection system using the public web as a text corpus.

Web Search • Sequence Alignment • Natural Language Processing

Computational biology

Align Like a Protein

Sequence alignment is a common problem in computational biology that has many similarities to challenges in natural language processing.

Smith-Waterman • local alignment • dynamic programming

Smith-Waterman · two proteins

Biologists compare proteins letter by letter. Each cell scores the best match ending there: match +2, mismatch −1, gap −2, and never below 0, so a bad stretch ends a match instead of sinking it.

The highest cell traces back to the best local alignment: the stretch the two proteins share, gap and all.

Mutations didn’t hide the shared stretch. A paraphrase is a mutation of text: could the same idea find copied writing?

The example

Spot the Copy

To illustrate the function of each step, a simple example of plagiarism from Wikipedia is used.

Wikipedia original • paraphrased copy • three-word phrases

Original · en.wikipedia.org/wiki/Plagiarism

Suspect text · paraphrased from it

Pre-processing

Break It Down

Cite Unseen detects plagiarism by breaking a submitted document down into short phrases (n-grams) and passing these phrases through a designated search engine.

Unicode segmentation • overlapping trigrams • hash set

Suspect text

Zipf’s law

Ask the Web

Therefore, most n-grams are rare and if two unrelated documents are compared, they should share relatively few n-grams between them.

When searching for more common n-grams, a plagiarized source may not fall within the first ten, or even fifty search results for that n-gram.

A few phrases everywhere • most phrases rare • ten results per query

The first 11 trigrams, each searched on Google. Bar: how many pages contain it (log scale). Boxes: the first ten results, lit where the Wikipedia original appears.

Snippets

Read the Snippets

As each individual search result is processed, Cite Unseen also analyzes the summary text for additional matches.

This summary text is used by Cite Unseen to overcome the limitations of locating common n-grams in search results.

Keyword in context • O(1) hash lookups • first ten results only

Why not open each result and compare? That’s up to ten page downloads per trigram, for these two sentences alone, each to fetch and parse. But every result already comes with a snippet, the page’s own words around the query, so Cite Unseen matches those instead, with no extra requests.

query: “plagiarism is not”

Plagiarism - Wikipedia

en.wikipedia.org › wiki › Plagiarism

Match arrays

Score the Runs

Any n-gram in the submitted document that matches with a particular URL is represented by a positive weight value, while any n-gram that does not match with a particular URL is represented by a negative weight value.

As position information for matched n-grams in the source URL is not known, any break in a match sequence with the submitted document can only be seen as a gap.

+1 match • −1 gap • + (n − 1) for words

Unlike the proteins, a search result has no positions, only whether each trigram is on the page. So instead of a grid, each URL gets one row: +1 match, −1 gap, no mismatch.

Suspect text × en.wikipedia.org/wiki/Plagiarism

Kadane’s algorithm

Keep the Sum

Finding the subarray of highest net value within an array of values is known as the “maximum subarray problem” and is done quite easily in linear time using Kadane’s algorithm (Bentley, 1984).

Cite Unseen expands on Kadane’s algorithm to locate all significant word sequences for a given URL.

Running total • reset below zero • linear time

Walk the run scores left to right keeping a running total (current). Each new high is the stretch’s score. If the total drops below zero, the stretch is over: reset to 0 and start again, like Smith-Waterman’s floor of 0.

Positive subarrays

Run It Again

It is necessary to run the algorithm repeatedly until all significant subarrays are found.

Thus, subarrays can be missed after a max score has already been found but prior to reaching a point where current drops below zero.

Skip known subarrays • 2ℓ − 1 steps at worst • still O(ℓ)

A longer example from the thesis. Pass 1 works as before: a stretch closes only when the running total drops below zero.

Pass 2 skips what’s already found and scans what’s left. Repeat until a pass finds nothing: at worst about 2ℓ − 1 steps for ℓ values, still linear.

Report

Flag the Source

Displaying the copied text in the context of the original source provides a convenient method for the user to verify that the copied text came from a source of interest and helps in quickly eliminating false positive matches.

Scoring threshold 15 • highlighted by source • the original in context

What the user sees · threshold 15

Plagiarism - Wikipedia

en.wikipedia.org/wiki/Plagiarism · score

Results

Show the Evidence

While plagiarism can be identified with great success programmatically, it ultimately requires a human eye to make any final determinations.

Online tests • trigrams • sequence score 15

Read the thesis↗github.com/0xBrsm/CiteUnseen↗brsm.dev↗

F1 score on online content

F1, precision and recall in online testing, n = 3
Stage	Precision	Recall	F1