How WCopyfind works

How can a program compare hundreds of documents, every one against every other, in a few seconds? The trick is to avoid comparing text directly at all.

1. Words become numbers

WCopyfind reads each document one word at a time. After applying your settings (ignoring case, punctuation, or numbers, and skipping non-words), it turns each word into a 32-bit number called a hash code, computed from the word's letters. The same word always gets the same number, and different words almost always get different numbers. From then on, WCopyfind never looks at letters again: comparing two numbers is much faster than comparing two words.

Each document becomes a list of numbers in reading order, and WCopyfind also makes a second copy of that list sorted from smallest to largest, remembering where in the document each number came from.

2. Shared words are found by merging

To compare two documents, WCopyfind walks through their two sorted lists together, the way you would merge two sorted decks of cards. Whenever it finds the same number in both, the two documents share that word, and it notes where the word appears in each. This finds every shared word in a single pass through both lists, instead of checking each word of one document against each word of the other.

Very short words such as "a", "the", and "of" appear everywhere, so WCopyfind doesn't start matches from words of three letters or fewer. Any matching phrase long enough to count almost always contains a longer word to start from.

3. Matches grow into phrases

Each shared word is a possible starting point. From there, WCopyfind looks at the words before and after it in both documents (now in reading order) and extends the match as long as the words keep agreeing. The result is the longest phrase the two documents share around that word.

If you allow imperfections, WCopyfind keeps going across small differences: a changed word, or a word added or dropped in one copy. It tallies each such flaw and stops when there are more flaws in a row than you allow, or when the share of exactly matching words falls below your minimum percentage. The percentage rule means long, nearly identical passages are easily joined, while short phrases with several differences are not, which stops unrelated text from being stitched together.

A phrase is kept if it contains at least as many exactly matching words as your Match phrases of at least setting. Its words are then marked as used, so the same text isn't counted twice.

4. Pairs are reported

When all the shared words of a pair have been tried, WCopyfind adds up the words in its matching phrases. If the total reaches your Report pairs that share at least setting, it writes a side-by-side page for the pair, marking each phrase so that both documents can be highlighted and linked.

Why it's fast

Sorting each document once, and then merging sorted lists, means the work of comparing two documents grows roughly with their length, not with the product of their lengths. Most of the time goes into the pairs that actually share text; unrelated pairs are dismissed almost immediately. That's why a class set of papers takes seconds.

Where the code is

WCopyfind is written in C++. The comparison engine is in WCopyfind/clib/CompareDocuments.cpp in the source code on GitHub, and the document reading and word handling it shares with WRepeatfind are in the Common folder. Lou Bloomfield's original explanation of how WCopyfind and Copyfind work (PDF) describes the same approach in more detail.

WCopyfind's companion, WRepeatfind, turns this engine inward to find repetition within one document. See how that works.