Fuzzy Search với BK-Tree là gì? Giải thích dễ hiểu kèm demo tìm kiếm gần đúng trên từ điển nhỏ

Trong thực tế, không phải lúc nào người dùng cũng gõ chính xác:

• Lỗi chính tả: googel thay vì google.
• Gõ thiếu / thừa ký tự: bok thay vì book.
• Không nhớ đúng tên sản phẩm, người, địa danh…

Lúc này, ta cần một cơ chế fuzzy search (tìm kiếm gần đúng): thay vì chỉ trả về kết quả khớp 100%, ta còn trả về những chuỗi “gần giống” với từ khóa tìm kiếm.

Một trong những cấu trúc dữ liệu kinh điển để hỗ trợ fuzzy search trên tập từ là BK-Tree (Burkhard–Keller Tree). Nó được thiết kế đặc biệt cho các không gian có khái niệm “khoảng cách” (distance), ví dụ:

• Khoảng cách Levenshtein giữa hai chuỗi.
• Khoảng cách Hamming.
• Các metric khác có tính chất giống “metric space”.

Trong bài viết này, chúng ta sẽ:

• Hiểu fuzzy search và khoảng cách chuỗi (edit distance).
• Nắm được ý tưởng xây dựng và truy vấn BK-Tree.
• Xem demo trực quan BK-Tree tìm kiếm gần đúng trên một từ điển nhỏ bằng JavaScript.

Fuzzy Search là gì?

Thông thường, search “chính xác” (exact search) chỉ trả về kết quả khi chuỗi khớp 100%. Ví dụ:

• Tìm book chỉ trả về kết quả chứa đúng book, không có bok, boook…

Fuzzy search thì khác. Ta sẽ:

• Định nghĩa một khoảng cách giữa hai chuỗi (thường dùng Levenshtein distance).
• Chỉ cần distance(query, word) ≤ K (K là ngưỡng cho phép) thì coi như “khớp gần đúng”.

Ví dụ, nếu ta dùng Levenshtein distance:

• book & bok có distance = 1 (xoá hoặc thêm 1 ký tự).
• book & back có distance = 2 (thay đổi 2 ký tự).

Nếu ta cho phép sai lệch tối đa 1 ký tự (K = 1), thì khi tìm bok, cả bok và book đều là kết quả hợp lệ.

Levenshtein Distance (Edit Distance) – nền tảng của fuzzy search

Levenshtein distance giữa hai chuỗi A và B là số thao tác nhỏ nhất để biến A thành B, với mỗi thao tác là:

• Chèn một ký tự.
• Xoá một ký tự.
• Thay một ký tự.

Ví dụ:

• book → bok: xoá 1 ký tự → distance = 1.
• cat → cart: chèn 1 ký tự → distance = 1.
• cat → cut: thay 1 ký tự → distance = 1.

Ta có thể tính Levenshtein bằng DP, nhưng trong demo dưới mình dùng phiên bản code đơn giản cho dễ hiểu.

BK-Tree là gì?

BK-Tree là một cây trong đó mỗi node chứa:

• Một từ (word).
• Các cạnh nối đến các node con, mỗi cạnh được gán nhãn là khoảng cách giữa từ ở node cha và từ ở node con.

Ý tưởng xây dựng BK-Tree:

1. Chọn một từ làm gốc (root), ví dụ "book".
2. Khi chèn từ mới, ví dụ "back":
   • Tính d = distance("back", "book").
   • Nếu con tại cạnh d chưa tồn tại → gắn từ đó vào vị trí đó.
   • Nếu đã có node ở cạnh đó → đệ quy tiếp xuống node đó.

Khi truy vấn với từ khóa query và ngưỡng K:

1. Tại mỗi node, tính d = distance(query, node.word).
2. Nếu d ≤ K → thêm vào danh sách kết quả.
3. Chỉ cần tiếp tục duyệt những node con có cạnh trong khoảng [d - K, d + K], vì:
   • Các node con khác chắc chắn có distance lớn hơn K với query (do tam giác bất đẳng thức).

Nhờ vậy, thay vì duyệt toàn bộ từ điển, ta chỉ duyệt một phần nhỏ mà vẫn đảm bảo trả về tất cả từ có khoảng cách ≤ K.

Mô hình demo: fuzzy search trên một từ điển nhỏ

Để trực quan, ta sẽ:

• Dùng một danh sách từ nhỏ (15–20 từ tiếng Anh đơn giản).
• Xây BK-Tree từ danh sách đó.
• Cho người dùng nhập từ khóa (query) và chọn ngưỡng sai lệch K (0–3).
• Hiển thị:
  • Các kết quả khớp gần đúng kèm khoảng cách.
  • Log các node đã duyệt theo thứ tự, để thấy BK-Tree “cắt bớt” được những nhánh nào.

Demo BK-Tree fuzzy search bằng JavaScript

Giải thích ngắn gọn đoạn code BK-Tree

1. Định nghĩa node BK-Tree

Mỗi node chứa một từ và một map từ “khoảng cách” → “node con”:

function BKNode(word) {
    this.word = word;
    this.children = {}; // key: khoảng cách, value: BKNode
}

2. Hàm chèn từ vào BK-Tree

Khi chèn một từ mới:

function bkInsert(node, word) {
    var d = levenshtein(word, node.word);
    if (!node.children[d]) {
        node.children[d] = new BKNode(word);
    } else {
        bkInsert(node.children[d], word);
    }
}

3. Hàm tìm kiếm gần đúng trong BK-Tree

Khi tìm kiếm với query và ngưỡng K:

function bkSearch(node, query, maxDist, results, logger, visitedCounter) {
    if (!node) return;
    visitedCounter.count++;

    var d = levenshtein(query, node.word);
    logger("Đang xét node <strong>" + node.word + "</strong>, khoảng cách đến query = <strong>" + d + "</strong>.");

    if (d <= maxDist) {
        results.push({ word: node.word, dist: d });
    }

    var start = d - maxDist;
    var end = d + maxDist;

    for (var key in node.children) {
        if (!node.children.hasOwnProperty(key)) continue;
        var edgeDist = parseInt(key, 10);
        if (edgeDist >= start && edgeDist <= end) {
            logger("→ Đi xuống nhánh có khoảng cách " + edgeDist + " từ node <strong>" + node.word + "</strong>.");
            bkSearch(node.children[key], query, maxDist, results, logger, visitedCounter);
        } else {
            logger("✕ Bỏ qua nhánh khoảng cách " + edgeDist + " từ node <strong>" + node.word + "</strong> (chắc chắn xa hơn K).");
        }
    }
}

4. Hàm tính Levenshtein distance

Ta dùng một phiên bản chuẩn, nhưng tối ưu cho demo:

function levenshtein(a, b) {
    a = a || "";
    b = b || "";
    var m = a.length, n = b.length;
    if (m === 0) return n;
    if (n === 0) return m;

    var dp = [];
    for (var i = 0; i <= m; i++) {
        dp[i] = [];
        dp[i][0] = i;
    }
    for (var j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    for (var i = 1; i <= m; i++) {
        for (var j = 1; j <= n; j++) {
            var cost = (a[i - 1] === b[j - 1]) ? 0 : 1;
            dp[i][j] = Math.min(
                dp[i - 1][j] + 1,      // delete
                dp[i][j - 1] + 1,      // insert
                dp[i - 1][j - 1] + cost // replace
            );
        }
    }
    return dp[m][n];
}

Khi nào nên dùng BK-Tree cho fuzzy search?

BK-Tree phù hợp khi:

• Bạn có một tập từ (dictionary) vừa phải đến lớn (hàng ngàn đến hàng trăm ngàn từ).
• Khoảng cách giữa các chuỗi tuân theo metric (tam giác bất đẳng thức).
• Cần fuzzy search với K nhỏ (0–2, 0–3) để sửa lỗi gõ phím, gợi ý từ khóa.

Một số ứng dụng điển hình:

• Gợi ý khi người dùng gõ sai chính tả trong ô search.
• Tìm tên sản phẩm / user / tag gần giống.
• Autocomplete với khả năng chịu lỗi.

Kết luận

Fuzzy search giúp hệ thống tìm kiếm trở nên “thông minh” và thân thiện hơn với người dùng thực tế (luôn gõ sai). BK-Tree là một cấu trúc dữ liệu gọn, đẹp, tận dụng tính chất metric của khoảng cách để cắt bỏ rất nhiều nhánh không cần thiết.

Với demo JavaScript ở trên, bạn có thể:

• Nhập các biến thể khác nhau của một từ (vd: bok, boook) và quan sát kết quả.
• Thay đổi giá trị K để xem số lượng kết quả và số node được duyệt.
• Mở rộng danh sách từ điển hoặc tái sử dụng đoạn code BK-Tree cho các dự án thực tế.

Từ đây, bạn có thể:

• Kết hợp BK-Tree với hệ thống search hiện tại (SQL, full-text search…) như một lớp “suggestion”.
• Thử nghiệm các metric khác (Hamming, Damerau-Levenshtein…).
• Tối ưu hiệu năng cho tập dữ liệu lớn hơn (cache, phân mảnh cây, v.v.).