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

bk_tree:new ([root_word[, dist_func=levenshtein_dist]]) Creates a new bk-tree.
bk_tree:insert (word) Inserts word into the tree.
bk_tree:query (word, n) Query the tree for matches.
bk_tree:query_sorted (word, n) Queries the the tree for a match, sorts the results.

Metrics

bk_tree.levenshtein_dist (s1, s2) Levenshtein distance function.

Debug

bk_tree:debug () Hooks debugging into tree execution.
bk_tree:print_stats () Print execution stats.
bk_tree:get_stats () Fetch execution stats.


Functions

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)

Metrics

bk_tree.levenshtein_dist (s1, s2)
Levenshtein distance function.

Parameters:

Returns:

    number the levenshtein distance

Debug

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()
    
    -- output
    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,...}
generated by LDoc 1.4.6 Last updated 2022-02-22 17:51:40