Thank you for the patch and your patience. I have pushed it
http://hg.code.sf.net/p/octave/strings/rev/f7e5023db4f4

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.

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)

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 subfunction? 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:

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"

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

I added the testblock. 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)

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?

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.

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/googlewebtoolkit/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.
