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.

 

(Jump to the original submission Jump to the original submission)

Fri 08 Aug 2014 01:19:17 PM UTC, comment #6:

Seems I mangled the verbatim syntax so I'll paste the part that got cut out again:

  • "(nargin >= 3 && length (weights) < 3)" deserves an error message on its own. Also, do not use length it will return true for a matrix size [2 3]. Finally, shouldn't an empty weigths be allowed? The documentation says "For the special case that @var{weights} is empty"
  • I can't figure out "(nargin >= 2 || weights(1) == weights(3) && weights(1) == 1 && weights(2) == 0)" ? This will always return true because this function is always called with at least 2 arguments. But I remove it, then the rest is the same as `weigths = [1 0 1]`. What should this be doing? From the documentation, it would seem it should be:
  • while the algorithm seems like it's not really requires a char, it does require the input to be a vector. You should check for that. For the same reason mentioned above, do not use length in:
  • use more whitespace please. For example, add a space between operators (including "="), and after commas in a comma separated list
  • can you avoid the nested sub-function? I can see that it can modify the sparse matrix when it's called so this will avoid copying it for write. But nested functions in Octave and Matlab have weird scoping rules and can lead to weird bugs later on (and I'm not sure if we're completely Matlab compatible on that respect). I guess that since is less prone to problems so it should be fine if you can't find a way that would not impact performance.
  • finally, if you clone the repository and submit a changeset, it's easier to review and you'll keep authorship of the changes:
Carnë Draug <carandraug>
Project Member
Fri 08 Aug 2014 01:15:30 PM UTC, comment #5:

As I mentioned, we don't have at the moment a maintainer of the strings package and I don't have the expertise to comment on the algorithms being implemented so I'll just comment on the required Octave conventions and push this if you can fix them:

  • on the copyright, add a new line with your name and this year. DO not add your name to the previous copyright owner (you are not the copyright owner of this since 2006)
  • since there's multiple ways to call this, note them as separate deftypefnx lines on the header, i.e.,
  • the first line of the help text should be a single sentence, since it is used by functions such as `lookfor`. Use something like "Compute the Levenshtein edit distance between two strings."
  • if weights defaults to [1 0 1], set it on the function signature
  • "(nargin >= 3 && length (weights) < 3)" deserves an error message on its own. Also, do not use length it will return true for a matrix size [2 3]. Finally, shouldn't an empty weigths be allowed? The documentation says "For the special case that @var{weights} is empty"
Carnë Draug <carandraug>
Project Member
Sun 03 Aug 2014 11:30:15 PM UTC, comment #4:

What will happen to this patch? I'd love to see it in Octave!

Max G. <maxg>
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