package wu-manber-fuzzy-search

  1. Overview
  2. Docs

Wu and Manber algorithm modified for right leaning matches.

The right leaning variant of the algorithm requires the user to feed k sentinel characters into the algorithm at the end of the text to get matches near the end, where k is the error limit that the algorithm was started with. See the code for the FirstMatch module for an example.

val initial_bvs : k:int -> Optint.Int63.t array

initial_bv ~k creates a starting array of bitvectors used by the algorithm.

val next_bvs : mismatch:Optint.Int63.t -> Optint.Int63.t array -> Optint.Int63.t array

next_bvs ~pattern_length ~mismatch bvs produces an updated bitvector array based on ~mismatch. pattern_length must be less than or equal 63.

val feed_sentinel : Optint.Int63.t array -> Optint.Int63.t array

next_bvs ~pattern_length bvs produces an updated bitvector array assuming that a sentinel character different from anything in the alphabet is being fed into the algorithm. pattern_length must be less than or equal 63.

OCaml

Innovation. Community. Security.