开发者

Order preserving minimal perfect hash functions

I want to implement an OPMPH fu开发者_Go百科nction for the words in a dictionary in C++. How do I do it?

Thanks!


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 (the short form 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


Limit your word length to 6 letters or less and you might be able to make it work. Not very practical.


If you need alphabetical order use a Trie or a DAWG (like I recommended in your last question). For an order besides alphabetic I would use a binary tree (std::map in C++ is implemented with a red-black tree usually).

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜