Predicting words based on swiping a keyboard

Question

I thought this question was particularly interesting DailyProgrammer 284: Wandering Fingers so thought I'd have a pop at it myself. See the other question for the nitty gritty but the brief problem statement is:

You'll be given a string of characters representing the letters the user has dragged their finger over.

For example, if the user wants "rest", the string of input characters might be "resdft" or "resert".

Input

Given the following input strings, find all possible output words 5 characters or longer.

1. qwertyuytresdftyuioknn
2. gijakjthoijerjidsdfnokg

Output

Your program should find all possible words (5+ characters) that can be derived from the strings supplied.

Use http://norvig.com/ngrams/enable1.txt as your search dictionary.

The order of the output words doesn't matter.

1. queen question
2. gaeing garring gathering gating geeing gieing going goring

I've made the assumption that this is the English alphabet (i.e. [a-z]) which is pretty normal for a qwerty keyboard.

I created a simple lookup class:

public class AutocompleteCache
{
    private readonly IList<string>[] cache = new IList<string>[26*26]; 

    public AutocompleteCache(IEnumerable<string> wordList)
    {
        if (wordList == null)
        {
            throw new ArgumentNullException(nameof(wordList));
        }
        foreach (var word in wordList.Where(w => w.Length >= 5))
        {
            var index = CalculateIndex(word);
            var cachedWords = cache[index];
            if (cachedWords == null)
            {
                cache[index] = new List<string>();
            }
            cache[index].Add(word);
        }
    }

    private static int CalculateIndex(string word)
    {
        Debug.Assert(!string.IsNullOrEmpty(word));
        return (word[0] - 97)*26 + (word[word.Length - 1] - 97);
    }

    public IEnumerable<string> SuggestWords(string input)
    {
        if (string.IsNullOrEmpty(input))
        {
            return Enumerable.Empty<string>();
        }
        var candidates = (cache[CalculateIndex(input)] ?? Enumerable.Empty<string>());
        return candidates.Where(candidate => CheckWordIsValidForInput(candidate, input));
    }

    private bool CheckWordIsValidForInput(string word, string input)
    {
        int currentPosition = 0;
        foreach (var c in word)
        {
            currentPosition = input.IndexOf(c, currentPosition);
            if (currentPosition == -1)
            {
                return false;
            }
        }
        return true;
    }
}

The responsibility of this class is to take a dictionary of words and sort it into an array of lists of words. The index of the array is determined by a simple calculation of the first and last letters of the word (CalculateIndex). Which gives us an O(1) lookup for the list of candidate words. This is the same complexity as using a dictionary would have but has smaller constant terms than using the dictionary. The overall algorithm is O(n*m) with O(n) startup cost where n is the number of words and m is the length of the input string. The memory requirement is O(k^2) where k is the alphabet length (hard coded to 26 here).

I benchmarked this against the OP's solution and Jonbot's dictionary and found that for input 1 over 10000 iterations it's approximately twice as fast as Jobbot's and about 200 times faster than OPs solution. For words with a larger list of candidates, i.e. more common first and last letters, it ends up being only very slightly faster ~5% that the dictionary approach but still an order of magnitude faster than the OP.

Usage of the code:

 var words = File.ReadAllLines(@"C:\some\path\to\dictionary.txt");
 var autoCompleteCache = new AutocompleteCache(words);
 var results = autoCompleteCache.SuggestWords("quen"); 
 Console.WriteLine(string.Join(", ", results)); // queen

Looking for any and all comments.

Answer 1

To me it looks fine. Just some minor adjustments:

I think it would look even nicer if you defined constants for the magic numbers.

 const int AlphabetLength = 26;
 const int MinWordLength = 5;

In place of 97 I'd put simply an 'a'.

---

Instead of

currentPosition == -1

I suggest

currentPosition < 0

The -1 looks like a magic number. I sometimes use a constant for it that I name IndexOutOfRange.

---

You use var everywhere but here :-)

int currentPosition = 0;

---

It might also be a good idea to move the code from the constructor into a new method like AddWords or AddWord so you can extend the dictionary later if necessary. Usually those dictionaries can learn new words.

Answer 2

Below please find some comments and suggestions inline:

  public class AutocompleteCache
  {
    private readonly string[][] cache; // Why not a jagged array as it is a one time creation?
    private readonly int alphabetSize;

    // sizeOfAlphabet makes it usefull for other languages than english
    public AutocompleteCache(IEnumerable<string> wordList, int sizeOfAlphabet = 26)
    {
      if (wordList == null)
      {
        throw new ArgumentNullException(nameof(wordList));
      }

      alphabetSize = sizeOfAlphabet;

      //cache = new List<string>[alphabetSize * alphabetSize];
      cache = new string[alphabetSize * alphabetSize][];

      //foreach (var word in wordList.Where(w => w.Length >= 5))
      //{
      //  var index = CalculateKey(word);
      //  var cachedWords = cache[index];
      //  if (cachedWords == null)
      //  {
      //    cache[index] = new List<string>();
      //  }
      //  cache[index].Add(word);
      //}

      // You could use linq here:
      var groups = wordList.GroupBy(w => CalculateKey(w));
      foreach (var group in groups)
      {
        cache[group.Key] = group.ToArray();
      }
    }

    // Just for test
    public void PrintCache()
    {
      var min = cache.Where(arr => arr != null).Min(arr => arr.Length);
      var max = cache.Where(arr => arr != null).Max(arr => arr.Length);
      var avg = cache.Where(arr => arr != null).Average(arr => arr.Length);

      Console.WriteLine($"Min: {min} -> Max: {max} -> Average: {avg}");
    }

    // Why static if private?
    private /* static */ int CalculateKey(string word)
    {
      return (word[0] - 97) * alphabetSize + (word[word.Length - 1] - 97);
    }

    public IEnumerable<string> SuggestWords(string input)
    {
      if (string.IsNullOrEmpty(input))
        return Enumerable.Empty<string>();

      var key = CalculateKey(input);

      // You should check for valid key...
      if (key < 0 || key >= cache.Length)
        return Enumerable.Empty<string>();

      // ... because an invalid key will cause an exception here
      //var candidates = (cache[CalculateKey(input)] ?? Enumerable.Empty<string>());
      //return candidates.Where(candidate => IsCandidateValid(candidate, input));

      // You know the key is in range here.
      return cache[key]?.Where(candidate => IsCandidateValid(candidate, input)) ?? Enumerable.Empty<string>();
    }

    private bool IsCandidateValid(string candidate, string input)
    {
      int currentPosition = 0;
      foreach (var c in candidate)
      {
        currentPosition = input.IndexOf(c, currentPosition);
        if (currentPosition == -1)
        {
          return false;
        }
      }
      return true;
    }
  }