-
-
Notifications
You must be signed in to change notification settings - Fork 9
/
fuzzy.ts
145 lines (137 loc) · 3.2 KB
/
fuzzy.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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// Trivial fuzzy sorter written by TANIGUCHI Masaya
// Public Domain
export interface Match {
pos: number[];
score: number;
}
export function scoreMatch(source: string, pos: number[]): number {
if (pos.length === 0) {
return 0;
}
const length = pos.length > 1 ? pos.at(-1)! - pos[0] + 1 : 1;
let ngroup = 1;
for (let i = 1; i < pos.length; i++) {
if (pos[i - 1] + 1 !== pos[i]) {
ngroup += 1;
}
}
let score = 0;
score += 1 / ngroup;
score += 1 / (pos[0] + 1) / 10;
score += 1 / length / 100;
score += 1 / source.length / 1000;
return score;
}
export function findAllMatches(
pattern: string,
source: string,
threshold = 100,
): Match[] {
if (pattern.length === 0) {
return [];
}
const h = new Map<string, number[]>();
for (let i = 0; i < source.length; i++) {
const c = source[i];
h.has(c) || h.set(c, []);
h.get(c)!.push(i);
}
if (Array.from(pattern).some((c) => !h.has(c))) {
return [];
}
const thresholdFilter = (posList: number[][]): number[][] => {
if (threshold === 0 || posList.length <= threshold) {
return posList;
}
// filter by last pos is more lower
return posList.sort((a, b) => {
for (let i = a.length - 1; i >= 0; --i) {
const d = a[i] - b[i];
if (d) return d;
}
return 0;
}).slice(0, threshold);
};
const posList = Array.from(pattern).slice(1).reduce(
(oldPosList, c): number[][] => {
const newPosList = [];
const patPosList = h.get(c)!;
for (const oldPos of oldPosList) {
const last = oldPos.at(-1)!;
for (const j of patPosList) {
if (last < j) {
newPosList.push(oldPos.concat(j));
}
}
}
return thresholdFilter(newPosList);
},
thresholdFilter(h.get(pattern[0])!.map((c) => [c])),
);
return posList.map((pos): Match => ({
pos,
score: scoreMatch(source, pos),
}));
}
export function findBestMatch(
pattern: string,
source: string,
threshold?: number,
): Match {
let bestMatch: Match = { pos: [], score: -Infinity };
for (const m of findAllMatches(pattern, source, threshold)) {
if (m.score > bestMatch.score) {
bestMatch = m;
}
}
return bestMatch;
}
export function score(
pattern: string,
source: string,
threshold?: number,
): number {
return findBestMatch(pattern, source, threshold).score;
}
export function match(
pattern: string,
source: string,
threshold?: number,
): number[] {
return findBestMatch(pattern, source, threshold).pos;
}
export function ctest(pattern: string, source: string): boolean {
let p = 0;
let s = 0;
while (p < pattern.length) {
if (s >= source.length) {
return false;
}
if (pattern[p] === source[s]) {
p++;
}
s++;
}
return true;
}
export function wtest(pattern: string, source: string): boolean {
let p = 0;
let s = 0;
let m = true;
while (p < pattern.length) {
if (s >= source.length) {
return false;
}
const w = m ||
/[^a-zA-Z]/.test(source[s - 1]) ||
/[a-z][A-Z]/.test(source.slice(s - 1, s + 1));
if (w && pattern[p] === source[s]) {
p++;
m = true;
} else {
m = false;
}
s++;
}
return true;
}