Uploaded image for project: 'Commons Lang'
  1. Commons Lang
  2. LANG-684

Levenshtein Distance Within a Given Threshold

    XMLWordPrintableJSON

    Details

    • Type: New Feature
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.0
    • Component/s: lang.*
    • Labels:
      None

      Description

      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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                elindsey Eli Lindsey
              • Votes:
                0 Vote for this issue
                Watchers:
                0 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: