Language.Distance.Search.BK

An implementation of Search based on a BK-tree: https://en.wikipedia.org/wiki/Bk-tree. It performs reasonably, and it scales decently as the query distance increases. Moreover the data structure can work on any instance of EditDistance, or in fact any metric space (although no interface for that purpose is defined): https://en.wikipedia.org/wiki/Metric_space.

However, for very short distances (less than 3), TST is faster.

Data type

data BKTree full algo

Operations

empty :: BKTree full algo

insert :: forall full sym algo. (Eq sym, EditDistance sym algo, ListLike full sym) => full -> BKTree full algo -> BKTree full algo

query :: forall full sym algo. (ListLike full sym, EditDistance sym algo) => Int -> full -> BKTree full algo -> [(full, Distance algo)]

levenshtein :: (ListLike full sym, EditDistance sym Levenshtein) => Int -> full -> BKTree full Levenshtein -> [(full, Distance Levenshtein)]

damerauLevenshtein :: (ListLike full sym, EditDistance sym DamerauLevenshtein) => Int -> full -> BKTree full DamerauLevenshtein -> [(full, Distance DamerauLevenshtein)]