系統設計

1function tokenize(text: string): string[] {
2  return text.toLowerCase().match(/[a-z0-9]+/g) ?? [];
3}
4 
5function crawl(seeds: string[], links: Record<string, string[]>, limit: number): string[] {
6  const frontier = [...seeds];
7  const seen = new Set(seeds);
8  const fetched: string[] = [];
9  while (frontier.length > 0 && fetched.length < limit) {
10    const url = frontier.shift()!;
11    const outLinks = links[url] ?? [];
12    fetched.push(url);
13    for (const next of outLinks) {
14      if (!seen.has(next)) {
15        seen.add(next);
16        frontier.push(next);
17      }
18    }
19  }
20  return fetched;
21}
22 
23type Hit = [doc: number, score: number];
24const byScore = (a: Hit, b: Hit) => b[1] - a[1] || a[0] - b[0];
25 
26class Shard {
27  private postings = new Map<string, Map<number, number>>(); // term -> doc -> count
28 
29  add(term: string, doc: number): void {
30    const docs = this.postings.get(term) ?? new Map<number, number>();
31    docs.set(doc, (docs.get(doc) ?? 0) + 1);
32    this.postings.set(term, docs);
33  }
34 
35  topK(terms: string[], k: number): Hit[] {
36    const lists = terms.map((t) => this.postings.get(t) ?? new Map<number, number>());
37    const hits: Hit[] = [];
38    for (const [doc] of lists[0] ?? []) {
39      if (lists.every((list) => list.has(doc))) {
40        hits.push([doc, lists.reduce((sum, list) => sum + list.get(doc)!, 0)]);
41      }
42    }
43    return hits.sort(byScore).slice(0, k);
44  }
45}
46 
47class SearchService {
48  private cache = new Map<string, Hit[]>();
49 
50  constructor(private shards: Shard[]) {}
51 
52  index(doc: number, text: string): void {
53    const shard = this.shards[doc % this.shards.length];
54    for (const term of tokenize(text)) shard.add(term, doc);
55  }
56 
57  search(query: string, k: number): Hit[] {
58    const cached = this.cache.get(query);
59    if (cached) return cached;
60    const terms = tokenize(query);
61    const partial = this.shards.map((s) => s.topK(terms, k));
62    const merged = partial.flat().sort(byScore).slice(0, k);
63    this.cache.set(query, merged);
64    return merged;
65  }
66}