(** Edition distance between two strings (dynamic algorithm) *)
let edit_distance sa sb =
let la, lb = String.length sa, String.length sb in
let t = Array.create_matrix (la + 1) (lb + 1) (-1) in
for i = 0 to la do
t.(i).(lb) <- (la - i)
done;
for j = 0 to lb do
t.(la).(j) <- (lb - j)
done;
for i = la - 1 downto 0 do
for j = lb - 1 downto 0 do
t.(i).(j) <- min
(1 + min t.(i+1).(j) t.(i).(j+1))
(t.(i+1).(j+1) + if sa.[i] = sb.[j] then 0 else 1)
done
done;
t.(0).(0)
(** Spell-correcting choice in a string association list
If the given key is not found in the assoc list, use edit distance
to determine the likely candidate. First, sort the assoc by
increasing order of edit distance to the key. Next, we could
choose the first candidate (minimal edit distance), but that could
lead to absurd choices :
- if the list is a singleton, we would always choose the first, no
matter how big the error is. If it's really not what the user
typed, it can be more helpful to report the mistake instead of
making a dumb choice.
- if they are different candidates of nearby edit distances to the
key, we cannot make a meaningful choice : any of the first items
would be as good.
Therefore :
- if the list is a singleton, we only choose its element if the
edit distance is inferior to a fixed constant (3).
- if there are a least two elements, we only choose the first one
if its edit distance is twice shorter than the second one
(unambiguous choice).
*)
let select_nearest key_string get_string list =
let list' =
let weight elem =
(edit_distance key_string (get_string elem), elem) in
List.map weight list in
let list' = List.sort (fun (k1, _) (k2, _) -> compare k1 k2) list' in
match list' with
| [] -> None
| (key, elem)::[] -> if key <= 3 then Some elem else None
| (k1, elem)::(k2, _)::_ -> if 2 * k1 < k2 then Some elem else None
Hello,
I grew tired of the Arg module. For a quick and easy way to make your
functions available from the command line you may be interested in
Cmdliner :
Cmdliner is a module for the declarative definition of command line interfaces.
It provides a simple and compositional mechanism to convert command
line arguments to OCaml values and pass them to your functions. The
module automatically handles syntax errors, help messages and UNIX man
page generation. It supports programs with single or multiple commands
(like darcs or git) and respect most of the POSIX and GNU conventions.
Cmdliner is made of a single, independent, module and distributed
under the BSD3 license.
Project home page : http://erratique.ch/software/cmdliner
The basics section of the documentation can be read as tutorial introduction:
http://erratique.ch/software/cmdliner/doc/Cmdliner#basics
Your feedback is welcome.
Daniel
P.S. The examples use syntactic constructs only available in 3.12
however I took care not to use them in the implementation of Cmdliner
itself.
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs