Skip to content
master
Switch branches/tags
Go to file
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
t
 
 
 
 
 
 
 
 
 
 
 
 

README.md

Build Status

NAME

Algorithm::TernarySearchTree - the algorithm which blends trie and binary search tree

SYNOPSIS

use Algorithm::TernarySearchTree;

my $tst = Algorithm::TernarySearchTree.new();

$tst.insert("Perl6 is fun");
$tst.insert("Perl5 is fun");

my $false-flag = $tst.contains("Kotlin is fun"); # False
my $true-flag = $tst.contains("Perl6 is fun"); # True

my $matched = $tst.partial-match("Perl. is fun"); # set("Perl5 is fun","Perl6 is fun")
my $not-matched = $tst.partial-match("...lin is fun"); # set()

DESCRIPTION

Algorithm::TernarySearchTree is a implementation of the ternary search tree. Ternary search tree is the algorithm which blends trie and binary search tree.

CONSTRUCTOR

new

my $tst = Algorithm::TernarySearchTree.new();

METHODS

insert(Str $key)

$tst.insert($key);

Inserts the key to the tree.

contains(Str $key) returns Bool:D

my $flag = $tst.contains($key);

Returns whether given key exists in the tree.

partial-match(Str $fuzzy-key) returns Set:D

my Set $matched = $tst.partial-match($fuzzy-key);

Searches partially matched keys in the tree. If you want to match any character except record separator(hex: 0x1e), you can use dot symbol. For example, the query "Perl." matches "Perla", "Perl5", "Perl6", and so on.

METHODS NOT YET IMPLEMENTED

near-search, traverse, and so on.

AUTHOR

titsuki titsuki@cpan.org

COPYRIGHT AND LICENSE

Copyright 2016 titsuki

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.

This algorithm is from Bentley, Jon L., and Robert Sedgewick. "Fast algorithms for sorting and searching strings." SODA. Vol. 97. 1997.

About

the algorithm which blends trie and binary search tree

Resources

License

Packages

No packages published

Languages

  • Other 100.0%