Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
1

Search a table for a close enough match ?

Asked by
Voltoxus 248 Moderation Voter
10 years ago

How would I search a table for a close enough match to a keyword for example,

The keyword would be "Volt" and

Table = {"Guest 12930", "Voltoxus", "Player", "Noob"}

How would I search that table and return the word that it most likely resembles please help.

3 answers

Log in to vote
1
Answered by
BlueTaslem 18071 Moderation Voter Administrator Community Moderator Super Administrator
10 years ago

You haven't really defined what "close enough" means. Here's a few possible definitions


The first two approaches have more obvious drawbacks.

  • Contains

    • Doesn't allow any way to break ties. In principle, either shortest or longest could break ties -- longest allows you to save the most time on average, and shortest means you're more likely to type out most of a name to disambiguate (and in that way is more intuitive)
  • Length of LCS

    • Longer strings to match against will just, by virtue of having more characters, have longer LCSs
    • Doesn't match human perception of similarity in some cases since many letters may be skipped in between

I think Levenshtein distance is the most promising.

It has a simple recursive definition (taken from Rosetta Code)

function Levenshtein_Distance( s1, s2 )
    if s1:len() == 0 then return s2:len() end
    if s2:len() == 0 then return s1:len() end

    if s1:sub( -1, -1 ) == s2:sub( -1, -1 ) then
        return Levenshtein_Distance( s1:sub( 1, -2 ), s2:sub( 1, -2 ) )
    end

    local a = Levenshtein_Distance( s1:sub( 1, -2 ), s2:sub( 1, -2 ) )
    local b = Levenshtein_Distance( s1:sub( 1, -1 ), s2:sub( 1, -2 ) )
    local c = Levenshtein_Distance( s1:sub( 1, -2 ), s2:sub( 1, -1 ) )

    if a > b then return b + 1 end
    if a > c then return c + 1 end
    return a + 1
end

Unfortunately this is incredibly inefficient because of memoization reasons.

A "dynamic programming" approach could solve this, or we can apply memoization (save previously computed values).

local LevenshteinMemoize = {};
function Levenshtein_Distance( s1, s2 )
    if #s1 < #s2 then
        return Levenshtein_Distance(s2, s1)
    end

    LevenshteinMemoize[s1] = LevenshteinMemoize[s1] or {}
    if LevenshteinMemoize[s1][s2] then
        return LevenshteinMemoize[s1][s2]
    end

    if s1:len() == 0 then return s2:len() end
    if s2:len() == 0 then return s1:len() end

    if s1:sub( -1, -1 ) == s2:sub( -1, -1 ) then
        return Levenshtein_Distance( s1:sub( 1, -2 ), s2:sub( 1, -2 ) )
    end

    local a = Levenshtein_Distance( s1:sub( 1, -2 ), s2:sub( 1, -2 ) )
    local b = Levenshtein_Distance( s1:sub( 1, -1 ), s2:sub( 1, -2 ) )
    local c = Levenshtein_Distance( s1:sub( 1, -2 ), s2:sub( 1, -1 ) )

    if a > b then
        R = b + 1
    elseif a > c then
        R = c + 1
    else
        R = a + 1
    end
    LevenshteinMemoize[s1][s2] = R
    return R
end

Now we can find the string most similar by the smallest Levenshtein_Distance:

best = 1
keyword = "volt"
keyword = keyword:lower()
for i = 2, #list do
    if Levenshtein_Distance(list[i]:lower(), keyword) < 
    Levenshtein_Distance(list[best]:lower(), keyword) then
        best = i
    end
end

-- best match is list[best]
0
So best would be the number that matches in the table ? list[1] Voltoxus 248 — 10y
0
I think you overdid it here, Blue. xD Tkdriverx 514 — 10y
Ad
Log in to vote
1
Answered by
Tkdriverx 514 Moderation Voter
10 years ago

Function straight out of the VoteKicker script provided by Roblox.

local players = {"Guest 12930", "Voltoxus", "Player", "Noob"}

function matchPlayer(str)
    -- find all players that start with the str
    -- if there is only one, match it
    -- 0 or 2+, don't match it
    local result = nil

    for i = 1,#players do
        if (string.find(string.lower(players[i]), str) == 1) then
            if (result ~= nil) then return nil end
            result = players[i]
        end
    end

    return result
end

To call the function, you do

matchPlayer(string)

This is a general example of what you may want to use:

-- Let's say this variable is an inputed value that is being searched for:
local search = "volT" -- Also, case doesn't matter.
local result = matchPlayer(search)

print(result) -- If there is a match, this should return the name.
print(result ~= nil) -- This will print true if it exists, and false if it doesn't.
0
Returns nil every time Voltoxus 248 — 10y
0
Well you have to set the function at the beginning of the function. Tkdriverx 514 — 10y
Log in to vote
0
Answered by 10 years ago

You could try (just for example an admin check)

local admins = {"Guest 12930", "Voltoxus", "Player", "Noob"}

getPermission = function(name)
    local admin = false
    name = string.lower(name)

    for _, v in pairs(admins) do
        v = string.lower(v)
        if string.sub(v, 1, #name) == name then
            --If the first part of the admin name is equal to the name given then it returns that admin is true
            admin = true
        end
    end
    return admin
    --If there is someone that matches it then it will return they are an admin
end

--Blah blah blah
if getPermission(name) then
    --blah
end

Answer this question