[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Max G.
Subject: [Octave-bug-tracker] [bug #41920] O(n^2) memory usage for editdistance
Date: Fri, 21 Mar 2014 11:24:33 +0000
User-agent: Mozilla/5.0 (X11; Linux i686) AppleWebKit/537.36 (KHTML, like Gecko) Ubuntu Chromium/32.0.1700.107 Chrome/32.0.1700.107 Safari/537.36


                 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



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

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

Date: Fr 21 Mär 2014 11:24:32 GMT  Name: levenshtein.m  Size: 788B   By: maxg



Reply to this item at:


  Nachricht gesendet von/durch Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]