Khi xây dựng tính năng tìm kiếm mờ (Fuzzy Search) trên các trường văn bản lớn tại các ứng dụng Enterprise, khoảng cách Levenshtein (Levenshtein Distance) hoạt động như thế nào và làm thế nào để tối ưu hóa hiệu năng khi truy vấn trên hàng triệu bản ghi?

Question

Accepted Answer

Bản chất vấn đề
Khoảng cách Levenshtein đo lường mức độ khác biệt giữa hai chuỗi ký tự dựa trên số lượng phép toán tối thiểu cần thiết để biến đổi chuỗi này thành chuỗi khác (bao gồm chèn, xóa, hoặc thay thế ký tự). Đối với các ứng dụng Enterprise có dữ liệu lớn, việc tính toán trực tiếp khoảng cách này cho mọi bản ghi trong cơ sở dữ liệu sẽ dẫn đến độ phức tạp thời gian O(M * N) cho mỗi lần tìm kiếm, gây sập hệ thống do tràn CPU.
Giải pháp và Best Practices cho cấp độ Middle

Sử dụng cấu trúc Index chuyên dụng: Thay vì quét tuần tự toàn bộ bảng, hãy kết hợp với các công cụ tìm kiếm toàn văn bản như Elasticsearch hoặc PostgreSQL tích hợp tiện ích pg_trgm (Trigram matching) để tạo inverted index.
Giới hạn không gian tìm kiếm (Pruning): Áp dụng bộ lọc sơ bộ bằng độ dài chuỗi (Length filtering). Nếu độ chênh lệch độ dài giữa từ khóa tìm kiếm và từ trong cơ sở dữ liệu lớn hơn khoảng cách tối đa cho phép, loại bỏ ngay lập tức.
Thuật toán quy hoạch động (Dynamic Programming) có tối ưu hóa bộ nhớ: Khi bắt buộc phải tính toán bằng code tầng ứng dụng, giảm thiểu việc cấp phát mảng 2 chiều xuống mảng 1 chiều để tiết kiệm Garbage Collection.

Ví dụ thực tế
Triển khai tính toán khoảng cách Levenshtein tối ưu hóa bộ nhớ bằng mảng 1 chiều:
function getLevenshteinDistance(a, b) {
    if (a.length === 0) return b.length;
    if (b.length === 0) return a.length;

let prevRow = Array(b.length + 1).fill(0).map((_, i) => i);

for (let i = 0; i < a.length; i++) {
        let currRow = [i + 1];
        for (let j = 0; j < b.length; j++) {
            let insertions = prevRow[j + 1] + 1;
            let deletions = currRow[j] + 1;
            let substitutions = prevRow[j] + (a[i] === b[j] ? 0 : 1);
            currRow.push(Math.min(insertions, deletions, substitutions));
        }
        prevRow = currRow;
    }
    return prevRow[prevRow.length - 1];
}
Lưu ý kinh nghiệm thực chiến
Không bao giờ chạy thuật toán Levenshtein thuần túy trên Thread chính của ứng dụng Node.js hoặc Web Server khi xử lý đồng thời nhiều request. Hãy offload sang Worker Threads hoặc sử dụng cơ chế tìm kiếm gốc của Database.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi strings liên quan cùng chủ đề