The bk-tree Reference Manual

This is the bk-tree Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 14:43:50 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 bk-tree

Source

bk-tree.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 bk-tree/bk-tree.asd

Source

bk-tree.asd.

Parent Component

bk-tree (system).

ASDF Systems

bk-tree.


3.1.2 bk-tree/packages.lisp

Source

bk-tree.asd.

Parent Component

bk-tree (system).

Packages

bk-tree.


3.1.3 bk-tree/specials.lisp

Dependency

packages.lisp (file).

Source

bk-tree.asd.

Parent Component

bk-tree (system).

Public Interface

3.1.4 bk-tree/utils.lisp

Dependency

specials.lisp (file).

Source

bk-tree.asd.

Parent Component

bk-tree (system).

Public Interface

3.1.5 bk-tree/bk-tree.lisp

Dependency

utils.lisp (file).

Source

bk-tree.asd.

Parent Component

bk-tree (system).

Public Interface

4 Packages

Packages are listed by definition order.


4.1 bk-tree

Source

packages.lisp.

Use List

common-lisp.

Public Interface

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Ordinary functions

Function: average-children-count (tree)

Returns average children count per node of the supplied ‘TREE’.

Package

bk-tree.

Source

bk-tree.lisp.

Function: hairy-search-value (value tree &key threshold metric limit ordered-results ordered-traversal)

Return a list of ‘SEARCH-RESULT’ instances built from ‘TREE’ and its children whose value is no more distant from ‘VALUE’ than ‘THRESHOLD’, using ‘METRIC’ to measure the distance.

If ‘LIMIT’ is non-NIL, given number of first found results will be
returned.

If ‘ORDERED-RESULTS’ is non-NIL, returned results will be ordered according to their distances from ‘VALUES’.

If ‘ORDERED-TRAVERSAL’ is non-NIL, candidates in a level (e.g. children of a validated node) will be traversed in sorted order according to the absolute difference between the parent distance and child distance – the (probably) more similar is first.

‘HAIRY-SEARCH-VALUE’ is a feature rich and hence slower derivative of ‘SEARCH-VALUE’. For simple query patterns, consider using ‘SEARCH-VALUE’.

Package

bk-tree.

Source

bk-tree.lisp.

Function: insert-value (value tree &key metric)

Inserts given ‘VALUE’ into supplied ‘TREE’.

Package

bk-tree.

Source

bk-tree.lisp.

Function: levenshtein (src dst &key insert-cost delete-cost substitute-cost)

An O(mn) implementation of the Levenshtein distance metric.

Package

bk-tree.

Source

utils.lisp.

Function: maximum-depth (tree)

Returns maximum depth of the ‘TREE’.

Package

bk-tree.

Source

bk-tree.lisp.

Function: print-tree (tree &key stream depth)

Prints supplied ‘TREE’ in a human-readable(?) format.

Package

bk-tree.

Source

bk-tree.lisp.

Function: search-value (value tree &key threshold metric ordered-results)

Return a list of ‘SEARCH-RESULT’ instances built from ‘TREE’ and its children whose value is no more distant from ‘VALUE’ than ‘THRESHOLD’, using ‘METRIC’ to measure the distance.

If ‘ORDERED-RESULTS’ is non-NIL, collected results will be sorted according to their distances from ‘VALUE’.

Package

bk-tree.

Source

bk-tree.lisp.


5.1.2 Generic functions

Generic Reader: distance-of (object)
Package

bk-tree.

Methods
Reader Method: distance-of ((search-result search-result))

automatically generated reader method

Source

specials.lisp.

Target Slot

distance.

Reader Method: distance-of ((bk-tree bk-tree))

Metric distance between current node and its parent.

Source

specials.lisp.

Target Slot

distance.

Generic Writer: (setf distance-of) (object)
Package

bk-tree.

Methods
Writer Method: (setf distance-of) ((search-result search-result))

automatically generated writer method

Source

specials.lisp.

Target Slot

distance.

Writer Method: (setf distance-of) ((bk-tree bk-tree))

Metric distance between current node and its parent.

Source

specials.lisp.

Target Slot

distance.

Generic Reader: nodes-of (object)
Generic Writer: (setf nodes-of) (object)
Package

bk-tree.

Methods
Reader Method: nodes-of ((bk-tree bk-tree))
Writer Method: (setf nodes-of) ((bk-tree bk-tree))

Nodes collected under this node.

Source

specials.lisp.

Target Slot

nodes.

Generic Reader: value-of (object)
Package

bk-tree.

Methods
Reader Method: value-of ((condition duplicate-value))
Source

specials.lisp.

Target Slot

value.

Reader Method: value-of ((search-result search-result))

automatically generated reader method

Source

specials.lisp.

Target Slot

value.

Reader Method: value-of ((bk-tree bk-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

value.

Generic Writer: (setf value-of) (object)
Package

bk-tree.

Methods
Writer Method: (setf value-of) ((condition duplicate-value))
Source

specials.lisp.

Target Slot

value.

Writer Method: (setf value-of) ((search-result search-result))

automatically generated writer method

Source

specials.lisp.

Target Slot

value.

Writer Method: (setf value-of) ((bk-tree bk-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

value.


5.1.3 Standalone methods

Method: print-object ((self bk-tree) stream)
Source

specials.lisp.

Method: print-object ((self search-result) stream)
Source

specials.lisp.


5.1.4 Conditions

Condition: duplicate-value

Signaled upon every duplicated entry insertion.

Package

bk-tree.

Source

specials.lisp.

Direct superclasses

error.

Direct methods
Direct slots
Slot: value
Initargs

:value

Readers

value-of.

Writers

(setf value-of).


5.1.5 Classes

Class: bk-tree
Package

bk-tree.

Source

specials.lisp.

Direct methods
Direct slots
Slot: distance

Metric distance between current node and its parent.

Type

unsigned-byte

Initform

0

Initargs

:distance

Readers

distance-of.

Writers

(setf distance-of).

Slot: value
Initargs

:value

Readers

value-of.

Writers

(setf value-of).

Slot: nodes

Nodes collected under this node.

Type

list

Initargs

bk-tree::nodes

Readers

nodes-of.

Writers

(setf nodes-of).

Class: search-result
Package

bk-tree.

Source

specials.lisp.

Direct methods
Direct slots
Slot: distance
Type

unsigned-byte

Initargs

:distance

Readers

distance-of.

Writers

(setf distance-of).

Slot: value
Initargs

:value

Readers

value-of.

Writers

(setf value-of).


5.1.6 Types

Type: levenshtein-cost ()

Available penalty costs.

Package

bk-tree.

Source

utils.lisp.

Type: levenshtein-max-distance ()

Maximum distance a comparison can result.

Package

bk-tree.

Source

utils.lisp.


5.2 Internals


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
A   D   F   G   H   I   L   M   N   P   S   V  
Index Entry  Section

(
(setf distance-of): Public generic functions
(setf distance-of): Public generic functions
(setf distance-of): Public generic functions
(setf nodes-of): Public generic functions
(setf nodes-of): Public generic functions
(setf value-of): Public generic functions
(setf value-of): Public generic functions
(setf value-of): Public generic functions
(setf value-of): Public generic functions

A
average-children-count: Public ordinary functions

D
distance-of: Public generic functions
distance-of: Public generic functions
distance-of: Public generic functions

F
Function, average-children-count: Public ordinary functions
Function, hairy-search-value: Public ordinary functions
Function, insert-value: Public ordinary functions
Function, levenshtein: Public ordinary functions
Function, maximum-depth: Public ordinary functions
Function, print-tree: Public ordinary functions
Function, search-value: Public ordinary functions

G
Generic Function, (setf distance-of): Public generic functions
Generic Function, (setf nodes-of): Public generic functions
Generic Function, (setf value-of): Public generic functions
Generic Function, distance-of: Public generic functions
Generic Function, nodes-of: Public generic functions
Generic Function, value-of: Public generic functions

H
hairy-search-value: Public ordinary functions

I
insert-value: Public ordinary functions

L
levenshtein: Public ordinary functions

M
maximum-depth: Public ordinary functions
Method, (setf distance-of): Public generic functions
Method, (setf distance-of): Public generic functions
Method, (setf nodes-of): Public generic functions
Method, (setf value-of): Public generic functions
Method, (setf value-of): Public generic functions
Method, (setf value-of): Public generic functions
Method, distance-of: Public generic functions
Method, distance-of: Public generic functions
Method, nodes-of: Public generic functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, value-of: Public generic functions
Method, value-of: Public generic functions
Method, value-of: Public generic functions

N
nodes-of: Public generic functions
nodes-of: Public generic functions

P
print-object: Public standalone methods
print-object: Public standalone methods
print-tree: Public ordinary functions

S
search-value: Public ordinary functions

V
value-of: Public generic functions
value-of: Public generic functions
value-of: Public generic functions
value-of: Public generic functions