# Generate a unique number for a set of sequences of letters

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.

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.
• Thanks. Using the huffman coding makes the tree to be very height, then the searching won't be $O(\ log {n})$. But I explore other solutions :) Dec 26, 2017 at 14:53