trees :: BKTree :: default_tolerance
Default tolerance used to find matchestrees :: BKTree :: default_tolerance=
Default tolerance used to find matchestrees :: BKTree :: defaultinit
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
trees :: BKTree :: default_tolerance
Default tolerance used to find matchestrees :: BKTree :: default_tolerance=
Default tolerance used to find matchescore :: Object :: defaultinit
trees :: BKTree :: defaultinit
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
core :: Object :: output_class_name
Display class name on stdout (debug only).
# A BKTree implementation
#
# See `add` to insert a new word.
# See `search` to find matches from a `key`.
class BKTree
# Default tolerance used to find matches
#
# Default is `2`.
var default_tolerance = 2 is writable
# Tree root
private var root: nullable BKNode = null
# Add a `key` in the tree
fun add(key: String) do
var root = self.root
if root == null then
self.root = new BKNode(key)
return
end
var node = root
var dist = node.key.levenshtein_distance(key)
while node.has_key(dist) do
if dist == 0 then return
node = node[dist]
dist = node.key.levenshtein_distance(key)
end
node[dist] = new BKNode(key)
end
# Search `key` with a distance of `tolerance` in `self`.
#
# If `tolerance` is null, the use `default_tolerance` instead.
fun search(key: String, tolerance: nullable Int): Array[BKMatch] do
var res = new Array[BKMatch]
var root = self.root
if root != null then
if tolerance == null then tolerance = self.default_tolerance
search_recursive(root, res, key, tolerance)
end
default_comparator.sort(res)
return res
end
private fun search_recursive(node: BKNode, res: Array[BKMatch], key: String, tolerance: Int) do
var dist = node.key.levenshtein_distance(key)
var min = dist - tolerance
var max = dist + tolerance
if dist < tolerance then
res.add new BKMatch(dist, node.key)
end
for odist, child in node do
if odist < min or odist > max then continue
search_recursive(child, res, key, tolerance)
end
end
end
lib/trees/bktree.nit:50,1--111,3