Trie: Giải thích tìm kiếm tiền tố tốc độ cao

Gõ git ch vào command palette, các gợi ý hữu ích đã xuất hiện trước khi câu lệnh hoàn chỉnh tồn tại. Nhập mar trong ô tìm liên hệ, những cái tên bắt đầu bằng ba ký tự ấy hiện ra gần như tức thì. Đây không phải bài toán tra cứu khóa chính xác thông thường: truy vấn còn dang dở, và mọi kết quả có chung tiền tố đều có thể phù hợp.

Hash table rất hiệu quả khi ta đã biết toàn bộ khóa, nhưng nó không lưu quan hệ giữa các khóa. Trie, đọc gần giống “try” và có tên bắt nguồn từ retrieval, biến quan hệ ấy thành cấu trúc rõ ràng. Mỗi cạnh đóng góp một ký hiệu; mỗi đường đi từ gốc biểu diễn một tiền tố. Các từ có phần đầu giống nhau dùng chung đường đi, vì vậy thời gian tìm tiền tố chủ yếu phụ thuộc vào độ dài tiền tố thay vì tổng số từ đã lưu.

Đó là một giới hạn hấp dẫn, nhưng mới chỉ là điểm khởi đầu. Một trie dùng được trong sản phẩm phải định nghĩa “ký tự” là gì, kiểm soát chi phí con trỏ đáng kể, xếp hạng kết quả, xóa an toàn, hỗ trợ persistence và truy cập đồng thời, đồng thời biết khi nào sorted array hoặc hash table mới là lựa chọn hợp lý hơn.

Vì sao tìm tiền tố cần một kiểu chỉ mục khác #

Giả sử từ điển chứa car, card, care, cat và dog. Hash set có thể trả lời care có tồn tại hay không trong thời gian kỳ vọng $O(L)$, với L là số ký hiệu của truy vấn. Nhưng để trả lời “những giá trị nào bắt đầu bằng ca?”, nó phải quét các khóa hoặc duy trì thêm một chỉ mục có thứ tự. Hàm băm cố tình phá vỡ vùng lân cận từ vựng mà tìm kiếm tiền tố cần đến.

Sorted array giữ được vùng lân cận đó. Binary search tìm phần tử phù hợp đầu tiên qua $O(P \log N)$ phép so sánh, trong đó P là độ dài tiền tố và N là số khóa, rồi quét vùng kết quả liên tiếp. Với dữ liệu tĩnh, cách này thường nhanh đáng ngạc nhiên vì mảng gọn và thân thiện với cache CPU.

Trie chọn một con đường khác. Từ nút gốc, ta đi theo một cạnh cho mỗi ký hiệu của tiền tố. Thiếu bất kỳ cạnh nào nghĩa là không có kết quả. Nếu đường đi tồn tại, nút cuối chính là gốc của cây con chứa toàn bộ completion phù hợp.

Dấu sao đánh dấu terminal node. Nút car phải là terminal dù vẫn có nút con; nếu không, cấu trúc chỉ biểu diễn được card và care mà không phân biệt car là một khóa đã lưu. Đường đến ca không phải terminal trong ví dụ này, nhưng vẫn là một tiền tố hợp lệ.

Xây dựng trie TypeScript hiểu Unicode #

Implementation dưới đây hỗ trợ insert, exact search, kiểm tra prefix, autocomplete có xếp hạng và delete. Nó giữ hai dạng của một term: normalized key để duyệt cây và chuỗi hiển thị gốc tại terminal node. Nếu không tách hai dạng này, thao tác chuyển chữ thường có thể khiến gợi ý hiển thị thiếu tự nhiên.

Hàm normalize được tiêm từ ngoài vì không tồn tại một policy đúng cho mọi miền nghiệp vụ. Mặc định áp dụng NFC normalization và chuyển chữ thường theo locale tiếng Anh. NFC giúp các chuỗi tương đương chuẩn tắc, chẳng hạn é dựng sẵn và e đi cùng combining accent, đi qua cùng một đường. Sản phẩm tiếng Thổ Nhĩ Kỳ, chỉ mục symbol phân biệt hoa thường, hoặc hệ thống chủ động bỏ dấu cần cung cấp policy phù hợp riêng.

type Normalizer = (value: string) => string;

type Suggestion = {
  value: string;
  score: number;
};

class TrieNode {
  readonly children = new Map<string, TrieNode>();
  terminalValue: string | undefined;
  score = 0;
}

export class Trie {
  private readonly root = new TrieNode();

  constructor(
    private readonly normalize: Normalizer = (value) =>
      value.normalize('NFC').toLocaleLowerCase('en-US'),
  ) {}

  insert(value: string, score = 0): void {
    const key = this.normalize(value);
    if (key.length === 0) {
      throw new Error('Trie keys must not be empty');
    }

    let node = this.root;
    for (const symbol of key) {
      let child = node.children.get(symbol);
      if (!child) {
        child = new TrieNode();
        node.children.set(symbol, child);
      }
      node = child;
    }

    node.terminalValue = value;
    node.score = score;
  }

  search(value: string): boolean {
    const node = this.findNode(this.normalize(value));
    return node?.terminalValue !== undefined;
  }

  hasPrefix(prefix: string): boolean {
    return this.findNode(this.normalize(prefix)) !== undefined;
  }

  autocomplete(prefix: string, limit = 10): Suggestion[] {
    if (!Number.isInteger(limit) || limit < 0) {
      throw new Error('limit must be a non-negative integer');
    }

    const start = this.findNode(this.normalize(prefix));
    if (!start || limit === 0) return [];

    const candidates: Suggestion[] = [];
    const visit = (node: TrieNode): void => {
      if (node.terminalValue !== undefined) {
        candidates.push({ value: node.terminalValue, score: node.score });
      }
      for (const child of node.children.values()) visit(child);
    };

    visit(start);
    candidates.sort(
      (left, right) =>
        right.score - left.score || left.value.localeCompare(right.value),
    );
    return candidates.slice(0, limit);
  }

  delete(value: string): boolean {
    const symbols = Array.from(this.normalize(value));

    const remove = (
      node: TrieNode,
      index: number,
    ): { deleted: boolean; prune: boolean } => {
      if (index === symbols.length) {
        if (node.terminalValue === undefined) {
          return { deleted: false, prune: false };
        }
        node.terminalValue = undefined;
        node.score = 0;
        return { deleted: true, prune: node.children.size === 0 };
      }

      const symbol = symbols[index];
      if (symbol === undefined) return { deleted: false, prune: false };
      const child = node.children.get(symbol);
      if (!child) return { deleted: false, prune: false };

      const result = remove(child, index + 1);
      if (result.prune) node.children.delete(symbol);
      return {
        deleted: result.deleted,
        prune: node.terminalValue === undefined && node.children.size === 0,
      };
    };

    return remove(this.root, 0).deleted;
  }

  private findNode(key: string): TrieNode | undefined {
    let node = this.root;
    for (const symbol of key) {
      const child = node.children.get(symbol);
      if (!child) return undefined;
      node = child;
    }
    return node;
  }
}

JavaScript lưu string bằng UTF-16, nhưng for...of và Array.from duyệt theo Unicode code point thay vì từng code unit. Nhờ đó, một ký tự astral không bị chẻ thành hai cạnh vô nghĩa. Tuy nhiên, code point vẫn chưa phải grapheme cluster mà người dùng cảm nhận: emoji kèm modifier hoặc một gia đình nối bằng zero-width joiner có thể gồm nhiều code point. Hãy dùng Intl.Segmenter nếu semantics của sản phẩm đòi hỏi mỗi grapheme là một cạnh. Quan trọng hơn, insert, search, delete và prefix lookup phải dùng chính xác cùng một normalization policy. Policy không nhất quán tạo ra những entry đã ghi thành công nhưng không bao giờ tìm lại được.

Delete cũng cần xử lý cẩn thận. Xóa car phải giữ các nút mà card cần; xóa card chỉ được bỏ nhánh d nay không còn dùng. Vì vậy kết quả đệ quy tách hai ý nghĩa: “đã xóa được khóa” và “có thể prune nút này an toàn.”

Độ phức tạp không dừng ở bước đi theo tiền tố #

Gọi L là số ký hiệu đã normalize trong khóa đầy đủ, P là số ký hiệu của prefix, S là số nút được thăm dưới prefix khớp, R là số terminal result tìm thấy, K là giới hạn kết quả yêu cầu, và U là số prefix node phân biệt được lưu.

Con số nổi bật $O(P)$ chỉ tìm được cây con; không thuật toán nào xuất R chuỗi trong ít hơn $O(R)$. Autocomplete mẫu ưu tiên sự rõ ràng, chưa tối ưu cho prefix rất phổ biến như chuỗi rỗng. Min-heap kích thước K giảm bước chọn theo hạng xuống $O(R \log K)$, dù traversal vẫn chạm S nút. Cache top K suggestion tại mọi nút có thể đưa read gần $O(P + K)$, đổi lại tốn thêm bộ nhớ và khiến mỗi lần cập nhật score phức tạp hơn.

Memory thường là giới hạn thật sự của trie. Một Map, object header, pointer, allocator alignment, terminal value và score có thể tốn nhiều byte hơn hẳn ký tự mà nút đại diện. Prefix dùng chung giúp giảm lưu ký tự về mặt khái niệm, nhưng object graph thưa trong JavaScript vẫn có thể lớn hơn dữ liệu chuỗi gốc nhiều lần. Hãy đo retained heap bằng dữ liệu giống production; node count không phải memory budget.

Compression, ranking và chiến lược cập nhật #

Radix tree, còn gọi là compressed trie hoặc gần với Patricia trie trong một số cấu trúc nhị phân, gộp mọi chuỗi nút chỉ có một con thành một cạnh mang cả đoạn string. Thay vì c -> a -> r, nó có thể giữ một cạnh car cho tới nơi đường đi phân nhánh. Lookup vẫn so sánh cùng số ký hiệu, nhưng cần ít object và pointer hop hơn. Insert và delete phức tạp hơn vì có lúc phải tách hoặc gộp cạnh.

Với vocabulary tĩnh rất lớn, succinct trie, minimal deterministic acyclic word graph hoặc finite-state transducer có thể dùng chung các suffix tương đương và mã hóa cạnh trong mảng gọn. Những representation này đánh đổi mutation đơn giản để lấy bộ nhớ nhỏ, truy cập tuần tự và tốc độ load cao. Chúng phù hợp với từ điển được đóng gói cùng ứng dụng, nhưng bất tiện với tập gợi ý thay đổi từng giây.

Ranking làm thay đổi data model, không chỉ thêm một lệnh sort cuối cùng. Score trong production có thể kết hợp tần suất toàn cục, độ mới, edit distance, ngôn ngữ, lịch sử riêng của tài khoản và business rule. Nên lưu signal toàn cục ổn định trong index, nhưng tránh nhân bản cả trie cho từng user. Trước hết lấy một candidate set toàn cục vừa phải, sau đó rerank bằng signal của request. Tie-break phải deterministic để pagination, snapshot và test không nhấp nháy.

Ba chiến lược phổ biến cho top result có đánh đổi khác nhau:

Approximate matching là một yêu cầu riêng. Trie thường xử lý prefix chứ không tự sửa lỗi gõ ở vị trí bất kỳ. Levenshtein automaton có thể chỉ duyệt các đường trie nằm trong edit distance cho phép, nhưng nó thêm state và trở nên đắt khi threshold rộng. Không nên quảng bá typo tolerance chỉ vì hệ thống đã có autocomplete.

Persistence, concurrency và kiểm thử #

Class trên là một in-memory mutable index. Lưu nó thành JSON lồng sâu tuy dễ làm nhưng phình to, parse chậm và khó version. Trong nhiều hệ thống, database hoặc append-only log nên tiếp tục là source of truth, còn trie là derived index có thể rebuild. Để khởi động nhanh, có thể ghi snapshot có version bằng các mảng node và edge phẳng, lưu normalization version, scoring version và replay update sau offset của snapshot.

Trong một JavaScript event loop, từng method đồng bộ là atomic so với callback khác, nhưng chuỗi “đọc score, await, cập nhật score” thì không. Worker và các server replica tạo ra parallelism thật. Một thiết kế thực dụng là single writer phát hành immutable snapshot, còn reader giữ một snapshot reference suốt request. Copy-on-write path cho phép làm vậy mà không clone toàn bộ trie. Hệ thống khác có thể đặt read-write lock quanh mutable index hoặc dồn mutation qua một owner. Dù chọn mô hình nào, cần nói rõ reader phải thấy write mới nhất hay chỉ cần một version nhất quán.

Test nên tập trung vào invariant và boundary đối nghịch, không chỉ happy path:

import { describe, expect, it } from 'vitest';
import { Trie } from './trie.js';

describe('Trie', () => {
  it('phân biệt khóa đầy đủ với prefix và xếp hạng kết quả', () => {
    const trie = new Trie();
    trie.insert('car', 2);
    trie.insert('card', 7);
    trie.insert('care', 5);

    expect(trie.search('ca')).toBe(false);
    expect(trie.hasPrefix('ca')).toBe(true);
    expect(trie.autocomplete('car', 2).map((item) => item.value)).toEqual([
      'card',
      'care',
    ]);
  });

  it('normalize Unicode tương đương và chỉ prune nhánh không dùng', () => {
    const trie = new Trie();
    trie.insert('Café');
    trie.insert('cafeteria');

    expect(trie.search('CAFE\u0301')).toBe(true);
    expect(trie.delete('café')).toBe(true);
    expect(trie.search('Café')).toBe(false);
    expect(trie.search('cafeteria')).toBe(true);
    expect(trie.delete('missing')).toBe(false);
  });
});

Khi trie trở thành hạ tầng dùng chung, hãy thêm property-based test. Sinh chuỗi thao tác ngẫu nhiên và so exact membership với một Map tham chiếu dùng cùng normalizer. Sau mỗi insert và delete, xác minh autocomplete chỉ chứa key có normalized prefix được yêu cầu, không trùng lặp, tuân thủ ranking order và không làm mất neighboring key. Các case quan trọng gồm input rỗng, insert trùng, limit bằng không, key rất dài, combining mark, astral symbol và case mapping nhạy với locale.

Chọn chỉ mục nhỏ nhất nhưng đúng bài toán #

Trie thuyết phục khi prefix query chiếm ưu thế, vocabulary đủ lớn để đáng xây index, và latency cần ổn định theo độ dài prefix. Nó cũng hỗ trợ duyệt theo thứ tự từ vựng và chia sẻ prefix trong route, identifier, từ điển hay IP prefix. Tuy nhiên, trie không phải bản nâng cấp tự động cho mọi collection chứa string.

Với năm mươi tên command, filter một array có thể rõ ràng và đủ nhanh. Với danh sách tĩnh gồm một triệu term đã normalize, sorted packed array có thể thắng JavaScript trie về cả memory lẫn wall-clock time. Với lookup session token chính xác, nên dùng hash table. Quyết định đúng đến từ hình dạng query, update rate, phân phối latency và số đo memory, không đến từ hàng Big-O trông hấp dẫn nhất.

Điều cần nhớ #

• Trie biến prefix dùng chung thành đường đi dùng chung, tìm cây con của một prefix trong thời gian kỳ vọng $O(P)$.
• Terminal marker phân biệt một key đã lưu với đường đi chỉ dẫn tới key dài hơn.
• Unicode normalization là một phần của contract; mọi operation phải dùng cùng policy và nên giữ riêng display value.
• Chi phí autocomplete gồm cả traversal descendant lẫn ranking. Heap và top-K cache tại mỗi nút tối ưu cho hai workload khác nhau.
• Node và pointer overhead có thể thống trị memory, khiến radix compression hoặc packed static representation trở nên đáng giá.
• Persistence và concurrency cần lựa chọn rõ về snapshot, ownership và consistency; class in-memory mới chỉ là thuật toán lõi.
• Hash table và sorted array vẫn tốt hơn khi query là exact, dữ liệu nhỏ, hoặc vocabulary chủ yếu thay đổi qua batch rebuild.

Trie chỉ thực sự đáng dùng khi sản phẩm đặt câu hỏi theo hình dạng prefix đủ thường xuyên. Khi normalization, ranking, memory và update đều được xem là đầu vào thiết kế hạng nhất, nó không còn là một cây trong giáo trình mà trở thành search index có chi phí rõ ràng và có thể vận hành có chủ đích.