模糊搜索基于Levenshtein算法,该算法对两个字符串的距离进行评级.当您具有此距离值时,您可以根据分数对列表中的元素进行排序或删除.

我在lua here中找到了算法.

function levenshtein(s,t)
  local s,t = tostring(s),tostring(t)
  if type(s) == 'string' and type(t) == 'string' then
    local m,n,d = #s,#t,{}
    for i = 0,m do d[i] = { [0] = i } end
    for j = 1,n do d[0][j] = j end
    for i = 1,m do
      for j = 1,n do
        local cost = s:sub(i,i) == t:sub(j,j) and 0 or 1
        d[i][j] = math.min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost)
      end
    end
    return d[m][n]
  end
end

如网站中所述,您比较两个字符串,并根据它们的距离得分,然后根据给出的分数对要搜索的项目进行排序或删除.由于这是cpu昂贵的,我建议缓存或使用memoize函数来存储常见错误.

levenshtein('referrer','referrer') -- zero distance
  >>> 0
  levenshtein('referrer','referer') -- distance of one character
  >>> 1
  levenshtein('random','strings') -- random big distance
  >>> 6

有一个简单的版本工作在lua here我必须说lua是一个简单的语言来接收和开始编码.

local monsters = {'A Golden Dragon','Goblins','Bunny','Dragoon'}

function levenshtein(s,d[i-1][j-1]+cost)
      end
    end
    return d[m][n]
  end
end

--Fuzzy Search Returns the Best Match in a list
function fuzzySearch(list,searchText)
    local bestMatch = nil;
    local lowestscore = nil;

    for i = 1,#list do
        local score = levenshtein(list[i],searchText)
        if lowestscore == nil or score < lowestscore then
            bestMatch = list[i]
            lowestscore = score
        end 
    end

    return bestMatch
end

print ( fuzzySearch(monsters,'golen dragggon') )
print ( fuzzySearch(monsters,'A Golden Dfigon') )
print ( fuzzySearch(monsters,'A Gelden Dragon') )

print ( fuzzySearch(monsters,'Dragooon') ) --should be Dragoon
print ( fuzzySearch(monsters,'Funny') ) --should be Bunny
print ( fuzzySearch(monsters,'Gob') ) --should be Goblins

产量

A Golden Dragon
A Golden Dragon
A Golden Dragon
Dragoon
Bunny
Goblins

对于sql

您可以尝试在T-sql中执行相同的算法,如here所述.

在sqllite中有一个名为editdist3的扩展,它也使用这个算法,文档是here.