[![Build Status](https://travis-ci.org/gugod/Tree-VP.svg?branch=master)](https://travis-ci.org/gugod/Tree-VP) [![Coverage Status](https://img.shields.io/coveralls/gugod/Tree-VP/master.svg?style=flat)](https://coveralls.io/r/gugod/Tree-VP?branch=master) # 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](https://metacpan.org/pod/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](https://metacpan.org/pod/Tree::DAG_Node) objects, the `freeze` and `unfreeze` subroutine here needs be able to serealize and unserealize perl objects. [Sereal](https://metacpan.org/pod/Sereal) is a good choice, but basically any subroutines that can convert [Tree::DAG\_Node](https://metacpan.org/pod/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](http://en.wikipedia.org/wiki/Vantage-point_tree) # Author Kang-min Liu # License The MIT License.