Efficient string and table manipulation for an in-game dictionary

[MunkDev]

Hello, friends.

I've written code to auto-complete words in editboxes, using the global environment to scan for and break apart strings to generate a weighted dictionary. On an enUS client, the initial run generates approximately 5000 words, which is a pretty good starting point.

Now, when iterating the table of words to find potential matches, I'm using these conditions:

• Literal matches in words
• The union of characters in the current input as a length barrier
• The existence of the union of characters of the current input
• The dictionary word is not exactly equal to the input word
• The priority of suggestions is based in similarity, length difference and frequency

The downside to my current approach is:

• If the input word is misspelled, suggestion for anticipated word will be omitted
• If the input characters are in the wrong order, the first suggestion might be unexpected

Example:

• Misspell: "abhieve" -> "achieve", "achievement", "achievements" (these are omitted)
• Skewed: "abhieve" -> "behaving", "behavior", "behaviors" (these are suggested)

Also, to reduce "unnecessary" calculations, I've put a 20 index max on the generated suggestion list, meaning it will stop comparing words of the dictionary to the suggestion list after hitting the 20th index. The word will still be pushed to the list, though. Without optimizing to some degree, there will be a small FPS stutter when using extremely common combinations of characters, such as "es", "er", "et", "ae", "an", etc.

I was wondering if anyone has ideas to improve this algorithm and make it smarter.

This is the code used to generate suggestions:

function Keyboard:GetSuggestions()
    local word = self:GetCurrentWord() -- get the currently chosen word in the editbox
    wipe(suggestions) -- remove all old suggestions before proceeding
    if word then
        word = strlower(word)
        local length = word:len()
        local dictionary = self.Dictionary
        local chars, numChars = Union(word) -- returns the union of characters in a word
 
        local this, priority, valid
 
        -- Iterate through dictionary and push valid words to suggestion list
        for thisWord, thisWeight in pairs(dictionary) do
            valid = true
 
            -- skip exact matches and matches that are vastly longer than the union of input characters
            if thisWord == word or numChars * 4 < thisWord:len() then
                valid = false
            end
 
            -- check if word contains all characters to elicit a match
            for c in chars:gmatch(".") do
                if not strfind(thisWord, c) then
                    valid = false
                    break
                end
            end
 
            if valid then
                priority = 1
 
                this = {
                    word = thisWord,
                    weight = thisWeight,
                    match = strfind( thisWord, word ),
                    length = abs( length - thisWord:len() )
                }
 
                -- calculate priority in relation to already suggested words
                for index, compare in pairs(suggestions) do
 
                    -- don't calculate order beyond the 20th index, just push to list
                    if ( index >= 20 ) then
                        break
                    end
 
                    -- fix: if the best suggestion was pushed first, make sure its priority isn't nudged down
                    priority = #suggestions > 1 and index or 2
 
                    -- words with literal matches have higher priority 
                    if  ( this.match and not compare.match ) then
                        break
                    -- if both have literal match and this word is more favorable, or neither have literal match
                    elseif  ( this.match and compare.match and ( this.match <= compare.match ) ) or
                            ( not this.match and not compare.match ) then
 
                        -- if this word is shorter, or equally long but has a higher weight
                        if  ( this.length < compare.length or
                            ( this.length == compare.length and this.weight > compare.weight ) ) then
                            break
                        end
 
                    end
                end
                tinsert( suggestions, priority, this )
            end
        end
    end
    self:SetSuggestions(1)
end

This is the code used to generate the dictionary:

function Keyboard:GenerateDictionary()
   -- generates a localized game-oriented dictionary (5000+ words on enUS clients)
   -- scan the global environment for strings
   local genv = getfenv(0)
   local dictionary = {}
   for index, object in pairs(genv) do
      if type(object) == "string" then
         -- remove escape sequences, uses a table of patterns for gsub
         object = Unescape(object)
         -- scan each string for individual words
         for word in object:gmatch("[%a][%w']*[%w]+") do
            word = strlower(word)
            if not dictionary[word] then -- first occurence
               dictionary[word] = 1
            else -- weight increment
               dictionary[word] = dictionary[word] + 1
            end
         end
      end
   end
   return dictionary
end

Pastebin: dictionary dump

[Barjack]

Interesting stuff. And a novel approach with the dictionary building.

I'm not sure about the best way to find misspelt words. But I did read this article a while ago: http://www.norvig.com/spell-correct.html

It implements a very simple spell checker in Python, and at the bottom are links to other languages as well (since we're talking Lua perhaps a Javascript one would be the closest equivalent). I'm not sure how CPU-heavy it is, though... Perhaps you'd need to only check at certain intervals or reduce the algorithm's complexity if it must run more often. But maybe it's a starting point.

Let us know what you end up doing, it's an interesting problem so I'd like to know what you find out.

[kurapica.igas]

I try it a little, without optimization or deeply consideration :

dict = {"AbandonQuest","AbandonSkill","AcceptAreaSpiritHeal","AcceptBattlefieldPort","AcceptDuel","AcceptGroup","AcceptGuild","AcceptLevelGrant","AcceptQuest","AcceptResurrect","AcceptSockets","AcceptXPLoss","ActionHasRange","AddAutoQuestPopUp","AddChatWindowChannel","AddChatWindowMessages","AddFriend","AddIgnore","AddMute","AddOrDelIgnore","AddOrDelMute","AddOrRemoveFriend","AddQuestWatch","AddTrackedAchievement","AddTradeMoney" }
 
-- Init the missspell diff check based on keybord
_Keyboard = {
    {"q", "w", "e", "r", "t", "y", "u", "i", "o", "p"},
    {"a", "s", "d", "f", "g", "h", "j", "k", "l"},
    {"", "z", "x", "c", "v", "b", "n", "m" }
}
 
for i, v in ipairs(_Keyboard) do
    for j, c in ipairs(v) do
        _Keyboard[c] = {i, j}
    end
end
 
function misspellDiff(a, b)
    local ka = _Keyboard[a]
    local kb = _Keyboard[b]
 
    return math.abs(ka[1] - kb[1]) + math.abs(ka[2] - kb[2])
end
 
function calcDiff(tar, match)
    if #tar > #match then return 9999 end
 
    local diff = 0
    local chr
    local pos
    local tarChecked = {}
    local matchUsed = {}
    local minDiff = 9999
    local minPos
    local chkDiff
 
    -- Ignore the case
    tar = tar:lower()
    match = match:lower()
 
    -- Match what can be matched
    for i = 1, #tar do
        chr = tar:sub(i, i)
 
        pos = match:find(chr)
 
        while true do
            if pos then
                if matchUsed[pos] then
                    pos = match:find(chr, pos+1)
                else
                    tarChecked[i] = pos
                    matchUsed[pos] = i
                    break
                end
            else
                break
            end
        end
    end
 
    -- Check the missspell
    for i = 1, #tar do
        if not tarChecked[i] then
            chr = tar:sub(i, i)
 
            for j = 1, #match do
                if not matchUsed[j] then
                    chkDiff = misspellDiff(chr, match:sub(j, j))
 
                    if chkDiff < minDiff then
                        minDiff = chkDiff
                        minPos = j
                    end
                end
            end
 
            -- Ten times so the missspell take high diff value
            diff = diff + minDiff * 10
            tarChecked[i] = minPos
            matchUsed[minPos] = i
        end
    end
 
    -- Calc the ignored
    for i = 2, #tarChecked do
        diff = diff + math.abs(tarChecked[i] - tarChecked[i - 1]) - 1
    end
 
    -- Calc the order diff
    for i = 1, #tarChecked do
        for j = i + 1, #tarChecked do
            if tarChecked[j] < tarChecked[i] then
                diff = diff + 1
            end
        end
    end
 
    return diff
end
 
-- Main
tar = [[AsTrdecht]]
 
local result = {}
local minDiff = 9999
local minMatch
 
for _, match in ipairs(dict) do
    local diff = calcDiff(tar, match)
 
    print(match, diff)
 
    if diff < minDiff then
        minDiff = diff
        minMatch = match
    end
end
 
print("---------Result---------")
print(tar, "->", minMatch)

Result is

---------Result--------- AsTrdecht -> AddTrackedAchievement

First find all matched chars, then check the misspell character, diff them with their distance on the keyboard(the diff has to be multiplied compared to the wrong orders).

Then calc the ignored chars like 'nd' for 'need', 'ee' is ignored. At the last, calc the diff caused by wrong orders.

Then we can get the most expected words with the least diff value.

The code is not well designed, may it can provide a little help for you.