package mula

  1. Overview
  2. Docs
ML's Universal Levenshtein Automata library

Install

Dune Dependency

Authors

Maintainers

Sources

mula-0.1.2.tbz
sha256=1f0ee42aca73e33459796baa26063bf82d290cb6f4c723d3e7c9a0e58f1e0d72
sha512=2158fb0cfd32b819141fca66ab29dbe480303191e744e617661aa39d772d03e2e158b4ca1ff4a8e18e9c1ea71cda10fe07b62df72beba04e29b289975f19f66e

Description

ML's radishal Universal Levenshtein Automata library.

Published: 10 Dec 2021

README

mula

ML's radishal library for matching with Universal Levenshtein Automata.

This library not only computes if strings are within a certain edit distance, but also computes what the edit distance is.

You can find documentation for the library here.

We support both the standard Levenshtein distance as well as the Demarau-Levenshtein distance which includes transpositions of two adjacent characters as a primitive edit operation.

We can also lazily feed characters into automata and get the current edit distance.

For OCaml strings, we offer the Mula.Strings module which contains submodules Lev for the standard Levenshtein distance and Dem for the (restricted) Demarau-Levenshtein distance.

Examples of use:

# #require "mula";;
# Mula.Strings.Lev.get_distance ~k:2 "abcd" "abdc";;
- : int option = Some 2
# Mula.Strings.Dem.get_distance ~k:2 "abcd" "abdc";;
- : int option = Some 1
# Mula.Strings.Lev.get_distance ~k:2 "abcd" "efgh";;
- : int option = None

We can also lazily feed characters and strings into an nfa and get live error counts:

# let lev_nfa = Mula.Strings.Lev.start ~k:2 ~str:"abcd";;
val lev_nfa : Mula.Strings.Lev.nfa_state = <abstr>
# Mula.Strings.Lev.(feed_str lev_nfa ~str:"ab" |> current_error);;
- : int option = Some 0
# Mula.Strings.Lev.(feed lev_nfa ~ch:'a' |> feed ~ch:'b' |> feed ~ch:'c' |> current_error);;
- : int option = Some 0
# Mula.Strings.Lev.(feed_str lev_nfa ~str:"abd" |> current_error);;
- : int option = Some 1
# Mula.Strings.Lev.(feed_str lev_nfa ~str:"ab" |> feed_str ~str:"dc" |> current_error);; (* counts 'd' as an insert edit *)
- : int option = Some 1
# Mula.Strings.Lev.(feed_str lev_nfa ~str:"ab" |> feed_str ~str:"dc" |> end_input);;
- : int option = Some 2

Mula also offers a functor if you want to use your own representations of strings:

# #require "mula";;
# module St = struct
  type ch = int
  type t = int array

  let length = Array.length
  let get = Array.get

  let equal = Int.equal
end;;
module St :
  sig
    ...
  end
# module M = Mula.Match.Make(St);;
module M :
  sig
    module Lev :
      sig
        type nfa_state = Mula.Match.Make(St).Lev.nfa_state
        val start : k:int -> str:St.t -> nfa_state
        val feed : nfa_state -> ch:int -> nfa_state
        val current_error : nfa_state -> int option
        val end_input : nfa_state -> int option
        val feed_str : nfa_state -> str:St.t -> nfa_state
        val get_distance : k:int -> St.t -> St.t -> int option
      end
    module Dem :
      sig
        ...
      end
  end

About the Name

মুলা (mula/moola) means radish in the author's first language.

Dependencies (2)

  1. ocaml >= "4.08.1"
  2. dune >= "2.8"

Dev Dependencies (2)

  1. odoc with-doc
  2. ppx_inline_test with-test

Used by

None

Conflicts

None

OCaml

Innovation. Community. Security.