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