Find the existence of a word in a large dictionary

Asked 2009-08-26T02:46:22.367

Suppose I'm given a large dictionary in flat file with 200 million words and my function needs to check the existence of any given word in the dictionary, what's the fastest way to do it? You can't store the dictionary in the memory because you only have 1GB of memory. You can store it in the database, however querying it would still be very very slow without any optimization. You can't index the full words because you don't have enough resources.

Edit: in addition to the file optimization approach mentioned below, are there any database optimization? I'm thinking of creating partial indices, say for every 2 letters in the word up to a limit, I create an index. Would this speed up the db query?

dictionary

Edit Report

2 Answers

Classically word lookup problems can be efficiently solved using a Trie. Unfortunately, as you mentioned, you can't store all of the data you need in memory, but that shouldn't stop you from using a Trie to reduce the search space. Suppose instead of storing the entire set of words in the Trie you store only the initial segment, and your end nodes point to small collections of data that are easily (and quickly) searched in the database.

answered 2009-08-26T03:07:13.707

If you have no index just use a stream.

Sometimes the most simple solution is the best.

   public Int32 IndexOf(FileStream file, Byte[] ascii_bytes, Int32 start_index)
   {
       Int32 index = -1;
       {
           Int32 current = 0;
           Int64 original_index = 0;
           Boolean found = true;

           file.Position = start_index;
           current = file.ReadByte();
           while (current >= 0)
           {
               if ((Byte)current == ascii_bytes[0])
               {
                   found = true;
                   original_index = file.Position - 1;
                   for (Int32 i = 1; (i < ascii_bytes.Length && current > 0); i++)
                   {
                       current = file.ReadByte();
                       if ((Byte)current != ascii_bytes[i])
                       {
                           file.Position--;
                           found = false;
                           break;
                       }
                   }

                   if (found)
                   {
                       file.Position = original_index;
                       index = (Int32)original_index;
                       break;
                   }
               }
               current = file.ReadByte();
           }
       }
       return index;
   }

answered 2009-08-26T02:54:31.683

Find the existence of a word in a large dictionary

2 Answers

Your Answer