-
-
Notifications
You must be signed in to change notification settings - Fork 84
/
distanceAStar.ts
75 lines (62 loc) · 1.83 KB
/
distanceAStar.ts
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
import { PairingHeap } from '../utils/PairingHeap';
/**
* Calculate the edit distance between two words using an A* algorithm.
*
* Using basic weights, this algorithm has the same results as the Damerau-Levenshtein algorithm.
*/
export function distanceAStar(a: string, b: string): number {
const aN = a.length;
const bN = b.length;
const cost = 100;
const candidates = new PairingHeap(compare);
candidates.add({ ai: 0, bi: 0, c: 0 });
function opSub(n: Node) {
const { ai, bi, c } = n;
if (ai < aN && bi < bN) {
const cc = a[ai] === b[bi] ? c : c + cost;
candidates.add({ ai: ai + 1, bi: bi + 1, c: cc });
}
}
function opIns(n: Node) {
const { ai, bi, c } = n;
if (bi < bN) {
candidates.add({ ai: ai, bi: bi + 1, c: c + cost });
}
}
function opDel(n: Node) {
const { ai, bi, c } = n;
if (ai < aN) {
candidates.add({ ai: ai + 1, bi: bi, c: c + cost });
}
}
function opSwap(n: Node) {
const { ai, bi, c } = n;
if (a[ai] === b[bi + 1] && a[ai + 1] === b[bi]) {
candidates.add({ ai: ai + 2, bi: bi + 2, c: c + cost });
}
}
let best: Node | undefined;
// const bc2 = 2 * bc;
while ((best = candidates.dequeue())) {
if (best.ai === aN && best.bi === bN) break;
opSwap(best);
opIns(best);
opDel(best);
opSub(best);
}
return best?.c ?? -1;
}
interface Pos {
/** the offset in string `a` */
ai: number;
/** the offset in string `b` */
bi: number;
}
interface Node extends Pos {
/** the current cost */
c: number;
}
function compare(a: Node, b: Node): number {
// Choose lowest cost or farthest Manhattan distance.
return a.c - b.c || b.ai + b.bi - a.ai - a.bi;
}