\BkTree

A serialisable BK-Tree Implementation.

Ref: https://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/

Summary

Methods

Properties

Constants

__construct()
edit_distance()
add()
remove()
trace()
lookup_one()
lookup()
stats()
walk()
close()

No public properties found

No constants found

No protected methods found

No protected properties found

N/A

No private methods found

No private properties found

N/A

Methods

__construct()

__construct(  $filename)

Parameters

$filename

edit_distance()

edit_distance(string  $a,string  $b): integer

A utility function for calculating edit distance.

Warning: Do not use this internally! It is slow. It's much faster to do this directly. This exists only for external use.

Parameters

string	$a	The first string.
string	$b	The second string to compare against.

Returns

integer —

The computed edit distance.

add()

add(string  $string,integer  $starting_node_id): integer

Adds a string to the tree.

Parameters

string	$string	The string to add.
integer	$starting_node_id	The id fo node to start insertion from. Defaults to 0 - for internal use only.

Returns

integer —

The depth at which the new node was added.

remove()

remove(string  $string): boolean

Removes a string from the tree.

Parameters

string

$string

The string to remove.

Returns

boolean —

Whether the removal was successful.

trace()

trace(\string  $string)

Parameters

\string

$string

lookup_one()

lookup_one(string  $string,integer  $distance = 1): string|null

Convenience function that returns just the first result when looking up a string.

Parameters

string	$string	The string to lookup
integer	$distance	The maximum edit distance to search.

Returns

string|null —

The first matching string, or null if no results were found.

lookup()

lookup(string  $string,integer  $max_distance = 1,integer  $count): \Generator<string>

Generator that walks the BK-Tree and iteratively yields results.

TODO: Refactor this to use an array, since generators are ~

Parameters

string	$string	The search string.
integer	$max_distance	The maximum edit distance to search.
integer	$count	The number of results to return. 0 = All results found. Note that results will be in a random order.

Returns

\Generator —

Iteratively yielded similar resultant strings from the BK-Tree.

stats()

stats(): array

Calculate statistics about the BK-Tree.

Useful for analysing a tree's structure. If the tree isn't balanced, you may need to insert items in a different order.

Returns

array —

An array of statistics about this BK-Tree.

walk()

walk()

close()

close(): void

Saves changes to the tree back to disk.