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

[lang] StringUtils#getLevenshteinDistance() performance is sub-optimal

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.2
    • Component/s: lang.*
    • Labels:
      None
    • Environment:

      Operating System: other
      Platform: Other

    • Bugzilla Id:
      38911

      Description

      The implementation of Commons Lang StringUtils#getLevenshteinDistance(String,
      String) is based on work from <http://www.merriampark.com/ld.htm>. While this
      implementation works, it is very memory hungry and can thus slow down heavy
      computations (GC has much more to collect in memory-constrained environment).
      Actual implementation needs x*y byte of memory.

      An improved implementation can be found at
      <http://www.merriampark.com/ldjava.htm>, which can lead to performance
      improvements of up to 3 times (my own internal benchmarks in low-memory
      situation). This new implementation needs x+y bytes of memory.

      Please change the getLevenshteinDistance() implementation to use the one at
      <http://www.merriampark.com/ldjava.htm>.

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              cedrik.lime@gmail.com Cédrik LIME
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: