  lua-l archive

• Subject: Re: [useless] Having some fun with lua
• From: Peter Odding <peter@...>
• Date: Thu, 30 Jul 2009 10:42:31 +0200

```Geoffroy Carrier schreef:
```
```Hello!

An "ridiculous" evaluation of the Levenshtein distance in pure Lua:
http://gist.github.com/158506/
I took no care in the "quality" of this code, so you might want to
I'd be very interested in performance tweaks/code reduction, from
minor remarks to global rewrites, as long as it remains pure Lua with
standard libraries. I didn't think a lot about it, specially the use
of table.sort which must be stupid.
```
```
```
I don't have any real insights but my implementation of Levenshtein uses a single Lua table to hold the whole matrix. I haven't a clue how much faster this is but it must account for something, with all that table creation :)
```
function levenshtein(s, t)
local d, sn, tn = {}, #s, #t
local byte, min = string.byte, math.min
for i = 0, sn do d[i * tn] = i end
for j = 0, tn do d[j] = j end
for i = 1, sn do
local si = byte(s, i)
for j = 1, tn do
```
d[i*tn+j] = min(d[(i-1)*tn+j]+1, d[i*tn+j-1]+1, d[(i-1)*tn+j-1]+(si == byte(t,j) and 0 or 1))
```		end
end
return d[#d]
end

- Peter

```