AutoHotkey Community

[esromneb]

I'm relativly new to ahk, but I've translated the Levenshtein Algorithm as found here:
http://www.merriampark.com/ldc.htm

The algorithm is explaned in detial here:
http://www.merriampark.com/ld.htm

(I find it rather ironic how similar those urls are)

Anyways can someone tell me if this is efficient or not? I'm still a little fuzzy on what you can do with references (arrays in this case).
Here it is:

[toralf]

you could replace

[toralf as guest]

And you can replace

[toralf as guest]

You could also write

[toralf]

I have taken a look at the original algorithm, it seams that you have made some modifications. Your loops go one iteration to much, since the loops in the c program go to k<n , k<m , i<n and j<m, but the loops in your code go up to n and m.
The original also returns m or n if one of the strings is empty. The c code you used as basis returns -1.

I guess you could also use Loop,Parse instead or normal loops and stringMid. But I do not know if that is faster.
_________________
Ciao
toralf

[toralf]

I guess this is the most effective way and closest to the original algorithm:

[Laszlo]

Thanks Esromneb, for the great script! It can be useful for many tasks.

In an interpreted language, the efficiency of the code is closely related to the number of lines executed, so there we could save some execution time. In AHK, expression evaluation is slower than direct string assignment, which would allow a little further speedup.

Continuing the trimming of the code, what ToRalf started, we could shave off another couple of lines of code by using two-dimensional arrays directly, instead of the index calculation. The expression (si <> A_LoopField) gives you 0/1 directly for cost, to be used in the function min.

[Decarlo110]

i don't know why these type of things get named. I suppose it's for a common terminology rather than an intellectual claim. Same thing for the "Boolean" term and "Venn" diagrams.

Here's my version in Ahk, which gives the same result. It drops the traditional matrix approach, which i find clumsy in this case.

[Laszlo]

Decarlo110's version computes a completely different (much simpler) distance between the strings. It is not the minimum number of changes to transform one string to the other, but the number of changes in a certain, monotone-scanning changing strategy. Even if a possible common initial string is located first, the result will be often wrong.

[Decarlo110]

My previous post on this thread was a result of hasty reading on my part, and insufficient example on the website without any mention of deletion. Laszlo is correct; my previous post should be disregarded entirely.
_________________
1) The Open Source Definition http://www.opensource.org/docs/definition_plain.php

2) Intuitive. Logical. Versatile. Adaptable. <<AutoHotkey>>

[Laszlo]

[esromneb]

Sorry for my delay...
Before swapping out my code with yours, I decided to check it first. There is a java (eww) applet online at http://www.merriampark.com/ld.htm
which will show you the correct value for the lev distance.

Tolraf: your code works just fine

Laszlo: your code doesn't work perfectly I wouldn't have noticed it, but your code returns 8 for

[Laszlo]

The right answer is 8, as you can easily verify: delete "To" from "Toralf" (2 letters) and add "LaDuce" to the end, which is 6 letters, making 8 all together. The question is, do you consider "r" and "R" different? Your code, and Toralf's, use "==" for comparison, which differentiates between upper- and lower- case letters. If you want that behavior, add "StringCaseSense On" to the beginning of my script, or replace "+(si <> A_LoopField)" in the table update expression with "+!(si==A_LoopField)". It is probably the best, if you introduce a third function parameter, which chooses between "StringCaseSense On" and "StringCaseSense Off", according to the user's desire:

[esromneb]

thanks, I lowered all my strings anyways. Case sensative would be faster for me then, right?

[toralf]