Module bk-tree
bk-tree datastructure
http://en.wikipedia.org/wiki/BK-tree
Info:
- Release: version 1.0.3
- License: MIT
- Author: Robin Hübner
robinhubner@gmail.com
-
bk_tree:new ([root_word[, dist_func=levenshtein_dist]])
-
Creates a new bk-tree.
Parameters:
- root_word
string
the root of the new tree
(optional)
- dist_func
function
the distance function used
(default levenshtein_dist)
Returns:
the new bk-tree instance
See also:
Usage:
local bktree = require "bk-tree"
local tree = bktree:new("word")
-
bk_tree:insert (word)
-
Inserts word into the tree.
Parameters:
Returns:
bool
true if inserted, false if word already exists in tree
Usage:
local bktree = require "bk-tree"
local tree = bktree:new("root")
local success = tree:insert("other_word")
-
bk_tree:query (word, n)
-
Query the tree for matches.
Parameters:
- word
string
- n
number
max edit distance to use when querying
Returns:
{{str=string,distance=number},....}
table of tables with matching words, empty table if no matches
Usage:
local bktree = require "bk-tree"
local tree = bktree:new("word")
tree:insert("hello")
tree:insert("goodbye")
tree:insert("woop")
local result = tree:query("woop", 1)
-
bk_tree:query_sorted (word, n)
-
Queries the the tree for a match, sorts the results.
Calls query and returns the results sorted.
Parameters:
- word
string
- n
number
max edit distance to use when querying
Returns:
{{str=string,distance=number},....}
table of tables with matching words sorted by distance, empty table if no matches
Usage:
local bktree = require "bk-tree"
local tree = bktree:new("word")
tree:insert("woop")
tree:insert("worp")
tree:insert("warp")
local result = tree:query_sorted("woop", 3)
-
bk_tree.levenshtein_dist (s1, s2)
-
Levenshtein distance function.
Parameters:
Returns:
number
the levenshtein distance
-
bk_tree:debug ()
-
Hooks debugging into tree execution.
Keeps track of number of nodes created, queries made,
note that this must be run directly after tree is created
in order to get correct information.
Usage:
local bktree = require "bk-tree"
local tree = bktree:new("word")
tree:debug()
tree:insert("perceive")
tree:insert("beautiful")
tree:insert("definitely")
local result = tree:query("definately", 3)
tree:print_stats()
Nodes: 4
Queries: 3
Nodes Queried: 75%
-
bk_tree:print_stats ()
-
Print execution stats.
Prints nodes queried and total nodes, as well as a fraction of
nodes visited to satisfy the query, resets the counter of nodes queried when called.
See also:
-
bk_tree:get_stats ()
-
Fetch execution stats.
Returns a copy of the execution stats that print_stats would print, requires debug to have been enabled
to not just return defaults. Useful if you want to profile things.
Returns:
{key = value,...}