From 71692710e25cee2ffbda576629d63e75af59dc25 Mon Sep 17 00:00:00 2001 From: Alexander Pickering Date: Mon, 27 Jun 2016 19:05:01 -0400 Subject: moved things to be compiled by ldoc --- dist/fuzzel_min.lua | 1 + doc/config.ld | 8 + doc/index.html | 598 ++++++++++++++++++++++++++++++++++++++++++++++++++++ doc/ldoc.css | 304 ++++++++++++++++++++++++++ fuzzel.lua | 286 ------------------------- fuzzel_min.lua | 2 - src/fuzzel.lua | 334 +++++++++++++++++++++++++++++ 7 files changed, 1245 insertions(+), 288 deletions(-) create mode 100644 dist/fuzzel_min.lua create mode 100644 doc/config.ld create mode 100644 doc/index.html create mode 100644 doc/ldoc.css delete mode 100644 fuzzel.lua delete mode 100644 fuzzel_min.lua create mode 100644 src/fuzzel.lua diff --git a/dist/fuzzel_min.lua b/dist/fuzzel_min.lua new file mode 100644 index 0000000..4916e2d --- /dev/null +++ b/dist/fuzzel_min.lua @@ -0,0 +1 @@ +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.VERSION="1.4"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;n.ffr=n[F]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[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 diff --git a/doc/config.ld b/doc/config.ld new file mode 100644 index 0000000..e6121b8 --- /dev/null +++ b/doc/config.ld @@ -0,0 +1,8 @@ +project = 'Fuzzel' +description = 'String matching library' +full_description = 'A few functions to do fuzzy string matching' +title = 'Penlight Documentation' +dir = 'doc' +use_markdown_titles = true +format = 'markdown' +file = '../src/fuzzel.lua' diff --git a/doc/index.html b/doc/index.html new file mode 100644 index 0000000..d2fab8f --- /dev/null +++ b/doc/index.html @@ -0,0 +1,598 @@ + + + + + Penlight Documentation + + + + +
+ +
+ +
+
+
+ + +
+ + + + + + +
+ +

Module fuzzel

+

A collection of methods for finding edit distance between two strings

+

+ +

+ + +

Functions

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
LevenshteinDistance_extended (str1, str2, addcost, subcost, delcost)Finds edit distance between two strings with custom costs.
LevenshteinDistance (str1, str2)Finds simple Levenshtein distance.
LevenshteinRatio (str1, str2)Finds edit ratio between two strings
DamerauLevenshteinDistance_extended (str1, str2, addcost, subcost, delcost, trncost)Finds edit distance between two strings, with custom values.
DamerauLevenshteinDistance (str1, str2)Finds simple Damerau-Levenshtein distance.
DamerauLevenshteinRatio (str1, str2)Finds edit ratio between two strings
HammingDistance (str1, str2)Finds the nubmer of subtitutions needed to turn one string into another.
HammingRatio (str1, str2)Calculates the Hamming distance between two strings, divided by the length of the first string.
FuzzyFindDistance (str, ...)Finds the closest argument to the first argument.
FuzzyFindRatio (str, ...)Finds the closest argument to the first argument.
FuzzySortDistance (str, ...)Sorts inputed strings by distance.
FuzzySortRatio (str, ...)Sorts inputed strings by ratio.
FuzzyAutocompleteDistance (str, ...)Sorts truncated versions of inputed strings by distance.
FuzzyAutocompleteRatio (str, ...)Sorts truncated versions of inputed strings by ratio.
+

Fields

+ + + + + +
VERSIONThe current version (1.4).
+ +
+
+ + +

Functions

+ +
+
+ + LevenshteinDistance_extended (str1, str2, addcost, subcost, delcost) +
+
+ Finds edit distance between two strings with custom costs. + The levenshtein distance is the minimum number of additions, deletions, and substitutions that are needed to turn one string into another. This methods allows custom costs for addition, deletion, and substitution. + + +

Parameters:

+
    +
  • str1 + string + the first string +
    • +
  • str2 + string + the second string +
    • +
  • addcost + number + the custom cost to add one character +
    • +
  • subcost + number + the custom cost to subtitute one character for another +
    • +
  • delcost + number + the custom cost to delete one character +
    • +
+ +

Returns:

+
    + + the distance from the first string to the second (which will always be the same as the distance from the second string to the first) +
+ + + + +
+
+ + LevenshteinDistance (str1, str2) +
+
+ Finds simple Levenshtein distance. + The levenshtein distance is the minimum number of additions, deletions, and substitutions that are needed to turn one string into another. + + +

Parameters:

+
    +
  • str1 + string + the first string +
    • +
  • str2 + string + the second string +
    • +
+ +

Returns:

+
    + + the distance between the two input strings +
+ + + + +
+
+ + LevenshteinRatio (str1, str2) +
+
+ Finds edit ratio between two strings + + +

Parameters:

+
    +
  • str1 + string + the first string, and the string to use for the ratio +
    • +
  • str2 + string + the second string +
    • +
+ +

Returns:

+
    + + the distance between the two strings divided by the length of the first string +
+ + + + +
+
+ + DamerauLevenshteinDistance_extended (str1, str2, addcost, subcost, delcost, trncost) +
+
+ Finds edit distance between two strings, with custom values. + The minimum number of additions, deletions, substitutions, or transpositions to turn str1 into str2 with the given weights + + +

Parameters:

+
    +
  • str1 + string + the first string +
    • +
  • str2 + string + the second string +
    • +
  • addcost + number + the cost of insterting a character +
    • +
  • subcost + number + the cost of substituteing one character for another +
    • +
  • delcost + number + the cost of removeing a character +
    • +
  • trncost + number + the cost of transposeing two adjacent characters. +
    • +
+ +

Returns:

+
    + + the edit distance between the two strings +
+ + + + +
+
+ + DamerauLevenshteinDistance (str1, str2) +
+
+ Finds simple Damerau-Levenshtein distance. + + +

Parameters:

+
    +
  • str1 + string + the fist string +
    • +
  • str2 + string + the second string +
    • +
+ +

Returns:

+
    + + the minimum number of additions, deletions, substitutions, or transpositions to turn str1 into str2 +
+ + + + +
+
+ + DamerauLevenshteinRatio (str1, str2) +
+
+ Finds edit ratio between two strings + + +

Parameters:

+
    +
  • str1 + string + the fist string, and number to use for ratio +
    • +
  • str2 + string + the second string +
    • +
+ +

Returns:

+
    + + the Damerau-Levenshtein distance divided by the length of the first string. +
+ + + + +
+
+ + HammingDistance (str1, str2) +
+
+ Finds the nubmer of subtitutions needed to turn one string into another. + Hamming distance can only be calculated on two strings of equal length. + + +

Parameters:

+
    +
  • str1 + string + the first string +
    • +
  • str2 + string + the second string +
    • +
+ +

Returns:

+
    + + the edit distance between str1 and str2 +
+ + + + +
+
+ + HammingRatio (str1, str2) +
+
+ Calculates the Hamming distance between two strings, divided by the length of the first string. + + +

Parameters:

+
    +
  • str1 + string + the first string, and string to use for the ratio +
    • +
  • str2 + string + the second string +
    • +
+ +

Returns:

+
    + + the edit distance between the two strings +
+ + + + +
+
+ + FuzzyFindDistance (str, ...) +
+
+ Finds the closest argument to the first argument. + Finds the closest argument to the first argument useing Damerau-Levenshtein distance + + +

Parameters:

+
    +
  • str + string + the string to compare to +
    • +
  • ... + A 1-indexed array of strings, or a list of strings to campare str against +
    • +
+ + + + + +
+
+ + FuzzyFindRatio (str, ...) +
+
+ Finds the closest argument to the first argument. + Finds the closest argument to the first argument useing Damerau-Levenshtein ratio + + +

Parameters:

+
    +
  • str + string + the string to compare to +
    • +
  • ... + A 1-indexed array of strings, or a list of strings to campare str against +
    • +
+ + + + + +
+
+ + FuzzySortDistance (str, ...) +
+
+ Sorts inputed strings by distance. + Finds the Damerau-Levenshtein distance of each string to the first argument, and sorts them into a table accordingly + + +

Parameters:

+
    +
  • str + string + the string to compare each result to +
    • +
  • ... + either a 1-indexed table, or a list of strings to sort +
    • +
+ +

Returns:

+
    + + a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +
+ + + + +
+
+ + FuzzySortRatio (str, ...) +
+
+ Sorts inputed strings by ratio. + Finds the Damerau-Levenshtein ratio of each string to the first argument, and sorts them into a table accordingly + + +

Parameters:

+
    +
  • str + string + the string to compare each result to +
    • +
  • ... + either a 1-indexed table, or a list of strings to sort +
    • +
+ +

Returns:

+
    + + a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +
+ + + + +
+
+ + FuzzyAutocompleteDistance (str, ...) +
+
+ Sorts truncated versions of inputed strings by distance. + truncates each input string, and finds the Damerau-Levenshtein distance of each string to the first argument, and sorts them into a table accordingly. Useful for auto-complete functions + + +

Parameters:

+
    +
  • str + string + the string to compare each result to +
    • +
  • ... + either a 1-indexed table, or a list of strings to sort +
    • +
+ +

Returns:

+
    + + a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +
+ + + + +
+
+ + FuzzyAutocompleteRatio (str, ...) +
+
+ Sorts truncated versions of inputed strings by ratio. + truncates each input string, and finds the Damerau-Levenshtein ratio of each string to the first argument, and sorts them into a table accordingly. Useful for auto-complete functions + + +

Parameters:

+
    +
  • str + string + the string to compare each result to +
    • +
  • ... + either a 1-indexed table, or a list of strings to sort +
    • +
+ +

Returns:

+
    + + a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +
+ + + + +
+
+

Fields

+ +
+
+ + VERSION +
+
+ The current version (1.4). + + + + + + + +
+
+ + +
+
+
+generated by LDoc 1.4.3 +Last updated 2016-06-27 18:24:14 +
+
+ + diff --git a/doc/ldoc.css b/doc/ldoc.css new file mode 100644 index 0000000..ce77ac8 --- /dev/null +++ b/doc/ldoc.css @@ -0,0 +1,304 @@ +/* BEGIN RESET + +Copyright (c) 2010, Yahoo! Inc. All rights reserved. +Code licensed under the BSD License: +http://developer.yahoo.com/yui/license.html +version: 2.8.2r1 +*/ +html { + color: #000; + background: #FFF; +} +body,div,dl,dt,dd,ul,ol,li,h1,h2,h3,h4,h5,h6,pre,code,form,fieldset,legend,input,button,textarea,p,blockquote,th,td { + margin: 0; + padding: 0; +} +table { + border-collapse: collapse; + border-spacing: 0; +} +fieldset,img { + border: 0; +} +address,caption,cite,code,dfn,em,strong,th,var,optgroup { + font-style: inherit; + font-weight: inherit; +} +del,ins { + text-decoration: none; +} +li { + list-style: disc; + margin-left: 20px; +} +caption,th { + text-align: left; +} +h1,h2,h3,h4,h5,h6 { + font-size: 100%; + font-weight: bold; +} +q:before,q:after { + content: ''; +} +abbr,acronym { + border: 0; + font-variant: normal; +} +sup { + vertical-align: baseline; +} +sub { + vertical-align: baseline; +} +legend { + color: #000; +} +input,button,textarea,select,optgroup,option { + font-family: inherit; + font-size: inherit; + font-style: inherit; + font-weight: inherit; +} +input,button,textarea,select {*font-size:100%; +} +/* END RESET */ + +body { + margin-left: 1em; + margin-right: 1em; + font-family: arial, helvetica, geneva, sans-serif; + background-color: #ffffff; margin: 0px; +} + +code, tt { font-family: monospace; font-size: 1.1em; } +span.parameter { font-family:monospace; } +span.parameter:after { content:":"; } +span.types:before { content:"("; } +span.types:after { content:")"; } +.type { font-weight: bold; font-style:italic } + +body, p, td, th { font-size: .95em; line-height: 1.2em;} + +p, ul { margin: 10px 0 0 0px;} + +strong { font-weight: bold;} + +em { font-style: italic;} + +h1 { + font-size: 1.5em; + margin: 0 0 20px 0; +} +h2, h3, h4 { margin: 15px 0 10px 0; } +h2 { font-size: 1.25em; } +h3 { font-size: 1.15em; } +h4 { font-size: 1.06em; } + +a:link { font-weight: bold; color: #004080; text-decoration: none; } +a:visited { font-weight: bold; color: #006699; text-decoration: none; } +a:link:hover { text-decoration: underline; } + +hr { + color:#cccccc; + background: #00007f; + height: 1px; +} + +blockquote { margin-left: 3em; } + +ul { list-style-type: disc; } + +p.name { + font-family: "Andale Mono", monospace; + padding-top: 1em; +} + +pre { + background-color: rgb(245, 245, 245); + border: 1px solid #C0C0C0; /* silver */ + padding: 10px; + margin: 10px 0 10px 0; + overflow: auto; + font-family: "Andale Mono", monospace; +} + +pre.example { + font-size: .85em; +} + +table.index { border: 1px #00007f; } +table.index td { text-align: left; vertical-align: top; } + +#container { + margin-left: 1em; + margin-right: 1em; + background-color: #f0f0f0; +} + +#product { + text-align: center; + border-bottom: 1px solid #cccccc; + background-color: #ffffff; +} + +#product big { + font-size: 2em; +} + +#main { + background-color: #f0f0f0; + border-left: 2px solid #cccccc; +} + +#navigation { + float: left; + width: 14em; + vertical-align: top; + background-color: #f0f0f0; + overflow: visible; +} + +#navigation h2 { + background-color:#e7e7e7; + font-size:1.1em; + color:#000000; + text-align: left; + padding:0.2em; + border-top:1px solid #dddddd; + border-bottom:1px solid #dddddd; +} + +#navigation ul +{ + font-size:1em; + list-style-type: none; + margin: 1px 1px 10px 1px; +} + +#navigation li { + text-indent: -1em; + display: block; + margin: 3px 0px 0px 22px; +} + +#navigation li li a { + margin: 0px 3px 0px -1em; +} + +#content { + margin-left: 14em; + padding: 1em; + width: 700px; + border-left: 2px solid #cccccc; + border-right: 2px solid #cccccc; + background-color: #ffffff; +} + +#about { + clear: both; + padding: 5px; + border-top: 2px solid #cccccc; + background-color: #ffffff; +} + +@media print { + body { + font: 12pt "Times New Roman", "TimeNR", Times, serif; + } + a { font-weight: bold; color: #004080; text-decoration: underline; } + + #main { + background-color: #ffffff; + border-left: 0px; + } + + #container { + margin-left: 2%; + margin-right: 2%; + background-color: #ffffff; + } + + #content { + padding: 1em; + background-color: #ffffff; + } + + #navigation { + display: none; + } + pre.example { + font-family: "Andale Mono", monospace; + font-size: 10pt; + page-break-inside: avoid; + } +} + +table.module_list { + border-width: 1px; + border-style: solid; + border-color: #cccccc; + border-collapse: collapse; +} +table.module_list td { + border-width: 1px; + padding: 3px; + border-style: solid; + border-color: #cccccc; +} +table.module_list td.name { background-color: #f0f0f0; min-width: 200px; } +table.module_list td.summary { width: 100%; } + + +table.function_list { + border-width: 1px; + border-style: solid; + border-color: #cccccc; + border-collapse: collapse; +} +table.function_list td { + border-width: 1px; + padding: 3px; + border-style: solid; + border-color: #cccccc; +} +table.function_list td.name { background-color: #f0f0f0; min-width: 200px; } +table.function_list td.summary { width: 100%; } + +ul.nowrap { + overflow:auto; + white-space:nowrap; +} + +dl.table dt, dl.function dt {border-top: 1px solid #ccc; padding-top: 1em;} +dl.table dd, dl.function dd {padding-bottom: 1em; margin: 10px 0 0 20px;} +dl.table h3, dl.function h3 {font-size: .95em;} + +/* stop sublists from having initial vertical space */ +ul ul { margin-top: 0px; } +ol ul { margin-top: 0px; } +ol ol { margin-top: 0px; } +ul ol { margin-top: 0px; } + +/* make the target distinct; helps when we're navigating to a function */ +a:target + * { + background-color: #FF9; +} + + +/* styles for prettification of source */ +pre .comment { color: #558817; } +pre .constant { color: #a8660d; } +pre .escape { color: #844631; } +pre .keyword { color: #aa5050; font-weight: bold; } +pre .library { color: #0e7c6b; } +pre .marker { color: #512b1e; background: #fedc56; font-weight: bold; } +pre .string { color: #8080ff; } +pre .number { color: #f8660d; } +pre .operator { color: #2239a8; font-weight: bold; } +pre .preprocessor, pre .prepro { color: #a33243; } +pre .global { color: #800080; } +pre .user-keyword { color: #800080; } +pre .prompt { color: #558817; } +pre .url { color: #272fc2; text-decoration: underline; } + diff --git a/fuzzel.lua b/fuzzel.lua deleted file mode 100644 index 6aad45f..0000000 --- a/fuzzel.lua +++ /dev/null @@ -1,286 +0,0 @@ ---[[ - Fuzzel v1.3 - Alexander "Apickx" Pickering - Entered into the public domain June 2, 2016 - 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 - - Provides: - fuzzel.LevenshteinDistance_extended(string_first, string_second, number_addcost, number_substituecost, number_deletecost) - Calculates the Levenshtein Distance between two strings, useing the costs given. "Real" Levenshtein Distance uses values 1,1,1 for costs. - returns number_distance - - fuzzel.LevenshteinDistance(string_first, strings_second) - Calculates the "real" Levenshtein Distance - returns number_distance - - fuzzel.LevensteinRatio(string_first, string_second) - The Levenshtein Ratio divided by the first string's length. Useing a ratio is a decent way to determin if a spelling is "close enough" - returns number_distance - - fuzzel.DamerauLevenshteinDistance_extended(string_first, string_second, number_addcost, number_substituecost, number_deletecost, number_transpositioncost) - Damerau-Levenshtein Distance is almost exactly like Levenshtein Distance, with the caveat that two letters next to each other, with swapped positions only counts as "one" cost (in "real" Damerau-Levenshtein Distance) - returns number - - fuzzel.DamerauLevenshteinDistance(stirng_first, strings_second) - Calculates the "real" Damerau-Levenshtein Distance - returns number - - fuzzel.DamerauLevenshteinRatio(string_first, string_second) - The Damerau-Levenshtein Distance divided by the first string's length - returns number_ratio - - fuzzel.HammingDistance(string_first, string_second) - Purely the number of substitutions needed to change one string into another. Note that both strings must be the same length. - returns number_distance - - fuzzel.HammingRatio(string_first, string_second) - The hamming distance divided by the length of the first string - returns number_ratio - - fuzzel.FuzzyFindDistance(string_needle, vararg_in) - in may be either a table, or a list of arguments. fuzzel.FuzzySearchDistance will find the string that most closely resembles needle, based on Damerau-Levenshtein Distance. If multiple options have the same distance, it will return the first one encountered (This may not be in any sort of order!) - returns string_closest, number_distance - - fuzzel.FuzzyFindRatio(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-Levenshtein ratio. - returns string_closest, nubmer_ratio - - fuzzel.FuzzySortDistance(string_needle, vararg_in) - Sorts either the table, or the arguments, and returns a table. Uses Damerau-Levenshtein Distance - returns table_sorted - - fuzzel.FuzzySortRatio(string needle, vararg_in) - 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------------------ - --Include the module - local fuzzel = require("fuzzel.lua") - - --A couple of options - local options = { - "Fat Cat", - "Lazy Dog", - "Brown Fox", - } - - --And use it, to see what option closest matches "Lulzy Cat" - local close,distance = fuzzel.FuzzyFindDistance("Lulzy Cat", options) - print("\"Lulzy Cat\" is close to \"" .. close .. "\", distance:" .. distance) - - --Sort the options to see the order in which they most closely match "Frag God" - print("\"Frag God\" is closest to:") - for k,v in ipairs(fuzzel.FuzzySortRatio("Frag God",options)) do - print(k .. "\t:\t" .. v) - end - -------------End FuzzelExample.lua------------------ - Outputs: - "Lulzy Cat" is close to "Fat Cat" - "Frag God" is closest to: - 1 : Fat Cat - 2 : Lazy Dog - 3 : Brown Fox - - Some easy-to-use mnemonics - fuzzel.ld_e = fuzzel.LevenshteinDistance_extended - fuzzel.ld = fuzzel.LevenshteinDistance - fuzzel.lr = fuzzel.LevensteinRatio - fuzzel.dld_e = fuzzel.DamerauLevenshteinDistance_extended - fuzzel.dld = fuzzel.DamerauLevenshteinDistance - fuzzel.dlr = fuzzel.DamerauLevenshteinRatio - fuzzel.hd = fuzzel.HammingDistance - fuzzel.hr = fuzzel.HammingRatio - fuzzel.ffd = fuzzel.FuzzyFindDistance - fuzzel.ffr = fuzzel.FuzzyFindRatio - fuzzel.fsd = fuzzel.FuzzySortDistance - fuzzel.fsr = fuzzel.FuzzySortRatio - fuzzel.fad = fuzzel.FuzzyAutocompleteDistance - fuzzel.far = fuzzel.FuzzyAutocompleteRatio - -]]--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,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, 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 = {...} - - --Length of each string - local salen, sblen = strlen(stringa), strlen(stringb) - - --Create a 0 matrix the size of len(a) x len(b) - local dyntbl = {} - for i = 0,salen do - dyntbl[i] = {} - for j = 0,sblen do - dyntbl[i][j] = 0 - end - end - - --Initalize the matrix - for i = 1,salen do - dyntbl[i][0] = i - end - for j = 1,sblen do - dyntbl[0][j] = j - end - - --And build up the matrix based on costs-so-far - for j = 1,sblen do - for i = 1,salen do - local ca,cb = chrat(stringa,i),chrat(stringb,j) - dyntbl[i][j] = min( - dyntbl[i-1][j] + delcost, --deletion - dyntbl[i][j-1] + addcost, --insertion - dyntbl[i-1][j-1] + (ca == cb and 0 or subcost) --substituion - ) - if arg[1] and i > 1 and j > 1 and ca == chrat(stringb,j-1) and chrat(stringa,i-1) == cb then - dyntbl[i][j] = min(dyntbl[i][j], - dyntbl[i-2][j-2] + (ca == cb and 0 or arg[2])) --transposition - end - end - end - - return dyntbl[salen][sblen] -end - -fuzzel[LevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost) - return genericDistance(stringa, stringb, addcost, subcost, delcost) -end -fuzzel.ld_e = fuzzel[LevenshteinDistance_extended] - -fuzzel[LevenshteinDistance] = function(stringa,stringb) - return fuzzel.ld_e(stringa,stringb,1,1,1) -end -fuzzel.ld = fuzzel[LevenshteinDistance] - -fuzzel[LevenshteinRatio] = function(stringa,stringb) - return fuzzel.ld(stringa,stringb) / strlen(stringa) -end -fuzzel.lr = fuzzel[LevenshteinRatio] - -fuzzel[DamerauLevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost, trncost) - return genericDistance(stringa,stringb,addcost,subcost,delcost,tru,trncost) -end -fuzzel.dld_e = fuzzel[DamerauLevenshteinDistance_extended] - -fuzzel[DamerauLevenshteinDistance] = function(stringa,stringb) - return fuzzel.dld_e(stringa,stringb,1,1,1,1) -end -fuzzel.dld = fuzzel[DamerauLevenshteinDistance] - -fuzzel[DamerauLevenshteinRatio] = function(stringa,stringb) - return fuzzel.dld(stringa,stringb) / strlen(stringa) -end -fuzzel.dlr = fuzzel[DamerauLevenshteinRatio] - -fuzzel[HammingDistance] = function(stringa,stringb) - local len,dist = strlen(stringa),0 - 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 - return dist -end -fuzzel.hd = fuzzel[HammingDistance] - -fuzzel[HammingRatio] = function(stringa,stringb) - return fuzzel.hd(stringa,stringb) / strlen(stringa) -end -fuzzel.hr = fuzzel[HammingRatio] - -local function FuzzySearch(str,func,...) - local arg = {...} - - --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,sout = func(looparg[1],str),looparg[1] - for k,v in prs(looparg) do - local t = func(v,str) - if t <= tmin then - tmin,sout = t,k - end - end - return looparg[sout], tmin -end - -fuzzel[FuzzyFindDistance] = function(str,...) - return upack{FuzzySearch(str,fuzzel.dld,...)} -end -fuzzel.ffd = fuzzel[FuzzyFindDistance] - -fuzzel[FuzzyFindRatio] = function(str,...) - return upack{FuzzySearch(str,fuzzel.dlr,...)} -end - -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,slen = {},{},{},strlen(str) - for k,v in prs(looparg) do - 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) - end - tblins(usorted[dist],v) - end - - --Actually sort them into something can can be iterated with ipairs - tblsrt(sorted) - - --Then build our output table - for k,v in iprs(sorted) do - for i,j in prs(usorted[v]) do - tblins(otbl,j) - end - end - return otbl -end -fuzzel.ffr = fuzzel[FuzzyFindRatio] - -fuzzel[FuzzySortDistance] = function(str,...) - return FuzzySort(str,fuzzel.dld,fal,...) -end -fuzzel.fsd = fuzzel[FuzzySortDistance] - -fuzzel[FuzzySortRatio] = function(str,...) - 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 deleted file mode 100644 index bffc02f..0000000 --- a/fuzzel_min.lua +++ /dev/null @@ -1,2 +0,0 @@ ---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 diff --git a/src/fuzzel.lua b/src/fuzzel.lua new file mode 100644 index 0000000..5a65514 --- /dev/null +++ b/src/fuzzel.lua @@ -0,0 +1,334 @@ +--[[ + Fuzzel v1.4 - Alexander "Apickx" Pickering + Entered into the public domain June 2, 2016 + You are not required to, but consider putting a link to the source in your file's comments! + + Example: + Returns a function that will return the closest string to the string it was passed + -----------------FuzzelExample.lua------------------ + --Include the module + local fuzzel = require("fuzzel.lua") + + --A couple of options + local options = { + "Fat Cat", + "Lazy Dog", + "Brown Fox", + } + + --And use it, to see what option closest matches "Lulzy Cat" + local close,distance = fuzzel.FuzzyFindDistance("Lulzy Cat", options) + print("\"Lulzy Cat\" is close to \"" .. close .. "\", distance:" .. distance) + + --Sort the options to see the order in which they most closely match "Frag God" + print("\"Frag God\" is closest to:") + for k,v in ipairs(fuzzel.FuzzySortRatio("Frag God",options)) do + print(k .. "\t:\t" .. v) + end + -------------End FuzzelExample.lua------------------ + Outputs: + "Lulzy Cat" is close to "Fat Cat" + "Frag God" is closest to: + 1 : Fat Cat + 2 : Lazy Dog + 3 : Brown Fox + + Some easy-to-use mnemonics + fuzzel.ld_e = fuzzel.LevenshteinDistance_extended + fuzzel.ld = fuzzel.LevenshteinDistance + fuzzel.lr = fuzzel.LevensteinRatio + fuzzel.dld_e = fuzzel.DamerauLevenshteinDistance_extended + fuzzel.dld = fuzzel.DamerauLevenshteinDistance + fuzzel.dlr = fuzzel.DamerauLevenshteinRatio + fuzzel.hd = fuzzel.HammingDistance + fuzzel.hr = fuzzel.HammingRatio + fuzzel.ffd = fuzzel.FuzzyFindDistance + fuzzel.ffr = fuzzel.FuzzyFindRatio + fuzzel.fsd = fuzzel.FuzzySortDistance + fuzzel.fsr = fuzzel.FuzzySortRatio + fuzzel.fad = fuzzel.FuzzyAutocompleteDistance + fuzzel.far = fuzzel.FuzzyAutocompleteRatio + +]]--You probably don't want to touch anything past this point + +--- A collection of methods for finding edit distance between two strings + + +--Assign locals to these to the minifier can compress the file better +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, 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 = {...} + + --Length of each string + local salen, sblen = strlen(stringa), strlen(stringb) + + --Create a 0 matrix the size of len(a) x len(b) + local dyntbl = {} + for i = 0,salen do + dyntbl[i] = {} + for j = 0,sblen do + dyntbl[i][j] = 0 + end + end + + --Initalize the matrix + for i = 1,salen do + dyntbl[i][0] = i + end + for j = 1,sblen do + dyntbl[0][j] = j + end + + --And build up the matrix based on costs-so-far + for j = 1,sblen do + for i = 1,salen do + local ca,cb = chrat(stringa,i),chrat(stringb,j) + dyntbl[i][j] = min( + dyntbl[i-1][j] + delcost, --deletion + dyntbl[i][j-1] + addcost, --insertion + dyntbl[i-1][j-1] + (ca == cb and 0 or subcost) --substituion + ) + if arg[1] and i > 1 and j > 1 and ca == chrat(stringb,j-1) and chrat(stringa,i-1) == cb then + dyntbl[i][j] = min(dyntbl[i][j], + dyntbl[i-2][j-2] + (ca == cb and 0 or arg[2])) --transposition + end + end + end + + return dyntbl[salen][sblen] +end + +--- The current version (1.4). +fuzzel.VERSION = "1.4" + +--- Finds edit distance between two strings with custom costs. +-- The levenshtein distance is the minimum number of additions, deletions, and substitutions that are needed to turn one string into another. This methods allows custom costs for addition, deletion, and substitution. +-- @function LevenshteinDistance_extended +-- @string str1 the first string +-- @string str2 the second string +-- @number addcost the custom cost to add one character +-- @number subcost the custom cost to subtitute one character for another +-- @number delcost the custom cost to delete one character +-- @return the distance from the first string to the second (which will always be the same as the distance from the second string to the first) +fuzzel[LevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost) + return genericDistance(stringa, stringb, addcost, subcost, delcost) +end +fuzzel.ld_e = fuzzel[LevenshteinDistance_extended] + +--- Finds simple Levenshtein distance. +-- The levenshtein distance is the minimum number of additions, deletions, and substitutions that are needed to turn one string into another. +-- @function LevenshteinDistance +-- @string str1 the first string +-- @string str2 the second string +-- @return the distance between the two input strings +fuzzel[LevenshteinDistance] = function(stringa,stringb) + return fuzzel.ld_e(stringa,stringb,1,1,1) +end +fuzzel.ld = fuzzel[LevenshteinDistance] + +--- Finds edit ratio between two strings +-- @function LevenshteinRatio +-- @string str1 the first string, and the string to use for the ratio +-- @string str2 the second string +-- @return the distance between the two strings divided by the length of the first string +fuzzel[LevenshteinRatio] = function(stringa,stringb) + return fuzzel.ld(stringa,stringb) / strlen(stringa) +end +fuzzel.lr = fuzzel[LevenshteinRatio] + +--- Finds edit distance between two strings, with custom values. +-- The minimum number of additions, deletions, substitutions, or transpositions to turn str1 into str2 with the given weights +-- @function DamerauLevenshteinDistance_extended +-- @string str1 the first string +-- @string str2 the second string +-- @number addcost the cost of insterting a character +-- @number subcost the cost of substituteing one character for another +-- @number delcost the cost of removeing a character +-- @number trncost the cost of transposeing two adjacent characters. +-- @return the edit distance between the two strings +fuzzel[DamerauLevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost, trncost) + return genericDistance(stringa,stringb,addcost,subcost,delcost,tru,trncost) +end +fuzzel.dld_e = fuzzel[DamerauLevenshteinDistance_extended] + +--- Finds simple Damerau-Levenshtein distance. +-- @function DamerauLevenshteinDistance +-- @string str1 the fist string +-- @string str2 the second string +-- @return the minimum number of additions, deletions, substitutions, or transpositions to turn str1 into str2 +fuzzel[DamerauLevenshteinDistance] = function(stringa,stringb) + return fuzzel.dld_e(stringa,stringb,1,1,1,1) +end +fuzzel.dld = fuzzel[DamerauLevenshteinDistance] + +--- Finds edit ratio between two strings +-- @function DamerauLevenshteinRatio +-- @string str1 the fist string, and number to use for ratio +-- @string str2 the second string +-- @return the Damerau-Levenshtein distance divided by the length of the first string. +fuzzel[DamerauLevenshteinRatio] = function(stringa,stringb) + return fuzzel.dld(stringa,stringb) / strlen(stringa) +end +fuzzel.dlr = fuzzel[DamerauLevenshteinRatio] + +--- Finds the nubmer of subtitutions needed to turn one string into another. +-- Hamming distance can only be calculated on two strings of equal length. +-- @function HammingDistance +-- @string str1 the first string +-- @string str2 the second string +-- @return the edit distance between str1 and str2 +-- @useage fuzzel.HammingDistance("one","two") +-- @useage fuzzel.HammingDistance("two","three") --Will throw an error, since "two" is 3 characters long while "three" is 5 characters long! +fuzzel[HammingDistance] = function(stringa,stringb) + local len,dist = strlen(stringa),0 + 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 + return dist +end +fuzzel.hd = fuzzel[HammingDistance] + +--- Calculates the Hamming distance between two strings, divided by the length of the first string. +-- @function HammingRatio +-- @string str1 the first string, and string to use for the ratio +-- @string str2 the second string +-- @return the edit distance between the two strings +-- @useage fuzzel.HammingRatio("four","five") +-- @useage fuzzel.HammingRatio("seven","ten") -- Will throw an error, since "seven" is 5 characters long while "ten" is 3 characters long +fuzzel[HammingRatio] = function(stringa,stringb) + return fuzzel.hd(stringa,stringb) / strlen(stringa) +end +fuzzel.hr = fuzzel[HammingRatio] + +local function FuzzySearch(str,func,...) + local arg = {...} + + --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,sout = func(looparg[1],str),looparg[1] + for k,v in prs(looparg) do + local t = func(v,str) + if t <= tmin then + tmin,sout = t,k + end + end + return looparg[sout], tmin +end + +--- Finds the closest argument to the first argument. +-- Finds the closest argument to the first argument useing Damerau-Levenshtein distance +-- @function FuzzyFindDistance +-- @string str the string to compare to +-- @param ... A 1-indexed array of strings, or a list of strings to campare str against +-- @usage fuzzel.FuzzyFindDistance("tap","tape","strap","tab") +-- @usage fuzzel.FuzzyFindDistance("tap",{"tape","strap","tab"}) +fuzzel[FuzzyFindDistance] = function(str,...) + return upack{FuzzySearch(str,fuzzel.dld,...)} +end +fuzzel.ffd = fuzzel[FuzzyFindDistance] + +--- Finds the closest argument to the first argument. +-- Finds the closest argument to the first argument useing Damerau-Levenshtein ratio +-- @function FuzzyFindRatio +-- @string str the string to compare to +-- @param ... A 1-indexed array of strings, or a list of strings to campare str against +-- @useage fuzzel.FuzzyFindRatio("light",{"lit","lot","lightbulb"}) +-- @useage fuzzel.FuzzyFindRatio("light","lit","lot","lightbulb") +fuzzel[FuzzyFindRatio] = function(str,...) + return upack{FuzzySearch(str,fuzzel.dlr,...)} +end +fuzzel.ffr = fuzzel[FuzzyFindRatio] + +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,slen = {},{},{},strlen(str) + for k,v in prs(looparg) do + 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) + end + tblins(usorted[dist],v) + end + + --Actually sort them into something can can be iterated with ipairs + tblsrt(sorted) + + --Then build our output table + for k,v in iprs(sorted) do + for i,j in prs(usorted[v]) do + tblins(otbl,j) + end + end + return otbl +end + +--- Sorts inputed strings by distance. +-- Finds the Damerau-Levenshtein distance of each string to the first argument, and sorts them into a table accordingly +-- @function FuzzySortDistance +-- @string str the string to compare each result to +-- @param ... either a 1-indexed table, or a list of strings to sort +-- @return a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +-- @usage fuzzel.FuzzySortDistance("tub",{"toothpaste","stub","tube"}) +-- @usage fuzzel.FuzzySortDistance("tub","toothpaste","stub","tube") +fuzzel[FuzzySortDistance] = function(str,...) + return FuzzySort(str,fuzzel.dld,fal,...) +end +fuzzel.fsd = fuzzel[FuzzySortDistance] + +--- Sorts inputed strings by ratio. +-- Finds the Damerau-Levenshtein ratio of each string to the first argument, and sorts them into a table accordingly +-- @function FuzzySortRatio +-- @string str the string to compare each result to +-- @param ... either a 1-indexed table, or a list of strings to sort +-- @return a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +-- @usage fuzzel.FuzzySortRatio("can",{"candle","candie","canister"}) +-- @usage fuzzel.FuzzySortRatio("can","candle","candie","canister") +fuzzel[FuzzySortRatio] = function(str,...) + return FuzzySort(str,fuzzel.dlr,fal,...) +end +fuzzel.fsr = fuzzel[FuzzySortRatio] + +--- Sorts truncated versions of inputed strings by distance. +-- truncates each input string, and finds the Damerau-Levenshtein distance of each string to the first argument, and sorts them into a table accordingly. Useful for auto-complete functions +-- @function FuzzyAutocompleteDistance +-- @string str the string to compare each result to +-- @param ... either a 1-indexed table, or a list of strings to sort +-- @return a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +-- @usage fuzzel.FuzzyAutocompleteDistance("brow",{"brown","brownie","high-brow"}) +-- @usage fuzzel.FuzzyAutocompleteDistance("brow","brown","brownie","high-brow") +fuzzel[FuzzyAutocompleteDistance] = function(str, ...) + return FuzzySort(str,fuzzel.dld,tru,...) +end +fuzzel.fad = fuzzel[FuzzyAutocompleteDistance] + +--- Sorts truncated versions of inputed strings by ratio. +-- truncates each input string, and finds the Damerau-Levenshtein ratio of each string to the first argument, and sorts them into a table accordingly. Useful for auto-complete functions +-- @function FuzzyAutocompleteRatio +-- @string str the string to compare each result to +-- @param ... either a 1-indexed table, or a list of strings to sort +-- @return a 1-indexed table of the input strings, in the order of closest-to str to farthest-from str +-- @usage fuzzel.FuzzyAutocompleteRatio("egg",{"eggman","excelent","excaliber"}) +-- @usage fuzzel.FuzzyAutocompleteRatio("egg","eggman","excelent","excaliber") +fuzzel[FuzzyAutocompleteRatio] = function(str,...) + return FuzzySort(str,fuzzel.dlr,tru,...) +end +fuzzel.far = fuzzel[FuzzyAutocompleteRatio] + +return fuzzel -- cgit v1.2.3-70-g09d2