string - Lua - 如何找到具有 1 或 2 个字符差异的子字符串

Question

说我有一个字符串

local a = "Hello universe"

我找到子字符串“宇宙”

a:find("universe")

现在，假设字符串是

local a = "un#verse"

要搜索的字符串是universe；但子字符串相差一个字符。所以显然 Lua 忽略了它。

即使单个字符存在差异，如何使函数找到字符串？

Answer 1

如果您知道该字符的位置，请使用.该字符代替：a:find("un.verse")

但是，看起来您正在寻找模糊字符串搜索。它超出了 Luastring库的范围。您可能想从这篇文章开始：http: //ntz-develop.blogspot.com/2011/03/fuzzy-string-search.html

至于 Lua 模糊搜索实现——我没有使用过，但是搜索“lua 模糊搜索”会给出一些结果。有些是基于这篇论文：http ://web.archive.org/web/20070518080535/http://www.heise.de/ct/english/97/04/386/

试试https://github.com/ajsher/luafuzzy。

Answer 2

听起来您想要类似TRE的东西：

TRE 是一个轻量级、健壮且高效的 POSIX 兼容正则表达式匹配库，具有一些令人兴奋的特性，例如近似（模糊）匹配。

近似模式匹配允许匹配是近似的，即允许匹配在某种接近度度量下接近搜索到的模式。TRE 使用编辑距离度量（也称为 Levenshtein 距离），可以在搜索文本中插入、删除或替换字符以获得精确匹配。每次插入、删除或替换都会增加匹配的距离或成本。TRE 可以报告成本低于某个给定阈值的匹配。TRE 也可用于搜索成本最低的匹配项。

它的 Lua 绑定可作为lrexlib的一部分使用。

Answer 3

一个简单的滚动你自己的方法（基于模式保持相同长度的假设）：

function hammingdistance(a,b)
    local ta={a:byte(1,-1)}
    local tb={b:byte(1,-1)}
    local res = 0
    for k=1,#a do
        if ta[k]~=tb[k] then
            res=res+1
        end
    end
    print(a,b,res) -- debugging/demonstration print
    return res
end

function fuz(s,pat)
    local best_match=10000
    local best_location
    for k=1,#s-#pat+1 do
        local cur_diff=hammingdistance(s:sub(k,k+#pat-1),pat)
        if  cur_diff < best_match then
            best_location = k
            best_match = cur_diff
        end
    end
    local start,ending = math.max(1,best_location),math.min(best_location+#pat-1,#s)
    return start,ending,s:sub(start,ending)
end

s=[[Hello, Universe! UnIvErSe]]
print(fuz(s,'universe'))

免责声明：不推荐，只是为了好玩：

如果你想要一个更好的语法（并且你不介意弄乱标准类型的元表），你可以使用这个：

getmetatable('').__sub=hammingdistance
a='Hello'
b='hello'
print(a-b)

但请注意，a-b不等于b-a这种方式。

Answer 4

如果您真的在寻找单个字符差异并且不关心性能，那么这是一个应该有效的简单方法：

local a = "Hello un#verse"

local myfind = function(s,p)  
  local withdot = function(n)
    return p:sub(1,n-1) .. '.' .. p:sub(n+1)
  end
  local a,b
  for i=1,#s do
    a,b = s:find(withdot(i))
    if a then return a,b end
  end
end

print(myfind(a,"universe"))