package levenshtein

  1. Overview
  2. Docs

Levenshtein distance algorithm for general array.

Author: jun.furuse@gmail.com License: public domain

module type Array = sig ... end

Generic array type.

module type S = sig ... end

Simple implementation without cache

module Make (A : Array) : S with type t = A.t
module String : S with type t = string
type result =
  1. | Exact of int
  2. | GEQ of int
    (*

    Cache knows the result is greater than or equal to this value

    *)

Cached result

module type Cache = sig ... end

Cache

module CacheByHashtbl (H : Hashtbl.HashedType) : Cache with type key = H.t

Build a cache using OCaml stdlib's Hashtbl

module type WithCache = sig ... end
module MakeWithCache (A : Array) (C : Cache with type key = A.t * A.t) : WithCache with type t = A.t and type cache = result C.t
module StringWithHashtbl : WithCache with type t = string

Sample implementation for String, using OCaml stdlib's Hashtbl as a cache

OCaml

Innovation. Community. Security.