[ https://issues.apache.org/jira/browse/LANG-684?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Matt Benson resolved LANG-684. ------------------------------ Resolution: Fixed Committed revision 1136496. > 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