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


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

Submitted by:  Max Görner <maxg>
Submitted on:  Fri Mar 28 17:06:15 2014  
Category: NonePriority: 5 - Normal
Status: DonePrivacy: Public
Assigned to: NoneOpen/Closed: Closed

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)

Tue Dec 16 01:52:17 2014, comment #9:

Thank you for the patch and your patience. I have pushed it

Carnë Draug <carandraug>
Project Member
Mon Dec 15 22:47:49 2014, comment #8:

Why is berghel_roach a separate function now? When I mentioned nested function, I was referring to the function "get_f" inside function "berghel_roach". I will guess that it is not easy to unest but that's ok then, I can just put them back together into one file.

I don't really have the time, or expertise, to check its details and since you're the most interested, I'll trust you're doing it right.

Carnë Draug <carandraug>
Project Member
Sun Dec 14 22:15:51 2014, comment #7:

I'm very sorry for the very long delay. But now I've applied all demands of reply 5/6. Please let me now, if it is not sufficient. The changeset is appended.

(file #32667)

Max Görner <maxg>
Fri Aug 8 13:19:17 2014, 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 Aug 8 13:15:30 2014, 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 Aug 3 23:30:15 2014, comment #4:

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

Max Görner <maxg>
Fri Apr 25 06:18:18 2014, 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örner <maxg>
Thu Apr 24 21:08:18 2014, 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 Mar 31 10:55:54 2014, 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örner <maxg>
Fri Mar 28 17:06:15 2014, 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 .

Therefore I implemented the algorithm of Berghel and Roach (, who improve on Ukkonen (

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 ( However, I do not have the time to implement that one.

I really hope this helps and will be applied.

Max Görner <maxg>


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

Attach File(s):

Attached Files
file #32667:  speedup-editdistance.diff added by maxg (12kB - text/x-patch)
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 7 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue Dec 16 01:52:17 2014carandraugStatusNone=>Done
    Sun Dec 14 22:15:51 2014maxgAttached File-=>Added speedup-editdistance.diff, #32667
    Fri Apr 25 06:18:18 2014maxgAttached File-=>Added editdistance.m, #31244
    Thu Apr 24 21:08:18 2014carandraugSummarySpeeding up the edit distance=>strings package: speeding up the edit distance
    Fri Mar 28 17:06:15 2014maxgAttached File-=>Added editdistance.m, #31070
      Attached File-=>Added testEditDistance.m, #31071

    Back to the top

    Powered by Savane 3.1-cleanup