1 | const { closest, distance } = require("./mod.js");
|
---|
2 |
|
---|
3 | const levenshtein = (a, b) => {
|
---|
4 | if (a.length === 0) {
|
---|
5 | return b.length;
|
---|
6 | }
|
---|
7 | if (b.length === 0) {
|
---|
8 | return a.length;
|
---|
9 | }
|
---|
10 |
|
---|
11 | if (a.length > b.length) {
|
---|
12 | const tmp = a;
|
---|
13 | a = b;
|
---|
14 | b = tmp;
|
---|
15 | }
|
---|
16 |
|
---|
17 | const row = [];
|
---|
18 | for (let i = 0; i <= a.length; i++) {
|
---|
19 | row[i] = i;
|
---|
20 | }
|
---|
21 |
|
---|
22 | for (let i = 1; i <= b.length; i++) {
|
---|
23 | let prev = i;
|
---|
24 | for (let j = 1; j <= a.length; j++) {
|
---|
25 | let val = 0;
|
---|
26 | if (b.charAt(i - 1) === a.charAt(j - 1)) {
|
---|
27 | val = row[j - 1];
|
---|
28 | } else {
|
---|
29 | val = Math.min(row[j - 1] + 1, prev + 1, row[j] + 1);
|
---|
30 | }
|
---|
31 | row[j - 1] = prev;
|
---|
32 | prev = val;
|
---|
33 | }
|
---|
34 | row[a.length] = prev;
|
---|
35 | }
|
---|
36 |
|
---|
37 | return row[a.length];
|
---|
38 | };
|
---|
39 |
|
---|
40 | const makeid = (length) => {
|
---|
41 | let result = "";
|
---|
42 | const characters =
|
---|
43 | "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
|
---|
44 | const charactersLength = characters.length;
|
---|
45 | for (let i = 0; i < length; i++) {
|
---|
46 | result += characters.charAt(Math.floor(Math.random() * charactersLength));
|
---|
47 | }
|
---|
48 | return result;
|
---|
49 | };
|
---|
50 |
|
---|
51 | test("test compare", () => {
|
---|
52 | for (let i = 0; i < 1000; i++) {
|
---|
53 | const rnd_num1 = (Math.random() * 1000) | 0;
|
---|
54 | const rnd_num2 = (Math.random() * 1000) | 0;
|
---|
55 | const rnd_string1 = makeid(rnd_num1);
|
---|
56 | const rnd_string2 = makeid(rnd_num2);
|
---|
57 | const actual = distance(rnd_string1, rnd_string2);
|
---|
58 | const expected = levenshtein(rnd_string1, rnd_string2);
|
---|
59 | expect(actual).toBe(expected);
|
---|
60 | }
|
---|
61 | });
|
---|
62 |
|
---|
63 | test("test find", () => {
|
---|
64 | const actual = closest("fast", ["slow", "faster", "fastest"]);
|
---|
65 | const expected = "faster";
|
---|
66 | expect(actual).toBe(expected);
|
---|
67 | });
|
---|