26 messages in org.apache.lucene.java-devRe: FST and FieldCache?| From | Sent On | Attachments |
|---|---|---|
| Davi...@MITRE.org) | May 18, 2011 9:52 pm | |
| Dawid Weiss | May 18, 2011 11:30 pm | |
| Earwin Burrfoot | May 19, 2011 1:24 am | |
| Dawid Weiss | May 19, 2011 1:42 am | |
| Michael McCandless | May 19, 2011 3:08 am | |
| Dawid Weiss | May 19, 2011 3:16 am | |
| Michael McCandless | May 19, 2011 3:21 am | |
| Dawid Weiss | May 19, 2011 3:36 am | |
| Earwin Burrfoot | May 19, 2011 5:30 am | |
| Michael McCandless | May 19, 2011 5:44 am | |
| Dawid Weiss | May 19, 2011 5:45 am | |
| Earwin Burrfoot | May 19, 2011 6:02 am | |
| Robert Muir | May 19, 2011 6:04 am | |
| Dawid Weiss | May 19, 2011 6:20 am | |
| Jason Rutherglen | May 19, 2011 6:22 am | |
| Earwin Burrfoot | May 19, 2011 6:29 am | |
| Jason Rutherglen | May 19, 2011 6:36 am | |
| Michael McCandless | May 19, 2011 6:40 am | |
| Jason Rutherglen | May 19, 2011 7:08 am | |
| Davi...@MITRE.org) | May 19, 2011 7:53 am | |
| Davi...@MITRE.org) | May 19, 2011 8:58 am | |
| Michael McCandless | May 19, 2011 8:59 am | |
| Jason Rutherglen | May 19, 2011 9:35 am | |
| Michael McCandless | May 19, 2011 9:42 am | |
| Earwin Burrfoot | May 19, 2011 11:00 am | |
| Dawid Weiss | May 19, 2011 11:48 am |
| Subject: | Re: FST and FieldCache? | |
|---|---|---|
| From: | Dawid Weiss (dawi...@cs.put.poznan.pl) | |
| Date: | May 19, 2011 1:42:48 am | |
| List: | org.apache.lucene.java-dev | |
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.
Dawid