Name

Tree::VP - Vantage-Point Tree builder and searcher.

Synopsis

A spellchecker.

my @words = read_file("/usr/share/dict/words", { chomp => 1, binmode => ":utf8" });
my $vptree = Tree::VP->new( distance => \&Text::Levenshtein::XS::distance );
$vptree->build(\@words);

my $r = $vptree->search(query => "amstedam", size => 5);
say "suggestion: " . join " ", map { $_ . " (" . distance($_, $q) . ")" } @{$r->{values}};

Methods

• new( distance => sub { ... })

  Construct the top-level tree object. The distance function must be able to calculate the distance between any 2 values in the ArrayRef passed to build method. It must return a number range from 0 to Inf. The number "0" meaning that the 2 values are the same, and larger number means that the given 2 values are further away in space.

• build( ArrayRef[ Val ] )

  Take a ArrayRef of values of whatever type that can be handled by the distance function, and build the tree structure.

• search( query => Val, size => Int )

  Take a "query", which is just a value of whatever type contained in the tree. And return HashRef that contains the results of top-K nearest nodes according to the distance function. size means the the upper-bound of result size.

• tree() (a public attribute)

  This points to the underlying tree data structure, which is an instance of Tree::DAG_Node . Since the creation process of VP trees is expensive, it is desired to be able to store the tree structure and re-use the stored state. To achieve this, do something like this:

    # Storing
    my $vptree = Tree::VP->new( distance => \&distance );
    $vptree->build(\@words);
    write_file("/db/tree_stored.db", freeze($vptree->tree));
  
    # Loading and use
    my $tree =  unfreeze(read_file("/db/tree_stored.db"));
    my $vptree = Tree::VP->new( tree => $tree, distance => \&distance );
    $vptree->search(...);
  

  Since we use Tree::DAG_Node objects, the freeze and unfreeze subroutine here needs be able to serealize and unserealize perl objects. Sereal is a good choice, but basically any subroutines that can convert Tree::DAG_Node objects to string and back, can be used. Obviously, the distance function must be the same in order to produce valid response.

See Also

http://en.wikipedia.org/wiki/Vantage-point_tree

Author

Kang-min Liu gugod@gugod.org

License

The MIT License.