patchGNU Octave - Patches: patch #8426, strings package: speeding up the...

 
 

patch #8426: strings package: speeding up the edit distance

Submitted by:  Max G. <maxg>
Submitted on:  Fri 28 Mar 2014 05:06:15 PM UTC  
 
Category: NonePriority: 5 - Normal
Status: NonePrivacy: Public
Assigned to: NoneOpen/Closed: Open

Add a New Comment (Rich MarkupRich Markup):
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Fri 25 Apr 2014 06:18:18 AM UTC, comment #3:

I added the test-block. It needs 15 seconds on my computer to complete. If that is still to long, reduce the parameters 'l' or 'n'.
I furthermore improved the description in the beginning.

(file #31244)

Max G. <maxg>
Thu 24 Apr 2014 09:08:18 PM UTC, comment #2:

The strings package does not have a current maintainer but I could apply your changes.

One big problem about changing it is that it has no tests to confirm that your changes did not introduce any new bug. Cool thing is that you are submitting a test file. Would you be able to add them to the actual function in %!test blocks, as it is done for the rest of Octave?

Carnë Draug <carandraug>
Project Member
Mon 31 Mar 2014 10:55:54 AM UTC, comment #1:

I just noticed, that the new version proposed here is still not sufficient for my use case. I'm currently implementing a C++-version which will be even faster than the algorithm by Berghel and Roach, just because it is done in C++.

Is there an interest in having that version as well? I then would try to make it more readable and post it here.

Max G. <maxg>
Fri 28 Mar 2014 05:06:15 PM UTC, original submission:

Calculating the Levenshtein distance provided by the package "strings" is a pain.

It is unbelievable slow, not only because it uses the algorithm of Wagner and Fisher, but also because it does this using loops. That leads to calculation times of 10 seconds for simple strings of length 200 and wastes plenty of memory. See for example http://savannah.gnu.org/bugs/?41920 .

Therefore I implemented the algorithm of Berghel and Roach (http://www.berghel.net/publications/asm/asm.php), who improve on Ukkonen (http://www.sciencedirect.com/science/article/pii/S0019995885800462).

Great things first: Now it is possible to calculate
in less than 2 seconds.

The new version is fully compatible with the former version, meaning that
(i) it calculates a specific matrix when asked for
(ii) can apply some specific weights

That comes at the cost of
(i) a new optional input parameter
(ii) not being able to use the new algorithm all the time.

Depending on its preferences, the user now can decide to
(i) use the former algorithm
(ii) use the algorithm of Berghel and Roach, which is almost always better but may have space issues as well
(iii) use a version with m*n runtime but linear memory usage.

I tested the correctness of the new algorithms by running the provided script uncountable times. Please note, that this produces test which are almost worst case for the algorithm by Berghel and Roach.

Please note further, that there exists a version of the algorithm used here, that uses only O(dist) memory (https://code.google.com/p/google-web-toolkit/source/browse/trunk/dev/core/src/com/google/gwt/dev/util/editdistance/ModifiedBerghelRoachEditDistance.java?r=8928). However, I do not have the time to implement that one.

I really hope this helps and will be applied.

Max G. <maxg>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #31244:  editdistance.m added by maxg (7kB - text/x-objcsrc)
file #31070:  editdistance.m added by maxg (6kB - text/x-objcsrc)
file #31071:  testEditDistance.m added by maxg (614B - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by maxg (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 25 Apr 2014 06:18:18 AM UTCmaxgAttached File-=>Added editdistance.m, #31244
    Thu 24 Apr 2014 09:08:18 PM UTCcarandraugSummarySpeeding up the edit distance=>strings package: speeding up the edit distance
    Fri 28 Mar 2014 05:06:15 PM UTCmaxgAttached File-=>Added editdistance.m, #31070
      Attached File-=>Added testEditDistance.m, #31071

    Back to the top


    Powered by Savane 3.1-cleanup