bktrees

A set data structure with approximate searching

Latest on Hackage:0.3.1

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

BSD3 licensed by Josef Svenningsson
This is a module I hacked together quickly after having read the following
blog post:
http://blog.notdot.net/archives/30-Damn-Cool-Algorithms,-Part-1-BK-Trees.html

I thought the data structure sounded cool so I thought it would be an
interesting excerise to implement it.

BK-trees can apparently perform very good in some circumstances. The
paper "Fast Approximate String Matching in a Dictionary" (Baeza-Yates,
Navarro 1998) recommends them over other structures for doing
approximate search.
http://citeseer.ist.psu.edu/1593.html

The original paper can be found here:
http://portal.acm.org/citation.cfm?id=362003.362025

Henning G√ľnter <h.guenther@tu-bs.de> generously supplied two algorithms for
computing the levenshtein edit distance. The better one of the two is used in
the list instance for the Metric class.
Depends on:
Used by 1 package:
comments powered byDisqus