lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dawid Weiss <>
Subject Re: FST and FieldCache?
Date Thu, 19 May 2011 08:43:11 GMT
> Though, it's possible to do if you associate an additional number with
> each node. (I invented some way, shared it with Mike and forgot.. good
> grief :/)

It doesn't need to be invented -- it's a known technique. On each arc
you store the number of strings under that arc; while traversing you
accumulate -- this gives you a unique number for each string (perfect
hash) and a way to locate a string given its number.

> And it can't do the reverse lookup, by design, that's a lossy
> compression for all good perfect hashing algos.
> So, it's irrelevant here, huh?

You can do both the way I described above. Jan Daciuk has details on
many more variants of doing that:

Jan Daciuk, Rafael C. Carrasco, Perfect Hashing with Pseudo-minimal
Bottom-up Deterministic Tree Automata, Intelligent Information Systems
XVI, Proceedings of the International IIS'08 Conference held in
Zakopane, Poland, June 16-18, 2008, Mieczysław A. Kłopotek, Adam
Przepiórkowski, Sławomir T. Wierzchoń, Krzysztof Trojanowski (eds.),
Academic Publishing House Exit, Warszawa 2008.


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message