/ 
Tree-Trie-0.1
River stage one • 3 direct dependents • 8 total dependents
/ Tree::Trie

NAME

Tree::Trie - An implementation of the Trie data structure in Perl

SYNOPSIS

use Tree::Trie;
use strict;

my($trie) = new Tree::Trie;
$trie->add(qw[aeode calliope clio erato euterpe melete melpomene mneme 
  polymnia terpsichore thalia urania]);
my(@all) = $trie->lookup("");
my(@ms)  = $trie->lookup("m");
$" = "--";
print "Entire trie contains: @all\nMuses beginning with 'm': @ms\n";
my(@deleted) = $trie->remove(qw[calliope thalia doc]);
print "Deleted @deleted\n";

DESCRIPTION

This module implements a trie data structure. The term "trie" comes from the word retrieval, but is generally pronounced like "try". A trie is a tree structure, the nodes of which represent letters in a word. For example, the final lookup for the word 'bob' would look something like $ref->{'b'}{'o'}{'b'}{'00'} (the '00' being the end marker). Only nodes which would represent words in the trie exist, making the structure slightly smaller than a hash of the same data set.

The advantages of the trie over other data storage methods is that lookup times are O(1) WRT the size of the index. For sparse data sets, it is probably not as efficient as performing a binary search on a sorted list, and for small files, it has a lot of overhead. The main advantage (at least from my perspective) is that it provides a relatively cheap method for finding a list of words in your set which begin with a certain string.

METHODS

new

This is the constructor method for the class. It takes no arguments.

add(word0 [, word1...wordN])

This method attempts to add words 0 through N to the trie. Returns, in list context, the words successfully added to the trie. In scalar context, returns the number of words successfully added. As of this release, the only reason a word would fail to be added is if it is already in the trie.

remove(word0 [, word1...wordN])

This method attempts to remove words 0 through N from the trie. Returns, in list context, the words successfully removed from the trie. In scalar context, returns the number of words successfully removed. As of this release, the only reason a word would fail to be removed is if it is not already in the trie.

lookup(word0)

This method performs lookups on the trie. In scalar context, returns the first word found in the trie which begins with word0. If word0 exists exactly in the trie, returns word0. Returns undef if no words beginning with word0 are in the trie. In list context, returns a complete list of words in the trie which begin with word0.

To get a list of all words in the trie, use lookup("") in list context.

Future Work

  • I plan on making a "DeepSearch" (or similarly named) method, allowing the bahviour of the lookup method in scalar context to be configured -- it will be able to return undef if word0 does not exist exactly in the trie.

  • The ability to associate data with each word in a trie will be added.

  • There are a few methods of compression that allow you same some amount of space in the trie. I have to figure out which ones are worth implemeting. I may end up making the different compression methods configurable.

  • The ability to have Tree::Trie store its internal hash as a TIE object of some sort.

AUTHOR

Copyright 1999 Avi Finkel <avi@lycos.com>

This package is free software and is provided "as is" without express or implied warranty. It may be used, redistributed and/or modified under the terms of the Perl Artistic License (see http://www.perl.com/perl/misc/Artistic.html)