SpellChecker.indexDictionary indexes a word twice when one dictionary repeats it, so suggestSimilar returns duplicates

SpellChecker.indexDictionary skips a word that is already in the spell index, but it checks only the index as it was when the call started: the documents it adds become visible after the call. So a word that one Dictionary yields twice, such as a repeated line in a PlainTextDictionary word list or a value stored by two documents under a DocumentDictionary, is indexed twice. suggestSimilar keeps every hit, so the copies take result slots: after indexing relieve, relieve, receive in one call, suggestSimilar("recieve", 2) returns [relieve, relieve] instead of [relieve, receive]. The same words split over two calls are indexed once, as LUCENE-883 made them in 2007. The gap dates from the spellchecker's first commit (2004); it reproduces on 24 releases from 1.9.1 to 10.5.2 and on main, and the source history shows the same check in the releases between. A per-call set of the words added (+8 lines) fixes it, and the suggest module's tests pass with it.

• SpellChecker (lucene-suggest, org.apache.lucene.search.spell) is the classic n-gram spell checker. It keeps a separate spell index with one document per dictionary word: the word itself in field word, plus its n-grams.
• indexDictionary(Dictionary, IndexWriterConfig, boolean fullMerge) reads every entry of a Dictionary and adds a document for each word of at least 3 characters, unless the word is already in the spell index.
• suggestSimilar(word, numSug) runs one n-gram query against the spell index for the top 10 * numSug hits, scores each hit with the StringDistance (default LevenshteinDistance: 1 - edits / max length), and keeps the best numSug in a queue.

1. Before its loop, indexDictionary takes the current searcher and collects one TermsEnum of field word per segment (SpellChecker.java:497-508).
2. For each entry it skips the word if one of those enums finds it (:525-531), else it adds a document to a new IndexWriter (:534-535). The searcher is replaced only after writer.close() (:544, :550).
3. So the enums never see words added earlier in the same call, and a repeated entry is added again. On an empty spell index there are no enums and no check at all (:510).
4. suggestSimilar inserts every hit that passes its filters (not the query word itself, not below the accuracy cutoff) into its queue with no check that the same string is already there (:395). Each copy is its own document and its own hit, so it takes its own slot; once the queue is full, the accuracy cutoff rises to the queue's lowest score (:396-399) and shuts out lower-scored distinct words.

One call, default SpellChecker and IndexWriterConfig, query recieve, numSug 2:

relieve is 1 edit from recieve (score 0.857), receive 2 edits (0.714). The same happens on a non-empty spell index, where the check does run, and with a DocumentDictionary over a stored field that two documents share.

More copies crowd out more. Dictionary: lantern N times plus lanterns, pattern, latern, lanter, lanternfish:

In the last row the 20 copies fill the whole 20-hit window and are all skipped as the query word itself (:377).

• Who. Users of the classic n-gram SpellChecker of lucene-suggest whose single indexDictionary call receives the same word twice: a PlainTextDictionary or FileDictionary over a word list with repeated lines (for example concatenated or merged lists), a DocumentDictionary over a stored field whose values repeat across documents, or a custom dictionary. The class javadoc's example indexes "a file containing words" with PlainTextDictionary (through a one-argument indexDictionary that no longer exists). Default constructor and IndexWriterConfig suffice; fullMerge does not help.
• Not affected. LuceneDictionary and HighFrequencyDictionary enumerate the terms of an index field, which are unique, so the common index-based build is safe. DirectSpellChecker, the newer spell checker that needs no separate spell index, does not use this code. Search results never change.
• Effect. Two copies already push a distinct word out when the repeated word ranks first. With enough copies (at most 10 * numSug) they can fill the whole hit window, as in the probe: every slot is that word, and a lookup of the word itself returns nothing. Whether they do depends on how the copies rank in the n-gram query against the other words. The spell index grows by one document per extra copy.
• Downstream (from reading source, nothing run there). Solr's FileBasedSpellChecker without a fieldType clears the spell index and rebuilds it in one call over a PlainTextDictionary of its source file, so repeated lines in that file trigger it; its fieldType path and IndexBasedSpellChecker use HighFrequencyDictionary and are not affected. GitHub code search (default branches only) found no indexDictionary call in Elasticsearch or OpenSearch.
• How likely. Rare: it needs a repeated entry within one call, and the searches below found no report since the API shipped in 1.9 (2006).

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => java.lang.AssertionError: expected:<[relieve, receive]> but was:<[relieve, relieve]>
       org.junit.Assert.fail(Assert.java:89)
       org.junit.Assert.failNotEquals(Assert.java:835)
       org.junit.Assert.assertEquals(Assert.java:120)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.spell.TestSpellCheckerDuplicateDictionaryWords.testWordRepeatedInOneDictionary(TestSpellCheckerDuplicateDictionaryWords.java:37)

• Design. The existence check is as old as the class: the 2004 first version skipped a word with if (this.exist(word)) { // if the word already exist in the gramindex. createDocument says the word field is "indexed so it can be quickly checked for rebuild (and stored for retrieval)" (SpellChecker.java:576-577).
• LUCENE-883 (#1958, 2007): "The problem without the patch is that consecutive calls to indexDictionary() will create a spelling index with duplicate words." CHANGES 2.2: "LUCENE-883: consecutive calls to Spellchecker.indexDictionary() won't insert terms twice anymore."
• Test. TestSpellChecker.testBuild (:113-124) indexes two overlapping fields one after the other and asserts num_field2 == num_field1 + 1.
• Inconsistent. The same input split over two calls is indexed once; in one call it is indexed twice.
• Contract. No javadoc requires a Dictionary to be duplicate-free: it is "a list of entries, where every entry consists of term, weight and payload" (Dictionary.java:23-24); PlainTextDictionary documents "1 word per line"; DocumentDictionary yields every stored value of the field from each live document, so values repeated across documents are normal. No javadoc promises distinct suggestions either, but a copy carries no information (the spell index stores no weight or frequency) while it removes a distinct word.
• No test pins it. No upstream test feeds a repeated entry in one call, and with fix A every suite in the suggest module passes.

The strongest works-as-designed case (the cross-model lenses, the independent reproducer, the devil's advocate and the adjudication): Dictionary is documented as a list, not a set; suggestSimilar never promises distinct words; LUCENE-883 is worded for consecutive calls only; and LUCENE-2391 (#3466, 2011) deliberately skips the check on an empty index: "we don't do any of the exists() logic if the index is empty (this is the case for i think solr which completely rebuilds ...)". On that reading the authors assumed each word comes once, as LuceneDictionary guarantees, and repeated lines are the caller's problem.

Why it fails: that uniqueness assumption is written nowhere (no javadoc, CHANGES or MIGRATE entry, test or issue), and three dictionaries shipped in the same module legally yield repeats. The empty-index skip is a performance shortcut: on a non-empty index the check runs and still misses repeats from the same call. The outcome is exactly what LUCENE-883 called the problem. A maintainer could still reasonably prefer a javadoc note "entries should be unique" over a code change. Verdict: not intended; a within-call gap in the LUCENE-883 de-duplication.

Two fixes of the same shape were built and run in a scratch worktree at a9779ef3c193: remember the words this call has added and skip repeats. A uses a BytesRefHash and is recommended; B, a HashSet<String>, is the finder's and the independent reproducer's fix.

Keep a BytesRefHash of the words added in this call. After the existing check against the old index, skip the entry if the hash already has it; add it to the hash after addDocument. +8 lines in SpellChecker.java.

boolean isEmpty = termsEnums.isEmpty();
// words added by this call: termsEnums only see the index as it was before the call
final BytesRefHash addedInThisCall = new BytesRefHash();
...
if (addedInThisCall.find(currentTerm) >= 0) {
  continue; // the dictionary repeated a word that this call has already added
}
// ok index the word
Document doc = createDocument(word, getMin(len), getMax(len));
writer.addDocument(doc);
addedInThisCall.add(currentTerm);

Trade-offs

• Heap grows with the distinct words added in one call (the bytes in shared blocks plus two int arrays, no object per word); words already in the index are not stored. The empty-index rebuild keeps its shortcut (no seekExact) and gains one hash lookup per entry of 3 or more characters and one insert per distinct word indexed; on a non-empty index, entries found in the old index cost neither. Not benchmarked.
• The insert comes after addDocument on purpose: BytesRefHash rejects entries over 32,766 bytes with its own exception. With the insert first (variant A0, also run: every suite passes), such an entry fails with MaxBytesLengthExceededException instead of the IllegalArgumentException that IndexWriter throws for an immense term today. With A it still fails in addDocument, as today.
• Two limits that B does not have (by reading; not run through indexDictionary): BytesRefHash stores at most 2 GB of bytes in total, so one call cannot add more distinct word bytes than that; and the hash keys on the entry's raw bytes, while the stored word is the decoded string. utf8ToString does not fully validate UTF-8, so two byte sequences can decode to the same word (a small probe: the overlong C1 A1 62 63 and abc both give "abc", and the hash does not match them). A dictionary that yields such bytes, for example binary stored values through DocumentDictionary, would get both indexed under A.

What the checks validated

Gradle in a scratch worktree at a9779ef3c193, seed DEADBEEF: the whole :lucene:suggest:test with the three repro classes and an edge-case probe added, 35 classes, 247 tests, 0 failures (7 skipped by the module itself), with assertions on and off; the 7 repro tests that fail on stock pass, and an over-long entry still raises IllegalArgumentException. :lucene:suggest:check -x test with the fix and the primary test (format, ecj lint, forbidden APIs, licenses): BUILD SUCCESSFUL. Not benchmarked.

final Set<String> addedInThisCall = new HashSet<>(); and if (addedInThisCall.add(word) == false) continue; before createDocument. +8 lines with the two imports. The finder and the independent reproducer each wrote this change.

Trade-offs

Simplest: the String already exists for every entry, and it is the stored word, so there is no raw-byte or 2 GB caveat. Keeps one String and one map entry per distinct word added, so it needs more heap than A for very large dictionaries. Over-long entries still fail in addDocument as today.

What the checks validated

Gradle, assertions on, seed DEADBEEF: the three repro classes, TestSpellChecker (6) and TestPlainTextDictionary (1) and the edge-case probe, 18 tests, 0 failures; an over-long entry still raises IllegalArgumentException. The whole module was not run with B.

Add "entries should be unique within one call" to indexDictionary (and maybe Dictionary).

Trade-offs

A legitimate maintainer choice, but it leaves PlainTextDictionary, FileDictionary and DocumentDictionary users to de-duplicate themselves, and the behaviour stays inconsistent with two calls. Not recommended.

Hide the symptom at query time.

Trade-offs

Also cleans spell indexes that already hold copies, but the copies still fill the 10 * numSug hit window, so with many copies distinct words are still lost, and the index stays bloated. At most a complement to A or B. Not run.

Let IndexWriter replace an earlier document of the same word (suggested by a cross-model reviewer).

Trade-offs

Buffers one delete term per word and applies them at flush, which costs more than a hash lookup on a full rebuild. Not run or benchmarked.

Method: code reading during modelling (the hunt's "non-formal" tier; no model checker, solver or proof found it).

• The finder was writing a bounded translation-validation reference for SpellChecker, which had to model the spell index as a set. That made the question "what if a word comes twice?" explicit, and reading indexDictionary showed that the TermsEnums come from the searcher opened before the call.
• The reference harness itself did not witness it: its random 1-12-word dictionaries rarely repeated a word.
• A main() probe on the stock jar indexed abcd, abcd, abce in one call and got [abcd, abcd, abce] as the suggestions for abcf; the finder reduced it to the JUnit test, and an independent reproducer then wrote its own test with other words and a DocumentDictionary trigger.