How to make an auto text suggestion system?

Question

If a user enters an invalid command then it returns the closest string to the user's input.

source = {"foo", "foo1"}
Suggest = function (input, source)
--do stuff
end

Thus when the user enters an undefined command "fo", for example it returns "foo". Sorry if this is poorly explained, in a hurry.

Answer 1

You can use Levenshtein or Damerau–Levenshtein distance function to find commands closest to input. Here is a C library implementing both of these functions. Here is Levenshtein distance implemented in Lua.

The following function assumes distance is the distance function of choice. It takes optional radius argument to specify maximum distance from input to suggestion(you may not want to provide any suggestion if user entered something very strange, far from any existing commands). It returns an array of suggestions.

function suggest(input, source, radius)
   local result = {}
   local min_distance = radius or math.huge

   for _, command in ipairs(source) do
      local current_distance = distance(input, command)

      if current_distance < min_distance then
         min_distance = current_distance
         result = {command}
      elseif current_distance == min_distance then
         table.insert(result, command)
      end
   end

   return result
end

Note that this search algorithm is quite inefficient. It may or may not be a problem for you depending on number of commands and rate of searches.