Generate a unique number for a set of sequences of letters

Question

A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I need to search if the $w$ exists in the database of words.

The framework of the database and the application is on the web and this job is part of an online game, So may be hundreds of requests come to website in a second so I need to do it as fast as possible. To do so as fast as possible, I want generate a unique number for every word in the database. For every string query, I generate its number using the algorithm used to generate numbers for the database, then check if the new number exists in the database or not using binary search tree.

Here is an algorithm that works perfectly to generate a unique number for a sequence:

For a sequence $<a_1, a_2, \cdots, a_n>$ where $a_i \in \mathbb{Z^{+}}$ (it is easy to map every letter to a number) the unique number is

$$ \prod_{i=1}^{n}{p_i^{a_i}} $$

where $p_i$ is the $i$-th prime number. But the problem is, the produced numbers are too large to be stored in current programming language variables.

My Solution

First I set the following mapping:

$MAP: [a=>2, b=>3, c=>5, \cdots, z=>101]$

So I set the $i$-th prime number to the $i$-th letter. (Actually it is not necessary to regard this order, more frequent characters can take smaller prime number)

For a sequence $<a_1, a_2, \cdots, a_n>$ where $a_i$s are letters this is my formula:

$$ \prod_{i=1}^{n}{MAP(a_i)^i} $$

For valid words, this formula generally, produces smaller numbers than the first one. I just wanted to know :

• if this formula always generates a unique number? I couldn't generate two words with the same numbers, but clearly it is not enough to convince other people

• Is there any solution that search for words in $O(\log n)$ (like binary search tree)?

thanks.

Answer 1

Use a hash function. Since you have less than $2^{16}$ words, if you use a hash of 32 bits then you are likely to not have any collisions. If you do get collisions, you can try varying the key (hashes usually use some magic numbers, which in some cases are known as keys), or you can just use a longer hash.

Another possibility is to store the dictionary as a decision tree. The decision tree contains a node for each prefix of a word in your dictionary, and as you read a new word, you travel along the decision tree until you hit a leaf (the word is in the dictionary) or you get stuck (the word is not in the dictionary). But that amounts to storing the entire dictionary, which perhaps you are trying to avoid for some reason.

If for some reason you don't like these solutions, I have two other solutions to offer, though I don't recommend using them. The first one is to encode your words in base 26. This will be much more efficient than your prime-based code, though still somewhat unwieldy (the result could be up to 71 bits long). A more economic but more complicated solution is to use a Huffman code, either first order (the same code for each letter), second order (one code for the first letter, and henceforth the code depends on the previous letter), or even higher order.