10

I am looking for ANSI C HAT-trie implementation released under some free license. I have not found one. Can you point me to some standalone implementation or a program that uses HAT-tries to get at least slight idea how to implement it the roght way, please?

The original paper on HAT-trie can be found here: http://crpit.com/confpapers/CRPITV62Askitis.pdf

PS: In case faster cache-conscious data structured well-suited for strings evolved since the time the above paper was written, please point me to the papers or example source codes rather.

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
mjf
  • 101
  • 1
  • 3
  • See http://stackoverflow.com/questions/1036504/trie-implementation – Robert Harvey Jul 26 '10 at 22:49
  • I know of that thread. I am not sure I want to use Judy for my task at all. I wanted the HAT-trie, but in the thread mentioned, there is just the same link to the paper I gave myself. But I am looking for some real implementation of the HAT-trie to see, decide and get inspired how to implement it right way. -- mjf – mjf Jul 26 '10 at 23:00

2 Answers2

2

Please see the HAT-trie implementation site at code.google.com/p/hat-trie for implementation notes and source code.

JOM
  • 8,139
  • 6
  • 78
  • 111
Malbrain
  • 83
  • 7
2

Someone is implementing it in C++ over on github

https://github.com/chris-vaszauskas/hat-trie

If you need a plain C implementation, this would be a good base to start from.

Java is also fairly readable for a C programmer

http://www.stochasticgeometry.ie/2008/05/06/implementing-hat-tries-in-java/

Michael Dillon
  • 31,973
  • 6
  • 70
  • 106