lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Geoffroy Carrier schreef:

An "ridiculous" evaluation of the Levenshtein distance in pure Lua:
I took no care in the "quality" of this code, so you might want to
tear your eyes out.
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))
	return d[#d]

 - Peter