[
https://issues.apache.org/jira/browse/TEXT-188?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17206076#comment-17206076
]
Jakob Vesterstrøm commented on TEXT-188:
----------------------------------------
I've created a pull request: [https://github.com/apache/commons-text/pull/174]
> Speed up LevenshteinDistance with threshold
> -------------------------------------------
>
> Key: TEXT-188
> URL: https://issues.apache.org/jira/browse/TEXT-188
> Project: Commons Text
> Issue Type: Improvement
> Affects Versions: 1.9.1
> Reporter: Jakob Vesterstrøm
> Priority: Major
> Attachments: improvement.patch
>
> Time Spent: 10m
> Remaining Estimate: 0h
>
> The calculation made by the LevenshteinDistance class can often be made
> faster, when the class in initialized with a threshold, and when the distance
> is found to be larger than the threshold. In those cases, it is often not
> necessary to iterate through the whole string, since a lower bound for the
> result can be established after each iteration. If that lower bound is larger
> than the threshold, the method can simply exit early with the same result as
> without this improvement.
> A patch with the proposed change is attached to this issue.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
