Alphabetically-sorted word lookup

Question

The goal of this code is to save a list of 250000 words with a number that indicates its frequency. The 250000 are sorted alphabetically but the frequency is unsorted. The idea is that a user must insert capitalized words, spaces or numbers after each word to lookup in the saved 250000-word list.

The max number of inputs are 1000 word+space+frequency pair per line.

The frequency domain is \$1 <= frequency <= 1000000\$. Every input must result in an output containing a list of the most relevant words \$>=\$ word-frequency entered and also ordered alphabetically in descending order.

How can I finish this code in a more efficient way?

public static void Main()
{
   {
      var dic = new Dictionary<string, int>();

      int counter = 0;

      StreamReader sr = new StreamReader("C:\\dicti.txt");

      while (true)
      {
          string line = sr.ReadLine();   // To read lines
          string[] ln;
          if (line == null) break;            // There is no more lines
          try
          {
              ln = line.Split(default(string[]), StringSplitOptions.RemoveEmptyEntries);
              string a = ln[0];
              int b = Convert.ToInt32(ln[1]);

              dic.Add(a, b);
          }
          catch (IndexOutOfRangeException) { break; }
      }

      string[] ln2;
      string am, word;
      int bm;

      do
      {
                //counter++;
                do
                {
                    word = Console.ReadLine();

                    ln2 = word.Split(default(string[]), StringSplitOptions.RemoveEmptyEntries);

                    am = ln2[0];

                    bm = Convert.ToInt32(ln2[1]);

                } while (!(am.Length >= 2 && bm >= 1 && bm <= 1000000));

                if (true)
                {
                    var aj = (dic.Where(x => x.Value >= bm)
                        .Where(x => x.Key.StartsWith(am))
                        .OrderByDescending(d => d.Value).Take(2));


                    foreach (var p in aj)
                    {
                        Console.WriteLine("{0} ", p.Key);
                    }
                }
            } while (counter < 1001);
   }
}

Answer 1

Dictionary<Y> is only efficient if you access the entries through the key. You are enumerating the dictionary with linq. This is very slow. Try to access it like this:

int count;
if (dic.TryGetValue(am, out count)) {
    // found
} else {
    // not found
}

You cannot search for keys that start with a text. If you want to do this then look for a more appropriate data structure. A binary tree inserts and looks up fast and sorting happens automatically. However, keep in mind that simple binary trees (not AVL trees) perform badly if items are added in a presorted order. A binary tree would also allow you to search for beginning of words.

---

EDIT:

I have thought things over. It would be possible to work with two collections at the same time. It is a bit complicated to handle, but should be faster.

Let me explain. We are using binary trees, because, unless dictionaries, they are ordered by the key. Let us store the information with the words as key and the frequencies as value in the first binary tree. In the second binary tree, we use the frequency as key. Because several words can have the same frequency, we use a list of words as value. With this approach, we have our information ordered by words and by frequencies at the same time.

Now let us update the frequency of a word, which is already contained in our collections. As an example, let us add 50 to the frequency of the word “TEDDY”:

1. We look up the word in collection 1. We see that the frequency of the word is 100.

2. We look up the words with frequency 100 in collection 2. We find two corresponding words, “TEDDY” and “HOUSE”.

3. We ignore “HOUSE” and remove “TEDDY” from collection 2.

4. We re-insert “TEDDY” in collection 2 with a frequency of 100 + 50 = 150. Because the frequency is used as key, it will probably be inserted at a different place in the tree structure.

5. We update the frequency in collection 1 to 150. Since the key does not change, we can just replace the value “in place”.

After these operations, both collections are still ordered by words and by frequencies respectively. Moreover, both look up operations, the remove and the insert operation were fast.

Answer 2

Here's a suggestion: there's no reason why list of words has to be stored in a simple list. If you build a tree where each node has 26 potential sub nodes, one for each letter of the alphabet, the obvious solution runs in under two seconds on my system, while your code takes about 50.

class WordsByPrefix
{
    public string Prefix;
    public WordsByPrefix[] Letters = new WordsByPrefix[26];
    public int Freq = 0;

    public void AddWord(string word, int freq)
    {
        if (word.Length == Prefix.Length)
            this.Freq = freq;
        else
        {
            var letter = word[Prefix.Length];
            if (Letters[letter - 'A'] == null)
                Letters[letter - 'A'] = new WordsByPrefix { Prefix = Prefix + letter };
            Letters[letter - 'A'].AddWord(word, freq);
        }
    }

    public void LoadWords(ICollection<WordsByPrefix> list)
    {
        if (Freq > 0)
            list.Add(this);
        foreach (var letter in Letters)
            if (letter != null)
                letter.LoadWords(list);
    }
}

root = new WordsByPrefix();
root.Prefix = String.Empty;

To load words into the tree, call root.AddWord(word, freq);. To select words from the tree, start from root, and for each letter, look up node.Letters[letter - 'A']. Call LoadWords on the result to get a list of all those combinations of letters that are valid words (have a nonzero Freq).

Note: ensure that all characters are from 'A' to 'Z' or things will break.