Levenshtein Distance Within a Given Threshold
---------------------------------------------
Key: LANG-684
URL: https://issues.apache.org/jira/browse/LANG-684
Project: Commons Lang
Issue Type: New Feature
Components: lang.*
Affects Versions: 3.1
Reporter: Eli Lindsey
Priority: Minor
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.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
