From 1c70e2dcaebe1bb18ec7d28f2caf2495efd5717d Mon Sep 17 00:00:00 2001 From: Alexander Pickering Date: Sun, 5 Jun 2016 20:58:42 -0400 Subject: Fixed a bug in hamming distance, and improved comments --- fuzzel.lua | 16 ++++++++++++++-- fuzzel_min.lua | 3 ++- 2 files changed, 16 insertions(+), 3 deletions(-) diff --git a/fuzzel.lua b/fuzzel.lua index f86de5c..f3432dc 100644 --- a/fuzzel.lua +++ b/fuzzel.lua @@ -1,7 +1,7 @@ --[[ Fuzzel v1.0 - Alexander "Apickx" Pickering Entered into the public domain June 2, 2016 - You are not required to, but consider linking back to the source! + You are not required to, but consider putting a link to the source in your file's comments! Some helper functions for calculateing distance between two strings @@ -97,6 +97,8 @@ fuzzel.fsd = fuzzel.FuzzySortDistance fuzzel.fsr = fuzzel.FuzzySortRatio ]] + +--Assign locals to these to the minifier can compress the file better local strlen,chrat,min,asrt,prs,iprs,typ,upack,tblins,tblsrt = string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack,table.insert,table.sort local fuzzel = {} @@ -178,7 +180,7 @@ function fuzzel.HammingDistance(stringa,stringb) asrt(len == strlen(stringb),"Hamming Distance cannot be calculated on two strings of different lengths:\"" .. stringa .. "\" \"" .. stringb .. "\"") local dist = 0 for i = 1,len do - dist = dist + (chrat(stringa,i) ~= chrat(stringb,i) and 1) + dist = dist + ((chrat(stringa,i) ~= chrat(stringb,i)) and 1 or 0) end return dist end @@ -190,7 +192,10 @@ end fuzzel.hr = fuzzel.HammingRatio local function FuzzySearch(str,func,...) + --Allow varargs, or a table local looparg = typ(arg[1]) == "table" and arg[1] or arg + + --Find the string with the shortest distance to the string we were supplied local tmin = func(looparg[1],str) local sout = looparg[1] for k,v in prs(looparg) do @@ -213,18 +218,25 @@ function fuzzel.FuzzyFindRatio(str,...) end local function FuzzySort(str, func, ...) + --allow varargs, or a table local looparg = typ(arg[1]) == "table" and arg[1] or arg + + --Roughly sort everything by it's distance to the string local usorted = {} for k,v in prs(looparg) do local dist = func(str,v) usorted[dist] = usorted[dist] or {} tblins(usorted[dist],v) end + + --Actually sort them into something can can be iterated with ipairs local sorted = {} for k,v in prs(usorted) do tblins(sorted,k) end tblsrt(sorted) + + --Then build our output table local otbl = {} for k,v in prs(sorted) do for i,j in prs(usorted[v]) do diff --git a/fuzzel_min.lua b/fuzzel_min.lua index 2482a7a..4862e3f 100644 --- a/fuzzel_min.lua +++ b/fuzzel_min.lua @@ -1 +1,2 @@ -local a,b,c,d,e,f,g,h,i,j=string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack,table.insert,table.sort;local k={}local function l(m,n,o,p,q,...)local r,s=a(m),a(n)local t={}for u=0,r do t[u]={}for v=0,s do t[u][v]=0 end end;for u=1,r do t[u][0]=u end;for v=1,s do t[0][v]=v end;for v=1,s do for u=1,r do local w=b(m,u)local x=b(n,v)t[u][v]=c(t[u-1][v]+q,t[u][v-1]+o,t[u-1][v-1]+(w==x and 0 or p))if arg[1]and u>1 and v>1 and w==b(n,v-1)and b(m,u-1)==x then t[u][v]=c(t[u][v],t[u-2][v-2]+(w==x and 0 or arg[2]))end end end;return t[r][s]end;function k.LevenshtienDistance_extended(m,n,o,p,q)return k.genericDistance(m,n,o,p,q)end;k.ld_e=k.LevenshtienDistance_extended;function k.LevenshtienDistance(m,n)return k.ld_e(m,n,1,1,1)end;k.ld=k.LevenshtienDistance;function k.LevenshteinRatio(m,n)return k.ld(m,n)/a(m)end;k.lr=k.LevensteinRatio;function k.DamerauLevenshtienDistance_extended(m,n,o,p,q,y)return l(m,n,o,p,q,true,y)end;k.dld_e=k.DamerauLevenshtienDistance_extended;function k.DamerauLevenshtienDistance(m,n)return k.dld_e(m,n,1,1,1,1)end;k.dld=k.DamerauLevenshtienDistance;function k.DamerauLevenshtienRatio(m,n)return k.dld(m,n)/a(m)end;k.dlr=k.DamerauLevenshtienRatio;function k.HammingDistance(m,n)local z=a(m)d(z==a(n),"Hamming Distance cannot be calculated on two strings of different lengths:\""..m.."\" \""..n.."\"")local A=0;for u=1,z do A=A+(b(m,u)~=b(n,u)and 1)end;return A end;k.hd=k.HammingDistance;function k.HammingRatio(m,n)return k.HammingDistance(m,n)/a(m)end;k.hr=k.HammingRatio;local function B(C,D,...)local E=g(arg[1])=="table"and arg[1]or arg;local F=D(E[1],C)local G=E[1]for H,I in e(E)do local J=D(I,C)if J1 and v>1 and w==b(n,v-1)and b(m,u-1)==x then t[u][v]=c(t[u][v],t[u-2][v-2]+(w==x and 0 or arg[2]))end end end;return t[r][s]end;function k.LevenshtienDistance_extended(m,n,o,p,q)return k.genericDistance(m,n,o,p,q)end;k.ld_e=k.LevenshtienDistance_extended;function k.LevenshtienDistance(m,n)return k.ld_e(m,n,1,1,1)end;k.ld=k.LevenshtienDistance;function k.LevenshteinRatio(m,n)return k.ld(m,n)/a(m)end;k.lr=k.LevensteinRatio;function k.DamerauLevenshtienDistance_extended(m,n,o,p,q,y)return l(m,n,o,p,q,true,y)end;k.dld_e=k.DamerauLevenshtienDistance_extended;function k.DamerauLevenshtienDistance(m,n)return k.dld_e(m,n,1,1,1,1)end;k.dld=k.DamerauLevenshtienDistance;function k.DamerauLevenshtienRatio(m,n)return k.dld(m,n)/a(m)end;k.dlr=k.DamerauLevenshtienRatio;function k.HammingDistance(m,n)local z=a(m)d(z==a(n),"Hamming Distance cannot be calculated on two strings of different lengths:\""..m.."\" \""..n.."\"")local A=0;for u=1,z do A=A+(b(m,u)~=b(n,u)and 1 or 0)end;return A end;k.hd=k.HammingDistance;function k.HammingRatio(m,n)return k.HammingDistance(m,n)/a(m)end;k.hr=k.HammingRatio;local function B(C,D,...)local E=g(arg[1])=="table"and arg[1]or arg;local F=D(E[1],C)local G=E[1]for H,I in e(E)do local J=D(I,C)if J