Reference (original) (raw)

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

Functions

Metrics

Debug

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:

levenshtein_dist

Usage:

local bktree = require "bk-tree" local tree = bktree:new("word")

bk_tree:insert (word)

Inserts word into the tree.

Parameters:

• word string

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:

• s1 string
• s2 string

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:

debug

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,...}