\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.