The order of preservation of the minimum perfect hash functions

Question

I want to implement the OPMPH function for words in a C ++ dictionary. How can I do it?

Thank!

Answer 1

Have you looked at these papers?

• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.4018&rep=rep1&type=pdf
• http://dx.doi.org/10.1016/0020-0190(92)90220-P (short link that leads to a very long link at http://www.sciencedirect.com/ )
• http://eprints.cs.vt.edu/archive/00000248/01/TR-91-01.pdf

Answer 2

Limit the word to 6 letters or less and you can make it work. Not very practical.

Answer 3

If you need alphabetical order, use Trie or DAWG (as I recommended in your last question). For the order, in addition to the alphabet, I would use a binary tree (std :: map in C ++ is implemented with a red-black tree usually).

Implementing an order-saving hash container sounds like the mother of all early optimizations.