search

elisbyberi / dawgdic

Automatically exported from code.google.com/p/dawgdic
BSD 3-Clause "New" or "Revised" License
0 stars 0 forks source link

Perfect hashing #6

Closed GoogleCodeExporter closed 8 years ago

GoogleCodeExporter commented 8 years ago 
Hello,

What does it take to implement perfect hashing for DAWG? What I need is a 
bidirectional 1-to-1 mapping between integer numbers and string keys.

Original issue reported on code.google.com by kmik...@gmail.com on 21 Sep 2012 at 3:30

GoogleCodeExporter commented 8 years ago 
Hello,

I have a question about your suggestion.
Does that mean an integer-to-string mapping or a string-to-integer mapping?

Original comment by susumu.y...@gmail.com on 22 Sep 2012 at 6:28

GoogleCodeExporter commented 8 years ago 
I mean each key is assigned an unique number and it is possible to get a key 
given the number and to get a number given a key (as in marisa-trie).

Original comment by kmik...@gmail.com on 22 Sep 2012 at 9:19

GoogleCodeExporter commented 8 years ago 
The idea is interesting but it's difficult in practice.

dawgdic cannot restore a key from its corresponding leaf node ID (because such 
a node may associate more than one keys), and thus an additional data structure 
is required for integer-to-string mapping.
In addition, the mapping is nearly independent from dawgdic.

Therefore, I think this features should be provided as another library, not as 
a part of dawgdic.

Original comment by susumu.y...@gmail.com on 26 Sep 2012 at 11:54