[LUCENE-9289] Speed up Levenshtein distance calculation when we don't need the exact distance

• Type: Improvement
• Status: Patch Available
• Priority: Minor
• Resolution: Unresolved
• Component/s: modules/spellchecker
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: Andras Salamon
• Created: 24/Mar/20 10:42
• Updated: 28/Aug/22 16:00

Description

Sometimes when we calculate the Levenshtein distance we don't need the exact distance, we only want to know if the strings are similar enough.

https://github.com/apache/lucene-solr/blob/master/solr/core/src/java/org/apache/solr/spelling/SolrSpellChecker.java#L113-L114

sug.score = sd.getDistance(original, sug.string);        
if (sug.score < min) continue; 

If we use this threshold in the distance calculation, we can speed it up, we can stop the calculation when we already know that the the the distance will be lower than the threshold.