@hackage / bktrees

A set data structure with approximate searching

Latest0.3.1

About

Metadata

  • Last updated , by JosefSvenningsson
  • License BSD-3-Clause
  • Categories Data Structures

  • Maintained by: josef.svenningsson@gmail.com

  • Lottery factor: 0

Links

Installation

Package Flags

Use the -f option with cabal commands to enable flags

    splitbase (on by default)

    Choose the new smaller, split-up base package.

Readme

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.