Mailing-List: contact issues-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: issues@commons.apache.org
Date: Wed, 25 May 2011 15:48:47 +0000 (UTC)
From: "Gary D. Gregory (JIRA)" <jira@apache.org>
To: issues@commons.apache.org
Message-ID: 
 <442955693.42509.1306338527489.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <945341120.2212.1299528359472.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] [Commented] (LANG-684) Levenshtein Distance Within a Given
 Threshold
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/LANG-684?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13039165#comment-13039165 ] 

Gary D. Gregory commented on LANG-684:
--------------------------------------

This functionality feels pretty high level for StringUtils. I wonder if this type of code would not a better match for the [codec] project? Thoughts from anyone?

> 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.x
>
>         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