1 | export function levenshtein(a, b) {
|
2 | if (a.length === 0) {
|
3 | return b.length;
|
4 | }
|
5 | if (b.length === 0) {
|
6 | return a.length;
|
7 | }
|
8 | var matrix = [];
|
9 | var i;
|
10 | for (i = 0; i <= b.length; i++) {
|
11 | matrix[i] = [i];
|
12 | }
|
13 | var j;
|
14 | for (j = 0; j <= a.length; j++) {
|
15 | matrix[0][j] = j;
|
16 | }
|
17 | for (i = 1; i <= b.length; i++) {
|
18 | for (j = 1; j <= a.length; j++) {
|
19 | if (b.charAt(i - 1) === a.charAt(j - 1)) {
|
20 | matrix[i][j] = matrix[i - 1][j - 1];
|
21 | }
|
22 | else {
|
23 | matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, Math.min(matrix[i][j - 1] + 1, matrix[i - 1][j] + 1));
|
24 | }
|
25 | }
|
26 | }
|
27 | return matrix[b.length][a.length];
|
28 | }
|
29 | export function newDistanceFn(str) {
|
30 | return function (x, y) {
|
31 | var xValue = str(x).trim();
|
32 | var yValue = str(y).trim();
|
33 | var lev = levenshtein(xValue, yValue);
|
34 | return lev / (xValue.length + yValue.length);
|
35 | };
|
36 | }
|
37 | export function newMatcherFn(distance) {
|
38 | function findBestMatch(a, b, cache) {
|
39 | if (cache === void 0) { cache = new Map(); }
|
40 | var bestMatchDist = Infinity;
|
41 | var bestMatch;
|
42 | for (var i = 0; i < a.length; ++i) {
|
43 | for (var j = 0; j < b.length; ++j) {
|
44 | var cacheKey = JSON.stringify([a[i], b[j]]);
|
45 | var md = void 0;
|
46 | if (!(cache.has(cacheKey) && (md = cache.get(cacheKey)))) {
|
47 | md = distance(a[i], b[j]);
|
48 | cache.set(cacheKey, md);
|
49 | }
|
50 | if (md < bestMatchDist) {
|
51 | bestMatchDist = md;
|
52 | bestMatch = { indexA: i, indexB: j, score: bestMatchDist };
|
53 | }
|
54 | }
|
55 | }
|
56 | return bestMatch;
|
57 | }
|
58 | function group(a, b, level, cache) {
|
59 | if (level === void 0) { level = 0; }
|
60 | if (cache === void 0) { cache = new Map(); }
|
61 | var bm = findBestMatch(a, b, cache);
|
62 | if (!bm || a.length + b.length < 3) {
|
63 | return [[a, b]];
|
64 | }
|
65 | var a1 = a.slice(0, bm.indexA);
|
66 | var b1 = b.slice(0, bm.indexB);
|
67 | var aMatch = [a[bm.indexA]];
|
68 | var bMatch = [b[bm.indexB]];
|
69 | var tailA = bm.indexA + 1;
|
70 | var tailB = bm.indexB + 1;
|
71 | var a2 = a.slice(tailA);
|
72 | var b2 = b.slice(tailB);
|
73 | var group1 = group(a1, b1, level + 1, cache);
|
74 | var groupMatch = group(aMatch, bMatch, level + 1, cache);
|
75 | var group2 = group(a2, b2, level + 1, cache);
|
76 | var result = groupMatch;
|
77 | if (bm.indexA > 0 || bm.indexB > 0) {
|
78 | result = group1.concat(result);
|
79 | }
|
80 | if (a.length > tailA || b.length > tailB) {
|
81 | result = result.concat(group2);
|
82 | }
|
83 | return result;
|
84 | }
|
85 | return group;
|
86 | }
|
87 |
|
\ | No newline at end of file |