Re: Compact transition matrix storage schemes

"Matt Timmermans" <mtimmerm@microstar.no-spam.com>
15 Dec 1997 21:58:17 -0500

          From comp.compilers
Related articles
Compact transition matrix storage schemes pprakash@mail.tea.state.tx.us (Praki Prakash) (1997-12-12)
Re: Compact transition matrix storage schemes chase@world.std.com (David Chase) (1997-12-13)
Re: Compact transition matrix storage schemes hbaker@netcom.com (1997-12-14)
Re: Compact transition matrix storage schemes mtimmerm@microstar.no-spam.com (Matt Timmermans) (1997-12-15)
Re: Compact transition matrix storage schemes autom@earthlink.net (Paul Mann) (1997-12-23)
| List of all articles for this month |
From: "Matt Timmermans" <mtimmerm@microstar.no-spam.com>
Newsgroups: comp.compilers
Date: 15 Dec 1997 21:58:17 -0500
Organization: IGS - Information Gateway Services
References: 97-12-086
Keywords: parse, optimize

Praki Prakash wrote...
>Can anybody point me to some published literature on the various schemes
>for storing transition matrix?


Perfect hashing is now the next-fastest alternative after permuting
and overlapping. Have a look at:


"An optimal algorithm for generating minimal perfect hash functions"
Infomation Processing Letters, 43(5):257-264, October 1992


which provides an amazingly accessible description.


I've used this method to implement transition functions as simple as:


a=((old_state<<16)+input_symbol)*K;a^=(a>>16);
b=h1[a&mask]^h2[(a>>8)&mask];
if (check[b]==a)
    new_state=trans[b];
else
    error


--

Post a followup to this message

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