TernaryTrees: Efficient pure ternary tree Sets and Maps

Ternary trees are an efficient structure often used for storing strings for fast lookups. This package implements a generic tree for storing lists of Ord instances, and a specialised String implementation which is about 30% faster than the generic version.

An example program is provided what shows how to use the package as a dictionary program for spell checking, and how it can be used to serialise data with Don Stewart's Data.Binary package.

From my testing, using the /usr/share/dict/words file on my system (over 230,000 words), inserting all words, checking they all exist in the tree, writing them to a binary file, reading them back in and checking the read in result is the same as the original takes slightly over 3 seconds using the StringSet. The written file is also slightly smaller than the input (by over 40% in some cases).

New in this version:

• Refactored a lot of the datatypes for the Sets (much of their code is exactly the same now)

• Made the get implementation shorter and clearer (thanks to olsner on IRC)

• There is now a darcs repo: http://random.axman6.com/darcs/TernaryTrees/

© 2009 by Alex Mason (http://random.axman6.com/blog/). BSD3 license.

Modules

[Last Documentation]

Downloads

• TernaryTrees-0.1.1.1.tar.gz [browse] (Cabal source package)
• Package description (as included in the package)

Maintainer's Corner

Package maintainers

• AlexMason

For package maintainers and hackage trustees

• edit package information

Candidates

• No Candidates