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 (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 BKTree full algo
- 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)]
Data type
Operations
insert :: forall full sym algo. (Eq sym, EditDistance sym algo, ListLike full sym) => full -> BKTree full algo -> BKTree full algoSource
query :: forall full sym algo. (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