在SQLite中使用乱码搜索数据库

Question

我想知道是否可以使用给定的加扰字在数据库中搜索.

我mobs在数据库中有一个表,它包含怪物名称的名称

如果给怪物的名字是A Golden Dregon或A Golden Dfigon或A Gelden Dragon我希望它发现A Golden Dragon或与接近它从数据库匹配.通常,最大的一个或两个字母像这样被加扰.

只有SQL查询才有可能吗？或者我应该通过解析给定的怪物名称来构建查询？

我在代码方面使用LUA.

Answer 1

我已经知道这种搜索类型是模糊搜索。我主要用JS编程，并且一直使用fuse.js来解决此类问题。

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

我在这里找到了lua中的算法。

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 中工作的简单版本，我必须说 lua 是一种易于学习和开始编码的语言。

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

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

--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 中执行与此处所述相同的算法。

在 SQLlite 中有一个名为的扩展editdist3，它也使用这个算法，文档在这里。