-
Notifications
You must be signed in to change notification settings - Fork 28
/
utils_candidates.cljc
75 lines (60 loc) · 1.92 KB
/
utils_candidates.cljc
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
(ns cli-matic.utils-candidates
"
### String candidates tools.
This namespace contains utilities to compute string candidates.
")
;
; String distance
; Patch by https://github.com/l3nz/cli-matic/pull/49/commits/07c392301a9e12c2f8ad76fd8a9115e0632e175a
;
(defn- deep-merge-with
[f & maps]
(apply
(fn m [& maps]
(if (every? map? maps)
(apply merge-with m maps)
(apply f maps)))
maps))
(defn- levenshtein-distance
"Ref https://en.wikipedia.org/wiki/Levenshtein_distance "
[a b]
(let [m (count a)
n (count b)
init (apply deep-merge-with (fn [_ b] b)
(concat
(for [i (range 0 (+ 1 m))]
{i {0 i}})
(for [j (range 0 (+ 1 n))]
{0 {j j}})))
table (reduce
(fn [d [i j]]
(deep-merge-with
(fn [_ b] b)
d
{i {j (if (= (nth a (- i 1))
(nth b (- j 1)))
((d (- i 1)) (- j 1))
(min
(+ ((d (- i 1))
j) 1)
(+ ((d i)
(- j 1)) 1)
(+ ((d (- i 1))
(- j 1)) 1)))}}))
init
(for [j (range 1 (+ 1 n))
i (range 1 (+ 1 m))] [i j]))]
((table m) n)))
(defn str-distance
"Distance between two strings, as expressed in percentage
of changes to the length of the longest string.
"
[a b]
(/ (levenshtein-distance a b)
(max (count a) (count b) 1)))
(defn candidate-suggestions
"Returns candidate suggestions, in order of
reliability."
[candidates cmd max-str-distance]
(let [valid (filter #(<= (str-distance % cmd) max-str-distance) candidates)]
(sort-by (partial str-distance cmd) valid)))