Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of the Levenshtein distance algorithm in LUA.
-- Returns the Levenshtein distance between the two given strings
function string.levenshtein(str1, str2)
local len1 = string.len(str1)
local len2 = string.len(str2)
local matrix = {}
local cost = 0
-- quick cut-offs to save time
if (len1 == 0) then
return len2
elseif (len2 == 0) then
return len1
elseif (str1 == str2) then
return 0
end
-- initialise the base matrix values
for i = 0, len1, 1 do
matrix[i] = {}
matrix[i][0] = i
end
for j = 0, len2, 1 do
matrix[0][j] = j
end
-- actual Levenshtein algorithm
for i = 1, len1, 1 do
for j = 1, len2, 1 do
if (str1:byte(i) == str2:byte(j)) then
cost = 0
else
cost = 1
end
matrix[i][j] = math.min(matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + cost)
end
end
-- return the last value - this is the Levenshtein distance
return matrix[len1][len2]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment