# Alphabetically-sorted word lookup

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;

while (true)
{
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]);

}
catch (IndexOutOfRangeException) { break; }
}

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

do
{
//counter++;
do
{

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);
}
}

• What is your question? – ruakh Jan 7 '12 at 22:19
• How can I finish this code in a more efficient way? – Mario Mindell Jan 7 '12 at 22:21
• WORD FREQUENCY LIST LOOKUP ========================== I.e: Input: SAC 500 TED 1000 Output: SACK SACRED SACRIFICED TEDDY TEDIOUS How can I finish this code in a more efficient way? – Mario Mindell Jan 7 '12 at 22:24
• while(true) is not my style, but I understand it's purpose, but if(true) ?? – jb. Jan 7 '12 at 22:34
• Ok it is doing nothing if(true) there, it was there because I have been editing this code a lot and I forget to delete it now I have the free lambda expression in which I think something could be improve but I haven´t figured out yet 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); } – Mario Mindell Jan 7 '12 at 22:40

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 {
}


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.

• Yes, the problem I got trying to implement binary tree is that I couldn´t find a way to insert the word relating to the value. In such a way that when the input process has finished the lookups are faster. – Mario Mindell Jan 7 '12 at 23:13
• You could insert items of KeyValuePair<string, int> into your tree. – Olivier Jacot-Descombes Jan 7 '12 at 23:18
• Yes, but how then it will be sorted alphabetically and numerically from highest value. When I tryied to order by value it just order it and I lost the alphabetical order configuration. – Mario Mindell Jan 7 '12 at 23:21
• You cannot have it sorted in both ways at the same time. Keep the alphabetical order and create a sorted copy when you need it. Possibly with a linq query. It is not very fast, but at least inserting and searching words is fast. Until now, you used dic in a very slow way. – Olivier Jacot-Descombes Jan 7 '12 at 23:39
• I added a new solution to my answer, which operates with two collections and should be fast for all the requested operations. – Olivier Jacot-Descombes Jan 8 '12 at 14:49

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 };
}
}

{
if (Freq > 0)
foreach (var letter in Letters)
if (letter != null)
}
}

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.

• I don´t understand how the automatic 1000 queries will be managed by the 26 array A-Z. I don´t have to count the words because each input is accompained with its frequency already. – Mario Mindell Jan 8 '12 at 0:29
• Yes, I got that. In your second loop, when you're reading from Console.In, look up each word. For example, if the input is SAC 500, look up root.Letters['S'-'A'].Letters['A'-'A'].Letters['C'-'A'], call LoadWords, and filter the results based on Freq. – hvd Jan 8 '12 at 10:07
• @MarioMindell you may want to look up the trie data structure for more information related to this answer. – Dan Lyons Mar 6 '14 at 19:40