1type Suggestion = {2 key: string;3 text: string;4 score: number;5};67class RankedTrieNode {8 readonly children = new Map<string, RankedTrieNode>();9 terminal = false;10 top: Suggestion[] = [];11}1213function canonicalize(input: string, locale = "vi"): string {14 return input15 .normalize("NFC")16 .trim()17 .replace(/\s+/g, " ")18 .toLocaleLowerCase(locale);19}2021class RankedTrie {22 private readonly root = new RankedTrieNode();2324 constructor(private readonly topK = 10) {}2526 upsert(text: string, score: number): void {27 const key = canonicalize(text);28 if (!key) return;29 if (!Number.isFinite(score)) throw new Error("score must be finite");3031 const suggestion: Suggestion = { key, text, score };32 let node = this.root;33 this.updateTop(node, suggestion);3435 for (const character of Array.from(key)) {36 let child = node.children.get(character);3738 if (!child) {39 child = new RankedTrieNode();40 node.children.set(character, child);41 }4243 node = child;44 this.updateTop(node, suggestion);45 }4647 node.terminal = true;48 }4950 suggest(rawPrefix: string): Suggestion[] {51 const prefix = canonicalize(rawPrefix);52 let node = this.root;5354 for (const character of Array.from(prefix)) {55 const child = node.children.get(character);56 if (!child) return [];57 node = child;58 }5960 return node.top.map((item) => ({ ...item }));61 }6263 private updateTop(node: RankedTrieNode, incoming: Suggestion): void {64 const withoutSameKey = node.top.filter(65 (item) => item.key !== incoming.key,66 );6768 withoutSameKey.push(incoming);69 withoutSameKey.sort(70 (a, b) => b.score - a.score || a.text.localeCompare(b.text),71 );7273 node.top = withoutSameKey.slice(0, this.topK);74 }75}7677const autocomplete = new RankedTrie(3);78autocomplete.upsert("career", 980);79autocomplete.upsert("care", 720);80autocomplete.upsert("card", 610);81autocomplete.upsert("car", 500);8283autocomplete.suggest("car");
