-
Notifications
You must be signed in to change notification settings - Fork 0
/
levenshtein.gleam
77 lines (74 loc) 路 1.85 KB
/
levenshtein.gleam
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
import gleam/int
import gleam/list
import gleam/result
import gleam/string
/// Compute the edit distance between two strings using the
/// [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance).
///
/// ## Examples
///
/// ```gleam
/// > distance("gleam", "beam")
/// 2
/// ```
///
/// ```gleam
/// > distance("cat", "cap")
/// 1
/// ```
///
pub fn distance(one: String, other: String) -> Int {
case one, other {
_, _ if one == other -> 0
"", string | string, "" -> string.length(string)
one, other -> {
let one = string.to_graphemes(one)
let other = string.to_graphemes(other)
let distance_list = list.range(0, list.length(other))
do_distance(one, other, distance_list, 1)
}
}
}
fn do_distance(
one: List(String),
other: List(String),
distance_list: List(Int),
step: Int,
) -> Int {
case one {
[] -> result.unwrap(list.last(distance_list), -1)
[first, ..rest] -> {
let distance_list =
update_distance_list(other, distance_list, first, step, [step])
do_distance(rest, other, distance_list, step + 1)
}
}
}
fn update_distance_list(
other: List(String),
distance_list: List(Int),
grapheme: String,
last_distance: Int,
acc: List(Int),
) -> List(Int) {
case other {
[] -> list.reverse(acc)
[first, ..rest] ->
case distance_list {
[] -> panic
[first_dist, ..rest_dist] -> {
let difference = case grapheme == first {
False -> 1
True -> 0
}
let min = case rest_dist {
[second_dist, ..] ->
int.min(first_dist + difference, last_distance + 1)
|> int.min(second_dist + 1)
_ -> int.min(first_dist + difference, last_distance + 1)
}
update_distance_list(rest, rest_dist, grapheme, min, [min, ..acc])
}
}
}
}