Bài 14: FTS5 Full-Text Search

Khi xây dựng các tính năng tìm kiếm văn bản như tìm sản phẩm, bài viết hay nhật ký giao dịch, các lập trình viên thường nghĩ ngay đến toán tử LIKE '%từ_khóa%'. Tuy nhiên, trên tập dữ liệu hàng triệu dòng, phương pháp này tốn rất nhiều thời gian do hệ thống phải thực hiện quét tuần tự toàn bảng (Full Table Scan) với độ phức tạp \(O(N)\). Bài viết này sẽ phân tích chi tiết cơ chế hoạt động của Inverted Index (Chỉ mục đảo ngược), cấu trúc bộ phân tích từ vựng (Tokenizer), thuật toán xếp hạng độ liên quan BM25, và cách ứng dụng module FTS5 để xây dựng một bộ máy tìm kiếm toàn văn siêu tốc trong SQLite.

1. Trái Tim Của Mọi Bộ Máy Tìm Kiếm: Chỉ Mục Đảo Ngược (Inverted Index)

Để hiểu vì sao các công cụ tìm kiếm như Elasticsearch hay module FTS (Full-Text Search) của SQLite có thể trả về kết quả trong vài mili-giây trên hàng triệu dòng tài liệu, chúng ta cần tìm hiểu cấu trúc dữ liệu bên dưới của chúng.

Trong bảng B-Tree thông thường, dữ liệu được tổ chức theo chiều xuôi: Document ID (Khóa chính) -> Nội dung văn bản. Khi bạn tìm một từ, hệ thống buộc phải đọc từng tài liệu và duyệt qua chuỗi ký tự để kiểm tra.

Inverted Index (Chỉ mục đảo ngược) tổ chức dữ liệu theo chiều ngược lại: Từ đơn (Term) -> Danh sách Document ID chứa từ đó + Vị trí từ.

Giả sử ta có hai tài liệu trong cơ sở dữ liệu:

• Tài liệu 1 (D1): "Học SQL rất thú vị."
• Tài liệu 2 (D2): "Học giải thuật trực quan."

Sau khi phân tích, Inverted Index sẽ lưu trữ như sau:

Từ đơn (Term)	Danh sách xuất hiện (Posting List)
học	(D1, vị trí 0), (D2, vị trí 0)
sql	(D1, vị trí 1)
rất	(D1, vị trí 2)
thú vị	(D1, vị trí 3)
giải thuật	(D2, vị trí 1)
trực quan	(D2, vị trí 2)

Khi người dùng tìm kiếm từ "SQL", SQLite không cần đọc nội dung bất kỳ hàng nào. Nó chỉ cần thực hiện tra cứu nhị phân trên danh sách từ đơn để tìm khóa sql, lập tức lấy được danh sách kết quả chứa D1. Độ phức tạp tìm kiếm giảm từ quét toàn bảng \(O(N)\) xuống còn tìm kiếm nhị phân hoặc bảng băm \(O(\log M)\) với $M$ là tổng số từ đơn phân biệt.

2. Bộ Phân Tích Từ Vựng (Tokenizer): unicode61 vs trigram

Quá trình chuyển đổi một câu văn bản thô thành danh sách các từ đơn trong Inverted Index được đảm nhận bởi Tokenizer. SQLite cung cấp một số bộ Tokenizer mặc định:

• simple: Chỉ phân tách từ dựa trên các ký tự khoảng trắng và dấu câu ASCII. Nó loại bỏ hoàn toàn các ký tự ngoài ASCII và không hỗ trợ tốt tiếng Việt có dấu.
• porter: Áp dụng thuật toán Stemming của Porter dành riêng cho tiếng Anh (ví dụ: biến đổi "running", "runs", "ran" về từ gốc chung là "run").
• unicode61: Hỗ trợ đầy đủ bảng mã Unicode (UTF-8). Nó nhận biết chính xác các nguyên âm có dấu trong tiếng Việt để tách từ một cách chuẩn xác nhất. Đây là lựa chọn bắt buộc khi làm ứng dụng đa ngôn ngữ hoặc ứng dụng thuần Việt.
• trigram (Từ SQLite 3.34.0, chỉ có ở FTS5): Phân rã chuỗi thành các cụm 3 ký tự liên tiếp. Trigram rất mạnh cho tìm kiếm mờ (fuzzy search) hoặc tìm kiếm chuỗi con không cần đúng ranh giới từ (ví dụ: tìm "code" có thể khớp cả "bytecode", "codegolf").

Khai báo bảng ảo FTS5 sử dụng Tokenizer unicode61 cấu hình loại bỏ dấu câu tùy biến:

-- FTS5 Syntax (Dành cho production)
CREATE VIRTUAL TABLE articles_search USING fts5(
  title, 
  body, 
  tokenize = "unicode61 remove_diacritics 1"
);

3. Thuật Toán Xếp Hạng Độ Liên Quan BM25 (Best Matching 25)

Khi một câu truy vấn có nhiều kết quả khớp, làm sao để đưa các tài liệu liên quan nhất lên đầu? Module FTS5 của SQLite sử dụng thuật toán xếp hạng nổi tiếng **BM25**. Điểm số BM25 của tài liệu $D$ đối với truy vấn $Q$ chứa các từ khóa $q_1, q_2, \dots, q_n$ được tính toán theo công thức toán học sau:

\[ \text{Score}(D, Q) = \sum_{i=1}^{n} \text{IDF}(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)} \]

Trong đó:

• \(f(q_i, D)\): Tần suất từ khóa $q_i$ xuất hiện trong tài liệu $D$ (Term Frequency). Từ khóa xuất hiện càng nhiều, điểm càng cao.
• \(|D|\): Chiều dài (số lượng từ) của tài liệu $D$.
• \(\text{avgdl}\): Chiều dài trung bình của tất cả tài liệu trong bảng.
• \(\text{IDF}(q_i)\): Trọng số nghịch đảo tần suất tài liệu chứa từ khóa (Inverse Document Frequency). Từ khóa nào càng hiếm trong cơ sở dữ liệu (ví dụ: thuật ngữ chuyên ngành) thì khi khớp sẽ mang lại điểm số cao hơn hẳn các từ phổ biến (như "và", "là", "thì").
• \(k_1\) và \(b\): Các siêu tham số hiệu chỉnh (mặc định trong SQLite thường là \(k_1 = 1.2\) điều khiển mức độ bão hòa tần suất từ, và \(b = 0.75\) điều khiển mức độ phạt độ dài tài liệu).

Trong FTS5, SQLite cung cấp hàm bm25() để tự động tính điểm số này. Điểm số trả về của hàm bm25() là một số âm, tài liệu nào có điểm số âm **càng nhỏ** (càng âm sâu) thì độ liên quan càng cao.

-- FTS5 query xếp hạng theo BM25 và lọc trọng số cột
SELECT title, bm25(articles_search, 10.0, 1.0) AS score
FROM articles_search 
WHERE articles_search MATCH 'học SQL'
ORDER BY score ASC; -- Xếp hạng tốt nhất lên đầu

Trọng số 10.0, 1.0 truyền vào hàm bm25() chỉ ra rằng nếu từ khóa khớp ở cột thứ nhất (title), nó sẽ có mức độ quan trọng gấp 10 lần so với khớp ở cột thứ hai (body).

4. Các Hàm Bổ Trợ Trực Quan Hóa: snippet() và highlight()

Một bộ máy tìm kiếm không thể chỉ trả về tiêu đề trơ trọi. Người dùng cần nhìn thấy một đoạn trích dẫn ngắn chứa từ khóa được tô đậm để quyết định có click vào xem hay không.

• snippet(table, column_index, start_tag, end_tag, ellipses, max_tokens): Tự động trích xuất một đoạn văn ngắn xung quanh từ khóa khớp, thêm dấu ba chấm ... ở hai đầu.
• highlight(table, column_index, start_tag, end_tag): Trả về toàn bộ nội dung cột nhưng bọc các từ khóa khớp bằng thẻ HTML tùy chọn (ví dụ: bọc bằng thẻ <mark>).

-- Sử dụng các hàm trực quan trong FTS5
SELECT highlight(articles_search, 0, '<span class="match">', '</span>') AS highlighted_title,
       snippet(articles_search, 1, '<mark>', '</mark>', '...', 15) AS preview_snippet
FROM articles_search
WHERE articles_search MATCH 'trực quan'
LIMIT 5;

5. Thực Hành Xây Dựng Search Engine Mini Trên Trình Duyệt

Để tiến hành thử nghiệm trực tiếp trên trình duyệt với thư viện sql.js, chúng ta sử dụng module FTS3 có sẵn. Cú pháp tìm kiếm và hàm cắt chuỗi snippet() hoạt động hoàn toàn tương thích.

Hãy cùng chạy thử các câu lệnh trên bảng tìm kiếm sản phẩm TechMart dưới đây.