src/vs/base/common/tfIdf.ts
240 LOC · 221 covered · 19 uncovered · 27 ranges · 10 concepts · 8 introducers · 10 tests
File neighbourhood
The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.
Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file
In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.
Graph controls are ready.
Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.
1
>
/*---------------------------------------------------------------------------------------------
tfIdf.ts ×8
2
>
* Copyright (c) Microsoft Corporation. All rights reserved.
3
>
* Licensed under the MIT License. See License.txt in the project root for license information.
4
>
*--------------------------------------------------------------------------------------------*/
5
>
6
>
import { CancellationToken } from './cancellation.js';
7
>
8
>
type SparseEmbedding = Record</* word */ string, /* weight */number>;
9
>
type TermFrequencies = Map</* word */ string, /*occurrences*/ number>;
10
>
type DocumentOccurrences = Map</* word */ string, /*documentOccurrences*/ number>;
11
>
12
>
function countMapFrom<K>(values: Iterable<K>): Map<K, number> {
13
>
const map = new Map<K, number>();
14
>
for (const value of values) {
15
>
map.set(value, (map.get(value) ?? 0) + 1);
16
>
}
17
>
return map;
18
>
}
19
>
20
>
interface DocumentChunkEntry {
21
>
readonly text: string;
22
>
readonly tf: TermFrequencies;
23
>
}
24
>
25
>
export interface TfIdfDocument {
26
>
readonly key: string;
27
>
readonly textChunks: readonly string[];
28
>
}
29
>
30
>
export interface TfIdfScore {
31
>
readonly key: string;
32
>
/**
33
>
* An unbounded number.
34
>
*/
35
>
readonly score: number;
36
>
}
37
>
38
>
export interface NormalizedTfIdfScore {
39
>
readonly key: string;
40
>
/**
41
>
* A number between 0 and 1.
42
>
*/
43
>
readonly score: number;
44
>
}
45
>
46
>
/**
47
>
* Implementation of tf-idf (term frequency-inverse document frequency) for a set of
48
>
* documents where each document contains one or more chunks of text.
49
>
* Each document is identified by a key, and the score for each document is computed
50
>
* by taking the max score over all the chunks in the document.
51
>
*/
52
>
export class TfIdfCalculator {
53
>
calculateScores(query: string, token: CancellationToken): TfIdfScore[] {
54
>
const embedding = this.computeEmbedding(query);
55
>
const idfCache = new Map<string, number>();
56
>
const scores: TfIdfScore[] = [];
57
>
// For each document, generate one score
58
>
for (const [key, doc] of this.documents) {
60
return [];
61
}
63
>
for (const chunk of doc.chunks) {
64
>
const score = this.computeSimilarityScore(chunk, embedding, idfCache);
65
>
if (score > 0) {
67
>
}
69
>
}
71
>
return scores;
72
>
}
73
>
74
>
/**
75
>
* Count how many times each term (word) appears in a string.
76
>
*/
77
>
private static termFrequencies(input: string): TermFrequencies {
78
>
return countMapFrom(TfIdfCalculator.splitTerms(input));
79
>
}
80
>
81
>
/**
82
>
* Break a string into terms (words).
83
>
*/
84
>
private static *splitTerms(input: string): Iterable<string> {
85
>
const normalize = (word: string) => word.toLowerCase();
86
>
87
>
// Only match on words that are at least 3 characters long and start with a letter
88
>
for (const [word] of input.matchAll(/\b\p{Letter}[\p{Letter}\d]{2,}\b/gu)) {
89
>
yield normalize(word);
90
>
91
>
const camelParts = word.replace(/([a-z])([A-Z])/g, '$1 $2').split(/\s+/g);
92
>
if (camelParts.length > 1) {
94
>
// Require at least 3 letters in the parts of a camel case word
95
>
if (part.length > 2 && /\p{Letter}{3,}/gu.test(part)) {
97
>
}
99
>
}
101
>
}
102
>
103
>
/**
104
>
* Total number of chunks
105
>
*/
106
>
private chunkCount = 0;
107
>
108
>
private readonly chunkOccurrences: DocumentOccurrences = new Map</* word */ string, /*documentOccurrences*/ number>();
109
>
110
>
private readonly documents = new Map</* key */ string, {
111
>
readonly chunks: ReadonlyArray<DocumentChunkEntry>;
112
>
}>();
113
>
114
>
updateDocuments(documents: ReadonlyArray<TfIdfDocument>): this {
116
>
this.deleteDocument(key);
117
>
}
118
>
119
>
for (const doc of documents) {
120
>
const chunks: Array<{ text: string; tf: TermFrequencies }> = [];
121
>
for (const text of doc.textChunks) {
122
>
// TODO: See if we can compute the tf lazily
123
>
// The challenge is that we need to also update the `chunkOccurrences`
124
>
// and all of those updates need to get flushed before the real TF-IDF of
125
>
// anything is computed.
126
>
const tf = TfIdfCalculator.termFrequencies(text);
127
>
128
>
// Update occurrences list
129
>
for (const term of tf.keys()) {
130
>
this.chunkOccurrences.set(term, (this.chunkOccurrences.get(term) ?? 0) + 1);
131
>
}
132
>
133
>
chunks.push({ text, tf });
134
>
}
135
>
136
>
this.chunkCount += chunks.length;
137
>
this.documents.set(doc.key, { chunks });
138
>
}
139
>
return this;
140
>
}
142
>
deleteDocument(key: string) {
144
>
if (!doc) {
145
>
return;
146
>
}
148
>
this.documents.delete(key);
149
>
this.chunkCount -= doc.chunks.length;
150
>
151
>
// Update term occurrences for the document
152
>
for (const chunk of doc.chunks) {
153
>
for (const term of chunk.tf.keys()) {
154
>
const currentOccurrences = this.chunkOccurrences.get(term);
155
>
if (typeof currentOccurrences === 'number') {
156
>
const newOccurrences = currentOccurrences - 1;
157
>
if (newOccurrences <= 0) {
158
>
this.chunkOccurrences.delete(term);
159
>
} else {
160
>
this.chunkOccurrences.set(term, newOccurrences);
161
>
}
162
>
}
163
>
}
164
>
}
167
>
private computeSimilarityScore(chunk: DocumentChunkEntry, queryEmbedding: SparseEmbedding, idfCache: Map<string, number>): number {
169
>
170
>
// Note that the chunk embedding is computed lazily on a per-term basis.
171
>
// This lets us skip a large number of calculations because the majority
172
>
// of chunks do not share any terms with the query.
173
>
174
>
let sum = 0;
175
>
for (const [term, termTfidf] of Object.entries(queryEmbedding)) {
177
>
if (!chunkTf) {
179
>
continue;
180
>
}
182
>
let chunkIdf = idfCache.get(term);
183
>
if (typeof chunkIdf !== 'number') {
184
>
chunkIdf = this.computeIdf(term);
185
>
idfCache.set(term, chunkIdf);
186
>
}
187
>
188
>
const chunkTfidf = chunkTf * chunkIdf;
189
>
sum += chunkTfidf * termTfidf;
190
>
}
192
>
}
194
>
private computeEmbedding(input: string): SparseEmbedding {
195
>
const tf = TfIdfCalculator.termFrequencies(input);
196
>
return this.computeTfidf(tf);
197
>
}
198
>
199
>
private computeIdf(term: string): number {
200
>
const chunkOccurrences = this.chunkOccurrences.get(term) ?? 0;
201
>
return chunkOccurrences > 0
205
>
206
>
private computeTfidf(termFrequencies: TermFrequencies): SparseEmbedding {
207
>
const embedding = Object.create(null);
208
>
for (const [word, occurrences] of termFrequencies) {
209
>
const idf = this.computeIdf(word);
210
>
if (idf > 0) {
212
>
}
214
>
return embedding;
215
>
}
216
>
}
217
>
218
>
/**
219
>
* Normalize the scores to be between 0 and 1 and sort them decending.
220
>
* @param scores array of scores from {@link TfIdfCalculator.calculateScores}
221
>
* @returns normalized scores
222
>
*/
223
>
export function normalizeTfIdfScores(scores: TfIdfScore[]): NormalizedTfIdfScore[] {
224
225
// copy of scores
226
const result = scores.slice(0) as { score: number }[];
227
228
// sort descending
229
result.sort((a, b) => b.score - a.score);
230
231
// normalize
232
const max = result[0]?.score ?? 0;
233
if (max > 0) {
234
for (const score of result) {
235
score.score /= max;
236
}
237
}
238
239
return result as TfIdfScore[];
240
}