Description
It'd be nice to have a function that calculates the Levenshtein distance only if it's within some integer threshold.
Oftentimes you care less about the actual LD and more about it being within a certain range. This common, limited computation can be performed much faster than the normal unbounded LD method; instead of O(nm), you can do it in O(km) (n and m are string lengths, k is the threshold).
Also, providing a function like this makes it easier for library users to rewrite the unbounded Levenshtein function to run in O(dm) time (d is the edit distance) if necessary.
I'm attaching a patch that implements this function and adds appropriate test cases.
Attachments
Attachments
Issue Links
- relates to
-
LANG-936 StringUtils.getLevenshteinDistance with too big of a threshold returns wrong result
-
- Closed
-