12

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?

6
  • 1
    Are the words in the flat file dictionary in alphabetical order? Aug 26, 2009 at 2:49
  • Will a database not let you define an index if the index is too large to fit in RAM?
    – ChrisW
    Aug 26, 2009 at 3:06
  • 2
    This seems like a very contrived question given a) No language I know of has anywhere near 200M words; and b) Why impose the limitation of a sub-optimal data structure?
    – JohnFx
    Aug 26, 2009 at 3:13
  • 2
    Sounds more like a rainbow table than a natural language.
    – Eric J.
    Aug 26, 2009 at 3:29
  • 1
    no, it's a real world problem. hw problem would be more well defined.
    – user157195
    Aug 26, 2009 at 3:51

8 Answers 8

21

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)

15
  • 3
    +1, but missing one thing: an arbitrary file position will most likely be in the middle of a word. Easy to fix by scanning forwards (or backwards) until a word boundary is found.
    – outis
    Aug 26, 2009 at 3:10
  • 1
    @wo_shi_ni_ba_ba: It depends on the filesystem API, but it should be a single function or method call. For PHP, there's fseek. In Java, you have SeekableByteChannel.position(long).
    – outis
    Aug 26, 2009 at 3:34
  • 1
    @Ryan: you can extend the position-guessing optimization. Let dict be the dictionary and word be the word being searched for. At a given iteration, suppose the first difference between the words at the lower l and upper u bounds is at position i. Then m = abs(word[i]-dict[l][i])/abs(dict[u][i]-dict[l][i]) + l is the guessed midpoint. Basically, you assume an even distribution. Still O(log(N)), but timing should involve a much smaller constant factor, giving real-world speedup.
    – outis
    Aug 26, 2009 at 3:46
  • 2
    By the way, storing the data on a flash drive could be faster than storing it on even a fairly fast hard disk. That's the basic idea behind ReadyBoost... actual IO transfers are slower on a flash drive, but "seek" time is MUCH faster. If your hard disk has a large amount of cache compared to your data set, you are probably better off with the hard disk.
    – Eric J.
    Aug 26, 2009 at 4:02
  • 1
    @wo_shi_ni_ba_ba Let's assume an absolutely horrible hard drive seek time of 50ms (for simplicity of also covering any other compute time). The worst case binary search will be log base 2 of 200,000,000 which is 27.5. 27.5 x 50ms = 1.375 seconds. (Most hard drive seeks times are around 9ms.) Aug 26, 2009 at 4:19
15

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.

2
  • I really like this as a suggestion, but the question makes it seem as though there isn't room for false positives. Aug 26, 2009 at 3:10
  • I don't see anything leaning one way or the other on this. But I'll clarify my response to add that it's only suitable if you're okay with a tiny probability of false positives. With 8 billion bits to work with, you can get a false positive rate a little bit better than one in every billion tries. That's an extremely low false positive rate. If you looked up all 200 million words, the probability that you'd never hit a single false positive is about 82%. Aug 26, 2009 at 10:48
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.

5
  • +1. Better than my answer. Trie leaves store start & end positions in the file, and binsearch can find the word in the file chunk.
    – outis
    Aug 26, 2009 at 3:31
  • suppose my sample space is all letters and all numbers, then 36^4 =1,679,616, I can build at most 4 to 5 levels of tries, but I guess it still helps reducing the search space a lot.
    – user157195
    Aug 26, 2009 at 3:50
  • Sure...but since you're encoding what amounts to the set of all 4 character prefixes you're still substantially reducing your set. It depends on the distribution of the lengths of your words how efficient this really is, but in the worst case you can search the first 4 characters in O(4) time and search the subset of words at that leaf using outis' solution, as he suggests in his comment. Aug 26, 2009 at 4:06
  • @wo_shi_ni_ba_ba: your math's off, but it still works out to 5 levels using 1/2 GiB. Each node takes n=37*sizeof(void*) bytes (36 child node pointers & a branch/leaf marker; in a leaf, the 36 pointers are interpreted as file ranges [start/length pairs]. With alignment, a node takes up same space as 37 pointers). There are t=2 ** 29 / n total nodes (1/2 GiB divided by size of a node), giving a depth of roughly log(t)/log(36)+1 for a complete tree. A node doesn't know which character it starts with; that information is stored implicitly in the node's index in a child pointer array.
    – outis
    Aug 26, 2009 at 4:52
  • This question is asked in "The Algorithm Design Manual" book, and AFAIK author has used compressed trie to hold big amount of dictionary-like data (in his case it was human genomes) in the memory/ram. Jun 12, 2021 at 5:56
3

If the words share a lot of prefixes and suffixes, you can probably load them all into memory using a Directed Acyclic Word Graph (What up, DAWG!)

It's like a trie, but compresses shared suffixes. Whether this will be useful depends on what's in your dictionary, but fitting 200M into 1GB ram might be feasible.

1
  • +1 for DAWG over Trie for more efficient storage in a memory constrained environment.
    – Joel
    Jun 19, 2013 at 4:12
0

Use The Boyer–Moore string search algorithm?

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

1
  • Would it be possible to use Boyer-Moore Algorithm without loading into the main memory? Oct 28, 2012 at 1:42
0

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;
   }
3
  • Hardly 'the fastest' way to do it
    – johnc
    Aug 26, 2009 at 3:11
  • 1
    +1 for the stream. -1 for the brute force search. Net result 0 Vote.
    – JohnFx
    Aug 26, 2009 at 3:14
  • 1
    @Chaos He requested fast in the question
    – johnc
    Aug 26, 2009 at 3:23
0

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.