How WRepeatfind works

WRepeatfind uses the same fast matching engine as WCopyfind, turned inward: instead of comparing two documents, it compares a document with itself.

1. Words become numbers

WRepeatfind reads your text word by word, applies your settings (ignoring case, punctuation, or numbers), and turns each word into a number, a hash code. The same word always gets the same number, so from here on comparing words means comparing numbers, which is very fast. For a book of chapters, the chapters are read in order into one long list.

2. Identical words are gathered

WRepeatfind sorts the list of numbers, so every occurrence of each word ends up side by side, still labeled with its position in the text. A word that appears five times is now a small group of five positions. Each pair of positions in a group, an earlier occurrence and a later one, is a place where a repeated passage might begin.

3. Matches grow into passages

From each such pair, WRepeatfind looks at the words before and after both occurrences and extends the match as long as they agree, bridging small differences if you allow them (a changed, added, or dropped word), the same way WCopyfind does. Two rules are special to looking within one text:

• The copies can't overlap. The earlier copy must end before the later one begins, so a phrase isn't "repeated" just by running into itself.
• A passage can be the source of many copies. A word can belong to the later copy of only one passage, but any passage can be the earlier copy of several. That's how a passage that appears three times is found three times, not twice.

For each later word, WRepeatfind tries every earlier occurrence and keeps the longest match, so a passage is paired with its real twin rather than a short coincidence. A match is kept if it has at least as many exactly matching words as your Report phrases of at least setting. Copies never cross from one chapter file into the next.

4. Copies are gathered into repeats

Pairs of copies that share any words are joined into one group, so a passage appearing in three places becomes one repeat with three copies. The repeats are numbered in the order they first appear, and the report highlights each one in its own color.

Why it's fast

Sorting brings identical words together in a single step, so WRepeatfind never has to compare every part of the text with every other part directly. A 250,000-word text takes under half a second, including writing the report.

The engine is in WRepeatfind/RepeatFinder.cpp in the source code on GitHub.