SpellChecker with SuggestWordFrequencyComparator can drop the most frequent suggestion once its queue is full

The index-based n-gram SpellChecker of lucene-suggest can rank suggestions with a pluggable comparator; the shipped SuggestWordFrequencyComparator orders "Frequency first, then score". Once suggestSimilar has collected numSug words, it raises its accuracy cutoff to the score of the queue's head, the word the queue evicts when a better one arrives. That shortcut is a valid lower bound only for the default score-first order. Under the frequency order the head is the least frequent word, so a later word that is more frequent but scores a little lower is rejected before its frequency is read, although the queue would have kept it.

In the smallest case, receive (50 documents) and relieve (1 document) for the typo recieve: asking for 2 returns [receive, relieve], asking for 1 returns [relieve]. At the javadoc-recommended numSug=5 a frequent word can be left out entirely. No error is raised, and the returned list is still sorted by the comparator: what goes wrong is which words get into it. With the frequency comparator it needs a reader and field (restricted mode) and a full queue; a user-written comparator that is not score-first may not need restricted mode. Every release from 3.1.0 to 10.6.0 (10.6.0 by reading) and main is affected; the default comparator, DirectSpellChecker, and the frequency comparator with SUGGEST_ALWAYS are not. Measured on an English test corpus, the user-visible harm is mild: the set differs from the comparator's top numSug in most lookups, but the typo's intended word is lost in only 0.2-0.4%.

• SpellChecker: lucene-suggest's index-based spell checker. It keeps a separate spell index of words split into n-grams. suggestSimilar runs an n-gram query against it, fetches up to 10 * numSug hits, scores each with a StringDistance (here LevenshteinDistance: 1 - edits / longer length) and keeps the best numSug in a bounded queue.
• Restricted mode: pass the user index's reader and a field (with SUGGEST_WHEN_NOT_IN_INDEX or SUGGEST_MORE_POPULAR). Each candidate's document frequency (freq) is then read from that field.
• Comparator: the order of the queue, set through the constructor or setComparator. The default, SuggestWordScoreComparator, is score, then frequency; SuggestWordFrequencyComparator is frequency, then score.
• Accuracy: the minimum score a word needs (default 0.5).

1. For each hit, suggestSimilar computes the score and skips the word if score < accuracy, before it reads the word's frequency (SpellChecker.java:382-385).
2. After each insertion, once the queue holds numSug words, it sets accuracy = sugQueue.top().score (:396-399, comment "if queue full, maintain the minScore score").
3. top() is the smallest element under the configured comparator (SuggestWordQueue.java:52). With the default order that is the lowest score, and any later word scoring below it would lose to it anyway: a valid shortcut. With the frequency order it is the least frequent word; its score says nothing about which later words the queue would keep.
4. So a later word that is more frequent but scores lower than that word is rejected at step 1, unread. The returned list is still sorted by the comparator; the defect is which words get into it.

receive in 50 documents, relieve in 1, query recieve: scores 1 - 2/7 = 0.714 and 1 - 1/7 = 0.857. The n-gram search returns relieve first. With numSug=1 the queue is full after relieve, accuracy becomes 0.857 and receive is skipped: [relieve]. With numSug=2 both get in: [receive, relieve]. With the default comparator the answers are [relieve] and [relieve, receive], consistent with each other.

At numSug=5: abcdfeg in 50 documents (two edits from abcdefg, 0.714) and six one-edit words with 1 document each (0.857). The six are reached first: five fill the queue (the sixth ties the head and is not kept), the cutoff rises to 0.857, and abcdfeg is dropped: [abcdefx, abcdefy, abcdefz, abcdexg, abcdeyg]. It fails for numSug 1-6 and is right from 7, when abcdfeg arrives before the queue is full.

The outcome depends on n-gram hit order: adding retrieve and reprieve (1 document each) to the first index makes the search reach receive first, and numSug=1 then returns [receive].

• Who is exposed. Opt-in: the constructor SpellChecker(Directory, StringDistance, Comparator) or setComparator, with SuggestWordFrequencyComparator in restricted mode (a user-written comparator that is not score-first may not need restricted mode). By reading downstream source (nothing run there): Solr's index-based spell checker maps comparatorClass=freq to SuggestWordFrequencyComparator and calls suggestSimilar with max(count, 5) suggestions (or alternativeTermCount, when set, for a token already in the index), the reader when a field is configured, and the field; the Elasticsearch frequency sort uses DirectSpellChecker, which does not run this code.
• What it takes. A full queue (numSug smaller than the number of qualifying hits) before a more frequent, lower-scored word is reached. Deterministic; it shows even with a 7-word spell index; numSug=5 still fails.
• How often. Measured on main (-da; -ea identical) over the 1,166 English lines of the Europarl sample in Lucene's test framework (11,181 terms), 2,000 typos per draw (one substitution, deletion, insertion or adjacent transposition), each looked up at numSug 5 and 10, LevenshteinDistance, accuracy 0.5. Reference: the comparator's top numSug among the same hits (the fix).

• Reading the table. For users who opt in, a result that differs from the comparator's top numSug is the normal case, but the intended word is rarely lost because of it; for example wihch (from which, 690 documents, numSug=5) returns [with, wish, watch, rich, witch] instead of [with, which, wish, watch, rich]. On this corpus selecting by the comparator (the fix) would include the intended word less often than today. With the default comparator, removing the cutoff changes nothing (0 of 8,000 lookups).
• Silent. The returned words look plausible and all pass the documented filters; search results are not involved.

# Lucene main 645d4fe14a20, assertions on (-ea), seed DEADBEEF: 1 test(s) run, 1 failed
    => org.junit.ComparisonFailure: expected:<[re[cei]ve]> but was:<[re[lie]ve]>
       org.junit.Assert.assertEquals(Assert.java:117)
       org.junit.Assert.assertEquals(Assert.java:146)
       org.apache.lucene.search.spell.TestSpellCheckerFrequencyComparator.testMostFrequentWordRanksFirst(TestSpellCheckerFrequencyComparator.java:52)

• Contract. Constructor javadoc (SpellChecker.java:129-132): "the given java.util.Comparator for sorting the results"; getComparator (:178): "the comparator in use for ranking suggestions"; SuggestWordFrequencyComparator.java:21: "Frequency first, then score."; lucene/CHANGES.txt:16164-16165: "Added ability to provide a sort comparator for spelling suggestions along with two implementations. The existing comparator (score, then frequency) is the default". None of these says outright that the comparator chooses which words are returned; that reading rests on the comparator's own rule, "ranking", the request below, and the fact that the comparator-ordered queue is what selects (SpellChecker.java:366, 395).
• Intent. The LUCENE-2479 (#3553) request: "there are situations where it would be useful to sort by freq first, instead of the current 'sort by edit distance, and then subsort by freq if edit distance is equal'". In the same thread the author did not fold frequency into the score because "this would mean having to look up the freq. for every suggestion, which I think would be pretty bad performance-wise": about the scoring, not the cutoff, but avoiding docFreq lookups was part of the design.
• Prefix check. If the comparator picks the top numSug, then with every candidate retrieved and passing the filters, numSug=k must be the first k of the full list under any fixed order. The frequency comparator breaks it ([relieve] vs [receive, relieve]; an independent case returns [abcdefghijkl, abcdefgx] for 2 but [abcdefghijkl, abxdefyh, abcdefgx] for 3); the default comparator never does.
• History. The 2004 sandbox import wrote min=((SuggestWord) sugqueue.top()).score when SuggestWord.compareTo (score, then frequency) was the only order, so it was correct. LUCENE-2479 (2010) built the queue with the comparator and left the cutoff; later commits only renamed or reformatted it.
• Tests. testComparator (TestSpellChecker.java:153-171) uses "five and fvei", which "have the same score", so it cannot reach the cutoff. Nothing pins the current behaviour: with either fix every suite in the module passes.

The strongest case for "works as designed" (a cross-model reviewer with the intended lens, the independent reproducer, the devil's advocate, the adjudication): the comparator is "for sorting the results" and the 6-argument @return says "first criteria: the edit distance, second criteria (only if restricted mode): the popularity", so the comparator may only order a set chosen by score; the javadoc warns "if numSug == 1, don't count on that suggestion being the best one ... set this value to at least 5"; DirectSpellChecker also builds a bounded pool by score before it applies the comparator; LUCENE-2479's author wanted to avoid a frequency lookup for every suggestion; and the measured harm is small.

Why it fails: the javadoc caveat names its own cause, n-gram retrieval ("the Lucene similarity that is used to fetch the most relevant n-grammed terms is not the same as the edit distance"), while here every candidate is retrieved and then rejected by the cutoff, and numSug=5 fails too. Today's output follows neither reading: the receive case contradicts "the comparator selects", and an order probe contradicts "score selects" (query abcdefg: abcdefgxy, 50 documents, 0.778, beats abcdefh, 1 document, 0.857, at numSug=1, because the n-gram search reaches it first). The @return text is the 2004 description of the only order that existed, and the returned list is already ordered frequency first, against it. The weaker reading "score picks a heuristic subset, the comparator only sorts it" is not refuted by one call, but no score-first precondition is documented and the hit-order dependence fits no rule; made consistent and documented, it is option C. DirectSpellChecker is no precedent for today's code: it sorts its pool with the comparator and then trims it to numSug (DirectSpellChecker.java:386-391), so there the comparator selects too, and its score cutoff applies only inside its score-ordered pool queue (:435). The performance remark is about the scoring, not the cutoff. The small harm bears on which consistent rule to choose (see Suggested fix), not on whether today's behaviour is coherent. Verdict: not intended.

Two fixes were built and run in a scratch worktree at a9779ef3c193; A is recommended if the comparator is meant to select. Option C is the other consistent semantics a maintainer may prefer (it was not run); the javadoc does not settle which one is meant.

Remove the if (sugQueue.size() == numSug) { accuracy = sugQueue.top().score; } block after insertWithOverflow (SpellChecker.java:396-399) and leave a comment. On every call that reaches the candidate loop the result becomes the comparator's top numSug among the qualifying 10 * numSug hits, for every comparator (a word already in the field still returns itself under SUGGEST_WHEN_NOT_IN_INDEX, as today). +3/-4, comment only besides the removed block.

        }
+        // insertWithOverflow keeps the best numSug words under the comparator. Do not raise
+        // accuracy to sugQueue.top().score once the queue is full: that is a lower bound only for
+        // a score-first comparator, and a frequency-first one can still prefer a lower score.
         sugQueue.insertWithOverflow(sugWord);
-        if (sugQueue.size() == numSug) {
-          // if queue full, maintain the minScore score
-          accuracy = sugQueue.top().score;
-        }
         sugWord = new SuggestWord();

Trade-offs

Simplest; it makes the comparator select, for any comparator. With the default comparator the results are unchanged (0 differences in 8,000 measured lookups), but the shortcut is gone: after the queue fills, each examined hit may also do one docFreq lookup and one queue offer, on top of the stored-field read and distance computation the loop already does per hit; still at most 10 * numSug hits. Not benchmarked. On the measured corpus, frequency-first selection includes the typo's intended word less often than today (74.0-94.9% vs 95.9-98.0%).

What the checks validated

Scratch worktree at a9779ef3c193, gradle, seed DEADBEEF: the whole :lucene:suggest:test task with the 3 repro classes added, 34 classes, 245 tests, 0 failures (7 skipped by the module itself), with assertions on and off. :lucene:suggest:check -x test (format, ecj lint, forbidden APIs) passes. Earlier, on ea57360912ed: the finder's equivalent guard passes upstream TestSpellChecker 18 of 18 (3 iterations) and leaves 0 of the harness's 5,721 mismatches; the likelihood probe finds it identical to "raise removed" on all 8,000 lookups.

Guard the raise with comparator.getClass() == SuggestWordScoreComparator.class. Same results as A for every comparator; the default keeps its shortcut. +5/-2.

if (sugQueue.size() == numSug
    && comparator.getClass() == SuggestWordScoreComparator.class) {
  accuracy = sugQueue.top().score;
}

Trade-offs

A user-written score-first comparator loses the shortcut (speed only). An instanceof check, as in the finder's sketch, is weaker: SuggestWordScoreComparator is not final, so a subclass that changes the order would still get the raise.

What the checks validated

Gradle with assertions on: the whole :lucene:suggest:test task with the 3 repro classes, 245 tests, 0 failures; :lucene:suggest:check -x test passes. Not run with assertions off; not benchmarked.

Select the top numSug by score with the existing shortcut, then sort the chosen words with the configured comparator, and say so in the constructor and @return javadoc. This matches the literal "for sorting the results" and the 2004 @return text. DirectSpellChecker is not a precedent for it: its comparator sorts a pool of up to numSug * maxInspections terms and trims it to numSug, so it selects.

Trade-offs

Its set equals today's default-comparator set, which included the intended word in 96.4-98.1% of the measured lookups. But SuggestWordFrequencyComparator would no longer select by frequency in SpellChecker, results change even where today's output already follows the comparator, and the repro (which asserts A's semantics) would need a different test. Not run.

Describe the cutoff in the javadoc.

Trade-offs

Not recommended: the procedure can be described, but that would codify a mixed rule whose result depends on n-gram hit order.

Method: bounded translation validation (the hunt's "semi-formal" tier: a tool witnessed the mismatch on the real jar against an exact reference; no model checker, solver or proof).

• The finder wrote a reference for SpellChecker.suggestSimilar from its documented behaviour: every spell-index word that shares a gram with the query is retrieved, the self, accuracy and suggest-mode filters apply, then the configured comparator picks the top numSug. Cases with more retrievable words than 10 * numSug were skipped, so the javadoc's retrieval caveat cannot apply.
• Over 25 random dictionaries, 5 distances, 2 shipped comparators, 363 queries and 6 configurations (544,485 checks) the stock main jar disagreed 5,721 times, all with SuggestWordFrequencyComparator in restricted mode; 0 times with the default comparator and 0 times with the fix shadowed. A deliberately wrong reference was caught (55 mismatches in 130,680 checks), so the check is not vacuous.
• The finder reduced it to a JUnit test; an independent reproducer wrote its own prefix test with other words; this doc's two-word test comes from those scenarios.