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

 
 

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

Submitter:  Max Görner <maxg>
Submitted:  Fri 28 Mar 2014 05:06:15 PM UTC
   
 
Category:  None Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

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

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

http://hg.code.sf.net/p/octave/strings/rev/f7e5023db4f4

Carnë Draug <carandraug>
Group Member
Mon 15 Dec 2014 10:47:49 PM UTC, 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>
Group Member
Sun 14 Dec 2014 10:15:51 PM UTC, 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 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"



function [dist, L] = editdistance (str1, str2, weights = [1 0 1], modus = 0)
  if (nargin < 2 || nargin > 4)
    print_usage ();
  endif

  if (nargin > 2 && (numel (weights) != 3 && ! isempty (weigths))
    error ("editdistance: WEIGTHS must be a 3 element vector.")
  endif


  • 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:



  saveMemory = nargout < 2;
  if (modus == 0 && saveMemory && isempty (weights))
    dist = berghel_roach (str1,str2);
    return
  endif


  • 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:



  L1 = length (str1) + 1;
  L2 = length (str2) + 1;



  • 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:



 hg clone http://hg.code.sf.net/p/octave/strings octave-forge-strings
 cd octave-forge-strings
 ## make your changes
 hg commit -m
 ## enter a commit message following commit message guidelines http://wiki.octave.org/Commit_message_guidelines
 ## probably something like:
 ##
 ## editdistance: use Berghel and Roach algorithm for performance (patch #8426)
 ##
 ## * editdistance.m: blah blah blah multi-line comment with deeper details, with
 ## each line not taking more than 80 characters.
 hg export -o ../speedup-editdistance.diff tip


Carnë Draug <carandraug>
Group 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)



## Copyright (C) 2006 Muthiah Annamalai <muthiah.annamalai@uta.edu> and Max Görner
## Copyright (C) 2014 Max Görner <maxistxxl@yahoo.de>


  • since there's multiple ways to call this, note them as separate deftypefnx lines on the header, i.e.,



## @deftypefn  {Function File} {[@var{dist}, @var{L}] =} editdistance (@var{str1}, @var{str2})
## @deftypefnx {Function File} {[@var{dist}, @var{L}] =} editdistance (@var{str1}, @var{str2}, @var{weights})
## @deftypefnx {Function File} {[@var{dist}, @var{L}] =} editdistance (@var{str1}, @var{str2}, @var{weights}, @var{modus})


  • 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"



function [dist, L] = editdistance (str1, str2, weights = [1 0 1], modus = 0)
  if (nargin < 2 || nargin > 4)
    print_usage ();
  endif

  if (nargin > 2 && (numel (weights) != 3 && ! isempty (weigths))
    error ("editdistance: WEIGTHS must be a 3 element vector.")
  endif
-verbatim

* 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:

+verbatim+
  saveMemory = nargout < 2;
  if (modus == 0 && saveMemory && isempty (weights))
    dist = berghel_roach (str1,str2);
    return
  endif


  • 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:



  L1 = length (str1) + 1;
  L2 = length (str2) + 1;



  • 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:



 hg clone http://hg.code.sf.net/p/octave/strings octave-forge-strings
 cd octave-forge-strings
 ## make your changes
 hg commit -m
 ## enter a commit message following commit message guidelines http://wiki.octave.org/Commit_message_guidelines
 ## probably something like:
 ##
 ## editdistance: use Berghel and Roach algorithm for performance (patch #8426)
 ##
 ## * editdistance.m: blah blah blah multi-line comment with deeper details, with
 ## each line not taking more than 80 characters.
 hg export -o ../speedup-editdistance.diff tip


Carnë Draug <carandraug>
Group 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örner <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örner <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>
Group 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örner <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

editdistance(repmat('AB',1,20000),repmat('BA',1,20000)

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örner <maxg>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #32667:  speedup-editdistance.diff added by maxg (12KiB - text/x-patch)
file #31244:  editdistance.m added by maxg (7KiB - text/x-objcsrc)
file #31070:  editdistance.m added by maxg (6KiB - 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
  • -email is unavailable- added by maxg (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2014-12-16 carandraug StatusNone Done
        Open/ClosedOpen Closed
    2014-12-14 maxg Attached File- Added speedup-editdistance.diff, #32667
    2014-04-25 maxg Attached File- Added editdistance.m, #31244
    2014-04-24 carandraug SummarySpeeding up the edit distance strings package: speeding up the edit distance
    2014-03-28 maxg Attached File- Added editdistance.m, #31070
        Attached File- Added testEditDistance.m, #31071

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code