|determining which bin contains which string email@example.com (Partha Saha) (2002-08-04)|
|Re: determining which bin contains which string firstname.lastname@example.org (VBDis) (2002-08-10)|
|Re: determining which bin contains which string email@example.com (Ralph Corderoy) (2002-08-14)|
|Re: determining which bin contains which string firstname.lastname@example.org (Grzegorz Jakacki) (2002-08-23)|
|From:||"Partha Saha" <email@example.com>|
|Date:||4 Aug 2002 11:42:53 -0400|
|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
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
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.
Return to the
Search the comp.compilers archives again.