The TernaryTrees package
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:
Moved datatype definitions into .Internal modules so that testing can be performed, without needing to export their definitions in the main modules.
Checked a lot of the source with HLint 1.6 and made some minor changes based on that ((mostly redundant brackets)).
© 2009 by Alex Mason (http://random.axman6.com/blog/). BSD3 license.
Properties
| Versions | 0.0.1, 0.0.2, 0.0.2.1, 0.0.2.2, 0.0.3.0, 0.0.4.0, 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.1.2.0, 0.1.3.0, 0.1.3.1, 0.1.3.2, 0.1.3.3, 0.1.3.4, 0.2.0.0, 0.2.0.2 |
|---|---|
| Dependencies | base (≥4.0.0.0 & <5.0.0.0), binary (≥0.5.0.0) |
| License | BSD3 |
| Author | Alex Mason |
| Maintainer | Alex Mason (irc: Axman6) <axman6@gmail.com> |
| Category | Data Structures |
| Executables | tdict |
| Upload date | Thu Jul 2 15:27:15 UTC 2009 |
| Uploaded by | AlexMason |
| Build failure | ghc-6.12 (log) |
Modules
- Data
- Map
- Data.Map.TernaryMap
- Set
- Data.Set.StringSet
- Data.Set.TernarySet
- Map
Downloads
- TernaryTrees-0.1.3.0.tar.gz (Cabal source package)
- package description (included in the package)