系統設計

1const STOP = new Set(["a", "an", "the", "in", "of", "to", "on", "and", "or", "is", "are", "be",
2  "can", "so", "when", "but", "it", "its", "into", "with", "one"]);
3 
4function tokenize(text: string): string[] {
5  return text.toLowerCase().split(/[^a-z]+/)
6    .filter((w) => w && !STOP.has(w));
7}
8 
9class InvertedIndex {
10  private postings = new Map<string, number[]>();
11 
12  // Add documents in id order and every posting list stays sorted.
13  add(docId: number, text: string): void {
14    for (const word of new Set(tokenize(text))) {
15      if (!this.postings.has(word)) this.postings.set(word, []);
16      this.postings.get(word)!.push(docId);
17    }
18  }
19 
20  search(query: string): number[] {
21    const words = [...new Set(tokenize(query))];
22    const lists = words.map((w) => this.postings.get(w) ?? []);
23    lists.sort((a, b) => a.length - b.length);
24    let result = lists[0] ?? [];
25    for (const list of lists.slice(1)) {
26      result = intersect(result, list);
27    }
28    return result;
29  }
30}
31 
32function intersect(a: number[], b: number[]): number[] {
33  const out: number[] = [];
34  let i = 0, j = 0;
35  while (i < a.length && j < b.length) {
36    if (a[i] === b[j]) {
37      out.push(a[i]); i++; j++;
38    } else if (a[i] < b[j]) i++;
39    else j++;
40  }
41  return out;
42}