Find the existence of a word in a large dictionary

Question

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?

Answer 1

Use The Boyer–Moore string search algorithm?

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%5Fstring%5Fsearch%5Falgorithm

Answer 2

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

Answer 3

Binary search

Assuming the dictionary has the words in alphabetical order, I would attempt a modified binary search. Divide and conquer the file by jumping to a midpoint location in the file and seeing what word is there. If guessed to high, split the lower in half and try again until there's no file location to attempt or the word is found.

(As outis mentioned in a comment, after jumping to a file location, you'll need to scan backwards and forwards to find the boundaries of the word you jumped to.)

You might be able to optimize this by guessing a location chunk right off the bat based on the first letter of the word. For example, if the word begins with "c" start your search around the 3/26th section of the file. Though, in reality, I think this early guess will only make a negligible difference overall.

Other optimizations could include keeping a small subset of an index. For example, keep an index of the first word that starts with each letter of the alphabet, or keep an index of each word that starts with each possible two letter combination. This would allow you to immediately narrow your search area.

O(log n)

Answer 4

This is a classic use case for a Bloom filter. A Bloom filter is a probabilistic data structure which is optimized for membership tests ("is X a member of this collection?"), and provides O(1) lookup. In exchange, you introduce an arbitrarily small probability of a false positive -- that is, the filter will say a particular word is present, but it is actually not there. The more memory you use, the smaller you can make this probability. However, the probability of false negatives is zero: the filter will never say that a word is absent if it is actually present.

In your specific case, with 8 billion bits (1 GB) to work with, you can get a false positive rate a little better than 1 in every 1,000,000,000 trials. That's an extremely low false positive rate. If you looked up 200 million random strings, the probability that you'd never hit a single false positive is about 82%.

This does not require the dictionary to be sorted, is highly space-efficient, and does not need a database or other ancillary storage structure. Overall, it's probably a good choice for your needs.

Answer 5

Assumptions:

1. You're going to search for a word many times in the lifetime of a process (as opposed to starting a process each time you look for a word).
2. The file is sorted.

You could partially index the data, taking up most of the available memory: store words and their starting position in the file using either a B-tree or a sorted array (latter is more space efficient, but requires a single continuous block; also, b-tree requires you store the end position of a chunk while array does not). Leave enough memory space to load a single chunk of words from the file. Search the index (tree traversal or binary search) for the chunk that would contain the word. Once you've found the specific chunk from the partial index, load the corresponding chunk from the file into memory and perform a binary search on it.

If you need additional memory, you can toss some elements from the index. With the array, you can reduce the index to n elements using the following pseudo-C pseudocode:

struct chunk {
    string word;
    int start;
};
chunk index[];
d = index.length / n;
for (i=0;i<n; ++i) {
    index[i] = index[i*d];
}
realloc(index, sizeof(chunk) * n);

As the end of chunk i is index[i+1].start, the algorithm is dead simple for an array implementation. For B-tree based indices, you can easily merge leaves with their parents.

Answer 6

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.

Answer 7

If some words are consulted with much higher frequency than others then it may make sense to have an in memory LRU cache and a database behind it.