package baguette_sharp

  1. Overview
  2. Docs

Source file levenshtein.ml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
let list_of_funct =
  [
    "PAINAUCHOCOLAT";
    "PAINVIENNOIS";
    "CROISSANT";
    "MADELEINE";
    "ECLAIR";
    "CANELE";
    "STHONORE";
    "KOUGNAMANN";
    "PROFITEROLE";
    "FINANCIER";
    "PAINAURAISIN";
    "CHOCOLATINE";
    "BRETZEL";
    "BAGUETTEVIENNOISE";
    "OPERA";
    "MILLEFEUILLE";
    "FRAISIER";
    "QUATREQUART";
    "TIRAMISU";
    "MERINGUE";
    "MERVEILLE";
    "BRIOCHE";
    "TARTE";
    "FLAN";
    "PAINDEPICE";
    "CREPE";
    "CHAUSSONAUXPOMMES";
    "SABLE";
    "CHOUQUETTE";
    "CLAFOUTIS";
    "PARISBREST";
    "TARTEAUXFRAISES";
    "TARTEAUXFRAMBOISES";
    "TARTEAUXPOMMES";
    "TARTEALARHUBARBE";
    "GLACE";
    "BEIGNET";
    "DOUGHNUT";
    "BUCHE";
    "GAUFFREDELIEGE";
    "GAUFFREDEBRUXELLE";
    "GAUFFRE";
    "PANCAKE";
    "SIROPDERABLE";
    "FROSTING";
    "CARROTCAKE";
    "GALETTEDESROIS";
    "FRANGIPANE";
    "BABAAURHUM";
    "CHARLOTTEAUXFRAISES";
    "BAGUETTE";
  ]

let minA s = String.sub s 1 (String.length s - 1)

(**Regular Slow AF levenshtein*)
let rec leven a b =
  let n, m = (String.length a, String.length b) in
  if min n m = 0 then max n m
  else if a.[0] = b.[0] then leven (minA a) (minA b)
  else
    1
    + min (min (leven (minA a) b) (leven a (minA b))) (leven (minA a) (minA b))

(**Fast DP Levenshtein algorithm Wagner/Fischer *)
let rapideLeven a b =
  let n, m = (String.length a, String.length b) in
  let d = Array.make_matrix (n + 1) (m + 1) 0 in
  let temp = ref 0 in
  for i = 0 to n do
    d.(i).(0) <- i
  done;
  for j = 0 to m do
    d.(0).(j) <- j
  done;
  for i = 1 to n do
    for j = 1 to m do
      if a.[i - 1] = b.[j - 1] then temp := 0 else temp := 1;
      d.(i).(j) <-
        min
          (min (d.(i - 1).(j) + 1) (d.(i).(j - 1) + 1))
          (d.(i - 1).(j - 1) + !temp)
    done
  done;
  d.(n).(m)

let select_minimal_distance_word word =
  let f s = (rapideLeven s word, s) in
  let l = list_of_funct in
  let l = List.map f l in
  let l = List.sort Stdlib.compare l in
  let _, w = List.hd l in
  w