Skip to content

Instantly share code, notes, and snippets.

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
-- initialise the base matrix values
for i = 0, len1, 1 do
matrix[i] = {}
matrix[i][0] = i
for j = 0, len2, 1 do
matrix[0][j] = j
-- 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
cost = 1
matrix[i][j] = math.min(matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + cost)
-- return the last value - this is the Levenshtein distance
return matrix[len1][len2]
Copy link

lost-RD commented Nov 1, 2016

Thanks for this!

Copy link

DrkSoulk commented Jan 11, 2021


Copy link

ThePC007 commented Jul 6, 2021

This is great, thanks. :)

Copy link

SoapHeadedSoap commented Sep 4, 2021

who came here from that one devforum

Copy link

gram-signal commented Nov 18, 2021

quick note: because in line 35 you only ever refer to matrix[i] and matrix[i-1], you can get away with just storing the two most recent lines of the matrix, rather than computing the whole thing. This gets you down to O(2n) space (while still taking O(n^2) time)

Copy link

jarble commented Apr 23, 2022

You can use a modified version of this algorithm to search for substrings that closely match another string.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment