[Octave-bug-tracker] [bug #41920] O(n^2) memory usage for editdistance

[Max G.]

URL:
  <http://savannah.gnu.org/bugs/?41920>

                 Summary: O(n^2) memory usage for editdistance
                 Project: GNU Octave
            Submitted by: maxg
            Submitted on: Fr 21 Mär 2014 11:24:32 GMT
                Category: Octave Forge Package
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Feature Request
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any
                 Release: 3.8.0
        Operating System: Any

    _______________________________________________________

Details:

The calculation of the levenshtein distance creates an 2D-Array to store
distance values. If one tries to calculate the distance between two not very
short strings (2^13 <= l < 2^14), the function fails since the array cannot be
constructed.

However, not all the array is needed. All what is needed are 2 rows of the
array. Therefore, the implementation should be changed or enhanced to enable
users to use the memory efficient version.

I attached a proposal for such an algorithm. It contains only some changes to
the old one.

I tested the correctness of that version using the second script.



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Fr 21 Mär 2014 11:24:32 GMT  Name:
testMemorySavingVersionOfEditDistance.m  Size: 255B   By: maxg

<http://savannah.gnu.org/bugs/download.php?file_id=30982>
-------------------------------------------------------
Date: Fr 21 Mär 2014 11:24:32 GMT  Name: levenshtein.m  Size: 788B   By: maxg

<http://savannah.gnu.org/bugs/download.php?file_id=30983>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?41920>

_______________________________________________
  Nachricht gesendet von/durch Savannah
  http://savannah.gnu.org/