# determining which bin contains which string

## "Partha Saha" <partha@berkeley.innomedia.com>4 Aug 2002 11:42:53 -0400

From comp.compilers

Related articles
determining which bin contains which string partha@berkeley.innomedia.com (Partha Saha) (2002-08-04)
Re: determining which bin contains which string vbdis@aol.com (VBDis) (2002-08-10)
Re: determining which bin contains which string ralph@inputplus.co.uk (Ralph Corderoy) (2002-08-14)
Re: determining which bin contains which string jakacki@hotmail.com (Grzegorz Jakacki) (2002-08-23)
| List of all articles for this month |

 From: "Partha Saha" Newsgroups: comp.compilers Date: 4 Aug 2002 11:42:53 -0400 Organization: Compilers Central Keywords: lex, question Posted-Date: 04 Aug 2002 11:42:53 EDT

I was seeking a solution to the following problem:

I have strings of length 12, the alphabets are 0-9,a,b,c,d,e,f (i.e.,
they are "hexadecimal" strings). Clearly the number of strings
possible is huge = 16^12

Let's say we have a finite number of them (N where is N is large, say
100000, but N << 16^12). These have been binned by some arbitrary
logic into n (where n is say 5, n << N) bins. The bins are numbered
from 1 to n.

Instead of keeping a table of N rows where each row has a mapping of
string to bin number, I am wondering if I could design a finite state
machine which would take a string, go through each string element, and
end up in a final state that corresponds to a bin number (of course if
the string is not one of the N strings, it should go into a
non-accepting state).

I would also like to dynamically alter the FSM as N->N+1, i.e., as new
strings get added to our set. and put into a certain bin (we cannot
predict which bin that would be).

I would also like to dynamically alter the FSM as n->n+1, i.e., as new
bins are added (but the contents of the previous bins are left
unaltered).

My training being in Physics, I can probably "hack" up a solution; I
was wondering if someone knew of a formal way of going about it.
Somehow a proof is also needed that the storage requirements of the
FSM will be better than the actual table itself.

Thanks much!
Partha Saha

Post a followup to this message