Safe Haskell | None |
---|
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 - a generic interface is provided in BKTree
.
However, for very short distances (less than 3),
TST
is faster.
- data BKTree full algo
- empty :: forall full sym algo. (EditDistance sym algo, ListLike full sym) => BKTree full algo
- insert :: (EditDistance sym algo, ListLike full sym) => full -> BKTree full algo -> BKTree full algo
- query :: (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)]
Data type
Operations
empty :: forall full sym algo. (EditDistance sym algo, ListLike full sym) => BKTree full algoSource
insert :: (EditDistance sym algo, ListLike full sym) => full -> BKTree full algo -> BKTree full algoSource
query :: (ListLike full sym, EditDistance sym algo) => Int -> full -> BKTree full algo -> [(full, Distance algo)]Source
levenshtein :: (ListLike full sym, EditDistance sym Levenshtein) => Int -> full -> BKTree full Levenshtein -> [(full, Distance Levenshtein)]Source
damerauLevenshtein :: (ListLike full sym, EditDistance sym DamerauLevenshtein) => Int -> full -> BKTree full DamerauLevenshtein -> [(full, Distance DamerauLevenshtein)]Source