diff options
| -rw-r--r-- | fuzzel.lua | 39 | ||||
| -rw-r--r-- | fuzzel_min.lua | 4 |
2 files changed, 31 insertions, 12 deletions
@@ -54,6 +54,14 @@ Same as above, but uses Damerau-Levenshtein Ratio instead returns table_sorted + fuzzel.FuzzyAutocompleteDistance(string_needle, vararg in) + vararg_in can be either a table, or a list of entries, this will fuzzy sort based on the length of the input, which makes it better at autocompletion than fuzzy sorting. Uses Damerau-Levenshtein Distance. + returns table_sorted + + fuzzel.FuzzyAutocompleteRatio(string_needle, vararg_in) + Same as above, but uses DamerauLevenshteinRatio + returns table_sorted + Example: Returns a function that will return the closest string to the string it was passed -----------------FuzzelExample.lua------------------ @@ -101,13 +109,13 @@ ]]--You probably don't want to touch anything past this point --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 strlen,chrat,min,asrt,prs,iprs,typ,upack,tblins,tblsrt,strsub,tru,fal = string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack,table.insert,table.sort,string.sub,true,false local fuzzel = {} --A clever way to allow the minifier to minify function names, this basically just assigns variables with their string equivalent. -local da, le, di, ra, fu, fi, so, ex, ha = "Damerau", "Levenshtein", "Distance", "Ratio", "Fuzzy", "Find", "Sort", "_extended", "Hamming" -local LevenshteinDistance_extended,LevenshteinDistance,LevenshteinRatio,DamerauLevenshteinDistance_extended,DamerauLevenshteinDistance,DamerauLevenshteinRatio,FuzzyFindDistance,FuzzyFindRatio,FuzzySortDistance,FuzzySortRatio,HammingDistance,HammingRatio = le..di..ex,le..di,le..ra,da..le..di..ex,da..le..di,da..le..ra,fu..fi..di,fu..fi..ra,fu..so..di,fu..so..ra,ha..di,ha..ra +local da, le, di, ra, fu, fi, so, ex, ha, au = "Damerau", "Levenshtein", "Distance", "Ratio", "Fuzzy", "Find", "Sort", "_extended", "Hamming", "Autocomplete" +local LevenshteinDistance_extended,LevenshteinDistance,LevenshteinRatio,DamerauLevenshteinDistance_extended,DamerauLevenshteinDistance,DamerauLevenshteinRatio,FuzzyFindDistance,FuzzyFindRatio,FuzzySortDistance,FuzzySortRatio,HammingDistance,HammingRatio,FuzzyAutocompleteDistance,FuzzyAutocompleteRatio = le..di..ex,le..di,le..ra,da..le..di..ex,da..le..di,da..le..ra,fu..fi..di,fu..fi..ra,fu..so..di,fu..so..ra,ha..di,ha..ra,fu..au..di,fu..au..ra local function genericDistance( stringa, stringb, addcost, subcost, delcost, ...) local arg = {...} @@ -167,7 +175,7 @@ end fuzzel.lr = fuzzel[LevenshteinRatio] fuzzel[DamerauLevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost, trncost) - return genericDistance(stringa,stringb,addcost,subcost,delcost,true,trncost) + return genericDistance(stringa,stringb,addcost,subcost,delcost,tru,trncost) end fuzzel.dld_e = fuzzel[DamerauLevenshteinDistance_extended] @@ -183,7 +191,7 @@ fuzzel.dlr = fuzzel[DamerauLevenshteinRatio] fuzzel[HammingDistance] = function(stringa,stringb) local len,dist = strlen(stringa),0 - asrt(len == strlen(stringb),"Hamming Distance cannot be calculated on two strings of different lengths:\"" .. stringa .. "\" \"" .. stringb .. "\"") + asrt(len == strlen(stringb), ha.." "..di.." cannot be calculated on two strings of different lengths:\"" .. stringa .. "\" \"" .. stringb .. "\"") for i = 1,len do dist = dist + ((chrat(stringa,i) ~= chrat(stringb,i)) and 1 or 0) end @@ -222,16 +230,17 @@ fuzzel[FuzzyFindRatio] = function(str,...) return upack{FuzzySearch(str,fuzzel.dlr,...)} end -local function FuzzySort(str, func, ...) +local function FuzzySort(str, func, short, ...) local arg = {...} --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,sorted,otbl = {},{},{} + local usorted,sorted,otbl,slen = {},{},{},strlen(str) for k,v in prs(looparg) do - local dist = func(str,v) + local sstr = short and strsub(v,0,slen) or v + local dist = func(str,sstr) if usorted[dist] == nil then usorted[dist] = {} tblins(sorted,dist) @@ -253,13 +262,23 @@ end fuzzel.ffr = fuzzel[FuzzyFindRatio] fuzzel[FuzzySortDistance] = function(str,...) - return FuzzySort(str,fuzzel.dld,...) + return FuzzySort(str,fuzzel.dld,fal,...) end fuzzel.fsd = fuzzel[FuzzySortDistance] fuzzel[FuzzySortRatio] = function(str,...) - return FuzzySort(str,fuzzel.dlr,...) + return FuzzySort(str,fuzzel.dlr,fal,...) end fuzzel.fsr = fuzzel[FuzzySortRatio] +fuzzel[FuzzyAutocompleteDistance] = function(str, ...) + return FuzzySort(str,fuzzel.dld,tru,...) +end +fuzzel.fad = fuzzel[FuzzyAutocompleteDistance] + +fuzzel[FuzzyAutocompleteRatio] = function(str,...) + return FuzzySort(str,fuzzel.dlr,tru,...) +end +fuzzel.far = fuzzel[FuzzyAutocompleteRatio] + return fuzzel diff --git a/fuzzel_min.lua b/fuzzel_min.lua index 600f8ba..bffc02f 100644 --- a/fuzzel_min.lua +++ b/fuzzel_min.lua @@ -1,2 +1,2 @@ ---This code has been minified! For the original, see cogarr.net/source/cgit.cgi/fuzzel -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 l,m,n,o,p,q,r,s,t="Damerau","Levenshtein","Distance","Ratio","Fuzzy","Find","Sort","_extended","Hamming"local u,v,w,x,y,z,A,B,C,D,E,F=m..n..s,m..n,m..o,l..m..n..s,l..m..n,l..m..o,p..q..n,p..q..o,p..r..n,p..r..o,t..n,t..o;local function G(H,I,J,K,L,...)local M={...}local N,O=a(H),a(I)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,T=b(H,Q),b(I,R)P[Q][R]=c(P[Q-1][R]+L,P[Q][R-1]+J,P[Q-1][R-1]+(S==T and 0 or K))if M[1]and Q>1 and R>1 and S==b(I,R-1)and b(H,Q-1)==T then P[Q][R]=c(P[Q][R],P[Q-2][R-2]+(S==T and 0 or M[2]))end end end;return P[N][O]end;k[u]=function(H,I,J,K,L)return G(H,I,J,K,L)end;k.ld_e=k[u]k[v]=function(H,I)return k.ld_e(H,I,1,1,1)end;k.ld=k[v]k[w]=function(H,I)return k.ld(H,I)/a(H)end;k.lr=k[w]k[x]=function(H,I,J,K,L,U)return G(H,I,J,K,L,true,U)end;k.dld_e=k[x]k[y]=function(H,I)return k.dld_e(H,I,1,1,1,1)end;k.dld=k[y]k[z]=function(H,I)return k.dld(H,I)/a(H)end;k.dlr=k[z]k[E]=function(H,I)local V,W=a(H),0;d(V==a(I),"Hamming Distance cannot be calculated on two strings of different lengths:\""..H.."\" \""..I.."\"")for Q=1,V do W=W+(b(H,Q)~=b(I,Q)and 1 or 0)end;return W end;k.hd=k[E]k[F]=function(H,I)return k.hd(H,I)/a(H)end;k.hr=k[F]local function X(Y,Z,...)local M={...}local _=g(M[1])=="table"and M[1]or M;local a0,a1=Z(_[1],Y),_[1]for a2,a3 in e(_)do local a4=Z(a3,Y)if a4<=a0 then a0,a1=a4,a2 end end;return _[a1],a0 end;k[A]=function(Y,...)return h{X(Y,k.dld,...)}end;k.ffd=k[A]k[B]=function(Y,...)return h{X(Y,k.dlr,...)}end;local function a5(Y,Z,...)local M={...}local _=g(M[1])=="table"and M[1]or M;local a6,a7,a8={},{},{}for a2,a3 in e(_)do local W=Z(Y,a3)if a6[W]==nil then a6[W]={}i(a7,W)end;i(a6[W],a3)end;j(a7)for a2,a3 in f(a7)do for Q,R in e(a6[a3])do i(a8,R)end end;return a8 end;k.ffr=k[B]k[C]=function(Y,...)return a5(Y,k.dld,...)end;k.fsd=k[C]k[D]=function(Y,...)return a5(Y,k.dlr,...)end;k.fsr=k[D]return k +--This code has been minified! Original at cogarr.net/source/cgit.cgi/fuzzel +local a,b,c,d,e,f,g,h,i,j,k,l,m=string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack,table.insert,table.sort,string.sub,true,false;local n={}local o,p,q,r,s,t,u,v,w,x="Damerau","Levenshtein","Distance","Ratio","Fuzzy","Find","Sort","_extended","Hamming","Autocomplete"local y,z,A,B,C,D,E,F,G,H,I,J,K,L=p..q..v,p..q,p..r,o..p..q..v,o..p..q,o..p..r,s..t..q,s..t..r,s..u..q,s..u..r,w..q,w..r,s..x..q,s..x..r;local function M(N,O,P,Q,R,...)local S={...}local T,U=a(N),a(O)local V={}for W=0,T do V[W]={}for X=0,U do V[W][X]=0 end end;for W=1,T do V[W][0]=W end;for X=1,U do V[0][X]=X end;for X=1,U do for W=1,T do local Y,Z=b(N,W),b(O,X)V[W][X]=c(V[W-1][X]+R,V[W][X-1]+P,V[W-1][X-1]+(Y==Z and 0 or Q))if S[1]and W>1 and X>1 and Y==b(O,X-1)and b(N,W-1)==Z then V[W][X]=c(V[W][X],V[W-2][X-2]+(Y==Z and 0 or S[2]))end end end;return V[T][U]end;n[y]=function(N,O,P,Q,R)return M(N,O,P,Q,R)end;n.ld_e=n[y]n[z]=function(N,O)return n.ld_e(N,O,1,1,1)end;n.ld=n[z]n[A]=function(N,O)return n.ld(N,O)/a(N)end;n.lr=n[A]n[B]=function(N,O,P,Q,R,_)return M(N,O,P,Q,R,l,_)end;n.dld_e=n[B]n[C]=function(N,O)return n.dld_e(N,O,1,1,1,1)end;n.dld=n[C]n[D]=function(N,O)return n.dld(N,O)/a(N)end;n.dlr=n[D]n[I]=function(N,O)local a0,a1=a(N),0;d(a0==a(O),w.." "..q.." cannot be calculated on two strings of different lengths:\""..N.."\" \""..O.."\"")for W=1,a0 do a1=a1+(b(N,W)~=b(O,W)and 1 or 0)end;return a1 end;n.hd=n[I]n[J]=function(N,O)return n.hd(N,O)/a(N)end;n.hr=n[J]local function a2(a3,a4,...)local S={...}local a5=g(S[1])=="table"and S[1]or S;local a6,a7=a4(a5[1],a3),a5[1]for a8,a9 in e(a5)do local aa=a4(a9,a3)if aa<=a6 then a6,a7=aa,a8 end end;return a5[a7],a6 end;n[E]=function(a3,...)return h{a2(a3,n.dld,...)}end;n.ffd=n[E]n[F]=function(a3,...)return h{a2(a3,n.dlr,...)}end;local function ab(a3,a4,ac,...)local S={...}local a5=g(S[1])=="table"and S[1]or S;local ad,ae,af,ag={},{},{},a(a3)for a8,a9 in e(a5)do local ah=ac and k(a9,0,ag)or a9;local a1=a4(a3,ah)if ad[a1]==nil then ad[a1]={}i(ae,a1)end;i(ad[a1],a9)end;j(ae)for a8,a9 in f(ae)do for W,X in e(ad[a9])do i(af,X)end end;return af end;n.ffr=n[F]n[G]=function(a3,...)return ab(a3,n.dld,m,...)end;n.fsd=n[G]n[H]=function(a3,...)return ab(a3,n.dlr,m,...)end;n.fsr=n[H]n[K]=function(a3,...)return ab(a3,n.dld,l,...)end;n.fad=n[K]n[L]=function(a3,...)return ab(a3,n.dlr,l,...)end;n.far=n[L]return n |