Skip to content

Instantly share code, notes, and snippets.

@james2doyle
Forked from Badgerati/levenshtein_algorithm.lua
Last active November 24, 2022 21:52
Show Gist options
  • Save james2doyle/e406180e143da3bdd102 to your computer and use it in GitHub Desktop.
Save james2doyle/e406180e143da3bdd102 to your computer and use it in GitHub Desktop.
An implementation of the Levenshtein distance algorithm in Lua
-- Returns the Levenshtein distance between the two given strings
-- Lower numbers are better
local function levenshtein(str1, str2)
local len1 = #str1
local len2 = #str2
local matrix = {}
local cost = 1
local min = math.min;
-- 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
end
matrix[i][j] = 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