diff options
| -rw-r--r-- | fuzzel.lua | 91 | ||||
| -rw-r--r-- | fuzzel_min.lua | 2 |
2 files changed, 59 insertions, 34 deletions
@@ -45,10 +45,33 @@ fuzzel.FuzzySearchRatio(string_needle, vararg_in) in may be either a table, or a list of arguments. Same as above, except it returns the string with the closest Damerau-Levenshtien ratio. returns string_closest, nubmer_ratio + + Example: + Returns a function that will return the closest string to the string it was passed + -----------------FuzzelExample.lua------------------ + local fuzzel = dofile("fuzzel.lua") + + function suggestoption(tbl_options) + return function(str) + local closest = fuzzel.FuzzySearchDistance(str,tbl_options) + return closest + end + end + + local options = { + "Fat Cat", + "Lazy Dog", + "Brown Fox", + } + local suggestfunc = suggestoption(options) + + suggestfunc("Brown Cat") + -------------End FuzzelExample.lua------------------ + ]] local strlen,chrat,min,asrt,prs,iprs,typ,upack = string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack -module("fuzzel") +local fuzzel = {} local function genericDistance( stringa, stringb, addcost, subcost, delcost, ...) --Length of each string @@ -91,33 +114,33 @@ local function genericDistance( stringa, stringb, addcost, subcost, delcost, ... return dyntbl[salen][sblen] end -function LevenshtienDistance_extended(stringa, stringb, addcost, subcost, delcost) - return genericDistance(stringa, stringb, addcost, subcost, delcost) +function fuzzel.LevenshtienDistance_extended(stringa, stringb, addcost, subcost, delcost) + return fuzzel.genericDistance(stringa, stringb, addcost, subcost, delcost) end -function LevenshtienDistance(stringa,stringb) - return LevenshtienDistance_extended(stringa,stringb,1,1,1) +function fuzzel.LevenshtienDistance(stringa,stringb) + return fuzzel.LevenshtienDistance_extended(stringa,stringb,1,1,1) end --The distance as a ratio of stringa's length -function LevenshteinRatio(stringa,stringb) - return LevenshtienDistance(stringa,stringb) / strlen(stringa) +function fuzzel.LevenshteinRatio(stringa,stringb) + return fuzzel.LevenshtienDistance(stringa,stringb) / strlen(stringa) end --Almost the same as LevenshtienDistance, but considers two characters swaped as only "one" mistake -function DamerauLevenshtienDistance_extended(stringa, stringb, addcost, subcost, delcost, trncost) +function fuzzel.DamerauLevenshtienDistance_extended(stringa, stringb, addcost, subcost, delcost, trncost) return genericDistance(stringa,stringb,addcost,subcost,delcost,true,trncost) end -function DamerauLevenshtienDistance(stringa,stringb) - return DamerauLevenshtienDistance_extended(stringa,stringb,1,1,1,1) +function fuzzel.DamerauLevenshtienDistance(stringa,stringb) + return fuzzel.DamerauLevenshtienDistance_extended(stringa,stringb,1,1,1,1) end -function DamerauLevenshtienRatio(stringa,stringb) - return DamerauLevenshtienDistance(stringa,stringb) / strlen(stringa) +function fuzzel.DamerauLevenshtienRatio(stringa,stringb) + return fuzzel.DamerauLevenshtienDistance(stringa,stringb) / strlen(stringa) end --Purely the number of mistakes -function HammingDistance(stringa,stringb) +function fuzzel.HammingDistance(stringa,stringb) local len = strlen(stringa) asrt(len == strlen(stringb),"Hamming Distance cannot be calculated on two strings of different lengths:\"" .. stringa .. "\" \"" .. stringb .. "\"") local dist = 0 @@ -127,15 +150,15 @@ function HammingDistance(stringa,stringb) return dist end -function HammingRatio(stringa,stringb) - return HammingDistance(stringa,stringb) / strlen(stringa) +function fuzzel.HammingRatio(stringa,stringb) + return fuzzel.HammingDistance(stringa,stringb) / strlen(stringa) end local function FuzzySearch(str,func,...) - local itrfunc = typ(arg[1]) == "table" and prs or iprs - local tmin = func(arg[1],str) - local sout = arg[1] - for k,v in itrfunc(arg) do + local looparg = typ(arg[1]) == "table" and arg[1] or arg + local tmin = func(looparg[1],str) + local sout = looparg[1] + for k,v in prs(looparg) do local t = func(v,str) if t < tmin then tmin = t @@ -145,22 +168,24 @@ local function FuzzySearch(str,func,...) return sout, tmin end -function FuzzySearchDistance(str,...) - return upack{FuzzySearch(str,DamerauLevenshtienDistance,...)} +function fuzzel.FuzzySearchDistance(str,...) + return upack{FuzzySearch(str,fuzzel.DamerauLevenshtienDistance,...)} end -function FuzzySearchRatio(str,...) - return upack{FuzzySearch(str,DamerauLevenshtienRatio,...)} +function fuzzel.FuzzySearchRatio(str,...) + return upack{FuzzySearch(str,fuzzel.DamerauLevenshtienRatio,...)} end --Some easy-to-use mnemonics -ld_e = LevenshtienDistance_extended -ld = LevenshtienDistance -lr = LevensteinRatio -dld_e = DamerauLevenshtienDistance_extended -dld = DamerauLevenshtienDistance -dlr = DamerauLevenshtienRatio -hd = HammingDistance -hr = HammingRatio -fsd = FuzzySearchDistance -fsr = FuzzySearchRatio +fuzzel.ld_e = fuzzel.LevenshtienDistance_extended +fuzzel.ld = fuzzel.LevenshtienDistance +fuzzel.lr = fuzzel.LevensteinRatio +fuzzel.dld_e = fuzzel.DamerauLevenshtienDistance_extended +fuzzel.dld = fuzzel.DamerauLevenshtienDistance +fuzzel.dlr = fuzzel.DamerauLevenshtienRatio +fuzzel.hd = fuzzel.HammingDistance +fuzzel.hr = fuzzel.HammingRatio +fuzzel.fsd = fuzzel.FuzzySearchDistance +fuzzel.fsr = fuzzel.FuzzySearchRatio + +return fuzzel diff --git a/fuzzel_min.lua b/fuzzel_min.lua index d2cec2c..4e845b3 100644 --- a/fuzzel_min.lua +++ b/fuzzel_min.lua @@ -1,2 +1,2 @@ --This file has been minified! For the original, see cogarr.net/source/ -local a,b,c,d,e,f,g,h=string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack;module("fuzzel")function LevenshtienDistance_extended(i,j,k,l,m,...)local n,o=a(i),a(j)local p={}for q=0,n do p[q]={}for r=0,o do p[q][r]=0 end end;for q=1,n do p[q][0]=q end;for r=1,o do p[0][r]=r end;for r=1,o do for q=1,n do local s=b(i,q)local t=b(j,r)p[q][r]=c(p[q-1][r]+m,p[q][r-1]+k,p[q-1][r-1]+(s==t and 0 or l))if arg[1]and q>1 and r>1 and s==b(j,r-1)and b(i,q-1)==t then p[q][r]=c(p[q][r],p[q-2][r-2]+(s==t and 0 or arg[2]))end end end;return p[n][o]end;function LevenshtienDistance(i,j)return LevenshtienDistance_extended(i,j,1,1,1,false,0)end;function LevenshteinRatio(i,j)return LevenshtienDistance(i,j)/a(i)end;function DamerauLevenshtienDistance_extended(i,j,k,l,m,u)return LevenshtienDistance_extended(i,j,k,l,m,true,u)end;function DamerauLevenshtienDistance(i,j)return DamerauLevenshtienDistance_extended(i,j,1,1,1,1)end;function DamerauLevenshtienRatio(i,j)return DamerauLevenshtienDistance(i,j)/a(i)end;function HammingDistance(i,j)local v=a(i)d(v==a(j),"Hamming Distance cannot be calculated on two strings of different lengths:\""..i.."\" \""..j.."\"")local w=0;for q=1,v do w=w+(b(i,q)~=b(j,q)and 1)end;return w end;function HammingRatio(i,j)return HammingDistance(i,j)/a(i)end;local function x(y,z,...)local A=g(arg[1])=="table"and e or f;local B=z(arg[1],y)local C=arg[1]for D,E in A(arg)do local F=z(E,y)if F<B then B=F;C=E end end;return C,B end;function FuzzySearchDistance(y,...)return h{x(y,DamerauLevenshtienDistance,...)}end;function FuzzySearchRatio(y,...)return h{x(y,DamerauLevenshtienRatio,...)}end;ld_e=LevenshtienDistance_extended;ld=LevenshtienDistance;lr=LevensteinRatio;dld_e=DamerauLevenshtienDistance_extended;dld=DamerauLevenshtienDistance;dlr=DamerauLevenshtienRatio;hd=HammingDistance;hr=HammingRatio;fsd=FuzzySearchDistance;fsr=FuzzySearchRatio +local a,b,c,d,e,f,g,h=string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack;local i={}local function j(k,l,m,n,o,...)local p,q=a(k),a(l)local r={}for s=0,p do r[s]={}for t=0,q do r[s][t]=0 end end;for s=1,p do r[s][0]=s end;for t=1,q do r[0][t]=t end;for t=1,q do for s=1,p do local u=b(k,s)local v=b(l,t)r[s][t]=c(r[s-1][t]+o,r[s][t-1]+m,r[s-1][t-1]+(u==v and 0 or n))if arg[1]and s>1 and t>1 and u==b(l,t-1)and b(k,s-1)==v then r[s][t]=c(r[s][t],r[s-2][t-2]+(u==v and 0 or arg[2]))end end end;return r[p][q]end;function i.LevenshtienDistance_extended(k,l,m,n,o)return i.genericDistance(k,l,m,n,o)end;function i.LevenshtienDistance(k,l)return i.LevenshtienDistance_extended(k,l,1,1,1)end;function i.LevenshteinRatio(k,l)return i.LevenshtienDistance(k,l)/a(k)end;function i.DamerauLevenshtienDistance_extended(k,l,m,n,o,w)return j(k,l,m,n,o,true,w)end;function i.DamerauLevenshtienDistance(k,l)return i.DamerauLevenshtienDistance_extended(k,l,1,1,1,1)end;function i.DamerauLevenshtienRatio(k,l)return i.DamerauLevenshtienDistance(k,l)/a(k)end;function i.HammingDistance(k,l)local x=a(k)d(x==a(l),"Hamming Distance cannot be calculated on two strings of different lengths:\""..k.."\" \""..l.."\"")local y=0;for s=1,x do y=y+(b(k,s)~=b(l,s)and 1)end;return y end;function i.HammingRatio(k,l)return i.HammingDistance(k,l)/a(k)end;local function z(A,B,...)local C=g(arg[1])=="table"and arg[1]or arg;local D=B(C[1],A)local E=C[1]for F,G in e(C)do local H=B(G,A)if H<D then D=H;E=G end end;return E,D end;function i.FuzzySearchDistance(A,...)return h{z(A,i.DamerauLevenshtienDistance,...)}end;function i.FuzzySearchRatio(A,...)return h{z(A,i.DamerauLevenshtienRatio,...)}end;i.ld_e=i.LevenshtienDistance_extended;i.ld=i.LevenshtienDistance;i.lr=i.LevensteinRatio;i.dld_e=i.DamerauLevenshtienDistance_extended;i.dld=i.DamerauLevenshtienDistance;i.dlr=i.DamerauLevenshtienRatio;i.hd=i.HammingDistance;i.hr=i.HammingRatio;i.fsd=i.FuzzySearchDistance;i.fsr=i.FuzzySearchRatio;return i |