{"id":235,"date":"2016-07-04T23:17:24","date_gmt":"2016-07-04T22:17:24","guid":{"rendered":"https:\/\/solidt.eu\/blog\/?p=235"},"modified":"2023-05-12T10:22:42","modified_gmt":"2023-05-12T09:22:42","slug":"lua-levenshtein-distance","status":"publish","type":"post","link":"https:\/\/solidt.eu\/site\/lua-levenshtein-distance\/","title":{"rendered":"Lua levenshtein distance"},"content":{"rendered":"\n<div style=\"height: 250px; position:relative; margin-bottom: 50px;\" class=\"wp-block-simple-code-block-ace\"><pre class=\"wp-block-simple-code-block-ace\" style=\"position:absolute;top:0;right:0;bottom:0;left:0\" data-mode=\"lua\" data-theme=\"monokai\" data-fontsize=\"14\" data-lines=\"Infinity\" data-showlines=\"true\" data-copy=\"false\">function levenshtein_distance(str1, str2)\n    local len1, len2 = #str1, #str2\n    local char1, char2, distance = {}, {}, {}\n    str1:gsub('.', function (c) table.insert(char1, c) end)\n    str2:gsub('.', function (c) table.insert(char2, c) end)\n    for i = 0, len1 do distance[i] = {} end\n    for i = 0, len1 do distance[i][0] = i end\n    for i = 0, len2 do distance[0][i] = i end\n    for i = 1, len1 do\n        for j = 1, len2 do\n            distance[i][j] = math.min(\n                distance[i-1][j  ] + 1,\n                distance[i  ][j-1] + 1,\n                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)\n                )\n        end\n    end\n    return distance[len1][len2]\nend\n\nfunction distance(string1, string2)\n    local str1, str2, distance = {}, {}, {};\n    str1.len, str2.len = string.len(string1), string.len(string2);\n    string.gsub(string1, \"(.)\", function(s) table.insert(str1, s); end);\n    string.gsub(string2, \"(.)\", function(s) table.insert(str2, s); end);\n\n    for i = 0, str1.len do\n      distance[i] = {}\n      distance[i][0] = i\n    end\n\n    for i = 0, str2.len do\n      distance[0][i] = i\n    end\n\n    for i = 1, str1.len do\n            for j = 1, str2.len do\n                    local tmpdist = 1;\n                    if(str1[i-1] == str2[j-1]) then tmpdist = 0; end\n                    distance[i][j] = math.min(\n                            distance[i-1][j] + 1, distance[i][j-1]+1, distance[i-1][j-1] + tmpdist);\n            end\n    end\n    return distance[str1.len][str2.len];\nend\n\nlocal prev = 'test'\nlocal input = io.read()\nprint(input)\n\nwhile not (input == '') do   \n    print(input, prev)\n    local dist = levenshtein_distance(input, prev)\n    print('Distance', dist)\n        \n    prev = input      \n    input = io.read()\nend\n\nprint('quiting')<\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[9],"tags":[],"class_list":["post-235","post","type-post","status-publish","format-standard","hentry","category-lua"],"_links":{"self":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts\/235","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/comments?post=235"}],"version-history":[{"count":4,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts\/235\/revisions"}],"predecessor-version":[{"id":7775,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts\/235\/revisions\/7775"}],"wp:attachment":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/media?parent=235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/categories?post=235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/tags?post=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}