determining which bin contains which string

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

Return to the comp.compilers page.
Search the comp.compilers archives again.