Possible shortcuts for fast filter

[abstractqqq]

I wonder if it is possible to have a function that returns early when the levenshtein distance is gauranteed to be < an input k, and returns a boolean. I think this might speed up queries that only ask for words that are close but do not care exactly how close they are.

Any thoughts? Thanks in advance.

[maxbachmann]

I did think about adding these in Python a while ago: rapidfuzz/RapidFuzz#188.

The main reason I didn't do so yet is that I haven't really seen any cases, where:

1. this is the wanted behaviour. In most cases you still want to know the similarity. One case I could think of is something like deduplication.
2. the score_cutoff is relatively high. For a low score_cutoff this wouldn't really help, since we would essentially need to calculate pretty much the complete distance anyway. In fact the additional check of the exit condition would cause slowdowns when we can't exit early.

Do you have an example where this is useful?

[abstractqqq]

No on second thought I think you are right. The cases I have all have a small cutoff and may not worth the early return

[maxbachmann]

For small cutoffs there I already use Ukkonens algorithm according to https://www.sciencedirect.com/science/article/pii/S0019995885800462 which helps significantly when comparing long texts.