Improve autocomplete suggestion in C#

[autocomplete]

This example improves on the example Suggest autocomplete words in C#. The previous example loads all of its words into a big array. Then, to find the words that start with a particular letter, the program uses a binary search to find the letter in the word list. The program then loops through the words in the list until it finds a word that doesn’t begin with the same letter.

When this new example starts, it loads the words that start with different letters into different lists. Then when it needs to process the words that start with a given letter, it simply loops through the appropriate list.

The following code shows how the program loads its lists of words.

// The dictionary.
private List<string>[] Words;

// Load the dictionary.
private void Form1_Load(object sender, EventArgs e)
{
    // Get the words from the dictionary file.
    string[] lines = File.ReadAllLines("Words.txt");

    // Group the words by first letter.
    Words = new List<string>[26];
    for (int i = 0; i < 26; i++)
        Words[i] = new List<string>();
    foreach (string line in lines)
    {
        if (line.Length > 1)
        {
            // Get the first letter.
            int index = (int)line.ToUpper()[0] - (int)'A';
            Words[index].Add(line);
        }
    }

    txtWord.Text = "absi";
}

The program uses the File class’s ReadAllLines method to read the words into an array. It then loops through the array.

For each word in the array (not counting single letters such as “A” and “R”), the code uses the word’s first letter to determine which list should hold the word and then adds the word to that list.

The other change to the program occurs in the FindBestMatches method. In the previous version of that method uses binary search to find the first word in the list starting with a given letter and then uses a somewhat confusing loop to examine the words that follow until it finds a word that starts with a new letter or it runs out of words.

The following code shows the new version of the loop.

// Get the word list for the word's first letter.
int index = (int)word.ToUpper()[0] - (int)'A';

// Find words that start with the same letter.
List<string> match_words = new List<string>();
List<int> match_values = new List<int>();
foreach (string test_word in Words[index])
{
    ...
}

This code subtracts the ASCII value of the letter A from the word’s first letter to get the index of the list that holds words starting with the same letter. It creates output lists for words that match and their edit distance values much as before. It then uses a simple foreach loop to examine the words that have the same first letter as the target word. The omitted code indicated by the ellipsis is the same as in the previous version.

This version is slightly faster (you can’t really tell the difference when you’re running it) but the loop in the FindBestMatches method is easier to understand.

In my next post, I’ll convert some of the searches performed by the program into LINQ. If you have time, you might want to give them a try yourself before you read that post.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, strings and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

One Response to Improve autocomplete suggestion in C#

  1. Pingback: Add LINQ to autocomplete in C# - C# HelperC# Helper

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.