foxxmd.dev
[READ-ONLY] Mirror of https://github.com/FoxxMD/string-sameness. Compare the sameness of two strings
foxxmd.github.io/string-sameness/
compare
cosine-similarity
dice-coefficient
levenshtein-distance
sameness
string
text
typescript
6.0 kB
182 lines
1import {cosineStrategy, levenStrategy, diceStrategy, cosineStrategyAggressive} from "./matchingStrategies/index.js";
2import {
3 ComparisonStrategyResult,
4 NamedComparisonStrategyObjectResult,
5 StringComparisonOptions,
6 StringSamenessResult,
7 StringTransformFunc
8} from "./atomic.js";
9import {strDefaultTransforms, transforms} from "./normalization/index.js";
10
11const sentenceLengthWeight = (length: number) => {
12 // thanks jordan :')
13 // constants are black magic
14 return (Math.log(length) / 0.20) - 5;
15}
16
17const defaultStrategies = [
18 diceStrategy,
19 levenStrategy,
20 cosineStrategy
21]
22
23const stringSameness = (valA: string, valB: string, options?: StringComparisonOptions): StringSamenessResult => {
24
25 const {
26 transforms = strDefaultTransforms,
27 strategies = defaultStrategies,
28 reorder = false,
29 delimiter = ' '
30 } = options || {};
31
32 let cleanA = transforms.reduce((acc, curr) => curr(acc), valA);
33 let cleanB = transforms.reduce((acc, curr) => curr(acc), valB);
34
35 if (reorder) {
36 // we want to ignore order of tokens as much as possible (user does not care about differences in word order, just absolute differences in characters overall)
37 // so we will reorder the shorter of the two strings so its tokens match the order of tokens in the longer string as closely as possible
38 // before we run strategies
39 const [orderedX, orderedY] = reorderStr(cleanA, cleanB);
40 cleanA = orderedX;
41 cleanB = orderedY;
42 }
43
44 const shortest = cleanA.length > cleanB.length ? cleanB : cleanA;
45
46 const stratResults: NamedComparisonStrategyObjectResult[] = [];
47
48 for (const strat of strategies) {
49 if (strat.isValid !== undefined && !strat.isValid(cleanA, cleanB)) {
50 continue;
51 }
52 const res = strat.strategy(cleanA, cleanB);
53 const resObj = typeof res === 'number' ? {score: res} : res;
54 stratResults.push({
55 ...resObj,
56 name: strat.name
57 });
58 }
59
60 // use shortest sentence for weight
61 const weightScore = sentenceLengthWeight(shortest.length);
62
63 // take average score
64 const highScore = stratResults.reduce((acc, curr) => acc + curr.score, 0) / stratResults.length;
65 // weight score can be a max of 15
66 const highScoreWeighted = highScore + Math.min(weightScore, 15);
67 const stratObj = stratResults.reduce((acc: { [key: string]: ComparisonStrategyResult }, curr) => {
68 const {name, score, ...rest} = curr;
69 acc[curr.name] = {
70 ...rest,
71 score,
72 };
73 return acc;
74 }, {});
75 return {
76 strategies: stratObj,
77 highScore,
78 highScoreWeighted,
79 }
80}
81
82export const reorderStr = (strA: string, strB: string, options?: StringComparisonOptions): [string, string] => {
83
84 const {
85 transforms = strDefaultTransforms,
86 strategies = defaultStrategies,
87 delimiter = ' '
88 } = options || {};
89
90 const cleanA = transforms.reduce((acc, curr) => curr(acc), strA);
91 const cleanB = transforms.reduce((acc, curr) => curr(acc), strB);
92
93 // split by "token"
94 const eTokens = cleanA.split(delimiter);
95 const cTokens = cleanB.split(delimiter);
96
97
98 let longerTokens: string[],
99 shorterTokens: string[];
100
101 if (eTokens.length > cTokens.length) {
102 longerTokens = eTokens;
103 shorterTokens = cTokens;
104 } else {
105 longerTokens = cTokens;
106 shorterTokens = eTokens;
107 }
108
109 // we will use longest string (token list) as the reducer and order the shorter list to match it
110 // so we don't have to deal with undefined positions in the shorter list
111
112 const orderedCandidateTokens = longerTokens.reduce((acc: { ordered: string[], remaining: string[] }, curr) => {
113 // if we've run out of tokens in the shorter list just return
114 if (acc.remaining.length === 0) {
115 return acc;
116 }
117
118 // on each iteration of tokens in the long list
119 // we iterate through remaining tokens from the shorter list and find the token with the most sameness
120
121 let highScore = 0;
122 let highIndex = 0;
123 let index = 0;
124 for (const token of acc.remaining) {
125 const result = stringSameness(curr, token, {strategies});
126 if (result.highScoreWeighted > highScore) {
127 highScore = result.highScoreWeighted;
128 highIndex = index;
129 }
130 index++;
131 }
132
133 // then remove the most same token from the remaining short list tokens
134 const splicedRemaining = [...acc.remaining];
135 splicedRemaining.splice(highIndex, 1);
136
137 return {
138 // finally add the most same token to the ordered short list
139 ordered: acc.ordered.concat(acc.remaining[highIndex]),
140 // and return the remaining short list tokens
141 remaining: splicedRemaining
142 };
143 }, {
144 // "ordered" is the result of ordering tokens in the shorter list to match longer token order
145 ordered: [],
146 // remaining is the initial shorter list
147 remaining: shorterTokens
148 });
149
150 return [longerTokens.join(' '), orderedCandidateTokens.ordered.join(' ')];
151}
152
153const createStringSameness = (defaults: StringComparisonOptions) => {
154 return (valA: string, valB: string, options: StringComparisonOptions = {}) => stringSameness(valA, valB, {...defaults, ...options});
155}
156
157const strategies = {
158 diceStrategy,
159 levenStrategy,
160 cosineStrategy,
161 cosineStrategyAggressive
162};
163
164// maintaining compatibility
165const defaultStrCompareTransformFuncs = strDefaultTransforms;
166
167export {
168 stringSameness,
169 createStringSameness,
170 defaultStrategies,
171 strategies,
172 transforms,
173 defaultStrCompareTransformFuncs,
174 strDefaultTransforms,
175}
176
177export type {
178 StringSamenessResult,
179 StringComparisonOptions,
180 ComparisonStrategyResult,
181 StringTransformFunc
182}