Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP

A ternary search tree implementation in Erlang.

branch: master

README updates.

This commit includes more of the TST interaction as well as a section on future
work.

Signed-off-by: Brian L. Troutwine <brian@troutwine.us>
latest commit afad081fab
Brian L. Troutwine authored July 20, 2013
Octocat-spinner-32 priv Include a dictionary in priv/. July 18, 2013
Octocat-spinner-32 src Bump version to 2.2.0. July 19, 2013
Octocat-spinner-32 .gitignore Library cleanup. July 14, 2013
Octocat-spinner-32 .travis.yml Back off Travis command to build on R16B01. July 18, 2013
Octocat-spinner-32 LICENSE Initial commit. April 29, 2012
Octocat-spinner-32 Makefile Put the library on a firm footing. July 15, 2013
Octocat-spinner-32 README.md README updates. July 20, 2013
Octocat-spinner-32 rebar.config Put the library on a firm footing. July 15, 2013
README.md

TST - Erlang ternary search tree

Build Status

The ternary search tree is a prefix binary search tree. Compared to similar tries, it is more memory efficient at the cost of execution speed.

This library provides an Erlang module for creating, manipulating and searching in-memory TSTs. The following operations are supported:

  • membership testing (tst:contains/2)
  • insertion (tst:insert/2)
  • partial match searches (tst:partial_matches/2)
  • near neighbor searches (tst:near_neighbors/3)
  • word size of given tree (tst:wc/1)
  • coercion from list of strings (tst:from_list/1)
  • coercion to list of strings (tst:to_list/1)

Binaries are not supported, though this is an intended feature. This TST is case-sensitive. The words "moose", "Moose" and "MoOsE" are all considered distinct words.

Example

> erl -pa ebin
Erlang R15B03 (erts-5.9.3) [source] [64-bit] [smp:8:8] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.9.3  (abort with ^G)
1> TST = tst:from_list(["moose", "goose", "house", "computer"]).
...
2> tst:contains("moose", TST).
true
3> tst:partial_matches(".oose", TST).
["goose","moose"]
4> tst:partial_matches(".o.se", TST).
["goose","house","moose"]
5> tst:to_list(TST).
["computer","goose","house","moose"]
6> tst:to_list(tst:insert("abba", TST)).
["abba","computer","goose","house","moose"]

Please see in-line documentation and in-line test cases for more.

Future Work

Because tst uses Erlang strings--lists of machine words as character--internally to represent strings the search tree will consume more memory than reading the source words into memory as binaries would. Consider:

> du -sh priv/words
priv/words    2.4M

The test suite reads this file in to run benchmarks; the size of the TST generated from priv/words is reported in megabytes.

src/tst.erl:459:<0.50.0>: TST size :: 42.339 megabytes

Future work will attempt to get the resulting TST to consume no more than the same amount of memory as an on-disk representation.


This data-structure is implemented from the discussion given in Bentley and Sedgewick's Fast Algorithsm for Searching and Sorting. It is released under the MIT license.

Something went wrong with that request. Please try again.