[
https://issues.apache.org/jira/browse/LANG-684?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Henri Yandell updated LANG-684:
-------------------------------
Fix Version/s: (was: 3.x)
3.0
I'm not against moving LD to Codec. It used to live with Soundex etc way back
in the early days of the codebases, but LD didn't really fit Codec and stayed
with Lang. We need to decide before 3.0; and ideally we would release a version
in Codec fairly soon.
> 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.*
> Reporter: Eli Lindsey
> Priority: Minor
> Fix For: 3.0
>
> Attachments: LevenshteinDistanceWithThreshold.patch
>
>
> 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
