User talk:Ledrug: Difference between revisions
Content added Content deleted
(Levenshtein distance C code) |
|||
| Line 2: | Line 2: | ||
I Just noticed that you posted a recursive C solution for [[Levenshtein distance]]. Could you maybe explain (here or in/near the example) what the variables mean in that solution? I tried to come up with a recursive solution in Java myself, but it didn't work out so well. If at all possible could you maybe just give some pseudocode for the recursive algorithm? --[[User:Mwn3d|Mwn3d]] 20:25, 20 June 2011 (UTC) |
I Just noticed that you posted a recursive C solution for [[Levenshtein distance]]. Could you maybe explain (here or in/near the example) what the variables mean in that solution? I tried to come up with a recursive solution in Java myself, but it didn't work out so well. If at all possible could you maybe just give some pseudocode for the recursive algorithm? --[[User:Mwn3d|Mwn3d]] 20:25, 20 June 2011 (UTC) |
||
:The recursion function has 4 parameters: s, string 1; ls: length of s; t: string 2; lt length of t. Basically, <lang>function levenschtein(s, t) |
|||
if length(s) = 0: return length(t) |
|||
if length(t) = 0: return length(s) |
|||
if s[0] = t[0] : return levelschtein(s[1 .. end], t[1 .. end]) |
|||
len1 := levelschtein(s, t[1 .. end]) + 1 |
|||
len2 := levelschtein(s[1 .. end], t) + 1 |
|||
len3 := levelschtein(s[1 .. end], t[1 .. end]) + 1 |
|||
return min(len1, len2, len3) |
|||
</lang>where s[0] meaning first char in string s; s[1 .. end] meaning s without first char. |
|||
Revision as of 20:38, 20 June 2011
Levenshtein distance C code
I Just noticed that you posted a recursive C solution for Levenshtein distance. Could you maybe explain (here or in/near the example) what the variables mean in that solution? I tried to come up with a recursive solution in Java myself, but it didn't work out so well. If at all possible could you maybe just give some pseudocode for the recursive algorithm? --Mwn3d 20:25, 20 June 2011 (UTC)
- The recursion function has 4 parameters: s, string 1; ls: length of s; t: string 2; lt length of t. Basically, <lang>function levenschtein(s, t)
if length(s) = 0: return length(t) if length(t) = 0: return length(s) if s[0] = t[0] : return levelschtein(s[1 .. end], t[1 .. end])
len1 := levelschtein(s, t[1 .. end]) + 1 len2 := levelschtein(s[1 .. end], t) + 1 len3 := levelschtein(s[1 .. end], t[1 .. end]) + 1 return min(len1, len2, len3)
</lang>where s[0] meaning first char in string s; s[1 .. end] meaning s without first char.